Opened 7 years ago
Last modified 7 years ago
#11406 new Bugs
Bug in edge connectivity - directed graphs
| Reported by: | 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)
Change History (3)
by , 7 years ago
by , 7 years ago
| Attachment: | boost_edge_connectivity_bug.cpp added |
|---|
comment:1 by , 7 years ago
Note:
See TracTickets
for help on using tickets.
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!