edge_input
クラス · 辺の列を読み込んで保持する入力中間型
template <class T>
struct edge_input;
概要
辺の列を読み込んで保持する入力中間型
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
T |
辺の重みの型。void で重みなし（入力から重みを読まない）。 標準入力から (from, to[, weight]) を origin 補正して読み込み、 グラフ表現に依存しない生の辺データとして保持する。 build_directed(graph) / build_undirected(graph) で任意のグラフ型に 流し込める（add_edge / add_edges を持つ型なら何でも受け取れる）。 |
計算量
- 辺数を $E$ として入力・構築は $O(E)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空の辺列を構築する (2) 標準入力から m 本の辺を読み込む（頂点番号は origin から） |
(1) $O(1)$ (2) $O(m)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
input |
標準入力から m 本の辺を追加で読み込む | $O(m)$ |
emplace |
1 本の辺を追加する | 償却 $O(1)$ |
size |
保持する辺数を返す | $O(1)$ |
begin |
先頭iteratorを返す | $O(1)$ |
end |
終端iteratorを返す | $O(1)$ |
build_directed |
有向辺として graph に流し込む（add_edge を呼ぶ） | $O(E)$ |
build_undirected |
無向辺として graph に流し込む（add_edges を呼ぶ） | $O(E)$ |
to_directed |
n 頂点の有向グラフを構築して返す | $O(V+E)$ |
to_undirected |
n 頂点の無向グラフを構築して返す | $O(V+E)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
i番目の辺を返す | $O(1)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
weight_type |
重みの実体型 | 型エイリアスで実行時計算量はない |
raw_edge |
入力した1本の辺 | データ型で実行時計算量はない |
メンバ変数
| 名前 | 説明 | 計算量 |
|---|---|---|
weighted |
— | コンパイル時定数で実行時計算量はない |
メンバの詳細
(constructor)
// (1)
edge_input() = default;
// (2)
explicit edge_input(int m, int origin = 1);
(1) 空の辺列を構築する
- 計算量: $O(1)$
(2) 標準入力から m 本の辺を読み込む（頂点番号は origin から）
- 計算量: $O(m)$
to_directed
template <template <class> class GraphT = csr_graph>
GraphT<T> to_directed(int n) const;
n 頂点の有向グラフを構築して返す
- テンプレートパラメータ
GraphT: 構築するグラフ型テンプレート（csr_graph（既定）/list_graph）csr_graphの場合は辺数（有向辺 = m 本）を予約してからbuild()まで行う。 - 計算量: $O(V+E)$
to_undirected
template <template <class> class GraphT = csr_graph>
GraphT<T> to_undirected(int n) const;
n 頂点の無向グラフを構築して返す
- テンプレートパラメータ
GraphT: 構築するグラフ型テンプレート（csr_graph（既定）/list_graph）csr_graphの場合は辺数（辺 ID = m 個・有向辺 = 2m 本）を予約してからbuild()まで行う。 - 計算量: $O(V+E)$
raw_edge
struct raw_edge;
入力した1本の辺
- 計算量: データ型で実行時計算量はない
| メンバ | 説明 |
|---|---|
to |
辺の始点と終点 |
weight |
辺の重み |
weighted
static constexpr bool weighted = !std::is_void_v<T>;
重みの実体型: void は空タグ Unweighted に正規化する
- 計算量: コンパイル時定数で実行時計算量はない