查看源代码 digraph_utils (stdlib v6.2)
此模块提供了基于有向图深度优先遍历的算法。
有关有向图的基本函数，请参见 digraph 模块。
- 一个有向图（或简称“digraph”）是一个由有限的顶点集合 V 和有限的有向边（或简称“边”）集合 E 组成的对 (V, E)。边集合 E 是 V × V 的子集（V 与自身的笛卡尔积）。
- 有向图可以使用更多信息进行注释。这些信息可以附加到有向图的顶点和边。带注释的有向图称为标记有向图，附加到顶点或边的信息称为标签。
- 一条边 e = (v, w) 被称为从顶点 v发出，并入射到顶点 w。
- 如果一条边从 v 发出并入射到 w，则 w 被称为 v 的出邻居，v 被称为 w 的入邻居。
- 一个路径 P 从有向图 (V, E) 中的 v[1] 到 v[k]，是一个非空的顶点序列 v[1], v[2], ..., v[k]，且对于 1 <= i < k，在 E 中存在边 (v[i],v[i+1])。
- 路径 P 的长度为 k-1。
- 如果 P 的长度不为零且 v[1] = v[k]，则路径 P 是一个环。
- 一个自环是长度为 1 的环。
- 一个无环有向图是没有环的有向图。
- 有向图的深度优先遍历可以看作是访问有向图所有顶点的过程。最初，所有顶点都被标记为未访问。遍历从任意选择的顶点开始，该顶点被标记为已访问，并沿着边到达一个未标记的顶点，标记该顶点。然后，搜索以相同的方式从该顶点继续进行，直到没有通往未访问顶点的边。此时，该过程回溯，并且只要存在未检查的边，遍历就会继续。如果当检查完第一个顶点的所有边后，仍有未访问的顶点，则选择一些目前未访问的顶点，并重复该过程。
- 集合 S 的偏序是 S 对象之间的一种传递性、反对称性和自反性关系。
- 拓扑排序的问题是找到 S 的全序，它是偏序的超集。有向图 G = (V, E) 等价于 V 上的关系 E（我们忽略了
digraph模块提供的有向图版本允许顶点之间存在多条边）。如果该有向图没有长度为 2 或更大的环，则 E 的自反和传递闭包是偏序。 - G 的一个子图 G' 是一个有向图，其顶点和边形成 G 的顶点和边的子集。
- 如果所有包含 G' 顶点的其他子图都不具有属性 P，则 G' 对于属性 P 是最大的。
- 一个强连通分量是一个最大子图，使得每对顶点之间都存在一条路径。
- 一个连通分量是一个最大子图，使得每对顶点之间都存在一条路径，将所有边视为无向边。
- 一个树形图是一个无环有向图，它有一个顶点 V，即根，使得从 V 到 G 的每个其他顶点都存在唯一的路径。
- 一个树是一个非空无环有向图，使得每对顶点之间都存在唯一的路径，将所有边视为无向边。
另请参阅
摘要
函数
如果 Root 是树形图 Digraph 的根，则返回 {yes, Root}，否则返回 no。
返回连通分量的列表。每个分量都由其顶点表示。顶点和分量的顺序是任意的。Digraph 的每个顶点都恰好出现在一个分量中。
创建一个有向图，其中顶点是由 strong_components/1 返回的 Digraph 的强连通分量。如果 X 和 Y 是两个不同的强连通分量，并且分别存在于 X 和 Y 中的顶点 x 和 y，使得存在从 x 发出并入射到 y 的边，则创建一条从 X 发出并入射到 Y 的边。
返回强连通分量的列表。每个强连通分量都由其顶点表示。顶点和分量的顺序是任意的。只返回包含在 Digraph 的某个环中的顶点，否则返回的列表与 strong_components/1 返回的列表相同。
当且仅当有向图 Digraph 是无环时，返回 true。
当且仅当有向图 Digraph 是树形图时，返回 true。
当且仅当有向图 Digraph 是一棵树时，返回 true。
返回 Digraph 中包含在某个自环中的所有顶点的列表。
返回有向图 Digraph 的所有顶点。顺序由有向图的深度优先遍历给出，以后序收集访问的顶点。更准确地说，从任意选择的顶点搜索时访问的顶点以后序收集，并且所有收集的顶点都放在后续访问的顶点之前。
返回有向图 Digraph 的所有顶点。顺序由有向图的深度优先遍历给出，以前序收集访问的顶点。
返回一个有向图顶点的无序列表，使得对于列表中的每个顶点，在 Digraph 中都存在从 Vertices 的某个顶点到该顶点的路径。特别是，由于路径的长度可以为零，因此 Vertices 的顶点包含在返回的列表中。
返回一个有向图顶点的无序列表，使得对于列表中的每个顶点，都存在从该顶点到 Vertices 的某个顶点的路径。特别是，由于路径的长度可以为零，因此 Vertices 的顶点包含在返回的列表中。
返回强连通分量的列表。每个强连通分量都由其顶点表示。顶点和分量的顺序是任意的。Digraph 的每个顶点都恰好出现在一个强连通分量中。
创建 Digraph 的最大子图，其顶点为 Vertices 中提到的 Digraph 的顶点。
函数
-spec arborescence_root(Digraph) -> no | {yes, Root} when Digraph :: digraph:graph(), Root :: digraph:vertex().
如果 Root 是树形图 Digraph 的根，则返回 {yes, Root}，否则返回 no。
-spec components(Digraph) -> [Component] when Digraph :: digraph:graph(), Component :: [digraph:vertex()].
返回连通分量的列表。每个分量都由其顶点表示。顶点和分量的顺序是任意的。Digraph 的每个顶点都恰好出现在一个分量中。
-spec condensation(Digraph) -> CondensedDigraph when Digraph :: digraph:graph(), CondensedDigraph :: digraph:graph().
创建一个有向图，其中顶点是由 strong_components/1 返回的 Digraph 的强连通分量。如果 X 和 Y 是两个不同的强连通分量，并且分别存在于 X 和 Y 中的顶点 x 和 y，使得存在从 x 发出并入射到 y 的边，则创建一条从 X 发出并入射到 Y 的边。
创建的有向图与 Digraph 具有相同的类型。所有顶点和边都具有默认的标签 []。
-spec cyclic_strong_components(Digraph) -> [StrongComponent] when Digraph :: digraph:graph(), StrongComponent :: [digraph:vertex()].
返回强连通分量的列表。每个强连通分量都由其顶点表示。顶点和分量的顺序是任意的。只返回包含在 Digraph 的某个环中的顶点，否则返回的列表与 strong_components/1 返回的列表相同。
-spec is_acyclic(Digraph) -> boolean() when Digraph :: digraph:graph().
当且仅当有向图 Digraph 是无环时，返回 true。
-spec is_arborescence(Digraph) -> boolean() when Digraph :: digraph:graph().
当且仅当有向图 Digraph 是树形图时，返回 true。
-spec is_tree(Digraph) -> boolean() when Digraph :: digraph:graph().
当且仅当有向图 Digraph 是一棵树时，返回 true。
-spec loop_vertices(Digraph) -> Vertices when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()].
返回 Digraph 中包含在某个自环中的所有顶点的列表。
-spec postorder(Digraph) -> Vertices when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()].
返回有向图 Digraph 的所有顶点。顺序由有向图的深度优先遍历给出，以后序收集访问的顶点。更准确地说，从任意选择的顶点搜索时访问的顶点以后序收集，并且所有收集的顶点都放在后续访问的顶点之前。
-spec preorder(Digraph) -> Vertices when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()].
返回有向图 Digraph 的所有顶点。顺序由有向图的深度优先遍历给出，以前序收集访问的顶点。
-spec reachable(Vertices, Digraph) -> Reachable when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], Reachable :: [digraph:vertex()].
返回一个有向图顶点的无序列表，使得对于列表中的每个顶点，在 Digraph 中都存在从 Vertices 的某个顶点到该顶点的路径。特别是，由于路径的长度可以为零，因此 Vertices 的顶点包含在返回的列表中。
-spec reachable_neighbours(Vertices, Digraph) -> Reachable when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], Reachable :: [digraph:vertex()].
返回一个有向图顶点的无序列表，使得对于列表中的每个顶点，在 Digraph 中都存在从 Vertices 的某个顶点到该顶点的长度为一个或多个的路径。因此，只返回包含在某个环中的 Vertices 的顶点。
-spec reaching(Vertices, Digraph) -> Reaching when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], Reaching :: [digraph:vertex()].
返回一个有向图顶点的无序列表，使得对于列表中的每个顶点，都存在从该顶点到 Vertices 的某个顶点的路径。特别是，由于路径的长度可以为零，因此 Vertices 的顶点包含在返回的列表中。
-spec reaching_neighbours(Vertices, Digraph) -> Reaching when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], Reaching :: [digraph:vertex()].
返回一个有向图顶点的无序列表，使得对于列表中的每个顶点，都存在从该顶点到 Vertices 的某个顶点的长度为一个或多个的路径。因此，只返回包含在某个环中的 Vertices 的顶点。
-spec strong_components(Digraph) -> [StrongComponent] when Digraph :: digraph:graph(), StrongComponent :: [digraph:vertex()].
返回强连通分量的列表。每个强连通分量都由其顶点表示。顶点和分量的顺序是任意的。Digraph 的每个顶点都恰好出现在一个强连通分量中。
-spec subgraph(Digraph, Vertices) -> SubGraph when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()], SubGraph :: digraph:graph().
等价于 subgraph/3。
-spec subgraph(Digraph, Vertices, Options) -> SubGraph when Digraph :: digraph:graph(), SubGraph :: digraph:graph(), Vertices :: [digraph:vertex()], Options :: [{type, SubgraphType} | {keep_labels, boolean()}], SubgraphType :: inherit | [digraph:d_type()].
创建 Digraph 的最大子图，其顶点为 Vertices 中提到的 Digraph 的顶点。
如果选项 type 的值为 inherit（默认值），则子图也使用 Digraph 的类型。否则，选项 type 的值将用作 digraph:new/1 的参数。
如果选项 keep_labels 的值为 true（默认值），则 Digraph 的顶点和边的标签也用于子图。如果该值为 false，则默认标签 [] 将用于子图的顶点和边。
subgraph(Digraph, Vertices) 等价于 subgraph(Digraph, Vertices, [])。
如果任何参数无效，则会引发 badarg 异常。
-spec topsort(Digraph) -> Vertices | false when Digraph :: digraph:graph(), Vertices :: [digraph:vertex()].
如果存在这样的排序，则返回有向图 Digraph 顶点的拓扑排序，否则返回 false。对于返回列表中的每个顶点，列表中较早出现的位置没有出邻居。