boostorg / boostorg/graph

`edge_connectivity()` returns wrong result on directed graphs

未关闭
#454 7 条评论 1 个 reaction 已指派 0 人 在 GitHub 查看
algorithm priority: medium
主要语言
C++
星标
392
派生
239
平均合并
1 天 11 分钟
30 天内合并 PR
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 摘要。