查找无向图中的所有循环

我需要一个工作algorithm来查找无向图中的所有简单循环。 我知道成本可以是指数的，问题是NP完全的，但是我打算在一个小的图中使用它（最多20-30个顶点），而且这个循环的数量是很less的。

经过长期的研究（主要是在这里），我还没有一个工作的方法。 这里是我的search的总结：

在无向图中find所有的周期

无向图中的循环 – >仅检测是否存在循环

在无向图中find多边形 – >非常好的描述，但没有解决scheme

在有向图中查找所有循环 – >仅在有向图中查找循环

使用boost图库检测无向图中的周期

我发现的唯一答案就是这个：

查找graphics中的所有循环，还原

看起来，find一组基本的循环和异或它们可以做到这一点。 find一个基本的循环集很容易，但我不明白如何将它们结合起来，以获得图中的所有循环…

Answer 1

对于无向图而言，标准方法是寻找所谓的循环基础：一组简单循环，可以通过组合所有其他循环生成一组简单循环。 这些并不一定是图中所有的简单循环。 考虑以下图表为例：

A / \ B ----- C \ / D 

这里有3个简单的周期：ABCA，BCDB和ABDCA。 但是，您可以将其中的每一个作为基础，并获得3d作为2的组合。这是与有向图无法自由组合的实质性差异，因为需要观察边的方向。

寻找无向图的循环基的标准基线algorithm是这样的：构build一棵生成树，然后为每个不是树的一部分的边创build一个从该边和树的一些边的循环。 这样的循环必须存在，否则边缘将是树的一部分。

对于上面的示例图，一棵生成树就是这样的：

  A / \ BC \ D 

不在树上的两条边是BC和CD。 而相应的简单周期是ABCA和ABDCA。

您也可以构build以下生成树：

  A / B ----- C \ D 

然后你得到的简单周期是ABCA和BCDB。

基线algorithm可以以不同的方式进行改进。 就我所知，最好的改进属于Paton（K.Paton，An algorithm for finding a fundamental set of cycles for an undirected linear graph，Comm.ACM 12（1969），第514-518页）。 Java中的开源实现可以在这里find： http ： //code.google.com/p/niographs/ 。

我应该提到如何将循环库中的简单循环结合起来，形成新的简单循环。 你可以在任何（但是固定的）后面列出图表的所有边。 然后，通过在属于循环的边的位置上放置一个零，并且在不是该循环的一部分的边的位置上放置零来表示循环。 然后你做序列的按位异或（XOR）。 您进行XOR的原因是您想要排除属于两个循环的边，从而使联合循环非简单。 您还需要通过检查序列的按位AND不全为零来检查2个周期是否有一些共同的边沿。 否则XOR的结果将是2个不相交的循环，而不是一个新的简单循环。

以上是上述示例图的示例：

（AB），（AC），（BC），（BD），（CD））。 然后简单循环ABCA，BDCB和ABDCA分别表示为（1,1,1,0,0），（0,0,1,1,1）和（1,1,0,1,1）。 现在我们可以例如XOR ABCA与BDCB，结果是（1,1,0,1,1），这正是ABDCA。 或者我们可以将ABCA和ABDCA进行异或运算（0,0,1,1,1）。 这正是BDCB。

给定循环基数，您可以通过检查2个或更多个不同基本循环的所有可能组合来发现所有简单循环。 此处详细介绍了此过程： http ： //dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf （第14页）。

为了完整性，我会注意到使用algorithm来查找有向图的所有简单循环似乎是可能的（并且效率低下）。 无向图的每一条边都可以被两条相反方向的边所取代。 然后有向图的algorithm应该可以工作。 对于无向图的每条边将有1个“假”2节点循环，这将不得不被忽略，并且无向图的每个简单循环将有顺时针和逆时针版本。 用JAVA开发的用于查找有向图中的所有循环的algorithm的实现可以在我已经引用的链接中find。

Answer 2

以下是基于深度优先search的C＃（和Java，请参阅答案的结尾）的演示实现。

外循环扫描图的所有节点，并从每个节点开始search。 节点邻居（根据边缘列表）被添加到循环path。 recursion如果没有更多的未被访问的邻居可以被添加结束。 如果path长于两个节点，并且下一个邻居是path的开始，则find新的周期。 为了避免重复的循环，通过将最小节点旋转到开始来对循环进行归一化。 倒序排列的循环也被考虑在内。

这只是一个天真的实现。 古典文章是：唐纳德B.约翰逊。 查找有向图的所有基本电路。 SIAM J. Comput。，4（1）：77-84,1975。

最近对现代algorithm的调查可以在这里find

 using System; using System.Collections.Generic; namespace akCyclesInUndirectedGraphs { class Program { // Graph modelled as list of edges static int[,] graph = { {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}, {2, 6}, {4, 6}, {7, 8}, {8, 9}, {9, 7} }; static List<int[]> cycles = new List<int[]>(); static void Main(string[] args) { for (int i = 0; i < graph.GetLength(0); i++) for (int j = 0; j < graph.GetLength(1); j++) { findNewCycles(new int[] {graph[i, j]}); } 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 n = path[0]; int x; int[] sub = new int[path.Length + 1]; for (int i = 0; i < graph.GetLength(0); i++) for (int y = 0; y <= 1; y++) 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); } 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; } } } 

演示图的周期：

 1,3,2 1,4,3,2 1,4,6,2 1,3,4,6,2 1,4,6,2,3 1,4,3 2,6,4,3 7,9,8 

用Java编码的algorithm：

 import java.util.ArrayList; import java.util.List; public class GraphCycleFinder { // Graph modeled as list of edges static int[][] graph = { {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}, {2, 6}, {4, 6}, {7, 8}, {8, 9}, {9, 7} }; static List<int[]> cycles = new ArrayList<int[]>(); /** * @param args */ public static void main(String[] args) { for (int i = 0; i < graph.length; i++) for (int j = 0; j < graph[i].length; j++) { findNewCycles(new int[] {graph[i][j]}); } for (int[] cy : cycles) { String s = "" + cy[0]; for (int i = 1; i < cy.length; i++) { s += "," + cy[i]; } o(s); } } static void findNewCycles(int[] path) { int n = path[0]; int x; int[] sub = new int[path.length + 1]; for (int i = 0; i < graph.length; i++) for (int y = 0; y <= 1; y++) if (graph[i][y] == n) // edge refers to our current node { x = graph[i][(y + 1) % 2]; if (!visited(x, path)) // neighbor node not on path yet { sub[0] = x; System.arraycopy(path, 0, sub, 1, path.length); // explore extended path findNewCycles(sub); } 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); } } } } // check of both arrays have same lengths and contents static Boolean equals(int[] a, int[] b) { Boolean 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; } // create a path array with reversed order 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; System.arraycopy(path, 0, p, 0, path.length); while (p[0] != x) { n = p[0]; System.arraycopy(p, 1, p, 0, p.length - 1); p[p.length - 1] = n; } return p; } // compare path against known cycles // return true, iff path is not a known cycle static Boolean isNew(int[] path) { Boolean ret = true; for(int[] p : cycles) { if (equals(p, path)) { ret = false; break; } } return ret; } static void o(String s) { System.out.println(s); } // return the int of the array which is the smallest static int smallest(int[] path) { int min = path[0]; for (int p : path) { if (p < min) { min = p; } } return min; } // check if vertex n is contained in path static Boolean visited(int n, int[] path) { Boolean ret = false; for (int p : path) { if (p == n) { ret = true; break; } } return ret; } } 

Answer 3

Axel，我把你的代码翻译成了python。 大约四分之一的代码行和更清晰的阅读。

 graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]] cycles = [] def main(): global graph global cycles for edge in graph: for node in edge: findNewCycles([node]) for cy in cycles: path = [str(node) for node in cy] s = ",".join(path) print(s) def findNewCycles(path): start_node = path[0] next_node= None sub = [] #visit each edge and each node of each edge for edge in graph: node1, node2 = edge if start_node in edge: if node1 == start_node: next_node = node2 else: next_node = node1 if not visited(next_node, path): # neighbor node not on path yet sub = [next_node] sub.extend(path) # explore extended path findNewCycles(sub); elif len(path) > 2 and next_node == path[-1]: # cycle found p = rotate_to_smallest(path); inv = invert(p) if isNew(p) and isNew(inv): cycles.append(p) def invert(path): return rotate_to_smallest(path[::-1]) # rotate cycle path such that it begins with the smallest node def rotate_to_smallest(path): n = path.index(min(path)) return path[n:]+path[:n] def isNew(path): return not path in cycles def visited(node, path): return node in path main() 

Answer 4

这里只是一个非常蹩脚的MATLAB版本的algorithm，从上面的python代码改编，任何人也可能需要它。

 function cycleList = searchCycles(edgeMap) tic global graph cycles numCycles; graph = edgeMap; numCycles = 0; cycles = {}; for i = 1:size(graph,1) for j = 1:2 findNewCycles(graph(i,j)) end end % print out all found cycles for i = 1:size(cycles,2) cycles{i} end % return the result cycleList = cycles; toc function findNewCycles(path) global graph cycles numCycles; startNode = path(1); nextNode = nan; sub = []; % visit each edge and each node of each edge for i = 1:size(graph,1) node1 = graph(i,1); node2 = graph(i,2); if node1 == startNode nextNode = node2; elseif node2 == startNode nextNode = node1; end if ~(visited(nextNode, path)) % neighbor node not on path yet sub = nextNode; sub = [sub path]; % explore extended path findNewCycles(sub); elseif size(path,2) > 2 && nextNode == path(end) % cycle found p = rotate_to_smallest(path); inv = invert(p); if isNew(p) && isNew(inv) numCycles = numCycles + 1; cycles{numCycles} = p; end end end function inv = invert(path) inv = rotate_to_smallest(path(end:-1:1)); % rotate cycle path such that it begins with the smallest node function new_path = rotate_to_smallest(path) [~,n] = min(path); new_path = [path(n:end), path(1:n-1)]; function result = isNew(path) global cycles result = 1; for i = 1:size(cycles,2) if size(path,2) == size(cycles{i},2) && all(path == cycles{i}) result = 0; break; end end function result = visited(node,path) result = 0; if isnan(node) && any(isnan(path)) result = 1; return end for i = 1:size(path,2) if node == path(i) result = 1; break end end 

Answer 5

这里是上面的python代码的C ++版本：

 std::vector< std::vector<vertex_t> > Graph::findAllCycles() { std::vector< std::vector<vertex_t> > cycles; std::function<void(std::vector<vertex_t>)> findNewCycles = [&]( std::vector<vertex_t> sub_path ) { auto visisted = []( vertex_t v, const std::vector<vertex_t> & path ){ return std::find(path.begin(),path.end(),v) != path.end(); }; auto rotate_to_smallest = []( std::vector<vertex_t> path ){ std::rotate(path.begin(), std::min_element(path.begin(), path.end()), path.end()); return path; }; auto invert = [&]( std::vector<vertex_t> path ){ std::reverse(path.begin(),path.end()); return rotate_to_smallest(path); }; auto isNew = [&cycles]( const std::vector<vertex_t> & path ){ return std::find(cycles.begin(), cycles.end(), path) == cycles.end(); }; vertex_t start_node = sub_path[0]; vertex_t next_node; // visit each edge and each node of each edge for(auto edge : edges) { if( edge.has(start_node) ) { vertex_t node1 = edge.v1, node2 = edge.v2; if(node1 == start_node) next_node = node2; else next_node = node1; if( !visisted(next_node, sub_path) ) { // neighbor node not on path yet std::vector<vertex_t> sub; sub.push_back(next_node); sub.insert(sub.end(), sub_path.begin(), sub_path.end()); findNewCycles( sub ); } else if( sub_path.size() > 2 && next_node == sub_path.back() ) { // cycle found auto p = rotate_to_smallest(sub_path); auto inv = invert(p); if( isNew(p) && isNew(inv) ) cycles.push_back( p ); } } } }; for(auto edge : edges) { findNewCycles( std::vector<vertex_t>(1,edge.v1) ); findNewCycles( std::vector<vertex_t>(1,edge.v2) ); } } 

Answer 6

这里是上面的Python代码的vb.net版本：

 Module Module1 ' Graph modelled as list of edges Public graph As Integer(,) = {{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}, {2, 6}, {4, 6}, {7, 8}, {8, 9}, {9, 7}} Public cycles As New List(Of Integer())() Sub Main() For i As Integer = 0 To graph.GetLength(0) - 1 For j As Integer = 0 To graph.GetLength(1) - 1 findNewCycles(New Integer() {graph(i, j)}) Next Next For Each cy As Integer() In cycles Dim s As String s = cy(0) For i As Integer = 1 To cy.Length - 1 s = s & "," & cy(i) Next Console.WriteLine(s) Debug.Print(s) Next End Sub Private Sub findNewCycles(path As Integer()) Dim n As Integer = path(0) Dim x As Integer Dim [sub] As Integer() = New Integer(path.Length) {} For i As Integer = 0 To graph.GetLength(0) - 1 For y As Integer = 0 To 1 If graph(i, y) = n Then ' edge referes to our current node x = graph(i, (y + 1) Mod 2) If Not visited(x, path) Then ' neighbor node not on path yet [sub](0) = x Array.Copy(path, 0, [sub], 1, path.Length) ' explore extended path findNewCycles([sub]) ElseIf (path.Length > 2) AndAlso (x = path(path.Length - 1)) Then ' cycle found Dim p As Integer() = normalize(path) Dim inv As Integer() = invert(p) If isNew(p) AndAlso isNew(inv) Then cycles.Add(p) End If End If End If Next Next End Sub Private Function equals(a As Integer(), b As Integer()) As Boolean Dim ret As Boolean = (a(0) = b(0)) AndAlso (a.Length = b.Length) Dim i As Integer = 1 While ret AndAlso (i < a.Length) If a(i) <> b(i) Then ret = False End If i += 1 End While Return ret End Function Private Function invert(path As Integer()) As Integer() Dim p As Integer() = New Integer(path.Length - 1) {} For i As Integer = 0 To path.Length - 1 p(i) = path(path.Length - 1 - i) Next Return normalize(p) End Function ' rotate cycle path such that it begins with the smallest node Private Function normalize(path As Integer()) As Integer() Dim p As Integer() = New Integer(path.Length - 1) {} Dim x As Integer = smallest(path) Dim n As Integer 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 End While Return p End Function Private Function isNew(path As Integer()) As Boolean Dim ret As Boolean = True For Each p As Integer() In cycles If equals(p, path) Then ret = False Exit For End If Next Return ret End Function Private Function smallest(path As Integer()) As Integer Dim min As Integer = path(0) For Each p As Integer In path If p < min Then min = p End If Next Return min End Function Private Function visited(n As Integer, path As Integer()) As Boolean Dim ret As Boolean = False For Each p As Integer In path If p = n Then ret = True Exit For End If Next Return ret End Function 

结束模块

Answer 7

看起来上面的循环查找器有一些问题。 C＃版本无法find一些周期。 我的图是：

  {2,8},{4,8},{5,8},{1,9},{3,9},{4,9},{5,9},{6,9},{1,10}, {4,10},{5,10},{6,10},{7,10},{1,11},{4,11},{6,11},{7,11}, {1,12},{2,12},{3,12},{5,12},{6,12},{2,13},{3,13},{4,13}, {6,13},{7,13},{2,14},{5,14},{7,14} 

例如，找不到周期： 1-9-3-12-5-10 。 我也尝试过C ++版本，它会返回非常大（数千万）的循环次数，这显然是错误的。 可能它不符合周期。

对不起，我有点紧张，我没有进一步调查。 我根据Nikolay Ognyanov的post编写了我自己的版本（非常感谢你的文章）。 对于上面的图表我的版本返回8833周期，我试图validation它是正确的。 C＃版本返回8397个周期。

Answer 8

Matlab版本遗漏了一些东西，函数findNewCycles（path）应该是：

函数findNewCycles（path）

 global graph cycles numCycles; startNode = path(1); nextNode = nan; sub = []; % visit each edge and each node of each edge for i = 1:size(graph,1) node1 = graph(i,1); node2 = graph(i,2); if (node1 == startNode) || (node2==startNode) %% this if is required if node1 == startNode nextNode = node2; elseif node2 == startNode nextNode = node1; end if ~(visited(nextNode, path)) % neighbor node not on path yet sub = nextNode; sub = [sub path]; % explore extended path findNewCycles(sub); elseif size(path,2) > 2 && nextNode == path(end) % cycle found p = rotate_to_smallest(path); inv = invert(p); if isNew(p) && isNew(inv) numCycles = numCycles + 1; cycles{numCycles} = p; end end end end