8421654220

Committed 25 Mar 2024 02:22PM CUT coverage: 79.934% (+53.8%) from 26.087%

Build # 8421654220

Build Type

Pull #495

github

Committed by

web-flow

Commit Message

Merge 4faeebea5 into 1869c986d

Pull Request Pull Request #495: chore: add licenses for non-NPM packages

Run Details

3256 of 3853 branches covered (84.51%)

25152 of 31466 relevant lines covered (79.93%)

1188.29 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.28

/apps/nestjs-backend/src/features/calculation/utils/dfs.ts

/* eslint-disable sonarjs/cognitive-complexity */
import { uniq } from 'lodash';

// topo item is for field level reference, all id stands for fieldId;
export interface ITopoItem {
  id: string;
  dependencies: string[];
}

export interface IGraphItem {
  fromFieldId: string;
  toFieldId: string;
}

export type IAdjacencyMap = Record<string, string[]>;

export function buildAdjacencyMap(graph: IGraphItem[]): IAdjacencyMap {
  const adjList: IAdjacencyMap = {};
  graph.forEach((edge) => {
    if (!adjList[edge.fromFieldId]) {
      adjList[edge.fromFieldId] = [];
    }
    adjList[edge.fromFieldId].push(edge.toFieldId);
  });
  return adjList;
}

export function findNextValidNode(
  current: string,
  adjMap: IAdjacencyMap,
  linkIdSet: Set<string>
): string | null {
  if (linkIdSet.has(current)) {
    return current;
  }

  const neighbors = adjMap[current];
  if (!neighbors) {
    return null;
  }

  for (const neighbor of neighbors) {
    const validNode = findNextValidNode(neighbor, adjMap, linkIdSet);
    if (validNode) {
      return validNode;
    }
  }

  return null;
}

/**
 * Builds a compressed adjacency map based on the provided graph, linkIdSet, and startFieldIds.
 * The compressed adjacency map represents the neighbors of each node in the graph, excluding nodes that are not valid according to the linkIdSet.
 *
 * @param graph - The graph containing the nodes and their connections.
 * @param linkIdSet - A set of valid link IDs.
 * @returns The compressed adjacency map representing the neighbors of each node.
 */
export function buildCompressedAdjacencyMap(
  graph: IGraphItem[],
  linkIdSet: Set<string>
): IAdjacencyMap {
  const adjMap = buildAdjacencyMap(graph);
  const compressedAdjMap: IAdjacencyMap = {};

  Object.keys(adjMap).forEach((from) => {
    const queue = [from];
    const visited = new Set<string>();

    while (queue.length > 0) {
      const current = queue.shift();
      if (!current || visited.has(current)) continue;

      visited.add(current);
      const neighbors = adjMap[current] || [];
      const compressedNeighbors = [];

      for (const neighbor of neighbors) {
        const nextValid = findNextValidNode(neighbor, adjMap, linkIdSet);
        if (nextValid && !visited.has(nextValid)) {
          compressedNeighbors.push(nextValid);
          if (!linkIdSet.has(current)) {
            queue.push(nextValid);
          }
        }
      }

      if (compressedNeighbors.length > 0) {
        compressedAdjMap[current] = compressedNeighbors;
      }
    }
  });

  return compressedAdjMap;
}

export function hasCycle(graphItems: IGraphItem[]): boolean {
  const adjList: Record<string, string[]> = {};
  const visiting = new Set<string>();
  const visited = new Set<string>();

  // Build adjacency list
  graphItems.forEach((item) => {
    if (!adjList[item.fromFieldId]) {
      adjList[item.fromFieldId] = [];
    }
    adjList[item.fromFieldId].push(item.toFieldId);
  });

  function dfs(node: string): boolean {
    if (visiting.has(node)) return true;
    if (visited.has(node)) return false;

    visiting.add(node);

    if (adjList[node]) {
      for (const neighbor of adjList[node]) {
        if (dfs(neighbor)) return true;
      }
    }

    visiting.delete(node);
    visited.add(node);

    return false;
  }

  // Check for cycles
  for (const node of Object.keys(adjList)) {
    if (!visited.has(node) && dfs(node)) {
      return true;
    }
  }

  return false;
}

/**
 * Generate a topological order based on the starting node ID.
 *
 * @param startNodeId - The ID to start the search from.
 * @param graph - The input graph.
 * @returns An array of ITopoItem representing the topological order.
 */
export function topoOrderWithDepends(startNodeId: string, graph: IGraphItem[]): ITopoItem[] {
  const visitedNodes = new Set<string>();
  const visitingNodes = new Set<string>();
  const sortedNodes: ITopoItem[] = [];

  // Build adjacency list and reverse adjacency list
  const adjList: Record<string, string[]> = {};
  const reverseAdjList: Record<string, string[]> = {};
  for (const edge of graph) {
    if (!adjList[edge.fromFieldId]) adjList[edge.fromFieldId] = [];
    adjList[edge.fromFieldId].push(edge.toFieldId);

    if (!reverseAdjList[edge.toFieldId]) reverseAdjList[edge.toFieldId] = [];
    reverseAdjList[edge.toFieldId].push(edge.fromFieldId);
  }

  function visit(node: string) {
    if (visitingNodes.has(node)) {
      throw new Error(`Detected a cycle: ${node} is part of a circular dependency`);
    }

    if (!visitedNodes.has(node)) {
      visitingNodes.add(node);

      // Get incoming edges (dependencies)
      const dependencies = reverseAdjList[node] || [];

      // Process outgoing edges
      if (adjList[node]) {
        for (const neighbor of adjList[node]) {
          visit(neighbor);
        }
      }

      visitingNodes.delete(node);
      visitedNodes.add(node);
      sortedNodes.push({ id: node, dependencies: dependencies });
    }
  }

  visit(startNodeId);
  return sortedNodes.reverse().map((node) => ({
    id: node.id,
    dependencies: uniq(node.dependencies),
  }));
}

/**
 * Generate a topological order with based on the starting node ID.
 */
export function topoOrderWithStart(startNodeId: string, graph: IGraphItem[]): string[] {
  const visitedNodes = new Set<string>();
  const sortedNodes: string[] = [];

  // Build adjacency list and reverse adjacency list
  const adjList: Record<string, string[]> = {};
  const reverseAdjList: Record<string, string[]> = {};
  for (const edge of graph) {
    if (!adjList[edge.fromFieldId]) adjList[edge.fromFieldId] = [];
    adjList[edge.fromFieldId].push(edge.toFieldId);

    if (!reverseAdjList[edge.toFieldId]) reverseAdjList[edge.toFieldId] = [];
    reverseAdjList[edge.toFieldId].push(edge.fromFieldId);
  }

  function visit(node: string) {
    if (!visitedNodes.has(node)) {
      visitedNodes.add(node);

      // Process outgoing edges
      if (adjList[node]) {
        for (const neighbor of adjList[node]) {
          visit(neighbor);
        }
      }

      sortedNodes.push(node);
    }
  }

  visit(startNodeId);
  return sortedNodes.reverse();
}

// simple topological sort
export function topologicalSort(graph: IGraphItem[]): string[] {
  const adjList: Record<string, string[]> = {};
  const visited = new Set<string>();
  const currentStack = new Set<string>();
  const result: string[] = [];

  graph.forEach((node) => {
    if (!adjList[node.fromFieldId]) {
      adjList[node.fromFieldId] = [];
    }
    adjList[node.fromFieldId].push(node.toFieldId);
  });

  function dfs(node: string) {
    if (currentStack.has(node)) {
      throw new Error(`Detected a cycle involving node '${node}'`);
    }

    if (visited.has(node)) {
      return;
    }

    currentStack.add(node);
    visited.add(node);

    const neighbors = adjList[node] || [];
    neighbors.forEach((neighbor) => dfs(neighbor));

    currentStack.delete(node);
    result.push(node);
  }

  graph.forEach((node) => {
    if (!visited.has(node.fromFieldId)) {
      dfs(node.fromFieldId);
    }
    if (!visited.has(node.toFieldId)) {
      dfs(node.toFieldId);
    }
  });

  return result.reverse();
}

/**
 * Returns all relations related to the given fieldIds.
 */
export function filterDirectedGraph(
  undirectedGraph: IGraphItem[],
  fieldIds: string[]
): IGraphItem[] {
  const result: IGraphItem[] = [];
  const visited: Set<string> = new Set();
  const addedEdges: Set<string> = new Set(); // 新增：用于存储已添加的边

  // Build adjacency lists for quick look-up
  const outgoingAdjList: Record<string, IGraphItem[]> = {};
  const incomingAdjList: Record<string, IGraphItem[]> = {};

  function addEdgeIfNotExists(edge: IGraphItem) {
    const edgeKey = edge.fromFieldId + '-' + edge.toFieldId;
    if (!addedEdges.has(edgeKey)) {
      addedEdges.add(edgeKey);
      result.push(edge);
    }
  }

  for (const item of undirectedGraph) {
    // Outgoing edges
    if (!outgoingAdjList[item.fromFieldId]) {
      outgoingAdjList[item.fromFieldId] = [];
    }
    outgoingAdjList[item.fromFieldId].push(item);

    // Incoming edges
    if (!incomingAdjList[item.toFieldId]) {
      incomingAdjList[item.toFieldId] = [];
    }
    incomingAdjList[item.toFieldId].push(item);
  }

  function dfs(currentNode: string) {
    visited.add(currentNode);

    // Add incoming edges related to currentNode
    if (incomingAdjList[currentNode]) {
      incomingAdjList[currentNode].forEach((edge) => addEdgeIfNotExists(edge));
    }

    // Process outgoing edges from currentNode
    if (outgoingAdjList[currentNode]) {
      outgoingAdjList[currentNode].forEach((item) => {
        if (!visited.has(item.toFieldId)) {
          addEdgeIfNotExists(item);
          dfs(item.toFieldId);
        }
      });
    }
  }

  // Run DFS for each specified fieldId
  for (const fieldId of fieldIds) {
    if (!visited.has(fieldId)) {
      dfs(fieldId);
    }
  }

  return result;
}

export function pruneGraph(node: string, graph: IGraphItem[]): IGraphItem[] {
  const relatedNodes = new Set<string>();
  const prunedGraph: IGraphItem[] = [];

  function dfs(currentNode: string) {
    relatedNodes.add(currentNode);
    for (const edge of graph) {
      if (edge.fromFieldId === currentNode && !relatedNodes.has(edge.toFieldId)) {
        dfs(edge.toFieldId);
      }
    }
  }

  dfs(node);

  for (const edge of graph) {
    if (relatedNodes.has(edge.fromFieldId) || relatedNodes.has(edge.toFieldId)) {
      prunedGraph.push(edge);
      if (!relatedNodes.has(edge.fromFieldId)) {
        dfs(edge.fromFieldId);
      }
      if (!relatedNodes.has(edge.toFieldId)) {
        dfs(edge.toFieldId);
      }
    }
  }

  return prunedGraph;
}

1	/* eslint-disable sonarjs/cognitive-complexity */	2✔
2	import { uniq } from 'lodash';	2✔
3		2✔
4	// topo item is for field level reference, all id stands for fieldId;	2✔
5	export interface ITopoItem {	2✔
6	id: string;	2✔
7	dependencies: string[];	2✔
8	}	2✔
9		2✔
10	export interface IGraphItem {	2✔
11	fromFieldId: string;	2✔
12	toFieldId: string;	2✔
13	}	2✔
14		2✔
15	export type IAdjacencyMap = Record<string, string[]>;	2✔
16		2✔
17	export function buildAdjacencyMap(graph: IGraphItem[]): IAdjacencyMap {	2✔
18	const adjList: IAdjacencyMap = {};	999✔
19	graph.forEach((edge) => {	999✔
20	if (!adjList[edge.fromFieldId]) {	2,717✔
21	adjList[edge.fromFieldId] = [];	2,087✔
22	}	2,087✔
23	adjList[edge.fromFieldId].push(edge.toFieldId);	2,717✔
24	});	2,717✔
25	return adjList;	999✔
26	}	999✔
27		2✔
28	export function findNextValidNode(	2✔
29	current: string,	2,803✔
30	adjMap: IAdjacencyMap,	2,803✔
31	linkIdSet: Set<string>	2,803✔
32	): string \| null {	2,803✔
33	if (linkIdSet.has(current)) {	2,803✔
34	return current;	2,601✔
35	}	2,601✔
36		202✔
37	const neighbors = adjMap[current];	202✔
38	if (!neighbors) {	202✔
39	return null;	202✔
40	}	202!
41		×
42	for (const neighbor of neighbors) {	×
43	const validNode = findNextValidNode(neighbor, adjMap, linkIdSet);	×
44	if (validNode) {	×
45	return validNode;	×
46	}	×
47	}	×
48		×
49	return null;	×
50	}	×
51		2✔
52	/**	2✔
53	* Builds a compressed adjacency map based on the provided graph, linkIdSet, and startFieldIds.	2✔
54	* The compressed adjacency map represents the neighbors of each node in the graph, excluding nodes that are not valid according to the linkIdSet.	2✔
55	*	2✔
56	* @param graph - The graph containing the nodes and their connections.	2✔
57	* @param linkIdSet - A set of valid link IDs.	2✔
58	* @returns The compressed adjacency map representing the neighbors of each node.	2✔
59	*/	2✔
60	export function buildCompressedAdjacencyMap(	2✔
61	graph: IGraphItem[],	999✔
62	linkIdSet: Set<string>	999✔
63	): IAdjacencyMap {	999✔
64	const adjMap = buildAdjacencyMap(graph);	999✔
65	const compressedAdjMap: IAdjacencyMap = {};	999✔
66		999✔
67	Object.keys(adjMap).forEach((from) => {	999✔
68	const queue = [from];	2,087✔
69	const visited = new Set<string>();	2,087✔
70		2,087✔
71	while (queue.length > 0) {	2,087✔
72	const current = queue.shift();	4,658✔
73	if (!current \|\| visited.has(current)) continue;	4,658!
74		4,658✔
75	visited.add(current);	4,658✔
76	const neighbors = adjMap[current] \|\| [];	4,658✔
77	const compressedNeighbors = [];	4,658✔
78		4,658✔
79	for (const neighbor of neighbors) {	4,658✔
80	const nextValid = findNextValidNode(neighbor, adjMap, linkIdSet);	2,803✔
81	if (nextValid && !visited.has(nextValid)) {	2,803✔
82	compressedNeighbors.push(nextValid);	2,601✔
83	if (!linkIdSet.has(current)) {	2,601✔
84	queue.push(nextValid);	2,571✔
85	}	2,571✔
86	}	2,601✔
87	}	2,803✔
88		4,658✔
89	if (compressedNeighbors.length > 0) {	4,658✔
90	compressedAdjMap[current] = compressedNeighbors;	1,977✔
91	}	1,977✔
92	}	4,658✔
93	});	2,087✔
94		999✔
95	return compressedAdjMap;	999✔
96	}	999✔
97		2✔
98	export function hasCycle(graphItems: IGraphItem[]): boolean {	2✔
99	const adjList: Record<string, string[]> = {};	889✔
100	const visiting = new Set<string>();	889✔
101	const visited = new Set<string>();	889✔
102		889✔
103	// Build adjacency list	889✔
104	graphItems.forEach((item) => {	889✔
105	if (!adjList[item.fromFieldId]) {	875✔
106	adjList[item.fromFieldId] = [];	875✔
107	}	875✔
108	adjList[item.fromFieldId].push(item.toFieldId);	875✔
109	});	875✔
110		889✔
111	function dfs(node: string): boolean {	889✔
112	if (visiting.has(node)) return true;	1,750!
113	if (visited.has(node)) return false;	1,750✔
114		1,736✔
115	visiting.add(node);	1,736✔
116		1,736✔
117	if (adjList[node]) {	1,750✔
118	for (const neighbor of adjList[node]) {	875✔
119	if (dfs(neighbor)) return true;	875!
120	}	875✔
121	}	875✔
122		1,736✔
123	visiting.delete(node);	1,736✔
124	visited.add(node);	1,736✔
125		1,736✔
126	return false;	1,736✔
127	}	1,736✔
128		889✔
129	// Check for cycles	889✔
130	for (const node of Object.keys(adjList)) {	889✔
131	if (!visited.has(node) && dfs(node)) {	875!
132	return true;	×
133	}	×
134	}	875✔
135		889✔
136	return false;	889✔
137	}	889✔
138		2✔
139	/**	2✔
140	* Generate a topological order based on the starting node ID.	2✔
141	*	2✔
142	* @param startNodeId - The ID to start the search from.	2✔
143	* @param graph - The input graph.	2✔
144	* @returns An array of ITopoItem representing the topological order.	2✔
145	*/	2✔
146	export function topoOrderWithDepends(startNodeId: string, graph: IGraphItem[]): ITopoItem[] {	2✔
147	const visitedNodes = new Set<string>();	2,855✔
148	const visitingNodes = new Set<string>();	2,855✔
149	const sortedNodes: ITopoItem[] = [];	2,855✔
150		2,855✔
151	// Build adjacency list and reverse adjacency list	2,855✔
152	const adjList: Record<string, string[]> = {};	2,855✔
153	const reverseAdjList: Record<string, string[]> = {};	2,855✔
154	for (const edge of graph) {	2,855✔
155	if (!adjList[edge.fromFieldId]) adjList[edge.fromFieldId] = [];	18,799✔
156	adjList[edge.fromFieldId].push(edge.toFieldId);	18,799✔
157		18,799✔
158	if (!reverseAdjList[edge.toFieldId]) reverseAdjList[edge.toFieldId] = [];	18,799✔
159	reverseAdjList[edge.toFieldId].push(edge.fromFieldId);	18,799✔
160	}	18,799✔
161		2,855✔
162	function visit(node: string) {	2,855✔
163	if (visitingNodes.has(node)) {	3,245!
164	throw new Error(`Detected a cycle: ${node} is part of a circular dependency`);	×
165	}	×
166		3,245✔
167	if (!visitedNodes.has(node)) {	3,245✔
168	visitingNodes.add(node);	3,245✔
169		3,245✔
170	// Get incoming edges (dependencies)	3,245✔
171	const dependencies = reverseAdjList[node] \|\| [];	3,245✔
172		3,245✔
173	// Process outgoing edges	3,245✔
174	if (adjList[node]) {	3,245✔
175	for (const neighbor of adjList[node]) {	336✔
176	visit(neighbor);	390✔
177	}	390✔
178	}	336✔
179		3,245✔
180	visitingNodes.delete(node);	3,245✔
181	visitedNodes.add(node);	3,245✔
182	sortedNodes.push({ id: node, dependencies: dependencies });	3,245✔
183	}	3,245✔
184	}	3,245✔
185		2,855✔
186	visit(startNodeId);	2,855✔
187	return sortedNodes.reverse().map((node) => ({	2,855✔
188	id: node.id,	3,245✔
189	dependencies: uniq(node.dependencies),	3,245✔
190	}));	3,245✔
191	}	2,855✔
192		2✔
193	/**	2✔
194	* Generate a topological order with based on the starting node ID.	2✔
195	*/	2✔
196	export function topoOrderWithStart(startNodeId: string, graph: IGraphItem[]): string[] {	2✔
197	const visitedNodes = new Set<string>();	16✔
198	const sortedNodes: string[] = [];	16✔
199		16✔
200	// Build adjacency list and reverse adjacency list	16✔
201	const adjList: Record<string, string[]> = {};	16✔
202	const reverseAdjList: Record<string, string[]> = {};	16✔
203	for (const edge of graph) {	16✔
204	if (!adjList[edge.fromFieldId]) adjList[edge.fromFieldId] = [];	20✔
205	adjList[edge.fromFieldId].push(edge.toFieldId);	20✔
206		20✔
207	if (!reverseAdjList[edge.toFieldId]) reverseAdjList[edge.toFieldId] = [];	20✔
208	reverseAdjList[edge.toFieldId].push(edge.fromFieldId);	20✔
209	}	20✔
210		16✔
211	function visit(node: string) {	16✔
212	if (!visitedNodes.has(node)) {	24✔
213	visitedNodes.add(node);	24✔
214		24✔
215	// Process outgoing edges	24✔
216	if (adjList[node]) {	24✔
217	for (const neighbor of adjList[node]) {	8✔
218	visit(neighbor);	8✔
219	}	8✔
220	}	8✔
221		24✔
222	sortedNodes.push(node);	24✔
223	}	24✔
224	}	24✔
225		16✔
226	visit(startNodeId);	16✔
227	return sortedNodes.reverse();	16✔
228	}	16✔
229		2✔
230	// simple topological sort	2✔
231	export function topologicalSort(graph: IGraphItem[]): string[] {	2✔
232	const adjList: Record<string, string[]> = {};	×
233	const visited = new Set<string>();	×
234	const currentStack = new Set<string>();	×
235	const result: string[] = [];	×
236		×
237	graph.forEach((node) => {	×
238	if (!adjList[node.fromFieldId]) {	×
239	adjList[node.fromFieldId] = [];	×
240	}	×
241	adjList[node.fromFieldId].push(node.toFieldId);	×
242	});	×
243		×
244	function dfs(node: string) {	×
245	if (currentStack.has(node)) {	×
246	throw new Error(`Detected a cycle involving node '${node}'`);	×
247	}	×
248		×
249	if (visited.has(node)) {	×
250	return;	×
251	}	×
252		×
253	currentStack.add(node);	×
254	visited.add(node);	×
255		×
256	const neighbors = adjList[node] \|\| [];	×
257	neighbors.forEach((neighbor) => dfs(neighbor));	×
258		×
259	currentStack.delete(node);	×
260	result.push(node);	×
261	}	×
262		×
263	graph.forEach((node) => {	×
264	if (!visited.has(node.fromFieldId)) {	×
265	dfs(node.fromFieldId);	×
266	}	×
267	if (!visited.has(node.toFieldId)) {	×
268	dfs(node.toFieldId);	×
269	}	×
270	});	×
271		×
272	return result.reverse();	×
273	}	×
274		2✔
275	/**	2✔
276	* Returns all relations related to the given fieldIds.	2✔
277	*/	2✔
278	export function filterDirectedGraph(	2✔
279	undirectedGraph: IGraphItem[],	2,807✔
280	fieldIds: string[]	2,807✔
281	): IGraphItem[] {	2,807✔
282	const result: IGraphItem[] = [];	2,807✔
283	const visited: Set<string> = new Set();	2,807✔
284	const addedEdges: Set<string> = new Set(); // 新增：用于存储已添加的边	2,807✔
285		2,807✔
286	// Build adjacency lists for quick look-up	2,807✔
287	const outgoingAdjList: Record<string, IGraphItem[]> = {};	2,807✔
288	const incomingAdjList: Record<string, IGraphItem[]> = {};	2,807✔
289		2,807✔
290	function addEdgeIfNotExists(edge: IGraphItem) {	2,807✔
291	const edgeKey = edge.fromFieldId + '-' + edge.toFieldId;	3,291✔
292	if (!addedEdges.has(edgeKey)) {	3,291✔
293	addedEdges.add(edgeKey);	2,899✔
294	result.push(edge);	2,899✔
295	}	2,899✔
296	}	3,291✔
297		2,807✔
298	for (const item of undirectedGraph) {	2,807✔
299	// Outgoing edges	3,236✔
300	if (!outgoingAdjList[item.fromFieldId]) {	3,236✔
301	outgoingAdjList[item.fromFieldId] = [];	2,335✔
302	}	2,335✔
303	outgoingAdjList[item.fromFieldId].push(item);	3,236✔
304		3,236✔
305	// Incoming edges	3,236✔
306	if (!incomingAdjList[item.toFieldId]) {	3,236✔
307	incomingAdjList[item.toFieldId] = [];	3,206✔
308	}	3,206✔
309	incomingAdjList[item.toFieldId].push(item);	3,236✔
310	}	3,236✔
311		2,807✔
312	function dfs(currentNode: string) {	2,807✔
313	visited.add(currentNode);	4,897✔
314		4,897✔
315	// Add incoming edges related to currentNode	4,897✔
316	if (incomingAdjList[currentNode]) {	4,897✔
317	incomingAdjList[currentNode].forEach((edge) => addEdgeIfNotExists(edge));	2,869✔
318	}	2,869✔
319		4,897✔
320	// Process outgoing edges from currentNode	4,897✔
321	if (outgoingAdjList[currentNode]) {	4,897✔
322	outgoingAdjList[currentNode].forEach((item) => {	342✔
323	if (!visited.has(item.toFieldId)) {	396✔
324	addEdgeIfNotExists(item);	392✔
325	dfs(item.toFieldId);	392✔
326	}	392✔
327	});	396✔
328	}	342✔
329	}	4,897✔
330		2,807✔
331	// Run DFS for each specified fieldId	2,807✔
332	for (const fieldId of fieldIds) {	2,807✔
333	if (!visited.has(fieldId)) {	4,523✔
334	dfs(fieldId);	4,505✔
335	}	4,505✔
336	}	4,523✔
337		2,807✔
338	return result;	2,807✔
339	}	2,807✔
340		2✔
341	export function pruneGraph(node: string, graph: IGraphItem[]): IGraphItem[] {	2✔
342	const relatedNodes = new Set<string>();	8✔
343	const prunedGraph: IGraphItem[] = [];	8✔
344		8✔
345	function dfs(currentNode: string) {	8✔
346	relatedNodes.add(currentNode);	20✔
347	for (const edge of graph) {	20✔
348	if (edge.fromFieldId === currentNode && !relatedNodes.has(edge.toFieldId)) {	32✔
349	dfs(edge.toFieldId);	4✔
350	}	4✔
351	}	32✔
352	}	20✔
353		8✔
354	dfs(node);	8✔
355		8✔
356	for (const edge of graph) {	8✔
357	if (relatedNodes.has(edge.fromFieldId) \|\| relatedNodes.has(edge.toFieldId)) {	12✔
358	prunedGraph.push(edge);	12✔
359	if (!relatedNodes.has(edge.fromFieldId)) {	12✔
360	dfs(edge.fromFieldId);	8✔
361	}	8✔
362	if (!relatedNodes.has(edge.toFieldId)) {	12!
363	dfs(edge.toFieldId);	×
364	}	×
365	}	12✔
366	}	12✔
367		8✔
368	return prunedGraph;	8✔
369	}	8✔

teableio / teable / 8421654220

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous