Tarjan-Zykluserkennung hilft C #

Hier ist eine C# - Implementierung von tarjan Zyklus-Erkennung.

Der Algorithmus ist hier zu finden:
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);
            }

        }

Hinweis: eine DepGraph ist nur eine Liste von Vertex. und der Scheitelpunkt hat eine Liste von anderen Vertex repräsentieren die Kanten. Auch index-und lowlink initialisiert werden -1

EDIT: Das funktioniert...ich habe nur falsch interpretiert die Ergebnisse.

InformationsquelleAutor der Frage user623879 | 2011-07-10

algorithm c#cycle directed-graph tarjans-algorithm

9

Oben ist tatsächlich korrekt, habe ich nicht verstanden, was eine starke zusammenhangskomponente war. Ich hatte erwartet die Funktion eine leere Liste zurück von starken zusammenhangskomponenten, doch es wurde wieder eine Liste der einzelnen Knoten.

Glaube ich, dass die oben genannten arbeiten. Fühlen Sie sich frei zu verwenden, wenn Sie es brauchen!

InformationsquelleAutor der Antwort user623879

2008 quickgraph unterstützt dieses Algorithmus. Finden Sie die StronglyConnectedComponentsAlgorithm - Klasse für die Implementierung, oder AlgorithmExtensions.StronglyConnectedComponents Methode für eine Nutzung Verknüpfung.

Beispiel:

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

InformationsquelleAutor der Antwort JohannesH

Oben dargestellten Beispiel in der Frage nicht funktionsfähig ist, sollte jemand wollen, um schnell zu spielen. Beachten Sie auch, dass es ist stack-basiert, das wird explodieren und dein stack, wenn Sie alles geben, aber der trivialste von Graphen. Hier ist ein funktionierendes Beispiel mit einem unit-test, dass die Modelle die Grafik präsentiert auf der Tarjan wikipedia-Seite:

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);
    }

Ich habe eine Id-Eigenschaft, um die Vertex-Objekt, so ist es einfach zu sehen, was getan wird, es ist nicht unbedingt erforderlich. Ich auch gereinigt einige der code ein wenig, die Autorin war mit der Benennung von Seite pseudo-code, das ist gut für den Vergleich, aber es war nicht sehr informativ.

InformationsquelleAutor der Antwort Roger Hill

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.