Boost's edge_connectivity returns wrong result on directed graphs

sagemath / sage

Main repository of SageMath

https://www.sagemath.org

Other

1.29k stars 443 forks source link

Boost's edge_connectivity returns wrong result on directed graphs #18753

Open 6bdad4c1-1e26-4f2f-a442-a01a2292c181 opened 9 years ago

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 9 years ago

Reported upstream at https://svn.boost.org/trac/boost/ticket/11406

Upstream: Reported upstream. No feedback yet.

CC: @dcoudert

Component: graph theory

Author: Michele Borassi

Issue created by migration from https://trac.sagemath.org/ticket/18753

dcoudert commented 1 year ago

Boost is now on GitHub (https://github.com/boostorg/boost) but the ticket has not been migrated and the reported issue has not been fixed.

sage: g = digraphs.Path(3)
sage: g.edge_connectivity(implementation="sage")
0.0
sage: g.edge_connectivity(implementation="boost")  # wrong answer
1
sage: g.add_edge(1, 0)
sage: g.edge_connectivity(implementation="sage")
0.0
sage: g.edge_connectivity(implementation="boost")
0

dcoudert commented 7 months ago

One should contribute https://github.com/boostorg/graph to fix this issue.