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

我在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}

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