Algorithm for finding all cycles in a directed graph on C++ using Adjacency matrix

Question

Given graph adjacency matrix (for ex. g[][]), graph is directed. Needs find count of all graph cycles (if exists) and print them.

I tried to wrote this algorithm in Java, sometimes it works correctly. If graph has complex cycles, algorithm return crazy cycles. Please, look at my code and help to resolve this problem

public static final int k = 6;

public static int g[][] = { { 0, 1, 0, 0, 0, 0 },
                            { 1, 0, 1, 0, 0, 0 },
                            { 0, 0, 0, 1, 0, 0 },
                            { 0, 0, 0, 0, 1, 0 },
                            { 0, 0, 1, 0, 0, 0 },
                            { 0, 0, 0, 0, 0, 0 } };

public static Vector stack = new Vector();

public static void printStack() {
    System.out.print("stack is: { ");
    for (int i = 0; i < stack.size(); i++) {
        System.out.print(stack.get(i) + " ");
    }
    System.out.println("};");

}

public static boolean checkCycle() {
    boolean res = false;

    for (int i = 0; i < stack.size() - 1; i++) {
        if (stack.get(i).equals(stack.lastElement())) {
            res = true;
            break;
        }

    }
    return res;
}

public static boolean go_to_line(int line) {
    boolean res = false;
    for (int i = 0; i < k; i++) {
        if (g[line][i] == 1) {
            stack.add(i);
            if (checkCycle() == true) {
                System.out.println("Cycle found!");
                res = true;
            } else {
                res = go_to_line(i);
            }
        }
    }

    return res;
}

public static int cycles_count() {
    int res = 0;

    for (int i = 0; i < k; i++) {
        if (g[i][i] == 1) {
            System.out.println("Knot detected at item {" + i + "}!");
            res++;
        }

        for (int j = i + 1; j < k; j++) {
            if (g[j][i] == 1) {
                stack.add(j);
                stack.add(i);

                if (go_to_line(i) == true) {
                    res++;

                    System.out.print("Final ");
                    printStack();
                    stack.removeAllElements();
                }
            }
        }
    }

    return res;
}

Answer 1

If C++ is the problem then change for another language. up to my knowledge C++ does not have particular feature that make it more efficient/convenient to work on graph matters. Alternatively you might want to look for a framework that will abstract the low level, letting you focusing on the high-level question. You might consider Boost Graph library for that purpose.

Answer 2

This problem has exponential complexity in the general case. The thing is that if each vertex is connected to each then the count of all graph cycles is more than 2^n (any subset of nodes forms several cycles).

Thus there is no good algorithm in the general case. To find some cycle you may use breadth-first search. To find all cycles you should use brute force algorithm.

Answer 3

@Alexey, can you throw some light on how you were able to deduce 2^n * n!.. trying with simple permutations & combinations didn't give me the same result.

Thanks

Answer 4

Have you considered that there may be infinitely many cycles?