Skip to content

Commit 21d4144

Browse files
trekhlebtrekhleb
committed
Add Tarjan's algorithm.
1 parent ff9877c commit 21d4144

3 files changed

Lines changed: 59 additions & 75 deletions

File tree

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
# Articulation Points (or Cut Vertices)
22

33
A vertex in an undirected connected graph is an articulation point
4-
(or cut vertex) iff removing it (and edges through it) disconnects
4+
(or cut vertex) if removing it (and edges through it) disconnects
55
the graph. Articulation points represent vulnerabilities in a
66
connected network – single points whose failure would split the
77
network into 2 or more disconnected components. They are useful for

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

Lines changed: 22 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -23,10 +23,9 @@ describe('articulationPoints', () => {
2323

2424
const articulationPointsSet = articulationPoints(graph);
2525

26-
expect(articulationPointsSet).toEqual([
27-
vertexC,
28-
vertexB,
29-
]);
26+
expect(articulationPointsSet.length).toBe(2);
27+
expect(articulationPointsSet[0].getKey()).toBe(vertexC.getKey());
28+
expect(articulationPointsSet[1].getKey()).toBe(vertexB.getKey());
3029
});
3130

3231
it('should find articulation points in simple graph with back edge', () => {
@@ -50,9 +49,8 @@ describe('articulationPoints', () => {
5049

5150
const articulationPointsSet = articulationPoints(graph);
5251

53-
expect(articulationPointsSet).toEqual([
54-
vertexC,
55-
]);
52+
expect(articulationPointsSet.length).toBe(1);
53+
expect(articulationPointsSet[0].getKey()).toBe(vertexC.getKey());
5654
});
5755

5856
it('should find articulation points in simple graph with back edge #2', () => {
@@ -79,9 +77,8 @@ describe('articulationPoints', () => {
7977

8078
const articulationPointsSet = articulationPoints(graph);
8179

82-
expect(articulationPointsSet).toEqual([
83-
vertexC,
84-
]);
80+
expect(articulationPointsSet.length).toBe(1);
81+
expect(articulationPointsSet[0].getKey()).toBe(vertexC.getKey());
8582
});
8683

8784
it('should find articulation points in graph', () => {
@@ -119,12 +116,11 @@ describe('articulationPoints', () => {
119116

120117
const articulationPointsSet = articulationPoints(graph);
121118

122-
expect(articulationPointsSet).toEqual([
123-
vertexF,
124-
vertexE,
125-
vertexD,
126-
vertexC,
127-
]);
119+
expect(articulationPointsSet.length).toBe(4);
120+
expect(articulationPointsSet[0].getKey()).toBe(vertexF.getKey());
121+
expect(articulationPointsSet[1].getKey()).toBe(vertexE.getKey());
122+
expect(articulationPointsSet[2].getKey()).toBe(vertexD.getKey());
123+
expect(articulationPointsSet[3].getKey()).toBe(vertexC.getKey());
128124
});
129125

130126
it('should find articulation points in graph starting with articulation root vertex', () => {
@@ -162,12 +158,11 @@ describe('articulationPoints', () => {
162158

163159
const articulationPointsSet = articulationPoints(graph);
164160

165-
expect(articulationPointsSet).toEqual([
166-
vertexF,
167-
vertexE,
168-
vertexC,
169-
vertexD,
170-
]);
161+
expect(articulationPointsSet.length).toBe(4);
162+
expect(articulationPointsSet[0].getKey()).toBe(vertexF.getKey());
163+
expect(articulationPointsSet[1].getKey()).toBe(vertexE.getKey());
164+
expect(articulationPointsSet[2].getKey()).toBe(vertexC.getKey());
165+
expect(articulationPointsSet[3].getKey()).toBe(vertexD.getKey());
171166
});
172167

173168
it('should find articulation points in yet another graph #1', () => {
@@ -194,10 +189,9 @@ describe('articulationPoints', () => {
194189

195190
const articulationPointsSet = articulationPoints(graph);
196191

197-
expect(articulationPointsSet).toEqual([
198-
vertexD,
199-
vertexC,
200-
]);
192+
expect(articulationPointsSet.length).toBe(2);
193+
expect(articulationPointsSet[0].getKey()).toBe(vertexD.getKey());
194+
expect(articulationPointsSet[1].getKey()).toBe(vertexC.getKey());
201195
});
202196

203197
it('should find articulation points in yet another graph #2', () => {
@@ -232,8 +226,7 @@ describe('articulationPoints', () => {
232226

233227
const articulationPointsSet = articulationPoints(graph);
234228

235-
expect(articulationPointsSet).toEqual([
236-
vertexC,
237-
]);
229+
expect(articulationPointsSet.length).toBe(1);
230+
expect(articulationPointsSet[0].getKey()).toBe(vertexC.getKey());
238231
});
239232
});

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

Lines changed: 36 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -7,11 +7,6 @@ class VisitMetadata {
77
constructor({ discoveryTime, lowDiscoveryTime }) {
88
this.discoveryTime = discoveryTime;
99
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-
1510
// We need this in order to check graph root node, whether it has two
1611
// disconnected children or not.
1712
this.independantChildrenCount = 0;
@@ -28,10 +23,10 @@ export default function articulationPoints(graph) {
2823
// Set of vertices we've already visited during DFS.
2924
const visitedSet = {};
3025

31-
// Set of articulation points found so far.
32-
const articulationPointsSet = [];
26+
// Set of articulation points.
27+
const articulationPointsSet = {};
3328

34-
// Time needed to get to the current vertex.
29+
// Time needed to discover to the current vertex.
3530
let discoveryTime = 0;
3631

3732
// Peek the start vertex for DFS traversal.
@@ -53,9 +48,6 @@ export default function articulationPoints(graph) {
5348
discoveryTime += 1;
5449

5550
if (previousVertex) {
56-
// Update child vertex information for previous vertex.
57-
visitedSet[previousVertex.getKey()].childVertex = currentVertex;
58-
5951
// Update children counter for previous vertex.
6052
visitedSet[previousVertex.getKey()].independantChildrenCount += 1;
6153
}
@@ -64,44 +56,43 @@ export default function articulationPoints(graph) {
6456
* @param {GraphVertex} currentVertex
6557
* @param {GraphVertex} previousVertex
6658
*/
67-
leaveVertex: ({ currentVertex }) => {
68-
// Detect whether current vertex is articulation point or not.
69-
// To do so we need to check two (OR) conditions:
59+
leaveVertex: ({ currentVertex, previousVertex }) => {
60+
if (previousVertex === null) {
61+
// Don't do anything for the root vertex if it is already current (not previous one)
62+
return;
63+
}
64+
65+
// Update the low time with the smallest time of adjacent vertices.
66+
// Get minimum low discovery time from all neighbors.
67+
/** @param {GraphVertex} neighbor */
68+
visitedSet[currentVertex.getKey()].lowDiscoveryTime = currentVertex.getNeighbors().reduce(
69+
(lowestDiscoveryTime, neighbor) => {
70+
const neighborLowTime = visitedSet[neighbor.getKey()].lowDiscoveryTime;
71+
return neighborLowTime < lowestDiscoveryTime ? neighborLowTime : lowestDiscoveryTime;
72+
},
73+
visitedSet[currentVertex.getKey()].lowDiscoveryTime,
74+
);
75+
76+
// Detect whether previous vertex is articulation point or not.
77+
// To do so we need to check two [OR] conditions:
7078
// 1. Is it a root vertex with at least two independent children.
7179
// 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()].independantChildrenCount >= 2) {
75-
articulationPointsSet.push(currentVertex);
80+
if (previousVertex === startVertex) {
81+
// Check that root vertex has at least two independent children.
82+
if (visitedSet[previousVertex.getKey()].independantChildrenCount >= 2) {
83+
articulationPointsSet[previousVertex.getKey()] = previousVertex;
7684
}
7785
} 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;
86+
// Get current vertex low discovery time.
87+
const currentLowDiscoveryTime = visitedSet[currentVertex.getKey()].lowDiscoveryTime;
88+
89+
// Compare current vertex low discovery time with parent discovery time. Check if there
90+
// are any short path (back edge) exists. If we can't get to current vertex other then
91+
// via parent then the parent vertex is articulation point for current one.
92+
const parentDiscoveryTime = visitedSet[previousVertex.getKey()].discoveryTime;
93+
if (parentDiscoveryTime <= currentLowDiscoveryTime) {
94+
articulationPointsSet[previousVertex.getKey()] = previousVertex;
8395
}
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-
);
10596
}
10697
},
10798
allowTraversal: ({ nextVertex }) => {
@@ -112,5 +103,5 @@ export default function articulationPoints(graph) {
112103
// Do Depth First Search traversal over submitted graph.
113104
depthFirstSearch(graph, startVertex, dfsCallbacks);
114105

115-
return articulationPointsSet;
106+
return Object.values(articulationPointsSet);
116107
}

0 commit comments

Comments
 (0)