[BUG] biconnected_components loses some edges - should we return only vertices ?

[etiennedeg]

This is a repost of this issue, I think it deserves discussion on whether we should return edges instead of vertices.

Summary :

start=[1,1,2,2,2,3,4,4,5,5,7,7,8,8,9,9,10,10,12,12,1,2,3]
destination=[2,4,4,5,3,5,7,8,7,8,9,10,9,10,11,12,12,13,13,11,11,12,13]

graph_s=SimpleWeightedGraph(start,destination,collect(1:23))

bi_components= biconnected_components(graph_s)

graph_s has 23 edges, but only 19 are returned in the unique biconnected component.

etienneINSA : The error is here : the edge is added only if state.low[v] > state.depth[w], whereas it should be always added to the stack. I can make a PR, but I have an interrogation: Why do we return the biconnected components by their edges? As the subgraphs are induced, this is more easily defined by the vertices. Is there a good reason to do that, or would it be too breaking to change this behavior?

[jpfairbanks]

I think this is a breaking API change, so I would rather fix the bug and possibly add an additional function that does biconnected_component_vertices or something that just computes the vertex set.

[gdalle]

See also sbromberger/SimpleWeightedGraphs.jl#72

[etiennedeg]

@jpfairbanks Wouldn't a new function be a bit redundant ? Or do you suggest to deprecate the old method ?

[simonschoelly]

It is indeed a bit unfortunate that this method returns sets of edges (which may not even have the same edge type as the input graph) and not sets of vertices. In most cases a user will probably have to do some extra work to get something out of this edge set.

But as this is indeed breaking, I think that should be a different PR from the bug fix itself. @etiennedeg you mentioned that you already know a way to solve that bug, would you mind making a PR that fixes that bug, with some additional test that would cover that case?

[etiennedeg]

Ok I'm doing it

[etiennedeg]

Fixed by etiennedeg@ee06ccc

[gdalle]

Was this fixed by a PR?

[etiennedeg]

No, this was done when I started contributing to this repo, and did some wild commits (which I don't do nowadays). I closed because my fix was a two line fix, and is already in the codebase since more than a year, but feel free to take a look / reopen for discussion if you feel like it.

[gdalle]

No worries! I like your wild side 🤣