boostorg / boostorg/graph

`edge_connectivity()` returns wrong result on directed graphs

Offen
#454 7 Kommentare 1 Reaktion 0 zugewiesene Personen Auf GitHub ansehen
algorithm priority: medium
Vorherrschende Sprache
C++
Sterne
392
Forks
239
Ø Merge
1 T. 11 Min.
Gemergte PRs (30 T.)
20

Beschreibung

## User bug description

It has been brought to my attention by David Coudert (maintainer of Sage Math graph that uses Boost Graph) that one ticket got lost long ago when migrating from SVN: https://github.com/sagemath/sage/issues/18753

Basically the edge_connectivity experience is broken for their users:

```
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
```

## Implementation

Looking quickly into the implementation, the implementation does not filter out directed graph, treating all as undirected, and unconditionally add reverse edges when consturcting the flow graph. There is reasonable ground to believe it was not clear for the author if the reverse edge should have capacity 0 or 1:

```cpp
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
{
u = source(*ei, g), v = target(*ei, g);
boost::tie(e1, inserted) = add_edge(u, v, flow_g);
cap[e1] = 1;
boost::tie(e2, inserted) = add_edge(v, u, flow_g);
cap[e2] = 1; // not sure about this
rev_edge[e1] = e2;
rev_edge[e2] = e1;
}
```

The bug seems to be present since early day ~2001 by Jeremy Siek. The file comes with a warning `// WARNING: not-yet fully tested!
`, and unless I'm mistaken there is indeed no test for this algorithm.

## Reproducer

See on [Compiler Explorer](https://godbolt.org/z/oY1exzbn6)
```cpp
#include
#include
#include
#include

int main() {
using G = boost::adjacency_list;
G g(3);
boost::add_edge(0, 1, g);
boost::add_edge(1, 2, g);

using E = boost::graph_traits::edge_descriptor;
std::vector cut;
auto k = boost::edge_connectivity(g, std::back_inserter(cut));

std::cout << "0 -> 1 -> 2\n";
std::cout << "expected: 0\n";
std::cout << "boost: " << k << "\n";

boost::add_edge(1, 0, g);
cut.clear();
k = boost::edge_connectivity(g, std::back_inserter(cut));
std::cout << "\nafter adding 1 -> 0:\n";
std::cout << "expected: 0\n";
std::cout << "boost: " << k << "\n";
}
```
```
Program returned: 0
Program stdout
0 -> 1 -> 2
expected: 0
boost: 1

after adding 1 -> 0:
expected: 0
boost: 0
```

## Proposed changes

1. Add a concept restriction to forbid directed graphs
2. Add extensive tests to lock-in functional behavior
3. Think about supporting directed graphs: I am unsure how to do this, and this could require an algorithmic modification.

Beitragsleitfaden

Beitragsleitfaden öffnen

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.