boostorg / boostorg/graph

`edge_connectivity()` returns wrong result on directed graphs

オープン
#454 コメント 7 件 リアクション 1 件 担当者 0 名 GitHub で見る
algorithm priority: medium
主要言語
C++
スター
392
フォーク
239
平均マージ
1日 11分
マージ済み PR(30日)
20

説明

## 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.

コントリビューションガイド

コントリビューションガイドを開く

評価

この issue はまだ評価されていません。

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。