Determine whether certain nodes on a graph are directly connected

user_6372449 0
Viewed 34

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:

enter image description here

Bad selection:

enter image description here

Is there some algorithm for checking that? Are you aware of some npm packages in case of JavaScript?

graph-traversal graph data-structures algorithm javascript
1 Answers

Possible solution

  1. Transform the current directed graph into an undirected graph (so for each pair (source, target), (target, source)should be added to edges 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
  2. 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 return false

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 keep O(1) time complexity. Running DFS/BFS from all selected nodes will result in O(N) time complexity, where N = # of nodes, and would also provide a correct result, but would introduce redundant graph traversals.
user_168154620
Related