isotonicq

Untitled

Feb 9th, 2018
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace akCyclesInUndirectedGraphs
  5. {
  6. class Program
  7. {
  8. // Graph modelled as list of edges
  9. static int[,] graph =
  10. {
  11. {1, 2}, {1, 3}, {1, 4}, {2, 3},
  12. {3, 4}, {2, 6}, {4, 6}, {7, 8},
  13. {8, 9}, {9, 7}
  14. };
  15.  
  16. static List<int[]> cycles = new List<int[]>();
  17.  
  18. static void Main(string[] args)
  19. {
  20. for (int i = 0; i < graph.GetLength(0); i++)
  21. for (int j = 0; j < graph.GetLength(1); j++)
  22. {
  23. findNewCycles(new int[] {graph[i, j]});
  24. }
  25.  
  26. foreach (int[] cy in cycles)
  27. {
  28. string s = "" + cy[0];
  29.  
  30. for (int i = 1; i < cy.Length; i++)
  31. s += "," + cy[i];
  32.  
  33. Console.WriteLine(s);
  34. }
  35. }
  36.  
  37. static void findNewCycles(int[] path)
  38. {
  39. int n = path[0];
  40. int x;
  41. int[] sub = new int[path.Length + 1];
  42.  
  43. for (int i = 0; i < graph.GetLength(0); i++)
  44. for (int y = 0; y <= 1; y++)
  45. if (graph[i, y] == n)
  46. // edge referes to our current node
  47. {
  48. x = graph[i, (y + 1) % 2];
  49. if (!visited(x, path))
  50. // neighbor node not on path yet
  51. {
  52. sub[0] = x;
  53. Array.Copy(path, 0, sub, 1, path.Length);
  54. // explore extended path
  55. findNewCycles(sub);
  56. }
  57. else if ((path.Length > 2) && (x == path[path.Length - 1]))
  58. // cycle found
  59. {
  60. int[] p = normalize(path);
  61. int[] inv = invert(p);
  62. if (isNew(p) && isNew(inv))
  63. cycles.Add(p);
  64. }
  65. }
  66. }
  67.  
  68. static bool equals(int[] a, int[] b)
  69. {
  70. bool ret = (a[0] == b[0]) && (a.Length == b.Length);
  71.  
  72. for (int i = 1; ret && (i < a.Length); i++)
  73. if (a[i] != b[i])
  74. {
  75. ret = false;
  76. }
  77.  
  78. return ret;
  79. }
  80.  
  81. static int[] invert(int[] path)
  82. {
  83. int[] p = new int[path.Length];
  84.  
  85. for (int i = 0; i < path.Length; i++)
  86. p[i] = path[path.Length - 1 - i];
  87.  
  88. return normalize(p);
  89. }
  90.  
  91. // rotate cycle path such that it begins with the smallest node
  92. static int[] normalize(int[] path)
  93. {
  94. int[] p = new int[path.Length];
  95. int x = smallest(path);
  96. int n;
  97.  
  98. Array.Copy(path, 0, p, 0, path.Length);
  99.  
  100. while (p[0] != x)
  101. {
  102. n = p[0];
  103. Array.Copy(p, 1, p, 0, p.Length - 1);
  104. p[p.Length - 1] = n;
  105. }
  106.  
  107. return p;
  108. }
  109.  
  110. static bool isNew(int[] path)
  111. {
  112. bool ret = true;
  113.  
  114. foreach(int[] p in cycles)
  115. if (equals(p, path))
  116. {
  117. ret = false;
  118. break;
  119. }
  120.  
  121. return ret;
  122. }
  123.  
  124. static int smallest(int[] path)
  125. {
  126. int min = path[0];
  127.  
  128. foreach (int p in path)
  129. if (p < min)
  130. min = p;
  131.  
  132. return min;
  133. }
  134.  
  135. static bool visited(int n, int[] path)
  136. {
  137. bool ret = false;
  138.  
  139. foreach (int p in path)
  140. if (p == n)
  141. {
  142. ret = true;
  143. break;
  144. }
  145.  
  146. return ret;
  147. }
  148. }
  149. }
RAW Paste Data