循环枚举多边有向图[关闭]-Java 学习之路

如何在具有多边的有向图中找到 all cyles ？

图示例1：

Graph 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 2

周期：

1-2-3
1-4
1-5

Notes:

我不想检测一个循环（布尔结果），我想列出所有循环 .

任何Strongly connected component算法都不足以解决我的问题（在两个示例中都只找到一个组件） .

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

3 回答

我很开心这个问题，谢谢！：P

我有一个C＃的解决方案 . 查找周期的算法非常短（~10行），但周围有很多杂乱（例如Node和Edge类的实现） .

我使用了字母"e"代表边的变量命名约定，字母"a"边缘开始的节点，以及它链接到的节点"b" . 有了这些约定，这就是 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;
            }
        }
    }
}

它有一个优化来重用一些Hashsets，这可能会令人困惑 . 我已经包含了以下代码，它产生完全相同的结果，但是这个实现 doesn't have optimizations ，所以你可以更容易地弄清楚它是如何工作的 .

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 and 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，我实现了你的两个 examples . 基本上它归结为，通过指定它们链接的节点来创建所有节点，然后调用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);
}

我必须注意，这些示例中的边的索引与图像中的索引不对应，但是通过简单的查找可以避免这种情况 . The results ：allCycles是第一个例子：

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

allCycles是第二个例子：

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

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

回复于 2024-04-20T00:25:06+08:00

如何使用Breadth-first search查找节点A和B之间的所有路径 - 让我们调用该函数 get_all_paths

要找到您需要的所有周期：

cycles = []
for x in nodes:
    cycles += get_all_paths(x,x)

get_all_paths(x,x) 因为循环只是在同一节点中开始和结束的路径 .

只是一个替代解决方案 - 我希望它提供新的想法 .

Edit

另一种选择是计算所有可能的路径，并在每次第一条边开始最后一条边完成时检查 - 一个周期 .

在这里，您可以看到它的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)

回复于 2024-04-20T00:25:06+08:00

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

回复于 2024-04-20T00:25:06+08:00

循环枚举多边有向图[关闭]

3 回答

相关问题