Tarjan算法在C#中的环检测帮助

Question

以下是 tarjan's cycle detection 的 C# 实现代码。

该算法的详细说明可参考： http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

public class TarjanCycleDetect
    {
        private static List<List<Vertex>> StronglyConnectedComponents;
        private static Stack<Vertex> S;
        private static int index;
        private static DepGraph dg;
        public static List<List<Vertex>> DetectCycle(DepGraph g)
        {
            StronglyConnectedComponents = new List<List<Vertex>>();
            index = 0;
            S = new Stack<Vertex>();
            dg = g;
            foreach (Vertex v in g.vertices)
            {
                if (v.index < 0)
                {
                    strongconnect(v);
                }
            }
            return StronglyConnectedComponents;
        }

        private static void strongconnect(Vertex v)
        {
            v.index = index;
            v.lowlink = index;
            index++;
            S.Push(v);

            foreach (Vertex w in v.dependencies)
            {
                if (w.index < 0)
                {
                    strongconnect(w);
                    v.lowlink = Math.Min(v.lowlink, w.lowlink);
                }
                else if (S.Contains(w))
                {
                    v.lowlink = Math.Min(v.lowlink, w.index);
                }
            }

            if (v.lowlink == v.index)
            {
                List<Vertex> scc = new List<Vertex>();
                Vertex w;
                do
                {
                    w = S.Pop();
                    scc.Add(w);
                } while (v != w);
                StronglyConnectedComponents.Add(scc);
            }

        }

请注意，DepGraph只是Vertex列表。每个Vertex包含其他Vertex的列表，这些Vertex表示边缘关系。此外，索引和低链接初始化为-1。

编辑：这是有效的...我只是对结果进行了错误解释。

- user623879

---

为什么是 v.lowlink = Math.Min(v.lowlink, w.index) 而不是 v.lowlink = Math.Min(v.lowlink, w.lowlink)？ - Lin Ma

@LinMa 两种说法在技术上都是正确的。 - Eric Zhang

此算法不适用于字符串值。我需要找到项目及其依赖项之间的循环依赖关系，是否需要进行任何更改以使其运行？ - Jatin Dave

Answer 1

上述内容实际上是正确的，我之前并不了解什么是强连通分量。我本来期望这个函数返回一个空的强连通分量列表，但它却返回了一个由单个节点组成的列表。

我认为上述内容已经可用。如果需要，可以随意使用！

- user623879

---

问题：在构建传递到DetectCycle函数的DepGraph时，您不会遇到循环吗？似乎会遇到，如果确实如此，那么在那时您不是已经检测到了循环吗？ - Joe

你好，我发现上述内容很有用，但是没有找到其他可靠的解决方案，所以我将其放到 Github 上供其他人查看并做出贡献：https://github.com/danielrbradley/CycleDetection 希望这样做没问题！ - Daniel Bradley

确认可行。我做了一些不同的事情，因为我不想在顶点本身上强制产生副作用（实际上是通过顶点创建索引和低值字典），但这个方法非常有效。谢谢！ - user420667

Answer 2

上面提供的问题示例无法快速运行。此外，需要注意的是它是基于堆栈的，如果您提供的图不太简单，就会导致堆栈崩溃。下面是一个可以正常运行的示例，其中包含了一个模拟Tarjan维基百科页面上展示的图形的单元测试：

public class Vertex
{
    public int Id { get;set; }
    public int Index { get; set; }
    public int Lowlink { get; set; }

    public HashSet<Vertex> Dependencies { get; set; }

    public Vertex()
    {
        Id = -1;
        Index = -1;
        Lowlink = -1;
        Dependencies = new HashSet<Vertex>();
    }

    public override string ToString()
    {
        return string.Format("Vertex Id {0}", Id);
    }

    public override int GetHashCode()
    {
        return Id;
    }

    public override bool Equals(object obj)
    {
        if (obj == null)
            return false;

        Vertex other = obj as Vertex;

        if (other == null)
            return false;

        return Id == other.Id;
    }
}

public class TarjanCycleDetectStack
{
    protected List<List<Vertex>> _StronglyConnectedComponents;
    protected Stack<Vertex> _Stack;
    protected int _Index;

    public List<List<Vertex>> DetectCycle(List<Vertex> graph_nodes)
    {
        _StronglyConnectedComponents = new List<List<Vertex>>();

        _Index = 0;
        _Stack = new Stack<Vertex>();

        foreach (Vertex v in graph_nodes)
        {
            if (v.Index < 0)
            {
                StronglyConnect(v);
            }
        }

        return _StronglyConnectedComponents;
    }

    private void StronglyConnect(Vertex v)
    {
        v.Index = _Index;
        v.Lowlink = _Index;

        _Index++;
        _Stack.Push(v);

        foreach (Vertex w in v.Dependencies)
        {
            if (w.Index < 0)
            {
                StronglyConnect(w);
                v.Lowlink = Math.Min(v.Lowlink, w.Lowlink);
            }
            else if (_Stack.Contains(w))
            {
                v.Lowlink = Math.Min(v.Lowlink, w.Index);
            }
        }

        if (v.Lowlink == v.Index)
        {
            List<Vertex> cycle = new List<Vertex>();
            Vertex w;

            do
            {
                w = _Stack.Pop();
                cycle.Add(w);
            } while (v != w);

            _StronglyConnectedComponents.Add(cycle);
        }
    }
}

    [TestMethod()]
    public void TarjanStackTest()
    {
        // tests simple model presented on https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
        var graph_nodes = new List<Vertex>();

        var v1 = new Vertex() { Id = 1 };
        var v2 = new Vertex() { Id = 2 };
        var v3 = new Vertex() { Id = 3 };
        var v4 = new Vertex() { Id = 4 };
        var v5 = new Vertex() { Id = 5 };
        var v6 = new Vertex() { Id = 6 };
        var v7 = new Vertex() { Id = 7 };
        var v8 = new Vertex() { Id = 8 };

        v1.Dependencies.Add(v2);
        v2.Dependencies.Add(v3);
        v3.Dependencies.Add(v1);
        v4.Dependencies.Add(v3);
        v4.Dependencies.Add(v5);
        v5.Dependencies.Add(v4);
        v5.Dependencies.Add(v6);
        v6.Dependencies.Add(v3);
        v6.Dependencies.Add(v7);
        v7.Dependencies.Add(v6);
        v8.Dependencies.Add(v7);
        v8.Dependencies.Add(v5);
        v8.Dependencies.Add(v8);

        graph_nodes.Add(v1);
        graph_nodes.Add(v2);
        graph_nodes.Add(v3);
        graph_nodes.Add(v4);
        graph_nodes.Add(v5);
        graph_nodes.Add(v6);
        graph_nodes.Add(v7);
        graph_nodes.Add(v8);

        var tcd = new TarjanCycleDetectStack();
        var cycle_list = tcd.DetectCycle(graph_nodes);

        Assert.IsTrue(cycle_list.Count == 4);
    }

我给Vertex对象添加了一个Id属性，这样就可以轻松看到正在执行的操作，虽然这并不是必须的。我还稍微整理了一下代码，原作者使用了页面伪代码中的命名方式，这对比较很好，但并不是很具有信息性。

- Roger Hill

---

“Above” 是没有意义的，因为答案会随机排序。最好通过用户的名称或链接（来自“分享”）引用特定的答案。 - Mogsdad

我只添加了两个节点，第一个连接到另一个节点，结果是两个“循环”，每个节点都包含一次。这不应该是零个循环吗？编辑：没关系（“任何不在有向循环上的顶点都可以自成一个强连通分量：例如，入度或出度为0的顶点，或无环图的任何顶点。”） - Siderite Zackwehdex

我fork了@danielbradley的项目，并添加了Roger Hill的版本。谢谢大家。https://github.com/damiensawyer/CycleDetection - Damien Sawyer

哈！忘了吧，我刚才看了代码...它仍然使用一个栈。这是我的复制/粘贴错误！ - Damien Sawyer

Answer 3

从2008年开始，QuickGraph就支持了这个算法。请参见StronglyConnectedComponentsAlgorithm类的实现或AlgorithmExtensions.StronglyConnectedComponents方法的使用快捷方式。

示例：

// Initialize result dictionary
IDictionary<string, int> comps = new Dictionary<string, int>();

// Run the algorithm
graph.StronglyConnectedComponents(out comps);

// Group and filter the dictionary
var cycles = comps
    .GroupBy(x => x.Value, x => x.Key)
    .Where(x => x.Count() > 1)
    .Select(x => x.ToList())

- JohannesH