javascriptalgorithmdata-structuresgraphgraph-traversal

Determine 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:

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?

Solution

  • 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