Finding all cycles in undirected graphs

Question

I need a working algorithm for finding all simple cycles in an undirected graph. I know the cost can be exponential and the problem is NP-complete, but I am going to use it in a small graph (up to 20-30 vertices) and the cycles are small in number.

After a long research (mainly here) I still don't have a working approach. Here is a summary of my search:

Finding all cycles in an undirected graph

Cycles in an Undirected Graph -> detects only whether there is a cycle or not

Finding polygons within an undirected Graph -> very nice description, but no solution

Finding all cycles in a directed graph -> finds cycles only in directed graphs

Detect cycles in undirected graph using boost graph library

The only answer I found, which approaches my problem, is this one:

Find all cycles in graph, redux

It seems that finding a basic set of cycles and XOR-ing them could do the trick. Finding a basic set of cycles is easy, but I don't understand how to combine them in order to obtain all cycles in the graph...

Answer 1

Inspired by @LetterRip and @Axel Kemper Here is a shorter version of Java:

public static int[][] graph =
        {
                {1, 2}, {2, 3}, {3, 4}, {2, 4},
                {3, 5}
        };
public static Set<List<Integer>> cycles = new HashSet<>();

static void findNewCycles(ArrayList<Integer> path) {
    int start = path.get(0);
    int next = -1;
    for (int[] edge : graph) {
        if (start == edge[0] || start == edge[1]) {
            next = (start == edge[0]) ? edge[1] : edge[0];
            if (!path.contains(next)) {
                ArrayList<Integer> newPath = new ArrayList<>();
                newPath.add(next);
                newPath.addAll((path));
                findNewCycles(newPath);
            } else if (path.size() > 2 && next == path.get(path.size() - 1)) {
                List<Integer> normalized = new ArrayList<>(path);
                Collections.sort(normalized);
                cycles.add(normalized);
            }
        }
    }
}

public static void detectCycle() {
    for (int i = 0; i < graph.length; i++)
        for (int j = 0; j < graph[i].length; j++) {
            ArrayList<Integer> path = new ArrayList<>();
            path.add(graph[i][j]);
            findNewCycles(path);
        }
    for (List<Integer> c : cycles) {
        System.out.println(c);
    }
}

Answer 2

It seems that the cycle finder above has some problems. The C# version fails to find some cycles. My graph is:

  {2,8},{4,8},{5,8},{1,9},{3,9},{4,9},{5,9},{6,9},{1,10},
  {4,10},{5,10},{6,10},{7,10},{1,11},{4,11},{6,11},{7,11},
  {1,12},{2,12},{3,12},{5,12},{6,12},{2,13},{3,13},{4,13},
  {6,13},{7,13},{2,14},{5,14},{7,14}

For example, the cycle: 1-9-3-12-5-10 is not found. I tried the C++ version as well, it returns very large (tens of millions) number of cycles which is apparently wrong. Probably, it fails to match the cycles.

Sorry, I am in a bit of crunch and I have not investigated further. I wrote my own version based on post of Nikolay Ognyanov (thank you very much for your post). For the graph above my version returns 8833 cycles and I am trying to verify that it is correct. The C# version returns 8397 cycles.

Answer 3

Here is a node version of the python code.

const graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
let cycles = []

function main() {
  for (const edge of graph) {
    for (const node of edge) {
      findNewCycles([node])
    }
  }
  for (cy of cycles) {
    console.log(cy.join(','))
  }
}

function findNewCycles(path) {
  const start_node = path[0]
  let next_node = null
  let sub = []

  // visit each edge and each node of each edge
  for (const edge of graph) {
    const [node1, node2] = edge
    if (edge.includes(start_node)) {
      next_node = node1 === start_node ? node2 : node1
    }
    if (notVisited(next_node, path)) {
      // eighbor node not on path yet
      sub = [next_node].concat(path)
      // explore extended path
      findNewCycles(sub)
    } else if (path.length > 2 && next_node === path[path.length - 1]) {
      // cycle found
      const p = rotateToSmallest(path)
      const inv = invert(p)
      if (isNew(p) && isNew(inv)) {
        cycles.push(p)
      }
    }
  }
}

function invert(path) {
  return rotateToSmallest([...path].reverse())
}

// rotate cycle path such that it begins with the smallest node
function rotateToSmallest(path) {
  const n = path.indexOf(Math.min(...path))
  return path.slice(n).concat(path.slice(0, n))
}

function isNew(path) {
  const p = JSON.stringify(path)
  for (const cycle of cycles) {
    if (p === JSON.stringify(cycle)) {
      return false
    }
  }
  return true
}

function notVisited(node, path) {
  const n = JSON.stringify(node)
  for (const p of path) {
    if (n === JSON.stringify(p)) {
      return false
    }
  }
  return true
}

main()

Answer 4

The following is a demo implementation in C# (and Java, see end of answer) based on depth first search.

An outer loop scans all nodes of the graph and starts a search from every node. Node neighbours (according to the list of edges) are added to the cycle path. Recursion ends if no more non-visited neighbours can be added. A new cycle is found if the path is longer than two nodes and the next neighbour is the start of the path. To avoid duplicate cycles, the cycles are normalized by rotating the smallest node to the start. Cycles in inverted ordering are also taken into account.

This is just a naive implementation. The classical paper is: Donald B. Johnson. Finding all the elementary circuits of a directed graph. SIAM J. Comput., 4(1):77–84, 1975.

A recent survey of modern algorithms can be found here

using System;
using System.Collections.Generic;

namespace akCyclesInUndirectedGraphs
{
    class Program
    {
        //  Graph modelled as list of edges
        static int[,] graph =
            {
                {1, 2}, {1, 3}, {1, 4}, {2, 3},
                {3, 4}, {2, 6}, {4, 6}, {7, 8},
                {8, 9}, {9, 7}
            };

        static List<int[]> cycles = new List<int[]>();

        static void Main(string[] args)
        {
            for (int i = 0; i < graph.GetLength(0); i++)
                for (int j = 0; j < graph.GetLength(1); j++)
                {
                    findNewCycles(new int[] {graph[i, j]});
                }

            foreach (int[] cy in cycles)
            {
                string s = "" + cy[0];

                for (int i = 1; i < cy.Length; i++)
                    s += "," + cy[i];

                Console.WriteLine(s);
            }
        }

        static void findNewCycles(int[] path)
        {
                int n = path[0];
                int x;
                int[] sub = new int[path.Length + 1];

                for (int i = 0; i < graph.GetLength(0); i++)
                    for (int y = 0; y <= 1; y++)
                        if (graph[i, y] == n)
                        //  edge referes to our current node
                        {
                            x = graph[i, (y + 1) % 2];
                            if (!visited(x, path))
                            //  neighbor node not on path yet
                            {
                                sub[0] = x;
                                Array.Copy(path, 0, sub, 1, path.Length);
                                //  explore extended path
                                findNewCycles(sub);
                            }
                            else if ((path.Length > 2) && (x == path[path.Length - 1]))
                            //  cycle found
                            {
                                int[] p = normalize(path);
                                int[] inv = invert(p);
                                if (isNew(p) && isNew(inv))
                                    cycles.Add(p);
                            }
                        }
        }

        static bool equals(int[] a, int[] b)
        {
            bool ret = (a[0] == b[0]) && (a.Length == b.Length);

            for (int i = 1; ret && (i < a.Length); i++)
                if (a[i] != b[i])
                {
                    ret = false;
                }

            return ret;
        }

        static int[] invert(int[] path)
        {
            int[] p = new int[path.Length];

            for (int i = 0; i < path.Length; i++)
                p[i] = path[path.Length - 1 - i];

            return normalize(p);
        }

        //  rotate cycle path such that it begins with the smallest node
        static int[] normalize(int[] path)
        {
            int[] p = new int[path.Length];
            int x = smallest(path);
            int n;

            Array.Copy(path, 0, p, 0, path.Length);

            while (p[0] != x)
            {
                n = p[0];
                Array.Copy(p, 1, p, 0, p.Length - 1);
                p[p.Length - 1] = n;
            }

            return p;
        }

        static bool isNew(int[] path)
        {
            bool ret = true;

            foreach(int[] p in cycles)
                if (equals(p, path))
                {
                    ret = false;
                    break;
                }

            return ret;
        }

        static int smallest(int[] path)
        {
            int min = path[0];

            foreach (int p in path)
                if (p < min)
                    min = p;

            return min;
        }

        static bool visited(int n, int[] path)
        {
            bool ret = false;

            foreach (int p in path)
                if (p == n)
                {
                    ret = true;
                    break;
                }

            return ret;
        }
    }
}

The cycles for the demo graph:

1,3,2
1,4,3,2
1,4,6,2
1,3,4,6,2
1,4,6,2,3
1,4,3
2,6,4,3
7,9,8

The algorithm coded in Java:

import java.util.ArrayList;
import java.util.List;

public class GraphCycleFinder {

    //  Graph modeled as list of edges
    static int[][] graph =
        {
            {1, 2}, {1, 3}, {1, 4}, {2, 3},
            {3, 4}, {2, 6}, {4, 6}, {7, 8},
            {8, 9}, {9, 7}
        };

    static List<int[]> cycles = new ArrayList<int[]>();

    /**
     * @param args
     */
    public static void main(String[] args) {

        for (int i = 0; i < graph.length; i++)
            for (int j = 0; j < graph[i].length; j++)
            {
                findNewCycles(new int[] {graph[i][j]});
            }

        for (int[] cy : cycles)
        {
            String s = "" + cy[0];

            for (int i = 1; i < cy.length; i++)
            {
                s += "," + cy[i];
            }

            o(s);
        }

    }

    static void findNewCycles(int[] path)
    {
            int n = path[0];
            int x;
            int[] sub = new int[path.length + 1];

            for (int i = 0; i < graph.length; i++)
                for (int y = 0; y <= 1; y++)
                    if (graph[i][y] == n)
                    //  edge refers to our current node
                    {
                        x = graph[i][(y + 1) % 2];
                        if (!visited(x, path))
                        //  neighbor node not on path yet
                        {
                            sub[0] = x;
                            System.arraycopy(path, 0, sub, 1, path.length);
                            //  explore extended path
                            findNewCycles(sub);
                        }
                        else if ((path.length > 2) && (x == path[path.length - 1]))
                        //  cycle found
                        {
                            int[] p = normalize(path);
                            int[] inv = invert(p);
                            if (isNew(p) && isNew(inv))
                            {
                                cycles.add(p);
                            }
                        }
                    }
    }

    //  check of both arrays have same lengths and contents
    static Boolean equals(int[] a, int[] b)
    {
        Boolean ret = (a[0] == b[0]) && (a.length == b.length);

        for (int i = 1; ret && (i < a.length); i++)
        {
            if (a[i] != b[i])
            {
                ret = false;
            }
        }

        return ret;
    }

    //  create a path array with reversed order
    static int[] invert(int[] path)
    {
        int[] p = new int[path.length];

        for (int i = 0; i < path.length; i++)
        {
            p[i] = path[path.length - 1 - i];
        }

        return normalize(p);
    }

    //  rotate cycle path such that it begins with the smallest node
    static int[] normalize(int[] path)
    {
        int[] p = new int[path.length];
        int x = smallest(path);
        int n;

        System.arraycopy(path, 0, p, 0, path.length);

        while (p[0] != x)
        {
            n = p[0];
            System.arraycopy(p, 1, p, 0, p.length - 1);
            p[p.length - 1] = n;
        }

        return p;
    }

    //  compare path against known cycles
    //  return true, iff path is not a known cycle
    static Boolean isNew(int[] path)
    {
        Boolean ret = true;

        for(int[] p : cycles)
        {
            if (equals(p, path))
            {
                ret = false;
                break;
            }
        }

        return ret;
    }

    static void o(String s)
    {
        System.out.println(s);
    }

    //  return the int of the array which is the smallest
    static int smallest(int[] path)
    {
        int min = path[0];

        for (int p : path)
        {
            if (p < min)
            {
                min = p;
            }
        }

        return min;
    }

    //  check if vertex n is contained in path
    static Boolean visited(int n, int[] path)
    {
        Boolean ret = false;

        for (int p : path)
        {
            if (p == n)
            {
                ret = true;
                break;
            }
        }

        return ret;
    }

}