Advertisement
mikymaione

Path-based strongly connected components algorithm

Feb 7th, 2017
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.99 KB | None | 0 0
  1.  
  2.         /// <summary>
  3.         /// Path-based strongly connected components algorithm
  4.         /// </summary>
  5.         public void Path_based_SCC()
  6.         {
  7.             Func<Queue<Nodo>, Queue<Nodo>> SCC_DFS = null;
  8.             SCC_DFS = (H) =>
  9.             {
  10.                 var tempo = 0;
  11.                 Sbianca();
  12.  
  13.                 Action<Nodo, Queue<Nodo>> SCCC_Visita = null;
  14.                 SCCC_Visita = (u, Z) =>
  15.                 {
  16.                     tempo++;
  17.                     u.d = tempo;
  18.                     u.colore = Nodo.Colori.Grigio;
  19.  
  20.                     foreach (var v in Adj[u])
  21.                         if (v.colore == Nodo.Colori.Bianco)
  22.                         {
  23.                             v.Pred = u;
  24.  
  25.                             if (Z == null)
  26.                                 Console.Write(v.N + " ");
  27.  
  28.                             SCCC_Visita(v, Z);
  29.                         }
  30.  
  31.                     tempo++;
  32.                     u.f = tempo;
  33.                     u.colore = Nodo.Colori.Nero;
  34.  
  35.                     if (Z != null)
  36.                         Z.Enqueue(u);
  37.                 };
  38.  
  39.                 if (H == null)
  40.                 {
  41.                     var L = new Queue<Nodo>();
  42.  
  43.                     foreach (var v in V)
  44.                         if (v.colore == Nodo.Colori.Bianco)
  45.                             SCCC_Visita(v, L);
  46.  
  47.                     return L;
  48.                 }
  49.                 else
  50.                 {
  51.                     while (H.Count > 0)
  52.                     {
  53.                         var u = H.Dequeue();
  54.                         if (u.colore == Nodo.Colori.Bianco)
  55.                         {
  56.                             Console.Write("SCC: ");
  57.                             SCCC_Visita(u, null);
  58.                             Console.WriteLine(u.N + " ");
  59.                         }
  60.                     }
  61.  
  62.                     return null;
  63.                 }                
  64.             };
  65.  
  66.             SCC_DFS(SCC_DFS(null));
  67.         }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement