具有多边的有向图的循环枚举

如何在多边有向图中找到所有cyles ？

图示例1：

周期：

 1-2-6
 1-2-3-4
 1-2-3-4-5-6
 1-2-6-5-3-4
 3-4-5
 5-6

图示例2（多边4/5）：

周期：

 1-2-3
 1-4
 1-5

笔记：

我不想检测一个循环 （布尔结果），我想列出所有循环 。

任何强连接组件算法都不足以解决我的问题（在两个示例中都只找到一个组件）。

我在C＃中使用QuickGraph实现，但我很高兴看到任何语言的算法。

Answer 1

我很开心这个问题，谢谢！ ：P

我有一个C＃的解决方案。 找到周期的算法非常短（~10行），但周围有很多杂乱（例如Node和Edge类的实现）。

我使用了变量命名约定，字母“e”表示边缘，字母“a”表示边缘开始的节点，“b”表示链接到的节点。 使用这些约定，这是算法 ：

 public static IEnumerable FindAllCycles() { HashSet alreadyVisited = new HashSet(); alreadyVisited.Add(Node.AllNodes[0]); return FindAllCycles(alreadyVisited, Node.AllNodes[0]); } private static IEnumerable FindAllCycles(HashSet alreadyVisited, Node a) { for (int i = 0; i < a.Edges.Count; i++) { Edge e = a.Edges[i]; if (alreadyVisited.Contains(eB)) { yield return new Cycle(e); } else { HashSet newSet = i == a.Edges.Count - 1 ? alreadyVisited : new HashSet(alreadyVisited); newSet.Add(eB); foreach (Cycle c in FindAllCycles(newSet, eB)) { c.Build(e); yield return c; } } } } 

它有一个优化来重用一些Hashsets，这可能会令人困惑。 我已经包含了以下代码，它产生完全相同的结果，但是这个实现没有优化 ，所以你可以更容易地弄清楚它是如何工作的。

 private static IEnumerable FindAllCyclesUnoptimized(HashSet alreadyVisited, Node a) { foreach (Edge e in a.Edges) if (alreadyVisited.Contains(eB)) yield return new Cycle(e); else { HashSet newSet = new HashSet(alreadyVisited); newSet.Add(eB);//EDIT: thnx dhsto foreach (Cycle c in FindAllCyclesUnoptimized(newSet, eB)) { c.Build(e); yield return c; } } } 

这使用了Node，Edge和Cycle的以下实现。 它们非常简单，虽然我确实考虑过使一切变得一成不变，并且成员尽可能地无法访问。

 public sealed class Node { public static readonly ReadOnlyCollection AllNodes; internal static readonly List allNodes; static Node() { allNodes = new List(); AllNodes = new ReadOnlyCollection(allNodes); } public static void SetReferences() {//call this method after all nodes have been created foreach (Edge e in Edge.AllEdges) eAedge.Add(e); } //All edges linking *from* this node, not to it. //The variablename "Edges" it quite unsatisfactory, but I couldn't come up with anything better. public ReadOnlyCollection Edges { get; private set; } internal List edge; public int Index { get; private set; } public Node(params int[] nodesIndicesConnectedTo) { this.edge = new List(nodesIndicesConnectedTo.Length); this.Edges = new ReadOnlyCollection(edge); this.Index = allNodes.Count; allNodes.Add(this); foreach (int nodeIndex in nodesIndicesConnectedTo) new Edge(this, nodeIndex); } public override string ToString() { return this.Index.ToString(); } } public sealed class Edge { public static readonly ReadOnlyCollection AllEdges; static readonly List allEdges; static Edge() { allEdges = new List(); AllEdges = new ReadOnlyCollection(allEdges); } public int Index { get; private set; } public Node A { get; private set; } public Node B { get { return Node.allNodes[this.bIndex]; } } private readonly int bIndex; internal Edge(Node a, int bIndex) { this.Index = allEdges.Count; this.A = a; this.bIndex = bIndex; allEdges.Add(this); } public override string ToString() { return this.Index.ToString(); } } public sealed class Cycle { public readonly ReadOnlyCollection Members; private List members; private bool IsComplete; internal void Build(Edge member) { if (!IsComplete) { this.IsComplete = member.A == members[0].B; this.members.Add(member); } } internal Cycle(Edge firstMember) { this.members = new List(); this.members.Add(firstMember); this.Members = new ReadOnlyCollection(this.members); } public override string ToString() { StringBuilder result = new StringBuilder(); foreach (var member in this.members) { result.Append(member.Index.ToString()); if (member != members[members.Count - 1]) result.Append(", "); } return result.ToString(); } } 

然后为了说明如何使用这个小API，我已经实现了两个例子 。 基本上它归结为，通过指定它们链接的节点来创建所有节点，然后调用SetReferences（）来设置一些引用。 之后，调用可公开访问的FindAllCycles（）应该返回所有循环。 我已经排除了重置静态成员的任何代码，但这很容易实现。 它应该只清除所有静态列表。

 static void Main(string[] args) { InitializeExampleGraph1();//or: InitializeExampleGraph2(); Node.SetReferences(); var allCycles = FindAllCycles().ToList(); } static void InitializeExampleGraph1() { new Node(1, 2);//says that the first node(node a) links to b and c. new Node(2);//says that the second node(node b) links to c. new Node(0, 3);//says that the third node(node c) links to a and d. new Node(0);//etc } static void InitializeExampleGraph2() { new Node(1); new Node(0, 0, 2); new Node(0); } 

我必须注意，这些示例中的边缘索引与图像中的索引不对应，但通过简单查找可以避免这种情况。 结果 ：allCycles是第一个例子：

 {3, 2, 0} {5, 4, 2, 0} {3, 1} {5, 4, 1} 

allCycles是第二个例子：

 {1, 0} {2, 0} {4, 3, 0} 

我希望您对此解决方案感到满意并且您使用它。 我几乎没有对代码发表评论，所以我知道它可能很难理解。 在这种情况下，请询问，我会对它发表评论！

Answer 2

如何使用广度优先搜索来查找节点A和B之间的所有路径 – 让我们调用该函数get_all_paths

要找到您需要的所有周期：

 cycles = [] for x in nodes: cycles += get_all_paths(x,x) 

get_all_paths(x,x)因为循环只是在同一节点中开始和结束的路径。

只是一个替代解决方案 – 我希望它提供新的想法。

编辑

另一种选择是计算所有可能的路径，并在每次第一条边开始最后一条边完成时检查 – 一个循环。

在这里，您可以看到它的Python代码。

 def paths_rec(path,edges): if len(path) > 0 and path[0][0] == path[-1][1]: print "cycle", path return #cut processing when find a cycle if len(edges) == 0: return if len(path) == 0: #path is empty so all edges are candidates for next step next_edges = edges else: #only edges starting where the last one finishes are candidates next_edges = filter(lambda x: path[-1][1] == x[0], edges) for edge in next_edges: edges_recursive = list(edges) edges_recursive.remove(edge) #recursive call to keep on permuting possible path combinations paths_rec(list(path) + [edge], edges_recursive) def all_paths(edges): paths_rec(list(),edges) if __name__ == "__main__": #edges are represented as (node,node) # so (1,2) represents 1->2 the edge from node 1 to node 2. edges = [(1,2),(2,3),(3,4),(4,2),(2,1)] all_paths(edges) 

Answer 3

JBSnorro给出了一个很棒的答案，但它看起来有点太硬了。 从他的解决方案开始，我提出了一个更容易理解的例子，它不需要Node，Edge和Cycle的定义，也适用于邻接矩阵。 但是，我的解决方案是，如果从不同的节点启动，则重复一些周期。

 int[,] Adjacency = new int[6, 6] { { 0,1,0,1,0,0 }, { 0,0,0,1,0,0 }, { 0,0,0,0,1,0 }, { 0,1,1,0,0,0 }, { 0,1,0,0,0,1 }, { 0,0,1,1,0,0 }}; public void Start() { List> Out = new List>(); FindAllCycles(new List(), Out, 0); Console.WriteLine(""); foreach (List CurrCycle in Out) { string CurrString = ""; foreach (int Currint in CurrCycle) CurrString += Currint + ", "; Console.WriteLine(CurrString); } } private void FindAllCycles(List CurrentCycleVisited, List> Cycles, int CurrNode) { CurrentCycleVisited.Add(CurrNode); for (int OutEdgeCnt = 0; OutEdgeCnt < Adjacency.GetLength(0); OutEdgeCnt++) { if (Adjacency[CurrNode, OutEdgeCnt] == 1)//CurrNode Is connected with OutEdgeCnt { if (CurrentCycleVisited.Contains(OutEdgeCnt)) { int StartIndex = CurrentCycleVisited.IndexOf(OutEdgeCnt); int EndIndex = CurrentCycleVisited.IndexOf(CurrNode); Cycles.Add(CurrentCycleVisited.GetRange(StartIndex, EndIndex - StartIndex + 1)); } else { FindAllCycles(new List(CurrentCycleVisited), Cycles, OutEdgeCnt); } } } }