I'm looking for a way to detect loops (including the nodes that form them) in an undirected graph.
This answer suggests that we can detect a loop during a depth-first-search "If an unexplored edge leads to a node visited before."
So with the code below I can successfully detect loops. My question is: once I have detected a loop, how can I know which are the nodes that form that loop?
class LoopFinder {
nodes = "A B C D E F".split(" ");
edges = [
["A", "B"],
["A", "D"],
["B", "C"],
["C", "D"],
["C", "E"],
["D", "E"],
["D", "F"],
["F", "E"]
];
adjacencyList = new Map();
addNode(point) {
this.adjacencyList.set(point, []);
}
addEdge(nodeOne, nodeTwo) {
this.adjacencyList.get(nodeOne).push(nodeTwo);
this.adjacencyList.get(nodeTwo).push(nodeOne);
}
setupGraph() {
this.nodes.forEach((point) => this.addNode(point));
this.edges.forEach((route) => this.addEdge(route[0], route[1]));
}
visitedEdges = [];
dfs(startNode, visitedNodes = new Set()) {
console.log(startNode);
visitedNodes.add(startNode);
const adjacentNodes = this.adjacencyList.get(startNode);
for (const adjacentNode of adjacentNodes) {
const edgeId = [startNode, adjacentNode].sort().join("-");
console.log("exporing edge", edgeId);
const edgeIsUnexplored = !this.visitedEdges.includes(edgeId);
const destinationHasBeenVisited = visitedNodes.has(adjacentNode);
if (edgeIsUnexplored && destinationHasBeenVisited) {
console.log('DETECTED LOOP - But which nodes form the loop?' );
}
this.visitedEdges.push(edgeId);
if (!destinationHasBeenVisited) {
this.dfs(adjacentNode, visitedNodes);
}
}
}
constructor() {
this.setupGraph();
this.dfs("A");
}
}
new LoopFinder()
Also on Codepen.
The graph used in the example below looks like this:
B---C---F
/ / \ /
A--D----E
So the expected output would be 3 loops made of the following nodes:
- ABCD
- CDE
- CEF