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

`is_connected()` is too slow

Đang mở
  • Có gì không ổn?
#398 1 bình luận 1 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 14/11/2024.

  • #397 của @Wavetrace — đang mở

Đánh giá

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

Mô tả

algorithm performance priority: medium

is_connected function is documented as

// Is the undirected graph connected?
// Is the directed graph strongly connected?

and achieves this goal by checking if each vertex is reachable from each other one. This is unnecessarily resource-consuming and slow, O(n^3) (or even O(n^4)). You could call this a performance bug.

Please see PR397 (https://github.com/boostorg/graph/pull/397) that fixes this to run in O(N) (O(N+E)).

See the attached log_vec.txt for speed evaluation.
log-vec.txt
(please tell if you're interested in the program that generates it)

Ngôn ngữ chính
C++
Star
399
Fork
247
Merge trung bình
1 ngày 9 giờ
Pull request đã merge (30 ngày)
40

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.