how to improve performance of finding all cycles in undirected graphs

Question

I have reference the question Finding all cycles in undirected graphs . and write a javascript version, but I got the performance problem, I run on chrome, it took about 8 seconds, too a long time, for only 16 vertices and 33 edges on my undirected graphs. this is codes:

<script>
    var graph = [[37,36], [37,168], [37,85], [37,2264], [37,3203], [36,85], [36,536], [36,5097], [85,168], [85,654], [85,755], [85,3607], [85,4021], [85,5097], [168,755], [536,4021], [536,5097], [536,5464], [536,6533], [654,3607], [654,4021], [654,5564], [654,6533], [755,2357], [755,3203], [755,3607], [2264,2357], [2264,3203], [2357,3203], [4021,5097], [5464,5564], [5464,6533], [5564,6533]];
    var cycles = [];

    function findAllCycles() {
        var i, j, len;

        var st1 = new Date().getTime();

        for (i = 0; i < graph.length; i++) {
            var edge = graph[i];
            for (j = 0; j < 2; j++) {
                findNewCycles( [edge[j]] );
            }
        }

        var st2 = new Date().getTime();
        console.log("time: " + (st2-st1));
    };

    function findNewCycles(path) {
        var startNode = path[0],
            nextNode;

        // visit each edge and each node of each edge
        for (var i = 0; i < graph.length; i++) {
            var edge = graph[i];
            for (var j = 0; j < 2; j++) {
                var node = edge[j];
                if (node === startNode) //  edge refers to our current node
                {
                    nextNode = edge[(j + 1) % 2];
                    if ( !visited(nextNode, path) ) { //  neighbor node not on path yet
                        //  explore extended path
                        findNewCycles( [nextNode].concat(path), graph, cycles );
                    }
                    else if ( (path.length > 2) && (nextNode === path[path.length - 1]) ) { //  cycle found
                        //var p = normalize(path);
                        //var inv = invert(p);
                        if ( isNew(path, cycles) ) {
                            cycles.push(path);
                        }
                    }
                }
            }
        }
    }

    // check if vertex n is contained in path
    function visited(node, path) {
        return (path.indexOf(node) !== -1);
    }

    function isNew(path, cycles) {
        for (var i = 0; i < cycles.length; i++) {
            if ( equal(path, cycles[i]) ) {
                return false;
            }
        }

        return true;
    }

    function equal(path1, path2) {
        if (path1.length !== path2.length) {
            return false;
        }

        for (var i = 0; i < path1.length; i++) {
            var node1 = path1[i];
            for (var j = 0; j < path2.length; j++) {
                var node2 = path2[j];
                if (node1 === node2) {
                    break;
                }
            }
            if (j === path2.length) {
                return false;
            }
        }

        return true;
    }

    findAllCycles();
    console.log(cycles);
</script>

how can I improve the performance.

Well, you should start by using a fast node<->edge lookup structure, instead of iterating over the edge set. — Bergi, May 13 '15 at 16:33
minor suggestions: equal() function seems bloated... can't you just loop over path1 and check path1[i] == path2[i]? — pythonjsgeo, Aug 14 '17 at 02:02

score 0 · Answer 1 · answered May 13 '15 at 14:20

0

I think you could try things differently.

You could calculate for each node it's depths. If you ever come to a node that already has a depth, then you have a cycles.

This algorithm would be in O(n) where n is the number of node. It should be much faster.

If you don't care about depth you could just "tag" the node.

answered May 13 '15 at 14:20

Unex

1,747
13
17

An `O(n)` algorithm can hardly be correct, as the result size is larger than `O(n)` – Bergi May 13 '15 at 16:27

pythonjsgeo · Answer 2 · 2017-08-16T09:32:18.007

I believe the problem is not the implementation of your algorithm. This graph is deceptively complicated, apparently containing a total of 3930 cycles! Including 39 chordless cycles plus 3891 cycles with chords (which include smaller cycles inside).

This is similar to the "how many squares" problem, it can be surprising how quickly it adds up.

You may be able to optimize significantly if you are only interested in chordless cycles.

(Side note: the equals function seems overly complicated, but this is presumably doesn't significantly affect performance)

function pathIsEqual(path1, path2) {

    if (path1.length !== path2.length) {
        return false
    }

    for(var i = path1.length; i--;) {
        if(path1[i] !== path2[i]){
            return false
        }
    }

    return true;
}

how to improve performance of finding all cycles in undirected graphs

2 Answers2