0
211
ViewsDetermine whether certain nodes on a graph are directly connected
How can I determine whether selected nodes on a graph are directly connected?
I think, I need to calculate paths for each selected node to all of the other selected nodes. Then, when I have the path, I have to check whether path contains only selected nodes.
In the code, all I have is a notion of nodes and edges, like this:
const nodes = [
{ id: "A" },
{ id: "B" },
{ id: "C" },
{ id: "D" },
{ id: "E" },
{ id: "F" },
];
const edges = [
{ target: "A", source: "B" },
{ target: "B", source: "C" },
{ target: "C", source: "D" },
{ target: "D", source: "E" },
{ target: "E", source: "F" },
];
Examples:
Good selection:
Bad selection:
Is there some algorithm for checking that? Are you aware of some npm packages in case of JavaScript?
·
Juan Pablo Isaza
1 answers
Answer question0
Possible solution
- Transform the current directed graph into an undirected graph (so for each pair
(source, target),(target, source)should be added toedgestoo), as we are not interested in whether A reaches B or B reaches A, but instead we are trying to see whether they are connected - Run a graph traversal algorithm (Depth First Search (DFS) or Breadth First Search (BFS) from any selected node on the undirected graph you've just created. If all selected nodes can be reached, return
true, otherwise returnfalse
Notes
- It does not matter from which
selected nodeyou run the DFS/BFS from as long as the graph is undirected. Therefore, it is important to run DFS/BFS only once to keepO(1)time complexity. Running DFS/BFS from all selected nodes will result inO(N)time complexity, whereN = # of nodes, and would also provide a correct result, but would introduce redundant graph traversals.
·
Juan Pablo Isaza
Report
Answer question