Ayuda de detección de ciclo de Tarjan C#

Question

Aquí hay una implementación de C# en funcionamiento de la detección de 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); 
      } 

     } 

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

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

Answer 1

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

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

Answer 2

A partir de 2008 quickgraph ha admitido este algoritmo. Consulte la clase StronglyConnectedComponentsAlgorithm para la implementación o el método AlgorithmExtensions.StronglyConnectedComponents para un acceso directo 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 3

Ejemplo presentado anteriormente en la pregunta no es funcional si alguien quiere jugar con él rápidamente. También tenga en cuenta que está basado en la pila, que detonará su pila si le da cualquier cosa menos los gráficos más triviales. Aquí está un ejemplo de trabajo con una unidad de prueba que los modelos de la gráfica presentada en la página de Wikipedia 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); 
    } 

He añadido una propiedad Id al objeto Vertex por lo que es fácil de ver lo que se está haciendo, ISN' 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.