檢視原始碼 digraph (stdlib v6.2)
此模組提供有標籤有向圖（"digraphs"）的版本。
此模組管理的有向圖儲存在 ETS 表格中。這意味著以下幾點
- 只有建立有向圖的進程才允許更新它。
- 有向圖不會被垃圾回收。用於有向圖的 ETS 表格只會在呼叫
delete/1或建立有向圖的進程終止時才會被刪除。 - 有向圖是一個可變的資料結構。
這裡提供的圖之所以不是真正的有向圖，是因為允許頂點之間存在多個邊。但是，這裡使用有向圖的習慣定義。
一個有向圖（或簡稱 "digraph"）是一個由有限集合 V 的頂點和有限集合 E 的有向邊（或簡稱 "邊"）組成的對 (V, E)。邊的集合 E 是 V × V（V 與其自身的笛卡爾積）的子集。
在這個模組中，允許 V 為空。由此得到的唯一有向圖稱為空有向圖。頂點和邊都用唯一的 Erlang 項表示。
有向圖可以使用更多資訊來註解。此類資訊可以附加到有向圖的頂點和邊。一個帶註解的有向圖稱為標籤有向圖，附加到頂點或邊的資訊稱為標籤。標籤是 Erlang 項。
邊 e = (v, w) 被稱為從頂點 v發出，並且被入射到頂點 w 上。
一個頂點的出度是從該頂點發出的邊的數量。
一個頂點的入度是入射到該頂點上的邊的數量。
如果一條邊從 v 發出並入射到 w 上，則 w 被稱為 v 的外鄰居，而 v 被稱為 w 的內鄰居。
有向圖 (V, E) 中從 v[1] 到 v[k] 的路徑 P 是一個非空的頂點序列 v[1], v[2], ..., v[k]，使得對於 1 <= i < k，E 中存在一條邊 (v[i], v[i+1])。
路徑 P 的長度是 k-1。
如果所有頂點都不同，則路徑 P 是簡單路徑，但第一個和最後一個頂點可以相同。
如果 P 的長度不為零且 v[1] = v[k]，則路徑 P 是一個循環。
迴路是長度為一的循環。
簡單循環是既是循環又是簡單路徑的路徑。
無環有向圖是沒有循環的有向圖。
另請參閱
摘要
函式
等效於 add_edge(G, E, V1, V2, Label)，其中 E 是建立的邊。
建立一個使用空列表作為標籤的頂點，並傳回建立的頂點。
使用 Label 作為頂點的（新）標籤，建立（或修改）有向圖 G 的頂點 V。傳回新的頂點 V。
從有向圖 G 中刪除邊 E。
從有向圖 G 中刪除列表 Edges 中的邊。
從有向圖 G 中刪除邊，直到沒有從頂點 V1 到頂點 V2 的路徑為止。
從有向圖 G 中刪除列表 Vertices 中的頂點。
刪除有向圖 G。此呼叫很重要，因為有向圖是使用 ETS 實作的。ETS 表格沒有垃圾回收。但是，如果建立有向圖的進程終止，則會刪除該有向圖。
以未指定的順序傳回有向圖 G 的所有邊的列表。
嘗試尋找從有向圖 G 的頂點 V1 到頂點 V2 的簡單路徑。將路徑作為頂點列表 [V1, ..., V2] 傳回，如果不存在從 V1 到 V2 的長度為一或以上的簡單路徑，則傳回 false。
嘗試尋找一個從有向圖 G 的頂點 V1 到頂點 V2 的盡可能短的簡單路徑。將路徑作為一個頂點列表 [V1, ..., V2] 傳回，如果不存在從 V1 到 V2 的長度為一或以上的簡單路徑，則傳回 false。
傳回有向圖 G 的頂點 V 的入度。
以未指定的順序傳回有向圖 G 中所有入射到 V 上的邊的列表。
以未指定的順序傳回有向圖 G 的 V 的所有內鄰居的列表。
傳回一個描述有向圖 G 的 {Tag, Value} 配對的列表。傳回以下配對
傳回有向圖 G 的邊數。
傳回有向圖 G 的頂點數。
傳回有向圖 G 的頂點 V 的出度。
以未指定的順序傳回有向圖 G 中所有從 V發出的邊的列表。
以未指定的順序傳回有向圖 G 的 V 的所有外鄰居的列表。
傳回 {V, Label}，其中 Label 是有向圖 G 的頂點 V 的標籤，如果不存在有向圖 G 的頂點 V，則傳回 false。
以未指定的順序傳回有向圖 G 的所有頂點的列表。
型別
當邊無法新增到圖形時的錯誤原因。
如果該邊會在非循環有向圖中產生一個循環，則會回傳 {error, {bad_edge, Path}}。如果 G 已經存在一個邊，其值為 E，且連接不同的頂點對，則會回傳 {error, {bad_edge, [V1, V2]}}。如果 V1 或 V2 其中之一不是有向圖 G 的頂點，則會回傳 {error, {bad_vertex,V}}，其中 V = V1 或 V = V2。
-type d_cyclicity() :: acyclic | cyclic.
-type d_protection() :: private | protected.
-type d_type() :: d_cyclicity() | d_protection().
-type edge() :: term().
作為邊的識別符或「名稱」。這與附加輔助資訊到邊而非識別邊本身的邊「標籤」不同。
-opaque graph()
由 new/0,1 傳回的有向圖。
-type label() :: term().
-type vertex() :: term().
函式
-spec add_edge(G, V1, V2) -> edge() | {error, add_edge_err_rsn()} when G :: graph(), V1 :: vertex(), V2 :: vertex().
-spec add_edge(G, V1, V2, Label) -> edge() | {error, add_edge_err_rsn()} when G :: graph(), V1 :: vertex(), V2 :: vertex(), Label :: label().
等效於 add_edge(G, E, V1, V2, Label)，其中 E 是建立的邊。
建立的邊以項 ['$e' | N] 表示，其中 N 是一個大於等於 0 的整數。
請參閱 add_edge_err_rsn/0 以了解可能錯誤的詳細資訊。
-spec add_edge(G, E, V1, V2, Label) -> edge() | {error, add_edge_err_rsn()} when G :: graph(), E :: edge(), V1 :: vertex(), V2 :: vertex(), Label :: label().
使用 Label 作為邊的（新）標籤，建立（或修改）有向圖 G 的識別符為 E 的邊。邊從 V1發出並入射到 V2 上。傳回 E。
請參閱 add_edge_err_rsn/0 以了解可能錯誤的詳細資訊。
建立一個使用空列表作為標籤的頂點，並傳回建立的頂點。
建立的頂點以項 ['$v' | N] 表示，其中 N 是一個大於等於 0 的整數。
等效於 add_vertex(G, V, [])。
使用 Label 作為頂點的（新）標籤，建立（或修改）有向圖 G 的頂點 V。傳回新的頂點 V。
從有向圖 G 中刪除邊 E。
從有向圖 G 中刪除列表 Edges 中的邊。
從有向圖 G 中刪除邊，直到沒有從頂點 V1 到頂點 V2 的路徑為止。
所採用程序的簡述
從有向圖 G 中刪除列表 Vertices 中的頂點。
-spec delete(G) -> true when G :: graph().
刪除有向圖 G。此呼叫很重要，因為有向圖是使用 ETS 實作的。ETS 表格沒有垃圾回收。但是，如果建立有向圖的進程終止，則會刪除該有向圖。
-spec edge(G, E) -> {E, V1, V2, Label} | false when G :: graph(), E :: edge(), V1 :: vertex(), V2 :: vertex(), Label :: label().
傳回 {E, V1, V2, Label}，其中 Label 是有向圖 G 中從 V1發出並入射到 V2 上的邊 E 的標籤。如果不存在有向圖 G 的邊 E，則傳回 false。
以未指定的順序傳回有向圖 G 的所有邊的列表。
-spec get_cycle(G, V) -> Vertices | false when G :: graph(), V :: vertex(), Vertices :: [vertex(), ...].
如果存在一個通過頂點 V 的長度為二或更多的簡單循環，則會將循環作為一個頂點列表 [V, ..., V] 傳回。如果存在一個通過 V 的迴路，則會將迴路作為一個列表 [V] 傳回。如果不存在通過 V 的循環，則傳回 false。
get_path/3 用於尋找通過 V 的簡單循環。
-spec get_path(G, V1, V2) -> Vertices | false when G :: graph(), V1 :: vertex(), V2 :: vertex(), Vertices :: [vertex(), ...].
嘗試尋找從有向圖 G 的頂點 V1 到頂點 V2 的簡單路徑。將路徑作為頂點列表 [V1, ..., V2] 傳回，如果不存在從 V1 到 V2 的長度為一或以上的簡單路徑，則傳回 false。
有向圖 G 以深度優先的方式遍歷，並回傳找到的第一條路徑。
-spec get_short_cycle(G, V) -> Vertices | false when G :: graph(), V :: vertex(), Vertices :: [vertex(), ...].
嘗試尋找一個通過有向圖 G 的頂點 V 的盡可能短的簡單循環。將循環作為一個頂點列表 [V, ..., V] 傳回，如果不存在通過 V 的簡單循環，則傳回 false。請注意，通過 V 的迴路會作為列表 [V, V] 傳回。
get_short_path/3 用於尋找通過 V 的簡單循環。
-spec get_short_path(G, V1, V2) -> Vertices | false when G :: graph(), V1 :: vertex(), V2 :: vertex(), Vertices :: [vertex(), ...].
嘗試尋找一個從有向圖 G 的頂點 V1 到頂點 V2 的盡可能短的簡單路徑。將路徑作為一個頂點列表 [V1, ..., V2] 傳回，如果不存在從 V1 到 V2 的長度為一或以上的簡單路徑，則傳回 false。
有向圖 G 以廣度優先的方式遍歷，並回傳找到的第一條路徑。
-spec in_degree(G, V) -> non_neg_integer() when G :: graph(), V :: vertex().
傳回有向圖 G 的頂點 V 的入度。
以未指定的順序傳回有向圖 G 中所有入射到 V 上的邊的列表。
以未指定的順序傳回有向圖 G 的 V 的所有內鄰居的列表。
-spec info(G) -> InfoList when G :: graph(), InfoList :: [{cyclicity, Cyclicity :: d_cyclicity()} | {memory, NoWords :: non_neg_integer()} | {protection, Protection :: d_protection()}].
傳回一個描述有向圖 G 的 {Tag, Value} 配對的列表。傳回以下配對
{cyclicity, Cyclicity}，其中Cyclicity根據給予new的選項，為cyclic或acyclic。{memory, NoWords}，其中NoWords是分配給 ETS 表格的字數。{protection, Protection}，其中Protection根據給予new的選項，為protected或private。
-spec new() -> graph().
等效於 new([])。
根據 Type 中的選項傳回具有屬性的空有向圖
cyclic- 允許有向圖中存在循環（預設）。acyclic- 有向圖將保持非循環。protected- 其他處理程序可以讀取有向圖（預設）。private- 有向圖只能由建立它的處理程序讀取和修改。
如果指定了無法識別的類型選項 T 或 Type 不是正確的列表，則會引發 badarg 例外。
-spec no_edges(G) -> non_neg_integer() when G :: graph().
傳回有向圖 G 的邊數。
-spec no_vertices(G) -> non_neg_integer() when G :: graph().
傳回有向圖 G 的頂點數。
-spec out_degree(G, V) -> non_neg_integer() when G :: graph(), V :: vertex().
傳回有向圖 G 的頂點 V 的出度。
以未指定的順序傳回有向圖 G 中所有從 V發出的邊的列表。
以未指定的順序傳回有向圖 G 的 V 的所有外鄰居的列表。
傳回 {V, Label}，其中 Label 是有向圖 G 的頂點 V 的標籤，如果不存在有向圖 G 的頂點 V，則傳回 false。
以未指定的順序傳回有向圖 G 的所有頂點的列表。