`is_connected()` is too slow
メンテナーはふだん 1 日以内に返信
評価
この issue はまだ評価されていません。
説明
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)
- 主要言語
- C++
- スター
- 399
- フォーク
- 247
- 平均マージ
- 1日 9時間
- マージ済み PR（30日）
- 40
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートあり
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
boostorg/graph のほかの issue
-
Good first issues: start contributing to Boost.Graph here再び着手できるかも @andreacassioli が 9 日前に担当しましたが、オープン中のプルリクエストはありません。 オープンbeginner friendly
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
boostorg/graph#593 · コメント 47 件 ·
メンテナーはふだん 1 日以内に返信
-
algorithm beginner friendly priority: high
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
boostorg/graph#231 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
-
Trivial Minimum Cycle Ratio Failing対応中かも @Becheler が 12 日前に担当しました。 オープンalgorithm
難易度 3/5 1〜2日 初心者へのやさしさ 68/100
boostorg/graph#599 · コメント 3 件 · 担当者 1 名 ·
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 30/100
メンテナーはふだん 1 日以内に返信
-
Implementing personalized PageRank for graph node scoring.対応中かも @Becheler が 147 日前に担当しました。 オープンalgorithm
boostorg/graph#493 · コメント 22 件 · リアクション 1 件 · 担当者 2 名 ·
メンテナーはふだん 1 日以内に返信
似ている issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 82/100
ROCm/rocm-systems#13754 · コメント 2 件 ·
メンテナーはふだん 2 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
raspberrypi/libpisp#80 ·
-
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
nanoporetech/pod5-file-format#198 ·
-
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
rhalbersma/xstd-ints#341 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 75/100
secondlife/lsl-definitions#222 ·
メンテナーはふだん 9 日以内に返信