Advertisement
mikymaione

CFC

Feb 20th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 3.56 KB | None | 0 0
  1.  
  2.         /// <summary>
  3.         /// Kosaraju's strongly connected components algorithm
  4.         /// </summary>
  5.         public void Kosaraju()
  6.         {
  7.             var L = new HashSet<Nodo>();
  8.  
  9.             Action<Nodo> Visit = null;
  10.             Visit = (u) =>
  11.             {
  12.                 // If u is unvisited then:
  13.                 if (u.color == Nodo.Color.White)
  14.                 {
  15.                     // Mark u as visited.
  16.                     u.color = Nodo.Color.Gray;
  17.  
  18.                     // For each out-neighbour v of u, do Visit(v).
  19.                     foreach (var v in Adj[u])
  20.                         Visit(v);
  21.  
  22.                     // Prepend u to L
  23.                     L.Add(u);
  24.                 }
  25.             };
  26.  
  27.             Action<Nodo, Nodo> Assign = null;
  28.             Assign = (u, root) =>
  29.             {
  30.                 // If u has not been assigned to a component then
  31.                 if (u.color != Nodo.Color.Black)
  32.                 {
  33.                     // Assign u as belonging to the component whose root is root.
  34.                     if (u == root)
  35.                         Console.Write("SCC: ");
  36.  
  37.                     Console.Write(u.N + " ");
  38.                     u.color = Nodo.Color.Black;
  39.  
  40.                     // For each in-neighbour v of u, do Assign(v,root).
  41.                     foreach (var v in Adj[u])
  42.                         Assign(v, root);
  43.  
  44.                     if (u == root)
  45.                         Console.WriteLine();
  46.                 }
  47.             };
  48.  
  49.             // For each vertex u of the graph do Visit(u)
  50.             foreach (var u in V)
  51.                 Visit(u);
  52.  
  53.             // For each element u of L in order, do Assign(u,u)
  54.             foreach (var u in L)
  55.                 Assign(u, u);
  56.         }
  57.  
  58.         /// <summary>
  59.         /// Tarjan's strongly connected components algorithm, Time: O(|V|+|E|)
  60.         /// </summary>
  61.         public void Tarjan()
  62.         {
  63.             Console.WriteLine($"Tarjan su {Nome}");
  64.             var indice = 0; // number of nodes
  65.             var S = new Stack<Nodo>();
  66.  
  67.             Action<Nodo> StrongConnect = null;
  68.             StrongConnect = (v) =>
  69.             {
  70.                 // Set the depth index for v to the smallest unused index
  71.                 v.indice = indice;
  72.                 v.minima_distanza = indice;
  73.  
  74.                 indice++;
  75.                 S.Push(v);
  76.  
  77.                 // Consider successors of v
  78.                 foreach (var w in Adj[v])
  79.                     if (w.indice < 0)
  80.                     {
  81.                         // Successor w has not yet been visited; recurse on it
  82.                         StrongConnect(w);
  83.                         v.minima_distanza = Math.Min(v.minima_distanza, w.minima_distanza);
  84.                     }
  85.                     else if (S.Contains(w))
  86.                         // Successor w is in stack S and hence in the current SCC
  87.                         v.minima_distanza = Math.Min(v.minima_distanza, w.indice);
  88.  
  89.                 // If v is a root node, pop the stack and generate an SCC
  90.                 if (v.minima_distanza == v.indice)
  91.                 {
  92.                     Console.Write("SCC: ");
  93.  
  94.                     Nodo w = null;
  95.                     while (v != w && S.Count > 0)
  96.                     {
  97.                         w = S.Pop();
  98.                         Console.Write(w.N + " ");
  99.                     }
  100.  
  101.                     Console.WriteLine();
  102.                 }
  103.             };
  104.  
  105.             foreach (var v in V)
  106.                 if (v.indice < 0)
  107.                     StrongConnect(v);
  108.         }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement