Find all the paths forming simple cycles on an undirected graph

Question

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

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

Additional cycles would be

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

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

The graph is shown below -

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:

• 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.
  

• 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.?

I would appreciate your comments

Answer 1

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:

• build the adjacency matrix from a JGraphT undirected graph (needed by Meyer's lib)
• filter the results to avoid cycles of length 2
• delete repeated cycles, since Meyer's lib is for directed graphs, and each undirected cycle is two directed cycles (one on each direction).

The code is

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

}

Answer 2

I'm answering this on the basis that you want to find chordless cycles, but it can be modified to find cycles with chords.

This problem reduces to finding all (inclusion) minimal paths between two vertices s and t.

• For all triplets, (v,s,t):
  • Either v,s,t form a triangle, in which case, output it and continue to next triplet.
  • Otherwise, remove v and its neighbor except s and t, and enumerate all s-t-paths.

Finding all s-t-paths can be done by dynamic programming.