algorithms-and-data-structures/AlgorithmsAndDataStructures/Algorithms/Graph/Misc/TarjansAlgorithm.cs at master · arst/algorithms-and-data-structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
using System;
using System.Collections.Generic;
using System.Linq;
using AlgorithmsAndDataStructures.Algorithms.Graph.Common;

namespace AlgorithmsAndDataStructures.Algorithms.Graph.Misc;

public class TarjansAlgorithm
{
    private const int NullParent = -1;

#pragma warning disable CA1822 // Mark members as static
    public int[] GetArticulationPoints(UndirectedGraph graph)
#pragma warning restore CA1822 // Mark members as static
    {
        if (graph is null) return Array.Empty<int>();

        var vertices = graph.Vertices();

        if (vertices.Length == 0) return Array.Empty<int>();

        var visited = new bool[vertices.Length];
        var articulationPoints = new bool[vertices.Length];
        var parents = new int[vertices.Length];
        var discoveryTime = new int[vertices.Length];
        var lowestSubTreeDiscoveryTime = new int[vertices.Length];

        parents[0] = NullParent;

        DfsArticulationTraversal(vertices, 0, visited, articulationPoints, parents, discoveryTime,
            lowestSubTreeDiscoveryTime, 0);

        return vertices.Select((arg, index) => index).Where(arg => articulationPoints[arg]).ToArray();
    }

    private static void DfsArticulationTraversal(
        IReadOnlyList<List<int>> vertices,
        int currentVertex,
        IList<bool> visited,
        IList<bool> articulationPoints,
        IList<int> parents,
        IList<int> discoveryTime,
        IList<int> lowestSubTreeDiscoveryTime,
        int time)
    {
        visited[currentVertex] = true;
        var children = 0;
        var currentDiscoveryTime = time + 1;
        discoveryTime[currentVertex] = currentDiscoveryTime;
        lowestSubTreeDiscoveryTime[currentVertex] = currentDiscoveryTime;

        foreach (var adjacentVertex in vertices[currentVertex])
            if (!visited[adjacentVertex])
            {
                children++;
                parents[adjacentVertex] = currentVertex;
                DfsArticulationTraversal(
                    vertices,
                    adjacentVertex,
                    visited,
                    articulationPoints,
                    parents,
                    discoveryTime,
                    lowestSubTreeDiscoveryTime,
                    currentDiscoveryTime);

                lowestSubTreeDiscoveryTime[currentVertex] = Math.Min(lowestSubTreeDiscoveryTime[currentVertex],
                    lowestSubTreeDiscoveryTime[adjacentVertex]);

                if (parents[currentVertex] == NullParent && children > 1) articulationPoints[currentVertex] = true;
                if (parents[currentVertex] != NullParent &&
                    lowestSubTreeDiscoveryTime[adjacentVertex] >= discoveryTime[currentVertex])
                    articulationPoints[currentVertex] = true;
            }
            else if (adjacentVertex != parents[currentVertex])
            {
                lowestSubTreeDiscoveryTime[currentVertex] = Math.Min(lowestSubTreeDiscoveryTime[currentVertex],
                    discoveryTime[adjacentVertex]);
            }
    }
}