CPLib.Graph
Defined in cp-library@0.16.0
グラフの表現と基本的なアルゴリズム
グラフは、GraphBuilderに辺を足していき、buildでGraphにしてから使います。
制約・計算量の n は頂点数、m は辺数を表します。
Examples
// 辺のデータをコストとして、ダイクストラ法で最短距離を求める
let g = GraphBuilder::create(3).add_edge(0, 1, 5).add_edge(1, 2, 2).add_edge(0, 2, 10).build;
assert_eq(|_|"", g.dijkstra(0), [0, 5, 7])
Values
namespace CPLib.Graph
@size
Type: CPLib.Graph::Graph c -> Std::I64
グラフの頂点数を取得する
計算量:O(1)
Parameters
graph: グラフ
bellman_ford
Type: [c : CPLib.Trait::Inf, c : Std::Additive, c : Std::Eq, c : Std::LessThan] Std::I64 -> CPLib.Graph::Graph c -> Std::Array c
ベルマンフォード法:グラフと開始ノードが与えられたとき、開始ノードから各ノードに到達するまでの最小コストの配列を返す。
到達できないノードまでの距離にはInf::infが設定されます。
制約:0 <= start < n, 開始ノードから到達できる負の閉路がない
計算量:O(n (n + m))
Parameters
start: 開始ノードの番号graph: グラフ
calc_scc_ids
Type: CPLib.Graph::Graph c -> (Std::I64, Std::Array Std::I64)
頂点ごとに、その頂点を含む強連結成分の番号を求める
戻り値は、強連結成分の数numと、長さが頂点数の配列idsの組。
番号は0以上num未満で、トポロジカル順に振られる:uとvが異なる強連結成分に属するとき、uからvに到達できるなら、ids.@(u) < ids.@(v)。
番号cの強連結成分は、calc_sccsの戻り値のc番目の要素である。
計算量:O(n + m)
Parameters
g: グラフ
Examples
// 0 -> 1 -> 2 -> 1、2 -> 3。{1, 2}が1つの強連結成分になる
let g = GraphBuilder::create(4).add_edge(0, 1, ()).add_edge(1, 2, ()).add_edge(2, 1, ()).add_edge(2, 3, ()).build;
assert_eq(|_|"", g.calc_scc_ids, (3, [0, 1, 1, 2]))
calc_sccs
Type: CPLib.Graph::Graph c -> Std::Array (Std::Array Std::I64)
グラフの強連結成分分解を求める
戻り値は、各強連結成分を構成する頂点のリストの配列です。 また、戻り値はトポロジカルソートされています:uとvが異なる強連結成分cu, cvに属するとき、uからvに到達できるなら、cuはcvの前に現れます。
計算量:O(n + m)
Parameters
g: グラフ
dijkstra
Type: [c : CPLib.Trait::Inf, c : Std::Additive, c : Std::LessThan] Std::I64 -> CPLib.Graph::Graph c -> Std::Array c
ダイクストラ法:グラフと開始ノードが与えられたとき、開始ノードから各ノードに到達するまでの最小コストの配列を返す。
到達できないノードまでの距離にはInf::infが設定されます。
制約:0 <= start < n, 辺のコスト >= 0
計算量:O((n + m) log m)
Parameters
start: 開始ノードの番号graph: グラフ
get_out_degree
Type: Std::I64 -> CPLib.Graph::Graph c -> Std::I64
頂点vから出る辺の本数を取得する
制約:0 <= v < n
計算量:O(1)
Parameters
v: 始点の頂点番号graph: グラフ
get_size
Deprecated: Use CPLib.Graph::@size instead.
Type: CPLib.Graph::Graph c -> Std::I64
@sizeの別名(非推奨)
reverse
Type: CPLib.Graph::Graph c -> CPLib.Graph::Graph c
すべての辺の向きを逆にしたグラフを作る
元のグラフの辺u -> vは、データを引き継いで辺v -> uになる。
計算量:O(n + m)
Parameters
graph: グラフ
Examples
// 0 -> 1 -> 2、0 -> 2。逆にすると、2から1と0へ、1から0へ辺が出る
let g = GraphBuilder::create(3).add_edge(0, 1, "a").add_edge(1, 2, "b").add_edge(0, 2, "c").build;
let rg = g.reverse;
assert_eq(|_|"", rg.get_out_degree(2), 2);;
assert_eq(|_|"", rg.to_iter_edges(1).map(|Edge { to, data }| (to, data)).to_array, [(0, "a")])
to_iter_edges
Type: [?it : Std::Iterator, Std::Iterator::Item ?it = CPLib.Graph::Edge c] Std::I64 -> CPLib.Graph::Graph c -> ?it
頂点vから出る辺を返すイテレータを作る
制約:0 <= v < n
計算量:O(1)
Parameters
v: 始点の頂点番号graph: グラフ
namespace CPLib.Graph::Edge
make
Type: Std::I64 -> c -> CPLib.Graph::Edge c
辺を作成する
namespace CPLib.Graph::GraphBuilder
add_edge
Type: Std::I64 -> Std::I64 -> c -> CPLib.Graph::GraphBuilder c -> CPLib.Graph::GraphBuilder c
グラフに辺を追加する
制約:0 <= from, to < n
計算量:ならしO(1)
Parameters
from: 始点の頂点番号to: 終点の頂点番号data: 辺のデータbuilder: 辺を足していく途中のグラフ
build
Type: CPLib.Graph::GraphBuilder c -> CPLib.Graph::Graph c
辺を足し終えたグラフを作る
制約:m < 2^31
計算量:O(n + m)
Parameters
builder: 辺を足していく途中のグラフ
create
Type: Std::I64 -> CPLib.Graph::GraphBuilder c
頂点数がnで辺のないGraphBuilderを作成する
制約:0 <= n < 2^31
計算量:O(1)
Parameters
n: 頂点数
Types and aliases
namespace CPLib.Graph
Edge
Defined as: type Edge c = unbox struct { ...fields... }
グラフの辺を表す型(始点番号はなし)
field to
Type: Std::I64
終点の頂点番号
field data
Type: c
辺のデータ
Graph
Defined as: type Graph c = unbox struct { ...fields... }
辺を足し終えたグラフ
GraphBuilder::buildで作ります。型パラメータcは辺に付随するデータの型です。
GraphBuilder
Defined as: type GraphBuilder c = unbox struct { ...fields... }
辺を足していく途中のグラフ
型パラメータcは辺に付随するデータの型です(例:ダイクストラ法に使うときはコスト)。不要な場合はユニット型()を指定するとメモリの節約になります。