Modify

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!

Modify Ticket

Change Properties
Set your email in Preferences
Action
as new The owner will remain Jeremiah Willcock.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.