Add Tarjan's algorithm.

trekhleb · trekhleb · commit ff9877cf6b9a · 2018-05-11T06:58:19.000+03:00
diff --git a/src/algorithms/graph/articulation-points/__test__/articulationPoints.test.js b/src/algorithms/graph/articulation-points/__test__/articulationPoints.test.js
@@ -55,6 +55,35 @@ describe('articulationPoints', () => {
     ]);
   });
 
+  it('should find articulation points in simple graph with back edge #2', () => {
+    const vertexA = new GraphVertex('A');
+    const vertexB = new GraphVertex('B');
+    const vertexC = new GraphVertex('C');
+    const vertexD = new GraphVertex('D');
+    const vertexE = new GraphVertex('E');
+
+    const edgeAB = new GraphEdge(vertexA, vertexB);
+    const edgeBC = new GraphEdge(vertexB, vertexC);
+    const edgeCD = new GraphEdge(vertexC, vertexD);
+    const edgeAE = new GraphEdge(vertexA, vertexE);
+    const edgeCE = new GraphEdge(vertexC, vertexE);
+
+    const graph = new Graph();
+
+    graph
+      .addEdge(edgeAB)
+      .addEdge(edgeAE)
+      .addEdge(edgeCE)
+      .addEdge(edgeBC)
+      .addEdge(edgeCD);
+
+    const articulationPointsSet = articulationPoints(graph);
+
+    expect(articulationPointsSet).toEqual([
+      vertexC,
+    ]);
+  });
+
   it('should find articulation points in graph', () => {
     const vertexA = new GraphVertex('A');
     const vertexB = new GraphVertex('B');
diff --git a/src/algorithms/graph/articulation-points/articulationPoints.js b/src/algorithms/graph/articulation-points/articulationPoints.js
@@ -14,7 +14,7 @@ class VisitMetadata {
 
     // We need this in order to check graph root node, whether it has two
     // disconnected children or not.
-    this.childrenCount = 0;
+    this.independantChildrenCount = 0;
   }
 }
 
@@ -57,7 +57,7 @@ export default function articulationPoints(graph) {
         visitedSet[previousVertex.getKey()].childVertex = currentVertex;
 
         // Update children counter for previous vertex.
-        visitedSet[previousVertex.getKey()].childrenCount += 1;
+        visitedSet[previousVertex.getKey()].independantChildrenCount += 1;
       }
     },
     /**
@@ -71,7 +71,7 @@ export default function articulationPoints(graph) {
       // 2. If its visited time is <= low time of adjacent vertex.
       if (currentVertex === startVertex) {
         // Check that it has at least two independent children.
-        if (visitedSet[currentVertex.getKey()].childrenCount >= 2) {
+        if (visitedSet[currentVertex.getKey()].independantChildrenCount >= 2) {
           articulationPointsSet.push(currentVertex);
         }
       } else {

Original file line number	Diff line number	Diff line change
`@@ -14,7 +14,7 @@ class VisitMetadata {`
`14`	`14`
`15`	`15`	`// We need this in order to check graph root node, whether it has two`
`16`	`16`	`// disconnected children or not.`
`17`		`- this.childrenCount = 0;`
	`17`	`+ this.independantChildrenCount = 0;`
`18`	`18`	`}`
`19`	`19`	`}`
`20`	`20`
`@@ -57,7 +57,7 @@ export default function articulationPoints(graph) {`
`57`	`57`	`visitedSet[previousVertex.getKey()].childVertex = currentVertex;`
`58`	`58`
`59`	`59`	`// Update children counter for previous vertex.`
`60`		`- visitedSet[previousVertex.getKey()].childrenCount += 1;`
	`60`	`+ visitedSet[previousVertex.getKey()].independantChildrenCount += 1;`
`61`	`61`	`}`
`62`	`62`	`},`
`63`	`63`	`/**`
`@@ -71,7 +71,7 @@ export default function articulationPoints(graph) {`
`71`	`71`	`// 2. If its visited time is <= low time of adjacent vertex.`
`72`	`72`	`if (currentVertex === startVertex) {`
`73`	`73`	`// Check that it has at least two independent children.`
`74`		`- if (visitedSet[currentVertex.getKey()].childrenCount >= 2) {`
	`74`	`+ if (visitedSet[currentVertex.getKey()].independantChildrenCount >= 2) {`
`75`	`75`	`articulationPointsSet.push(currentVertex);`
`76`	`76`	`}`
`77`	`77`	`} else {`