循環枚舉多邊有向圖

Question

如何在具有多邊的有向圖中找到所有循環？

格拉夫例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 

注：

我不想檢測週期（布爾值），我想列表中的所有周期。

任何Strongly connected component算法是不是足夠我的問題（它會發現只有一個組件在這兩個示例中）。

我在C＃中使用QuickGraph實現，但我很樂意看到任何語言的算法。

Answer 1

怎麼樣使用Breadth-first search找到節點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 2

我對這個問題很開心，謝謝！ ：P

我在C＃中有一個解決方案。找到這些週期的算法非常短（約10條線），但周圍存在很多混亂（例如Node和Edge類的實現）。

我已經使用了字母「e」代表邊的變量命名約定，字母「a」是邊開始的節點，「b」是它鏈接到的節點。這些公約，這是算法：

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

它有一個優化重用一些Hashsets，這可能會造成混亂。我已經包含了下面的代碼，它產生完全相同的結果，但是這個實現沒有優化，所以你可以更容易地找出它的工作原理。

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

這使用節點，邊緣和週期以下的實施方式。他們非常直截了當，儘管我在確保一切不可變和成員儘可能無障礙方面投入了很多精力。

public sealed class Node 
{ 
    public static readonly ReadOnlyCollection<Node> AllNodes; 
    internal static readonly List<Node> allNodes; 
    static Node() 
    { 
     allNodes = new List<Node>(); 
     AllNodes = new ReadOnlyCollection<Node>(allNodes); 
    } 
    public static void SetReferences() 
    {//call this method after all nodes have been created 
     foreach (Edge e in Edge.AllEdges) 
      e.A.edge.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<Edge> Edges { get; private set; } 
    internal List<Edge> edge; 
    public int Index { get; private set; } 
    public Node(params int[] nodesIndicesConnectedTo) 
    { 
     this.edge = new List<Edge>(nodesIndicesConnectedTo.Length); 
     this.Edges = new ReadOnlyCollection<Edge>(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<Edge> AllEdges; 
    static readonly List<Edge> allEdges; 
    static Edge() 
    { 
     allEdges = new List<Edge>(); 
     AllEdges = new ReadOnlyCollection<Edge>(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<Edge> Members; 
    private List<Edge> 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<Edge>(); 
     this.members.Add(firstMember); 
     this.Members = new ReadOnlyCollection<Edge>(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 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<List<int>> Out = new List<List<int>>(); 
     FindAllCycles(new List<int>(), Out, 0); 
     Console.WriteLine(""); 
     foreach (List<int> CurrCycle in Out) 
     { 
      string CurrString = ""; 
      foreach (int Currint in CurrCycle) CurrString += Currint + ", "; 
      Console.WriteLine(CurrString); 
     } 
    } 
    private void FindAllCycles(List<int> CurrentCycleVisited, List<List<int>> 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<int>(CurrentCycleVisited), Cycles, OutEdgeCnt); 
       } 
      } 
     } 
    }