Skip to content

Latest commit

 

History

History
130 lines (64 loc) · 4.02 KB

moyo_graph.md

File metadata and controls

130 lines (64 loc) · 4.02 KB

Module moyo_graph

マップに関する処理を集めたユーティリティモジュール.

Copyright (c) 2017 DWANGO Co., Ltd. All Rights Reserved.

Data Types

any_error()


any_error() = {error, term()}

graph()


graph() = graph(vertex())

graph()


graph(V) = #{V => [V]}

vertex()


vertex() = term()

vertex_not_found()


vertex_not_found() = {error, {vertex_not_found, vertex()}}

Function Index

dfs_post_order/3有向グラフに対してpost-orderedな深さ優先探索を行う.
graph_with_vertices/2mapで表現されたグラフに、存在しない頂点を追加する.

Function Details

dfs_post_order/3


dfs_post_order(Graph::graph(vertex()), RootVertex::vertex(), VertexFun) -> DFSRet

Graph: map形式で格納されたグラフ.
RootVertex: 探索を開始する頂点.
VertexFun: 訪れた頂点を処理する関数.

有向グラフに対してpost-orderedな深さ優先探索を行う.

Graphは始点=>[終点のリスト]という要素を持つmapで頂点間の接続関係が記述されている.

一度訪問した頂点は訪問対象から除外されるため,結果として行われるのは, RootVertexから到達可能なサブグラフから得られるスパニングツリーに対する探索となる.

post-orderedな探索であるため,葉から先に探索され,次に共通の先祖へと遡ってゆく.

探索された頂点に対しては順次VertexFunが適用される. 兄弟関係にある頂点について適用されたVertexFunの戻り値はlistでコレクションされ, 親の頂点に適用されるVertexFunの第二引数へと渡される.

時間計算量: O(|E|+|V|log|V|), |E|:枝の数, |V|:頂点の数

空間計算量: O(|V|), |V|:頂点の数

graph_with_vertices/2


graph_with_vertices(Graph::graph(vertex()), Vertices::[vertex()]) -> graph(vertex())

Graph: map形式で格納されたグラフ.
Vertices: 追加したい頂点のリスト.

mapで表現されたグラフに、存在しない頂点を追加する.

Graphは頂点=>[頂点のリスト]という要素を持つmapで頂点間の接続関係が記述されている.

追加する頂点は,Verticesとしてリストの形で渡す.

Graphが既に持っている頂点は追加しない.

時間計算量: O(|V|log|Vall|), |V|:追加しようとしている頂点の数, |Vall|:すべての頂点の数

空間計算量: O(|Vall|), |Vall|:すべての頂点の数