boostorg / boostorg/graph

Bug in biconnected_components when handling multiple (parallel) edges between the same pair of vertices

未关闭
#434 2 条评论 0 个 reaction 已指派 1 人 已被 @jeremy-murphy 认领 在 GitHub 查看
algorithm priority: high
主要语言
C++
星标
392
派生
239
平均合并
1 天 11 分钟
30 天内合并 PR
20

描述

### Version of Boost

1.88.0

### Problem description

In a block of parallel edges (e.g., three edges between A and B), only one edge receives the correct biconnected component label.
The rest are incorrectly assigned component ID 0 — even though they belong to the same biconnected component.

### Expected behavior
All edges in a block of parallel edges should have the same non-zero component ID

### Actual behavior
Only one edge gets the correct component ID; others are assigned 0 — which is wrong

### Reproducible example

Problem can be reproduced with such program.
```C++
#include
#include
#include
#include
#include
#include
#include
#include
#include

namespace boost
{
struct edge_component_t
{
typedef edge_property_tag kind;
} edge_component;
}

int main()
{
using namespace boost;
typedef adjacency_list,
property
> graph_t;

typedef graph_traits::vertex_descriptor vertex_t;
typedef graph_traits::vertices_size_type size_type;

std::vector> graph_edges = {
{0, 1}, {0, 1}, {0, 1}, // block of parallel edges
{1, 2}, // bridge
{2, 3}, {2, 3}, {2, 3}, // block of parallel edges
{3, 4}, // bridge
{4, 5} // bridge
};

graph_t g(graph_edges.size());

for (const auto& pair : graph_edges)
add_edge(pair.first, pair.second, g);

property_map::type comp_map = get(edge_component, g);

std::vector art_points;

auto num_comps = biconnected_components(g, comp_map, std::back_inserter(art_points));

std::cerr << "Found " << num_comps.first << " biconnected components.\n";
std::cerr << "Found " << art_points.size() << " articulation points.\n";

graph_traits::edge_iterator ei, ei_end;
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
std::cout << (char)(source(*ei, g) + 'A') << " -- "
<< (char)(target(*ei, g) + 'A')
<< " " << comp_map[*ei] << "\n";

return 0;
}
```

### Actual output

The proram output contains block index for each edge of graph:
```
Found 5 biconnected components.
Found 4 articulation points.
A -- B 4
A -- B 0
A -- B 0
B -- C 3
C -- D 2
C -- D 0
C -- D 0
D -- E 1
E -- F 0
```

Only one of parallel edges `A-B` has non-zero block index. Same stands for edges `C-D`.

Picture shows the graph from example. Red vertices indicate articulation points. Each edge is labeled with index of biconnected component (block) to which it belongs Picture makes clear that output of example is incorrect - each group of parallel edges should form a distinct block.

Image

### Expected output

```
Found 5 biconnected components.
Found 4 articulation points.
A -- B 4
A -- B 4
A -- B 4
B -- C 3
C -- D 2
C -- D 2
C -- D 2
D -- E 1
E -- F 0
```

贡献指南

打开贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。