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?
CodePudding user response:
Possible solution
- Transform the current directed graph into an undirected graph (so for each pair
(source, target)
,(target, source)
should be added toedges
too), 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 node
you 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.