Opened 3 years ago

Last modified 3 years ago

#11406 new Bugs

Bug in edge connectivity - directed graphs

Reported by: Michele Borassi <michele.borassi@…> Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.58.0 Severity: Problem
Keywords: edge connectivity, directed graphs Cc:

Description

The Boost edge connectivity algorithm gives a wrong result on a directed path with 3 vertices and 2 edges: 0 --> 1 --> 2. In particular, the output is 1, while it should be 0 (because the graph is not strongly connected).

This issue is not due to a different definition of directed edge connectivity, because the output becomes (correctly) 0 if I add an edge 1 --> 0, obtaining: 0 <-> 1 --> 2.

A minimal example of this issue is attached.

Attachments (2)

main.cpp (1.2 KB) - added by Michele Borassi <michele.borassi@…> 3 years ago.
boost_edge_connectivity_bug.cpp (1.2 KB) - added by Michele Borassi <michele.borassi@…> 3 years ago.

Download all attachments as: .zip

Change History (3)

Changed 3 years ago by Michele Borassi <michele.borassi@…>

Attachment: main.cpp added

Changed 3 years ago by Michele Borassi <michele.borassi@…>

comment:1 Changed 3 years ago by Michele Borassi <michele.borassi@…>

Hello, Martin just made me realize that in the code there is a comment "Create a network flow graph out of the undirected graph", and that line is the reason why the edge connectivity is not working on directed graphs. However, I think this issue should be more emphasized than a simple comment in the middle of a code, so I do not close the ticket (a user, like me, might not read the whole code before using the routine). Thank you very much!

Note: See TracTickets for help on using tickets.