找到在无向图上形成简单循环的所有路径

Question

我在编写一个算法时遇到了一些麻烦,该算法返回在无向图上形成简单循环的所有路径.

我首先考虑从顶点A开始的所有循环,对于下图

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和D开始来找到.

该图如下所示 -

我目前的方法是通过访问A的所有邻居,然后访问邻居的邻居等来构建A的所有可能路径,同时遵循以下规则:

• 每次存在多个邻居时,就会找到一个分叉,并创建并探索来自A的新路径.
  

• 如果任何创建的路径访问原始顶点,则该路径是循环.
  

• 如果任何创建的路径访问相同的顶点两次(不同于A),则丢弃该路径.
  

• 继续,直到探索了所有可能的路径.

我目前在尝试避免不止一次发现相同的循环时遇到问题,我试图通过查看新邻居是否已经是另一个现有路径的一部分来解决这个问题,以便两个路径组合(如果是独立的)构建一个周期.

我的问题是:我是否遵循正确/更好/更简单的逻辑来解决这个问题.

我很感激你的意见

Answer 1

根据@eminsenay对其他问题的回答，我使用了Frank Meyer开发的elementaryCycles库，来自web_at_normalisiert_dot_de，它实现了Johnson的算法。

但是，由于该库用于有向图，因此我添加了一些例程：

• 从 JGraphT 无向图构建邻接矩阵（Meyer 的库需要）
• 过滤结果以避免长度为 2 的循环
• 删除重复的循环，因为 Meyer 的 lib 用于有向图，并且每个无向循环是两个有向循环（每个方向一个）。

代码是

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

}