Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

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

Đang mở
  • Có gì không ổn?
#434 2 bình luận 0 reaction 1 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

@jeremy-murphy đang làm issue này rồi.

Từ ngày 7/10/2025.

  • #435 của @GlebGrishuhin — đang mở

Đánh giá

Issue này chưa được đánh giá.

Mô tả

algorithm priority: high
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.

#include <boost/config.hpp>
#include <vector>
#include <list>
#include <boost/graph/biconnected_components.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <iterator>
#include <iostream>

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

int main()
{
    using namespace boost;
    typedef adjacency_list<vecS, vecS, undirectedS,
        property<boost::vertex_index_t, std::size_t>,
        property<edge_component_t, std::size_t>  
    > graph_t;

    typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
    typedef graph_traits<graph_t>::vertices_size_type size_type;

    std::vector<std::pair<size_t, size_t>> 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<graph_t, edge_component_t>::type comp_map = get(edge_component, g);

    std::vector<vertex_t> 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<graph_t>::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
Ngôn ngữ chính
C++
Star
397
Fork
246
Merge trung bình
1 ngày 15 giờ
Pull request đã merge (30 ngày)
31

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của boostorg/graph

Tất cả issue của boostorg/graph

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.