Modernize BGL shortest path algorithms
メンテナーはふだん 1 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 25/100
- issue の種類
- 機能追加
- 明瞭さ
- おおむね明確
- 活発さ
- 停滞
- 技術スタック
- cpp
調査の方向性
まず、issue で名前が挙げられている Boost Graph の最短経路アルゴリズムと、提案されている代替案について引用されている論文を確認してください。issue では、ファイル、テスト、または実装対象となる単一のアルゴリズムが特定されていません。まず maintainer と協議して、対象を限定したアルゴリズムと統合範囲を決定してください。Done には合意したアルゴリズムの実装とテストが必要になりますが、その範囲はまだ指定されていません。
索引モデルが issue の本文から書いたものです。
説明
The Sage Math graph module uses Boost Graph. This quick exploration comes from kind feedback from its maintainer David Coudert:
The BGL currently implements traditional (~1990) algorithms for shortest paths:
dijkstra_shortest_paths: 1959 single source, single shortest path tree, but constrained to positive weightsbellman_ford_shortest_paths: 1958 extends to negative weights with negative cycle detectionjohnson_all_pairs_shortest_paths: 1977 combines bellman for reweighting with dijkstra running for each vertexfloyd_warshall_all_pairs_shortest_paths: 1962 better than johnson for dense graphs, uses dynamic programmingastar_search: 1968 single source to single target path, heuristically
But it lacks more modern algorithms:
- Yen's algorithm (Yen 1971, cited ~500x) : k-shortest simple (loopless) paths between two vertices. At each iteration, finds the next shortest path by deviating from previously found paths. Baseline must-have
- k-Shortest Simple Paths, Postponed Node Classification algorithm variant, (Al Zoobi et al 2023, cited ~13x) : best speed/memory tradeoff for finding k alternative paths, most performant
- k-Shortest Simple Paths, SB* variant, (Al Zoobi et al 2023, cited ~13x) : fastest for small k, higher memory
- Contraction Hierarchies (Geisberger et al., 2008, cited ~1200x) : amazing for road networks, 1000x+ speedup over Dijkstra
- Hub labelling ( Abraham et al., 2011, cited ~400x) : sub-milliseconds shorttest path length oracle: avoids running dijsktra millions of times
- 主要言語
- 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 が 6 日前に担当しました。 オープン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 が 9 日前に担当しました。 オープン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 が 145 日前に担当しました。 オープンalgorithm
boostorg/graph#493 · コメント 22 件 · リアクション 1 件 · 担当者 2 名 ·
メンテナーはふだん 1 日以内に返信
似ている issue
-
Mac mini M6 (16 GB): Q2_0 streaming works - measured 11.7->27.2 tok/s + arena fix for sub-32 GB Macsオープン
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
メンテナーはふだん 1 日以内に返信
-
champion good first issue remake source/qq
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
metasequoiaime/msime-windows#1025 ·
メンテナーはふだん 1 日以内に返信
-
backlog bug
難易度 2/5 1〜3時間 初心者へのやさしさ 75/100
EchoTools/nevr-runtime#653 ·
メンテナーはふだん 1 日以内に返信
-
`--fail-require-skip` never fires: run_tests.py searches stdout, but the unittest binary writes the skip summary to stderr対応中かも このイシューにリンクされたプルリクエストがオープン中、またはマージ済みです。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 75/100
InfiniTimeOrg/InfiniTime#2492 ·