On 25.04.2018 20:56, Andre Vieira wrote:
Hi,
is there a way to use the graph-tool algorithms to test whether a connected component of an undirected graph is 2-edge-connected, i.e., none of its edges is a bridge which, if removed, would disconnect the component?
Of course one can do that by filtering out edge by edge and labeling the components of the resulting graphs, but that is probably not the most efficient way.
There is only support for biconnected components, which is what you describe, but for vertices instead of edges: https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.la... The algorithm for 2-edge-connectivity is simple, and think can be implemented in time O(E). If you open an issue for this in the website, I'll implement it when I find the time. -- Tiago de Paula Peixoto <tiago@skewed.de>