查找所有周期的長度的有向圖<= K

Question

是否有對矯正在

Finding all cycles in undirected graphs

該算法考慮邊緣作爲長度< = k的定向和僅循環的方法是什麼？

Answer 1

我自己回答

static void Main(string[] args) 
    { 
     int k = 4; 
     for (int i = 0; i < graph.GetLength(0); i++) 
      for (int j = 0; j < graph.GetLength(1); j++) 
      { 
       findNewCycles(new int[] { graph[i, j] },k); 
      } 

     foreach (int[] cy in cycles) 
     { 
      string s = "" + cy[0]; 

      for (int i = 1; i < cy.Length; i++) 
       s += "," + cy[i]; 

      Console.WriteLine(s); 
     } 
    } 

    static void findNewCycles(int[] path, int k) 
    { 
     int n = path[0]; 
     int x; 
     int[] sub = new int[path.Length + 1]; 

     if (path.Length < k + 1) 
     { 

      for (int i = 0; i < graph.GetLength(0); i++) 
       for (int y = 0; y <= 1; y = y + 2) 
        if (graph[i, y] == n) 
        // edge referes to our current node 
        { 
         x = graph[i, (y + 1) % 2]; 
         if (!visited(x, path)) 
         // neighbor node not on path yet 
         { 
          sub[0] = x; 
          Array.Copy(path, 0, sub, 1, path.Length); 
          // explore extended path 
          findNewCycles(sub,k); 
         } 
         else if ((path.Length > 2) && (x == path[path.Length - 1])) 
         // cycle found 
         { 
          int[] p = normalize(path); 
          int[] inv = invert(p); 
          if (isNew(p) && isNew(inv)) 
           cycles.Add(p); 
         } 
        } 
     } 


    } 

    static bool equals(int[] a, int[] b) 
    { 
     bool ret = (a[0] == b[0]) && (a.Length == b.Length); 

     for (int i = 1; ret && (i < a.Length); i++) 
      if (a[i] != b[i]) 
      { 
       ret = false; 
      } 

     return ret; 
    } 

    static int[] invert(int[] path) 
    { 
     int[] p = new int[path.Length]; 

     for (int i = 0; i < path.Length; i++) 
      p[i] = path[path.Length - 1 - i]; 

     return normalize(p); 
    } 

    // rotate cycle path such that it begins with the smallest node 
    static int[] normalize(int[] path) 
    { 
     int[] p = new int[path.Length]; 
     int x = smallest(path); 
     int n; 

     Array.Copy(path, 0, p, 0, path.Length); 

     while (p[0] != x) 
     { 
      n = p[0]; 
      Array.Copy(p, 1, p, 0, p.Length - 1); 
      p[p.Length - 1] = n; 
     } 

     return p; 
    } 

    static bool isNew(int[] path) 
    { 
     bool ret = true; 

     foreach (int[] p in cycles) 
      if (equals(p, path)) 
      { 
       ret = false; 
       break; 
      } 

     return ret; 
    } 

    static int smallest(int[] path) 
    { 
     int min = path[0]; 

     foreach (int p in path) 
      if (p < min) 
       min = p; 

     return min; 
    } 

    static bool visited(int n, int[] path) 
    { 
     bool ret = false; 

     foreach (int p in path) 
      if (p == n) 
      { 
       ret = true; 
       break; 
      } 

     return ret; 
    } 
}