C# · 12月 24, 2021

c# – 循环枚举具有多边的有向图

如何在多边形的有向图中找到所有的圆形?

图示例1:

周期:

1-2-61-2-3-41-2-3-4-5-61-2-6-5-3-43-4-55-6

图示例2(多边4/5):

周期:

1-2-31-41-5

笔记:

我不想检测一个循环(布尔结果),我想列出所有循环.

任何Strongly connected component算法都不足以满足我的问题(在这两个例子中只能找到一个组件).

我在C#中使用QuickGraph实现,但我很乐意看到任何语言的算法.

解决方法 我有这个问题的乐趣,谢谢! :P

我在C#中有一个解决方案.找到周期的算法非常短(约10行),但是它周围有很多杂乱(例如类和节点类的实现).

我使用变量命名约定,字母“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; } }}

这使用Node,Edge和Cycle的以下实现.他们很简单,尽管我做了很多想法,使一切都不变,成员尽可能少的访问.

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,2); new Node(0);}

我必须注意,这些例子中边缘的索引不符合图像中的索引,但是通过简单的查找可以避免这些索引.
结果:allCycles是第一个例子:

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

allCycles是第二个例子:

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

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