digraph_utils

模块

digraph_utils

模块摘要

有向图的算法

描述

该模块提供了基于有向图深度优先遍历的算法.。有关有向图上的基本函数，请参见digraph(3)模块。

• 有向图（或者仅仅是“有向图”）是顶点有限集合V 和有向边（或者仅“边”）的有限集合E的一对（V，E ）。边E的集合是V×V（V与其自身的笛卡尔乘积）的子集。

• 可以使用更多信息对二元符号进行注释。这些信息可以附加到图的顶点和边上。一个带注释的有向图称为带标签的有向图，附加到顶点或边的信息称为标签。

• 边e =（v，w）据说从顶点v 发出并入射在顶点w上。

• 如果一条边从v发出并入射到w上，那么w被认为是v的一个 外部邻居，并且v被认为是w的一个邻居。

• 路径从V1 p来VK在有向图（V，E）是一个非空序列V1，V2，...，顶点VK以V使得存在于E为边缘（VI，VI + 1） 1 <= i <k。

• 路径P 的长度是k-1。

• 如果P的长度不为零并且v1 = vk，则路径P是一个周期。

• 环是长度为1的循环。

• 一个无环有向图是无环有向图。

• 深度优先遍历一个有向图的可以被看作是该访问有向图的所有顶点的处理。最初，所有顶点都被标记为未访问。遍历开始于任意选择的顶点，该顶点标记为已访问，并沿着未标记顶点的边缘标记顶点。然后搜索以相同的方式从该顶点继续，直到没有边缘通向未访问的顶点。此时该过程回溯，并且只要有未经检验的边缘，遍历就会继续。如果在检查到第一个顶点的所有边时检测到未访问的顶点，则选择一些到目前为止未访问的顶点，并重复该过程。

• 部分排序的一组S的是一个传递，反对称，和S的对象之间的自反关系

• 拓扑排序的问题是找到S的全部排序，这是部分排序的超集。有向图G =（V，E）等价于V上的关系E（我们忽略digraph模块提供的有向图的版本允许顶点之间有多个边）。如果有向图没有长度为2或更多的周期，则E的自反和传递闭包是偏序。

• 子图的G G”是有向图的顶点和顶点的边缘形式的子集和G的边缘

• 如果包含G'的顶点的所有其他子图不具有属性P，则G'对于属性P是最大的。

• 强连通分量是最大子图，使得在每对顶点之间的路径。

• 连接成分是最大子图，使得在每对顶点之间的路径，考虑到所有边缘无向。

• 一个树状结构是一个带顶点V的无环有向图，这个根有一条从V到每个其他顶点的唯一路径。

• 一个树是无环非空的有向图，使得在每对顶点之间的唯一路径，考虑所有边缘无方向。

输出

arborescence_root(Digraph) -> no | {yes, Root}

类型

如果Root是树状图Digraph的根，则返回{yes，Root}，否则返回no。

components(Digraph) -> Component

类型

返回一个列表connected components.。每个组件都由其顶点表示。顶点的顺序和组件的顺序是任意的。每个有向图的顶点Digraph恰好出现在一个组件中。

condensation(Digraph) -> CondensedDigraph

类型

创建一个有向图，顶点是由strong_components / 1返回的强有力的连接组件Digraph。 如果X和Y是两个不同的强连通分量，并且顶点x和y分别存在于X和Y中，从而存在从x发出并入射在y上的边缘，则创建从X发出并入射到Y的边缘。

创建的有向图与。的类型相同Digraph。所有的顶点和边都有默认值label []。

每个cycle都包含在一些强连通的组件中，这意味着topological ordering创建的二元图总是存在。

cyclic_strong_components(Digraph) -> StrongComponent

类型

返回强连通组件的列表。 每个强组件都由其顶点表示。 顶点的顺序和组件的顺序是任意的。 只返回Digraph中的某个循环中包含的顶点，否则返回的列表等同于由strong_components / 1返回的列表。

is_acyclic(Digraph) -> boolean()

类型

回报true当且仅当有向图Digraph是acyclic...

is_arborescence(Digraph) -> boolean()

类型

回报true当且仅当有向图Digraph是arborescence...

is_tree(Digraph) -> boolean()

类型

回报true当且仅当有向图Digraph是tree...

loop_vertices(Digraph) -> Vertices

类型

返回Digraph一些包含在其中的所有顶点的列表loop。

postorder(Digraph) -> Vertices

类型

返回有向图的所有顶点Digraph.命令是由depth-first traversal在有向图中，按后序收集访问过的顶点。更准确地说，从任意选择的顶点搜索时访问的顶点是按后序收集的，所有这些收集的顶点都放在随后访问的顶点之前。

preorder(Digraph) -> Vertices

类型

返回有向图的所有顶点Digraph。该顺序由有depth-first traversal向图中的一个给定，以预先顺序收集已访问的顶点。

reachable(Vertices, Digraph) -> Reachable

类型

返回未排序的有向图顶点列表，使得对于列表中的每个顶点path，Digraph从某个顶点Vertices到顶点有一个in 。特别是，由于路径长度为零，因此顶点Vertices将包含在返回的列表中。

reachable_neighbours(Vertices, Digraph) -> Reachable

类型

返回一个未排序的有向图顶点列表，使得对于列表中的每个顶点，有一个从顶点顶点到顶点的Digraph中的一个或多个路径。 因此，只返回包含在某个循环中的顶点的顶点。

reaching(Vertices, Digraph) -> Reaching

类型

返回未排序的有向图顶点列表，使得对于列表中的每个顶点，都有一个path从顶点到顶点的顶点Vertices。特别是，由于路径长度为零，因此顶点Vertices将包含在返回的列表中。

reaching_neighbours(Vertices, Digraph) -> Reaching

类型

返回未排序的有向图顶点列表，使得对于列表中的每个顶点，path从顶点到顶点有一个或多个长度Vertices。因此只有那些顶点Vertices被包含在某些中cycle才会被返回。

strong_components(Digraph) -> StrongComponent

类型

返回strongly connected components.每个强分量都由其顶点表示。顶点的顺序和分量的顺序是任意的。有向图的每个顶点Digraph发生在一个强组件中。

subgraph(Digraph, Vertices) -> SubGraph

subgraph(Digraph, Vertices, Options) -> SubGraph

类型

创建Digraph的最大子图，其顶点是顶点中提到的有向图的顶点。

如果选项类型的值是继承，这是默认值，那么Digraph的类型也用于子图。 否则，类型的选项值将用作有向图的参数：new / 1。

如果选项keep_labels的值为true，这是默认值，则Digraph的顶点和边的标签也会用于子图。 如果该值为false，则默认标签[]用于子组的顶点和边缘。

subgraph(Digraph, Vertices)等于subgraph(Digraph, Vertices, [])...

如果任何参数无效，则badarg引发异常。

topsort(Digraph) -> Vertices | false

类型

如果存在这样的排序，则返回二元图Digraph的顶点的拓扑排序，否则返回false。 对于返回列表中的每个顶点，列表中没有出现过邻居。

另见

digraph(3)