Skip to content

Commit 5f3588e

Browse files
trekhlebtrekhleb
committed
Add Tarjan's algorithm.
1 parent 5f50bd9 commit 5f3588e

5 files changed

Lines changed: 317 additions & 1 deletion

File tree

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,8 @@
7272
* [Prim’s Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/prim) - finding Minimum Spanning Tree (MST) for weighted undirected graph
7373
* [Kruskal’s Algorithm](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/kruskal) - finding Minimum Spanning Tree (MST) for weighted undirected graph
7474
* [Topological Sorting](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/topological-sorting) - DFS method
75-
* Eulerian path, Eulerian circuit
75+
* [Articulation Points](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/articulation-points) - Tarjan's algorithm
76+
* [Eulerian Path and Eulerian Circuit](https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/graph/eulerian-path)
7677
* Strongly Connected Component algorithm
7778
* Shortest Path Faster Algorithm (SPFA)
7879
* **Uncategorized**

‎src/algorithms/graph/articulation-points/README.md‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# Articulation Points (or Cut Vertices)
2+
3+
A vertex in an undirected connected graph is an articulation point
4+
(or cut vertex) iff removing it (and edges through it) disconnects
5+
the graph. Articulation points represent vulnerabilities in a
6+
connected network – single points whose failure would split the
7+
network into 2 or more disconnected components. They are useful for
8+
designing reliable networks.
9+
10+
For a disconnected undirected graph, an articulation point is a
11+
vertex removing which increases number of connected components.
12+
13+
![Articulation Points](https://www.geeksforgeeks.org/wp-content/uploads/ArticulationPoints.png)
14+
15+
![Articulation Points](https://www.geeksforgeeks.org/wp-content/uploads/ArticulationPoints1.png)
16+
17+
![Articulation Points](https://www.geeksforgeeks.org/wp-content/uploads/ArticulationPoints21.png)
18+
19+
## References
20+
21+
- [GeeksForGeeks](https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/)
22+
- [YouTube](https://www.youtube.com/watch?v=2kREIkF9UAs)

‎src/algorithms/graph/articulation-points/__test__/articulationPoints.test.js‎

Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
import GraphVertex from '../../../../data-structures/graph/GraphVertex';
2+
import GraphEdge from '../../../../data-structures/graph/GraphEdge';
3+
import Graph from '../../../../data-structures/graph/Graph';
4+
import articulationPoints from '../articulationPoints';
5+
6+
describe('articulationPoints', () => {
7+
it('should find articulation points in simple graph', () => {
8+
const vertexA = new GraphVertex('A');
9+
const vertexB = new GraphVertex('B');
10+
const vertexC = new GraphVertex('C');
11+
const vertexD = new GraphVertex('D');
12+
13+
const edgeAB = new GraphEdge(vertexA, vertexB);
14+
const edgeBC = new GraphEdge(vertexB, vertexC);
15+
const edgeCD = new GraphEdge(vertexC, vertexD);
16+
17+
const graph = new Graph();
18+
19+
graph
20+
.addEdge(edgeAB)
21+
.addEdge(edgeBC)
22+
.addEdge(edgeCD);
23+
24+
const articulationPointsSet = articulationPoints(graph);
25+
26+
expect(articulationPointsSet).toEqual([
27+
vertexC,
28+
vertexB,
29+
]);
30+
});
31+
32+
it('should find articulation points in simple graph with back edge', () => {
33+
const vertexA = new GraphVertex('A');
34+
const vertexB = new GraphVertex('B');
35+
const vertexC = new GraphVertex('C');
36+
const vertexD = new GraphVertex('D');
37+
38+
const edgeAB = new GraphEdge(vertexA, vertexB);
39+
const edgeBC = new GraphEdge(vertexB, vertexC);
40+
const edgeCD = new GraphEdge(vertexC, vertexD);
41+
const edgeAC = new GraphEdge(vertexA, vertexC);
42+
43+
const graph = new Graph();
44+
45+
graph
46+
.addEdge(edgeAB)
47+
.addEdge(edgeAC)
48+
.addEdge(edgeBC)
49+
.addEdge(edgeCD);
50+
51+
const articulationPointsSet = articulationPoints(graph);
52+
53+
expect(articulationPointsSet).toEqual([
54+
vertexC,
55+
]);
56+
});
57+
58+
it('should find articulation points in graph', () => {
59+
const vertexA = new GraphVertex('A');
60+
const vertexB = new GraphVertex('B');
61+
const vertexC = new GraphVertex('C');
62+
const vertexD = new GraphVertex('D');
63+
const vertexE = new GraphVertex('E');
64+
const vertexF = new GraphVertex('F');
65+
const vertexG = new GraphVertex('G');
66+
const vertexH = new GraphVertex('H');
67+
68+
const edgeAB = new GraphEdge(vertexA, vertexB);
69+
const edgeBC = new GraphEdge(vertexB, vertexC);
70+
const edgeAC = new GraphEdge(vertexA, vertexC);
71+
const edgeCD = new GraphEdge(vertexC, vertexD);
72+
const edgeDE = new GraphEdge(vertexD, vertexE);
73+
const edgeEG = new GraphEdge(vertexE, vertexG);
74+
const edgeEF = new GraphEdge(vertexE, vertexF);
75+
const edgeGF = new GraphEdge(vertexG, vertexF);
76+
const edgeFH = new GraphEdge(vertexF, vertexH);
77+
78+
const graph = new Graph();
79+
80+
graph
81+
.addEdge(edgeAB)
82+
.addEdge(edgeBC)
83+
.addEdge(edgeAC)
84+
.addEdge(edgeCD)
85+
.addEdge(edgeDE)
86+
.addEdge(edgeEG)
87+
.addEdge(edgeEF)
88+
.addEdge(edgeGF)
89+
.addEdge(edgeFH);
90+
91+
const articulationPointsSet = articulationPoints(graph);
92+
93+
expect(articulationPointsSet).toEqual([
94+
vertexF,
95+
vertexE,
96+
vertexD,
97+
vertexC,
98+
]);
99+
});
100+
101+
it('should find articulation points in graph starting with articulation root vertex', () => {
102+
const vertexA = new GraphVertex('A');
103+
const vertexB = new GraphVertex('B');
104+
const vertexC = new GraphVertex('C');
105+
const vertexD = new GraphVertex('D');
106+
const vertexE = new GraphVertex('E');
107+
const vertexF = new GraphVertex('F');
108+
const vertexG = new GraphVertex('G');
109+
const vertexH = new GraphVertex('H');
110+
111+
const edgeAB = new GraphEdge(vertexA, vertexB);
112+
const edgeBC = new GraphEdge(vertexB, vertexC);
113+
const edgeAC = new GraphEdge(vertexA, vertexC);
114+
const edgeCD = new GraphEdge(vertexC, vertexD);
115+
const edgeDE = new GraphEdge(vertexD, vertexE);
116+
const edgeEG = new GraphEdge(vertexE, vertexG);
117+
const edgeEF = new GraphEdge(vertexE, vertexF);
118+
const edgeGF = new GraphEdge(vertexG, vertexF);
119+
const edgeFH = new GraphEdge(vertexF, vertexH);
120+
121+
const graph = new Graph();
122+
123+
graph
124+
.addEdge(edgeDE)
125+
.addEdge(edgeAB)
126+
.addEdge(edgeBC)
127+
.addEdge(edgeAC)
128+
.addEdge(edgeCD)
129+
.addEdge(edgeEG)
130+
.addEdge(edgeEF)
131+
.addEdge(edgeGF)
132+
.addEdge(edgeFH);
133+
134+
const articulationPointsSet = articulationPoints(graph);
135+
136+
expect(articulationPointsSet).toEqual([
137+
vertexF,
138+
vertexE,
139+
vertexC,
140+
vertexD,
141+
]);
142+
});
143+
});

‎src/algorithms/graph/articulation-points/articulationPoints.js‎

Lines changed: 116 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,116 @@
1+
import depthFirstSearch from '../depth-first-search/depthFirstSearch';
2+
3+
/**
4+
* Helper class for visited vertex metadata.
5+
*/
6+
class VisitMetadata {
7+
constructor({ discoveryTime, lowDiscoveryTime }) {
8+
this.discoveryTime = discoveryTime;
9+
this.lowDiscoveryTime = lowDiscoveryTime;
10+
11+
// We need this to know to which vertex we need to compare discovery time
12+
// when leaving the vertex.
13+
this.childVertex = null;
14+
15+
// We need this in order to check graph root node, whether it has two
16+
// disconnected children or not.
17+
this.childrenCount = 0;
18+
}
19+
}
20+
21+
/**
22+
* Tarjan's algorithm for rinding articulation points in graph.
23+
*
24+
* @param {Graph} graph
25+
* @return {GraphVertex[]}
26+
*/
27+
export default function articulationPoints(graph) {
28+
// Set of vertices we've already visited during DFS.
29+
const visitedSet = {};
30+
31+
// Set of articulation points found so far.
32+
const articulationPointsSet = [];
33+
34+
// Time needed to get to the current vertex.
35+
let discoveryTime = 0;
36+
37+
// Peek the start vertex for DFS traversal.
38+
const startVertex = graph.getAllVertices()[0];
39+
40+
const dfsCallbacks = {
41+
/**
42+
* @param {GraphVertex} currentVertex
43+
* @param {GraphVertex} previousVertex
44+
*/
45+
enterVertex: ({ currentVertex, previousVertex }) => {
46+
// Put current vertex to visited set.
47+
visitedSet[currentVertex.getKey()] = new VisitMetadata({
48+
discoveryTime,
49+
lowDiscoveryTime: discoveryTime,
50+
});
51+
52+
// Tick discovery time.
53+
discoveryTime += 1;
54+
55+
if (previousVertex) {
56+
// Update child vertex information for previous vertex.
57+
visitedSet[previousVertex.getKey()].childVertex = currentVertex;
58+
59+
// Update children counter for previous vertex.
60+
visitedSet[previousVertex.getKey()].childrenCount += 1;
61+
}
62+
},
63+
/**
64+
* @param {GraphVertex} currentVertex
65+
* @param {GraphVertex} previousVertex
66+
*/
67+
leaveVertex: ({ currentVertex }) => {
68+
// Detect whether current vertex is articulation point or not.
69+
// To do so we need to check two (OR) conditions:
70+
// 1. Is it a root vertex with at least two independent children.
71+
// 2. If its visited time is <= low time of adjacent vertex.
72+
if (currentVertex === startVertex) {
73+
// Check that it has at least two independent children.
74+
if (visitedSet[currentVertex.getKey()].childrenCount >= 2) {
75+
articulationPointsSet.push(currentVertex);
76+
}
77+
} else {
78+
// Get child vertex low discovery time.
79+
let childVertexLowDiscoveryTime = null;
80+
if (visitedSet[currentVertex.getKey()].childVertex) {
81+
const childVertexKey = visitedSet[currentVertex.getKey()].childVertex.getKey();
82+
childVertexLowDiscoveryTime = visitedSet[childVertexKey].lowDiscoveryTime;
83+
}
84+
85+
// Compare child vertex low discovery time with current discovery time to if there
86+
// are any short path (back edge) exists. If we can get to child vertex faster then
87+
// to current one it means that there is a back edge exists (short path) and current
88+
// vertex isn't articulation point.
89+
const currentDiscoveryTime = visitedSet[currentVertex.getKey()].discoveryTime;
90+
if (currentDiscoveryTime <= childVertexLowDiscoveryTime) {
91+
articulationPointsSet.push(currentVertex);
92+
}
93+
94+
// Update the low time with the smallest time of adjacent vertices.
95+
96+
// Get minimum low discovery time from all neighbors.
97+
/** @param {GraphVertex} neighbor */
98+
visitedSet[currentVertex.getKey()].lowDiscoveryTime = currentVertex.getNeighbors().reduce(
99+
(lowestDiscoveryTime, neighbor) => {
100+
const neighborLowTime = visitedSet[neighbor.getKey()].lowDiscoveryTime;
101+
return neighborLowTime < lowestDiscoveryTime ? neighborLowTime : lowestDiscoveryTime;
102+
},
103+
visitedSet[currentVertex.getKey()].lowDiscoveryTime,
104+
);
105+
}
106+
},
107+
allowTraversal: ({ nextVertex }) => {
108+
return !visitedSet[nextVertex.getKey()];
109+
},
110+
};
111+
112+
// Do Depth First Search traversal over submitted graph.
113+
depthFirstSearch(graph, startVertex, dfsCallbacks);
114+
115+
return articulationPointsSet;
116+
}

‎src/algorithms/graph/eulerian-path/README.md‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# Eulerian Path
2+
3+
In graph theory, an **Eulerian trail** (or **Eulerian path**) is a
4+
trail in a finite graph which visits every edge exactly once.
5+
Similarly, an **Eulerian circuit** or **Eulerian cycle** is an
6+
Eulerian trail which starts and ends on the same vertex.
7+
8+
Euler proved that a necessary condition for the existence of Eulerian
9+
circuits is that all vertices in the graph have an even degree, and
10+
stated that connected graphs with all vertices of even degree have
11+
an Eulerian circuit.
12+
13+
![Eulerian Circuit](https://upload.wikimedia.org/wikipedia/commons/7/72/Labelled_Eulergraph.svg)
14+
15+
Every vertex of this graph has an even degree. Therefore, this is
16+
an Eulerian graph. Following the edges in alphabetical order gives
17+
an Eulerian circuit/cycle.
18+
19+
For the existence of Eulerian trails it is necessary that zero or
20+
two vertices have an odd degree; this means the Königsberg graph
21+
is not Eulerian. If there are no vertices of odd degree,
22+
all Eulerian trails are circuits. If there are exactly two vertices
23+
of odd degree, all Eulerian trails start at one of them and end at
24+
the other. A graph that has an Eulerian trail but not an Eulerian
25+
circuit is called semi-Eulerian.
26+
27+
![Königsberg graph](https://upload.wikimedia.org/wikipedia/commons/9/96/K%C3%B6nigsberg_graph.svg)
28+
29+
The Königsberg Bridges multigraph. This multigraph is not Eulerian,
30+
therefore, a solution does not exist.
31+
32+
## References
33+
34+
- [Wikipedia](https://en.wikipedia.org/wiki/Eulerian_path)

0 commit comments

Comments
 (0)