digraph

模块

digraph

模块摘要

有向图

描述

这个模块提供了一个有向标签图的版本。这里提供的图的非真有向图的原因是允许顶点之间有多条边。然而，这里使用了有向图的习惯定义。

有向图（或者仅仅是“有向图”）是顶点有限集合V 和有向边（或者仅“边”）的有限集合E的一对（V，E ）。边E的集合是V×V（V与其自身的笛卡尔乘积）的子集。在这个模块中，V被允许为空。如此获得的独特有向图被称为空有向图。顶点和边都由独特的Erlang术语表示。

有向图可以用更多的信息进行注释。这些信息可以附加到顶点和有向图的边缘。带注释的有向图称为标号有向图，而附加在顶点或边缘上的信息称为标签标签是Erlang术语。

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

顶点的出度是从顶点发出的边的数量。

所述入度顶点的是边缘入射在该顶点的数目。

如果边是从v发出的，并且在w上入射，那么w就是外邻v的，v被说成是近邻我们的。

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

路径P 的长度是k-1。

如果所有顶点都不同，则路径P很简单，除了第一个和最后一个顶点可以相同。

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

环是长度为1的循环。

一个简单的周期是既是一个周期和简单的路径。

非循环有向图是没有循环的有向图。数据类型d_type（）= d_cyclicity（）| d_protection（）d_cyclicity（）= acyclic |循环d_protection（）= private | protected graph（）由new / 0,1返回的有向图。 edge（）label（）= term（）vertex（）Exportsadd_edge（G，V1，V2） - > edge（）| {error，add_edge_err_rsn（）} add_edge（G，V1，V2，Label） - > edge（）| {error，add_edge_err_rsn（）} add_edge（G，E，V1，V2，Label） - >

找到一个任意的simple pathv1，v2，...，vk from V1to V2in G。

删除G emanatingvi和incidentvi + 1的所有边，1 <= i <k（包括多条边）。

重复，直到V1和V2之间没有路径。

del_vertex(G, V) -> true

类型

V从有向图中删除顶点G。任何边缘emanating的V或incident上V也被删除。

del_vertices(G, Vertices) -> true

类型

Vertices从有向图中删除列表中的顶点G。

delete(G) -> true

类型

删除图G。这个调用是重要的，因为有向图是用ETS实现的。没有ETS表的垃圾回收。但是，如果创建有向图的过程终止，则该有向图将被删除。

edge(G, E) -> {E, V1, V2, Label} | false

类型

返回{E, V1, V2, Label}，其中Label是label边缘的E emanating距离V1，并incident在V2有向图的G。如果E图的边缘不G存在，false则返回。

edges(G) -> Edges

类型

G以某种未指定的顺序返回有向图的所有边的列表。

edges(G, V) -> Edges

类型

以某种未指定的顺序返回从图G发出或发生的所有边的列表。

get_cycle(G, V) -> Vertices | false

类型

如果通过顶点V存在一个长度为两个或更多的简单循环，则循环返回为顶点的列表[V，...，V]。如果存在一个通过V的循环，则循环返回为列表[V]。如果不存在通过V的循环，则返回false。

get_path/3用于寻找简单的循环V。

get_path(G, V1, V2) -> Vertices | false

类型

尝试找到从图G的顶点V1到顶点V2的简单路径。返回顶点列表[V1，...，V2]的路径，如果不存在长度为1或更长的从V1到V2的简单路径，则返回false。

有向图G以深度优先的方式遍历，并返回第一个找到的路径。

get_short_cycle(G, V) -> Vertices | false

类型

尝试通过图G的顶点V找到尽可能短的简单循环。将循环作为顶点的列表[V，...，V]返回，如果不存在通过V的简单循环，则返回false。请注意，通过V的循环以列表[V，V]的形式返回。

get_short_path/3用于查找一个简单的循环。V...

get_short_path(G, V1, V2) -> Vertices | false

类型

尝试simple path从有向图的顶点V1到顶点找到尽可能短V2的点G。返回路径列表[V1, ..., V2]顶点，或者false如果没有简单的路径，从V1以V2长一个或多个存在的。

Digraph G以宽度优先的方式遍历，并返回第一个找到的路径。

in_degree(G, V) -> integer() >= 0

类型

返回图G的顶点V的入度。

in_edges(G, V) -> Edges

类型

返回图G中V的所有边的列表，以某种未指定的顺序。

in_neighbours(G, V) -> Vertex

类型

以某种未指定的顺序返回图G的V的所有内部邻居列表。

info(G) -> InfoList

类型

返回描述图G的{Tag，Value}对的列表。将返回以下对：

{循环性，循环性}，其中循环性是循环性的或非循环性的，根据赋予新的选项。

{memory, NoWords}，其中NoWords分配给ETS表格的单词数量。

{protection, Protection}，其中Protection是protected或private，根据给予的选项new。

new() -> graph()

相当于new([])...

new(Type) -> graph()

类型

根据Type中的选项返回具有属性的空白有向图：

cyclic

允许cycles有向图（默认）。

acyclic

该有向图应保持非循环。

protected

其他进程可以读取有向图（默认）。

private

只有创建过程才能读取和修改有向图。

如果T指定了无法识别的类型选项或者Type不是正确的列表，则会引发异常badarg。

no_edges(G) -> integer() >= 0

类型

返回图G的边数。

no_vertices(G) -> integer() >= 0

类型

返回图G的顶点数。

out_degree(G, V) -> integer() >= 0

类型

返回out-degree顶点V有向图G...

out_edges(G, V) -> Edges

类型

返回所有边emanating的列表。从V有向图中G，在一些未指定的顺序。

out_neighbours(G, V) -> Vertices

类型

以某种未指定的顺序返回图G的所有V的邻居列表。

vertex(G, V) -> {V, Label} | false

类型

返回{V，Label}，其中Label是图G的顶点V的标签，如果图G的顶点V不存在，则返回false。

vertices(G) -> Vertices

类型

返回有向图的所有顶点的列表。G，以某种未指明的顺序。

另见

digraph_utils(3)，ets(3)