8421671885

Committed 25 Mar 2024 02:23PM UTC coverage: 79.959% (+53.9%) from 26.087%

Build # 8421671885

Build Type

Pull #496

github

Committed by

web-flow

Commit Message

Merge f587f00fb into 9313e45fb

Pull Request Pull Request #496: fix: unexpected link convert

Run Details

3265 of 3865 branches covered (84.48%)

63 of 63 new or added lines in 4 files covered. (100.0%)

762 existing lines in 27 files now uncovered.

25183 of 31495 relevant lines covered (79.96%)

1188.33 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 = {};	993✔
19	graph.forEach((edge) => {	993✔
20	if (!adjList[edge.fromFieldId]) {	2,713✔
21	adjList[edge.fromFieldId] = [];	2,083✔
22	}	2,083✔
23	adjList[edge.fromFieldId].push(edge.toFieldId);	2,713✔
24	});	2,713✔
25	return adjList;	993✔
26	}	993✔
27		2✔
28	export function findNextValidNode(	2✔
29	current: string,	2,799✔
30	adjMap: IAdjacencyMap,	2,799✔
31	linkIdSet: Set<string>	2,799✔
32	): string \| null {	2,799✔
33	if (linkIdSet.has(current)) {	2,799✔
34	return current;	2,597✔
35	}	2,597✔
36		202✔
37	const neighbors = adjMap[current];	202✔
38	if (!neighbors) {	202✔
39	return null;	202✔
40	}	202!
UNCOV 41		×
UNCOV 42	for (const neighbor of neighbors) {	×
UNCOV 43	const validNode = findNextValidNode(neighbor, adjMap, linkIdSet);	×
UNCOV 44	if (validNode) {	×
UNCOV 45	return validNode;	×
UNCOV 46	}	×
UNCOV 47	}	×
UNCOV 48		×
UNCOV 49	return null;	×
UNCOV 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[],	993✔
62	linkIdSet: Set<string>	993✔
63	): IAdjacencyMap {	993✔
64	const adjMap = buildAdjacencyMap(graph);	993✔
65	const compressedAdjMap: IAdjacencyMap = {};	993✔
66		993✔
67	Object.keys(adjMap).forEach((from) => {	993✔
68	const queue = [from];	2,083✔
69	const visited = new Set<string>();	2,083✔
70		2,083✔
71	while (queue.length > 0) {	2,083✔
72	const current = queue.shift();	4,650✔
73	if (!current \|\| visited.has(current)) continue;	4,650!
74		4,650✔
75	visited.add(current);	4,650✔
76	const neighbors = adjMap[current] \|\| [];	4,650✔
77	const compressedNeighbors = [];	4,650✔
78		4,650✔
79	for (const neighbor of neighbors) {	4,650✔
80	const nextValid = findNextValidNode(neighbor, adjMap, linkIdSet);	2,799✔
81	if (nextValid && !visited.has(nextValid)) {	2,799✔
82	compressedNeighbors.push(nextValid);	2,597✔
83	if (!linkIdSet.has(current)) {	2,597✔
84	queue.push(nextValid);	2,567✔
85	}	2,567✔
86	}	2,597✔
87	}	2,799✔
88		4,650✔
89	if (compressedNeighbors.length > 0) {	4,650✔
90	compressedAdjMap[current] = compressedNeighbors;	1,973✔
91	}	1,973✔
92	}	4,650✔
93	});	2,083✔
94		993✔
95	return compressedAdjMap;	993✔
96	}	993✔
97		2✔
98	export function hasCycle(graphItems: IGraphItem[]): boolean {	2✔
99	const adjList: Record<string, string[]> = {};	893✔
100	const visiting = new Set<string>();	893✔
101	const visited = new Set<string>();	893✔
102		893✔
103	// Build adjacency list	893✔
104	graphItems.forEach((item) => {	893✔
105	if (!adjList[item.fromFieldId]) {	879✔
106	adjList[item.fromFieldId] = [];	879✔
107	}	879✔
108	adjList[item.fromFieldId].push(item.toFieldId);	879✔
109	});	879✔
110		893✔
111	function dfs(node: string): boolean {	893✔
112	if (visiting.has(node)) return true;	1,758!
113	if (visited.has(node)) return false;	1,758✔
114		1,744✔
115	visiting.add(node);	1,744✔
116		1,744✔
117	if (adjList[node]) {	1,758✔
118	for (const neighbor of adjList[node]) {	879✔
119	if (dfs(neighbor)) return true;	879!
120	}	879✔
121	}	879✔
122		1,744✔
123	visiting.delete(node);	1,744✔
124	visited.add(node);	1,744✔
125		1,744✔
126	return false;	1,744✔
127	}	1,744✔
128		893✔
129	// Check for cycles	893✔
130	for (const node of Object.keys(adjList)) {	893✔
131	if (!visited.has(node) && dfs(node)) {	879!
UNCOV 132	return true;	×
UNCOV 133	}	×
134	}	879✔
135		893✔
136	return false;	893✔
137	}	893✔
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,845✔
148	const visitingNodes = new Set<string>();	2,845✔
149	const sortedNodes: ITopoItem[] = [];	2,845✔
150		2,845✔
151	// Build adjacency list and reverse adjacency list	2,845✔
152	const adjList: Record<string, string[]> = {};	2,845✔
153	const reverseAdjList: Record<string, string[]> = {};	2,845✔
154	for (const edge of graph) {	2,845✔
155	if (!adjList[edge.fromFieldId]) adjList[edge.fromFieldId] = [];	18,795✔
156	adjList[edge.fromFieldId].push(edge.toFieldId);	18,795✔
157		18,795✔
158	if (!reverseAdjList[edge.toFieldId]) reverseAdjList[edge.toFieldId] = [];	18,795✔
159	reverseAdjList[edge.toFieldId].push(edge.fromFieldId);	18,795✔
160	}	18,795✔
161		2,845✔
162	function visit(node: string) {	2,845✔
163	if (visitingNodes.has(node)) {	3,235!
UNCOV 164	throw new Error(`Detected a cycle: ${node} is part of a circular dependency`);	×
UNCOV 165	}	×
166		3,235✔
167	if (!visitedNodes.has(node)) {	3,235✔
168	visitingNodes.add(node);	3,235✔
169		3,235✔
170	// Get incoming edges (dependencies)	3,235✔
171	const dependencies = reverseAdjList[node] \|\| [];	3,235✔
172		3,235✔
173	// Process outgoing edges	3,235✔
174	if (adjList[node]) {	3,235✔
175	for (const neighbor of adjList[node]) {	336✔
176	visit(neighbor);	390✔
177	}	390✔
178	}	336✔
179		3,235✔
180	visitingNodes.delete(node);	3,235✔
181	visitedNodes.add(node);	3,235✔
182	sortedNodes.push({ id: node, dependencies: dependencies });	3,235✔
183	}	3,235✔
184	}	3,235✔
185		2,845✔
186	visit(startNodeId);	2,845✔
187	return sortedNodes.reverse().map((node) => ({	2,845✔
188	id: node.id,	3,235✔
189	dependencies: uniq(node.dependencies),	3,235✔
190	}));	3,235✔
191	}	2,845✔
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✔
UNCOV 232	const adjList: Record<string, string[]> = {};	×
UNCOV 233	const visited = new Set<string>();	×
UNCOV 234	const currentStack = new Set<string>();	×
UNCOV 235	const result: string[] = [];	×
UNCOV 236		×
UNCOV 237	graph.forEach((node) => {	×
UNCOV 238	if (!adjList[node.fromFieldId]) {	×
UNCOV 239	adjList[node.fromFieldId] = [];	×
UNCOV 240	}	×
UNCOV 241	adjList[node.fromFieldId].push(node.toFieldId);	×
UNCOV 242	});	×
UNCOV 243		×
UNCOV 244	function dfs(node: string) {	×
UNCOV 245	if (currentStack.has(node)) {	×
UNCOV 246	throw new Error(`Detected a cycle involving node '${node}'`);	×
UNCOV 247	}	×
UNCOV 248		×
UNCOV 249	if (visited.has(node)) {	×
UNCOV 250	return;	×
UNCOV 251	}	×
UNCOV 252		×
UNCOV 253	currentStack.add(node);	×
UNCOV 254	visited.add(node);	×
UNCOV 255		×
UNCOV 256	const neighbors = adjList[node] \|\| [];	×
UNCOV 257	neighbors.forEach((neighbor) => dfs(neighbor));	×
UNCOV 258		×
UNCOV 259	currentStack.delete(node);	×
UNCOV 260	result.push(node);	×
UNCOV 261	}	×
UNCOV 262		×
UNCOV 263	graph.forEach((node) => {	×
UNCOV 264	if (!visited.has(node.fromFieldId)) {	×
UNCOV 265	dfs(node.fromFieldId);	×
UNCOV 266	}	×
UNCOV 267	if (!visited.has(node.toFieldId)) {	×
268	dfs(node.toFieldId);	×
269	}	×
UNCOV 270	});	×
UNCOV 271		×
UNCOV 272	return result.reverse();	×
UNCOV 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,799✔
280	fieldIds: string[]	2,799✔
281	): IGraphItem[] {	2,799✔
282	const result: IGraphItem[] = [];	2,799✔
283	const visited: Set<string> = new Set();	2,799✔
284	const addedEdges: Set<string> = new Set(); // 新增：用于存储已添加的边	2,799✔
285		2,799✔
286	// Build adjacency lists for quick look-up	2,799✔
287	const outgoingAdjList: Record<string, IGraphItem[]> = {};	2,799✔
288	const incomingAdjList: Record<string, IGraphItem[]> = {};	2,799✔
289		2,799✔
290	function addEdgeIfNotExists(edge: IGraphItem) {	2,799✔
291	const edgeKey = edge.fromFieldId + '-' + edge.toFieldId;	3,283✔
292	if (!addedEdges.has(edgeKey)) {	3,283✔
293	addedEdges.add(edgeKey);	2,891✔
294	result.push(edge);	2,891✔
295	}	2,891✔
296	}	3,283✔
297		2,799✔
298	for (const item of undirectedGraph) {	2,799✔
299	// Outgoing edges	3,216✔
300	if (!outgoingAdjList[item.fromFieldId]) {	3,216✔
301	outgoingAdjList[item.fromFieldId] = [];	2,327✔
302	}	2,327✔
303	outgoingAdjList[item.fromFieldId].push(item);	3,216✔
304		3,216✔
305	// Incoming edges	3,216✔
306	if (!incomingAdjList[item.toFieldId]) {	3,216✔
307	incomingAdjList[item.toFieldId] = [];	3,186✔
308	}	3,186✔
309	incomingAdjList[item.toFieldId].push(item);	3,216✔
310	}	3,216✔
311		2,799✔
312	function dfs(currentNode: string) {	2,799✔
313	visited.add(currentNode);	4,891✔
314		4,891✔
315	// Add incoming edges related to currentNode	4,891✔
316	if (incomingAdjList[currentNode]) {	4,891✔
317	incomingAdjList[currentNode].forEach((edge) => addEdgeIfNotExists(edge));	2,861✔
318	}	2,861✔
319		4,891✔
320	// Process outgoing edges from currentNode	4,891✔
321	if (outgoingAdjList[currentNode]) {	4,891✔
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,891✔
330		2,799✔
331	// Run DFS for each specified fieldId	2,799✔
332	for (const fieldId of fieldIds) {	2,799✔
333	if (!visited.has(fieldId)) {	4,517✔
334	dfs(fieldId);	4,499✔
335	}	4,499✔
336	}	4,517✔
337		2,799✔
338	return result;	2,799✔
339	}	2,799✔
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 / 8421671885

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