多边有向图的循环枚举 [英] Cycle enumeration of a directed graph with multi edges
问题描述
如何在具有多边的有向图中找到所有循环?
How can I find all cyles in a directed graph with multi edges?
图表示例 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):
Graph example 2 (multi-edge 4/5):
周期:
1-2-3
1-4
1-5
注意事项:
我不想检测循环(布尔结果)，我想列出所有循环.
I don't want to detect a cycle (boolean result), I want to list all cycles.
任何强连通分量算法都不足以解决我的问题(它会在两个示例中只找到一个组件).
Any Strongly connected component algorithm is not sufficient for my problem (it would find only one component in both examples).
我在 C# 中使用 QuickGraph 实现，但我很高兴看到任何语言的算法.
I'm using the QuickGraph implementation in C#, but I would be happy to see an algorithm in any language.
推荐答案
我对这个问题很感兴趣，谢谢！:P
I had fun with this question, thanks! :P
我在 C# 中有一个解决方案.找到循环的算法很短(约 10 行)，但周围有很多混乱(例如 Node 和 Edge 类的实现).
I have a solution in C#. The algorithm to find the cycles is very short(~10 lines), but there is a lot of clutter around it(implementations of the classes Node and Edge for instance).
我使用了变量命名约定，字母e"代表边，字母a"代表边开始的节点，b"代表它链接到的节点.有了这些约定，这就是算法:
I've used the variable naming convention that the letter "e" represents an edge, the letter "a" the node where the edge start, and "b" the node it links to. With those conventions, this is the algorithm:
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;
}
}
}
}
它有一个优化来重用一些哈希集，这可能会令人困惑.我已经包含了以下代码，它产生了完全相同的结果，但是这个实现没有优化，所以你可以更容易地弄清楚它是如何工作的.
It has an optimization to reuse some Hashsets, and that might be confusing. I've included the following code, which produces exactly the same results, but this implementation doesn't have optimizations, so you can figure out more easily how it works.
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;
}
}
}
这使用了节点、边缘和循环的以下实现.它们非常简单明了，尽管我确实花了很多心思让一切都变得不可变，并使成员尽可能少地可访问.
This uses the following implementations of Node, Edge and Cycle. They're pretty straightforward, although I did put a lot of thought in making everything immutable and members as least accessible as possible.
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() 应返回所有循环.我已经排除了重置静态成员的任何代码，但这很容易实现.它应该只清除所有静态列表.
Then to illustrate how you might use this small API, I have implemented your two examples. Basically it comes down to, create all the nodes by specifying to which nodes they link, then call SetReferences() to, well.... set some references. After that, calling the publicly accessible FindAllCycles() should return all cycles. I've excluded any code to reset the static members, but that is easily implemented. It should just clear all static lists.
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 用于第一个示例:
I must note that the indices of the edges in these examples do NOT correspond to the indices in your images, but that is avoidable with a simple lookup. The results: allCycles is for the first example:
{3, 2, 0}
{5, 4, 2, 0}
{3, 1}
{5, 4, 1}
allCycles 用于第二个示例:
allCycles is for the second example:
{1, 0}
{2, 0}
{4, 3, 0}
我希望您对此解决方案感到满意并使用它.我几乎没有对代码发表评论，所以我知道这可能很难理解.在这种情况下，请询问，我会对此发表评论！
I hope you are satisfied with this solution and that you use it. I've barely commented on the code, so I know it might be hard to understand. In that case, please ask and I'll comment on it!
这篇关于多边有向图的循环枚举的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
