c# - strongly - tarjan algorithm c++

La detección del ciclo Tarjan ayuda a C#

Question

Aquí hay una implementación en C # de la detección del ciclo de Tarjan.

El algoritmo se encuentra aquí: 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);
            }

        }

Tenga en cuenta que un DepGraph es sólo una lista de vértices. y Vertex tiene una lista de otros vértices que representan los bordes. También el índice y el enlace bajo se inicializan a -1

EDITAR: Esto está funcionando ... Acabo de malinterpretar los resultados.

Answer 1

A partir de 2008, Quickgraph ha soportado este algoritmo. Consulte la clase StronglyConnectedComponentsAlgorithm para la implementación, o AlgorithmExtensions.StronglyConnectedComponents para un método abreviado de uso.

Ejemplo:

// 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())

Answer 2

El ejemplo presentado anteriormente en cuestión no es funcional si alguien quiere jugar rápidamente con él. También tenga en cuenta que está basado en la pila, lo que detonará su pila si proporciona algo más que los gráficos más triviales. Este es un ejemplo práctico con una prueba unitaria que modela el gráfico presentado en la página de wikipedia de 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);
    }

Agregué una propiedad de identificación al objeto Vertex para que sea simple ver lo que se está haciendo, no es estrictamente necesario. También limpié un poco el código, el autor usaba el nombre del pseudocódigo de la página, lo cual es bueno para comparar, pero no fue muy informativo.

Answer 3

Lo anterior es realmente correcto, no entendí qué era un componente fuertemente conectado. Esperaba que la función devolviera una lista vacía de componentes fuertemente conectados, pero estaba devolviendo una lista de nodos individuales.

Creo que lo anterior está funcionando. Siéntase libre de usar si lo necesita!