How to improve performance of finding all loops in undirected graphs
I have a question Finding all cycles in undirected graphs . and write a javascript version, but i got a performance issue, i'm running on chrome, it took about 8 seconds, too long, only for 16 vertices and 33 edges on my undirected graphs. these are the 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 to improve productivity.
source to share
I think you could try differently.
You can calculate for each node its depth. If you ever come to a node that already has depth, then you have loops.
This algorithm will be in O (n), where n is the number of node. It should be much faster.
If you don't need depth, you can just "tag" node.
source to share
I believe the problem is not with the implementation of your algorithm. This graph is deceptively complex, apparently containing a total of 3930 cycles! Including 39 chord cycles plus 3891 chord cycles (including smaller inside cycles).
It's like 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 idle cycles.
(Side note: the equals function seems overly complicated, but it doesn't seem to have a significant performance impact)
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;
}
source to share