如何提高在无向图中查找所有循环的性能

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:

我参考了在无向图中查找所有循环的问题。并写了一个javascript版本,但是我遇到了性能问题,我在chrome上运行,花了大约8秒,太长时间了,在我的无向图上只有16个顶点和33个边。这是代码:

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

我怎样才能提高性能。

2 个解决方案

#1

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.

该算法将在O(n)中,其中n是节点的数量。它应该快得多。

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

如果你不关心深度,你可以“标记”节点。

#2

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

我认为问题不在于算法的实现。这个图表看起来很复杂,显然总共有3930个周期!包括39个无弦循环加上带有和弦的3891个循环(其中包括较小的循环)。

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

#1