找到所有的路径，形成简单的周期在一个无向图 [英] Find all the paths forming simple cycles on an undirected graph

问题描述

我有一些麻烦，写一个算法返回所有的无向图形成简单的循环路径。

I am having some trouble writing an algorithm that returns all the paths forming simple cycles on an undirected graph.

我正在考虑在首先从顶点A，这将是周期的开始，为图下方

I am considering at first all cycles starting from a vertex A, which would be, for the graph below

A，B，E，G，F
A，B，E，D，F
A，B，C，D，F
A，B，C，D，E，G，F

A,B,E,G,F
A,B,E,D,F
A,B,C,D,F
A,B,C,D,E,G,F

额外的周期将是

B，C，D，E
F，D，E，G

B,C,D,E
F,D,E,G

，但这些可能被找到，例如，通过再次调用相同的算法，但是从B和从D-，分别开始。

but these could be found, for example, by calling the same algorithm again but starting from B and from D, respectively.

该图显示如下 -

我目前的做法是建立从A所有可能的路径访问A的所有邻居，然后neightbors的邻居等，按照这些规则，同时：

My current approach is to build all the possible paths from A by visiting all the neighbors of A, and then the neighbors of the neightbors and so on, while following these rules:

• 每个不止一个邻居存在的时间，叉子被发现，从A新的路径创建和探索。
  

• each time that more than one neighbor exist, a fork is found and a new path from A is created and explored.
  

如果任何的创建的路径访问的原始顶点，该路径是一个周期。

if any of the created paths visits the original vertex, that path is a cycle.

如果任何的创建的路径访问同一顶点两次（不同于A）中的路径被丢弃。

if any of the created paths visits the same vertex twice (different from A) the path is discarded.

继续下去，直到所有可能的路径进行了探讨。

continue until all possible paths have been explored.

我目前遇到问题尽量避免在同一周期被发现多了一次，我试图寻找解决这一点，如果新的邻居已经是另外一个现有路径的一部分，这样的两个路径​​组合（如独立）建立一个循环。

I am currently having problems trying to avoid the same cycle being found more than once, and I am trying to solve this by looking if the new neighbor is already part of another existing path so that the two paths combined (if independent) build up a cycle.

我的问题是：？我​​是按照正确的/更好/更简单的逻辑来解决这个问题。

My question is: Am I following the correct/better/simpler logic to solve this problem.?

我会AP preciate您的意见

I would appreciate your comments

推荐答案

根据@eminsenay的答案其他问题，我用了 elementaryCycles 通过弗兰克·迈耶开发库，从web_at_normalisiert_dot_de它实现约翰逊的算法。

Based on the answer of @eminsenay to other question, I used the elementaryCycles library developed by Frank Meyer, from web_at_normalisiert_dot_de which implements the algorithms of Johnson.

然而，因为这个库是对于有向图，我添加了一些例程：

However, since this library is for directed graphs, I added some routines to:

• 从一个JGraphT无向图（需要迈耶的lib）建立邻接矩阵
• 筛选结果，以避免长度为2个周期
• 在删除重复的周期，因为梅耶的lib是向图，每个无向周期为两个定向周期（一个在每个方向）。

在code是

package test;

import java.util.*;

import org.jgraph.graph.DefaultEdge;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.graph.SimpleGraph;


public class GraphHandling<V> {

private UndirectedGraph<V,DefaultEdge>     graph;
private List<V>                         vertexList;
private boolean                         adjMatrix[][];

public GraphHandling() {
    this.graph             = new SimpleGraph<V, DefaultEdge>(DefaultEdge.class);
    this.vertexList     = new ArrayList<V>();
}

public void addVertex(V vertex) {
    this.graph.addVertex(vertex);
    this.vertexList.add(vertex);
}

public void addEdge(V vertex1, V vertex2) {
    this.graph.addEdge(vertex1, vertex2);
}

public UndirectedGraph<V, DefaultEdge> getGraph() {
    return graph;
}

public List<List<V>>     getAllCycles() {
    this.buildAdjancyMatrix();

    @SuppressWarnings("unchecked")
    V[] vertexArray                 = (V[]) this.vertexList.toArray();
    ElementaryCyclesSearch     ecs     = new ElementaryCyclesSearch(this.adjMatrix, vertexArray);

    @SuppressWarnings("unchecked")
    List<List<V>>             cycles0    = ecs.getElementaryCycles();

    // remove cycles of size 2
    Iterator<List<V>>         listIt    = cycles0.iterator();
    while(listIt.hasNext()) {
        List<V> cycle = listIt.next();

        if(cycle.size() == 2) {
            listIt.remove();
        }
    }

    // remove repeated cycles (two cycles are repeated if they have the same vertex (no matter the order)
    List<List<V>> cycles1             = removeRepeatedLists(cycles0);

    for(List<V> cycle : cycles1) {
        System.out.println(cycle);    
    }


    return cycles1;
}

private void buildAdjancyMatrix() {
    Set<DefaultEdge>     edges        = this.graph.edgeSet();
    Integer             nVertex     = this.vertexList.size();
    this.adjMatrix                     = new boolean[nVertex][nVertex];

    for(DefaultEdge edge : edges) {
        V v1     = this.graph.getEdgeSource(edge);
        V v2     = this.graph.getEdgeTarget(edge);

        int     i = this.vertexList.indexOf(v1);
        int     j = this.vertexList.indexOf(v2);

        this.adjMatrix[i][j]     = true;
        this.adjMatrix[j][i]     = true;
    }
}
/* Here repeated lists are those with the same elements, no matter the order, 
 * and it is assumed that there are no repeated elements on any of the lists*/
private List<List<V>> removeRepeatedLists(List<List<V>> listOfLists) {
    List<List<V>> inputListOfLists         = new ArrayList<List<V>>(listOfLists);
    List<List<V>> outputListOfLists     = new ArrayList<List<V>>();

    while(!inputListOfLists.isEmpty()) {
        // get the first element
        List<V> thisList     = inputListOfLists.get(0);
        // remove it
        inputListOfLists.remove(0);
        outputListOfLists.add(thisList);
        // look for duplicates
        Integer             nEl     = thisList.size();
        Iterator<List<V>>     listIt    = inputListOfLists.iterator();
        while(listIt.hasNext()) {
            List<V>     remainingList     = listIt.next();

            if(remainingList.size() == nEl) {
                if(remainingList.containsAll(thisList)) {
                    listIt.remove();    
                }
            }
        }

    }

    return outputListOfLists;
}

}

这篇关于找到所有的路径，形成简单的周期在一个无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！