循环枚举多边有向图

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); 
       } 
      } 
     } 
    }