DirectedGraph.getCycles returns an inexisting cycle

[Oaz]

Describe the bug DirectedGraph.getCycles returns an inexisting cycle, but somewhat close to the actual cycle.

To Reproduce var graph = new dataStructureTyped.DirectedGraph(); graph.addVertex('A'); graph.addVertex('B'); graph.addVertex('C'); graph.addVertex('D'); graph.addVertex('E'); graph.addEdge('A','B'); graph.addEdge('A','C'); graph.addEdge('B','D'); graph.addEdge('C','D'); graph.addEdge('D','E'); graph.addEdge('E','B'); var cycles = graph.getCycles(); console.log(Array.from(cycles.values()));

The log shows :

[ [ DirectedVertex { key: 'B', value: undefined }, DirectedVertex { key: 'C', value: undefined }, DirectedVertex { key: 'D', value: undefined }, DirectedVertex { key: 'E', value: undefined } ] ]

Expected behavior The log should show :

[ [ DirectedVertex { key: 'B', value: undefined }, DirectedVertex { key: 'D', value: undefined }, DirectedVertex { key: 'E', value: undefined } ] ]

[zrwusa]

This bug has been resolved in version 1.49.1

[zrwusa]

Please test the feature, and if there are no issues, you can close this issue.

[Oaz]

Thank you. The initial example now works fine.

But I think there is still something wrong with cycle detection.

I tried with multiple cycles:

var graph = new dataStructureTyped.DirectedGraph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addEdge('A','B');
graph.addEdge('A','C');
graph.addEdge('B','D');
graph.addEdge('C','D');
graph.addEdge('D','E');
graph.addEdge('E','B');
graph.addVertex('F');
graph.addEdge('B','F');
graph.addEdge('F','E');
graph.addVertex('G');
graph.addEdge('C','G');
graph.addEdge('G','A');
var cycles = graph.getCycles();
console.log(Array.from(cycles.values()));

Actual result:

[
  [
    DirectedVertex { key: 'B', value: undefined },
    DirectedVertex { key: 'D', value: undefined },
    DirectedVertex { key: 'E', value: undefined }
  ],
  [
    DirectedVertex { key: 'A', value: undefined },
    DirectedVertex { key: 'C', value: undefined },
    DirectedVertex { key: 'G', value: undefined }
  ]
]

Expected result:

[
  [
    DirectedVertex { key: 'B', value: undefined },
    DirectedVertex { key: 'D', value: undefined },
    DirectedVertex { key: 'E', value: undefined }
  ],
  [
    DirectedVertex { key: 'B', value: undefined },
    DirectedVertex { key: 'F', value: undefined },
    DirectedVertex { key: 'E', value: undefined }
  ],
  [
    DirectedVertex { key: 'A', value: undefined },
    DirectedVertex { key: 'C', value: undefined },
    DirectedVertex { key: 'G', value: undefined }
  ]
]

B->F->E->B cycle is missing

Now, if I remove the D->E edge, B->D->E->B cycle is no longer present (this is normal), the B->F->E->B magically appears and the result is correct.

var graph = new dataStructureTyped.DirectedGraph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addEdge('A','B');
graph.addEdge('A','C');
graph.addEdge('B','D');
graph.addEdge('C','D');
//graph.addEdge('D','E');
graph.addEdge('E','B');
graph.addVertex('F');
graph.addEdge('B','F');
graph.addEdge('F','E');
graph.addVertex('G');
graph.addEdge('C','G');
graph.addEdge('G','A');
var cycles = graph.getCycles();
console.log(Array.from(cycles.values()));

actual and expected result:

[
  [
    DirectedVertex { key: 'B', value: undefined },
    DirectedVertex { key: 'F', value: undefined },
    DirectedVertex { key: 'E', value: undefined }
  ],
  [
    DirectedVertex { key: 'A', value: undefined },
    DirectedVertex { key: 'C', value: undefined },
    DirectedVertex { key: 'G', value: undefined }
  ]
]

[zrwusa]

resolved in version 1.49.3, please have a try