digraph

Directed Graphs

The digraph module implements a version of labeled directed graphs. What makes the graphs implemented here non-proper directed graphs is that multiple edges between vertices are allowed. However, the customary definition of directed graphs will be used in the text that follows.

digraph模块实现了一个有标签的有向图. 允许顶点之间有多条边使这里实现的图为不完全有向图. 然而, the customary definition of directed graphs will be used in the text that follows.

A directed graph (or just "digraph") is a pair (V, E) of a finite set V of vertices and a finite set E of directed edges (or just "edges"). The set of edges E is a subset of V × V (the Cartesian product of V with itself). In this module, V is allowed to be empty; the so obtained unique digraph is called the empty digraph. Both vertices and edges are represented by unique Erlang terms.

有向图 (或称为"图")是一个由顶点的有限集合V 和有向边 (或称为"边")的有限集合E构成的(V, E)对. 边集合E 是V × V (V和它自身的笛卡尔积)的一个子集. 在这个模块中, V 允许为空; 所以获得的唯一有向图称为 空有向图. 顶点和边都是由唯一的Erlang项表示.

Digraphs can be annotated with additional information. Such information may be attached to the vertices and to the edges of the digraph. A digraph which has been annotated is called a labeled digraph, and the information attached to a vertex or an edge is called a label. Labels are Erlang terms.

有向图可以通过额外的信息来注释. 这样的信息可以加到顶点或者边上. 注释过的图称为标记有向图, 附加到顶点或者边的信息称为 标记. 标记是Erlang项.

An edge e = (v, w) is said to emanate from vertex v and to be incident on vertex w. The out-degree of a vertex is the number of edges emanating from that vertex. The in-degree of a vertex is the number of edges incident on that vertex. If there is an edge emanating from v and incident on w, then w is said to be an out-neighbour of v, and v is said to be an in-neighbour of w. A path P from v[1] to v[k] in a digraph (V, E) is a non-empty sequence v[1], v[2], ..., v[k] of vertices in V such that there is an edge (v[i],v[i+1]) in E for 1 <= i < k. The length of the path P is k-1. P is simple if all vertices are distinct, except that the first and the last vertices may be the same. P is a cycle if the length of P is not zero and v[1] = v[k]. A loop is a cycle of length one. A simple cycle is a path that is both a cycle and simple. An acyclic digraph is a digraph that has no cycles.

e = (v, w) 表示从顶点v发出 传入到顶点w的边. 出度 表示从某顶点发出的边的数量. 入度表示传入到某个顶点的边的数量. 如果有一条边从v发出传入到w, 那么就说w是v的一个 外邻点, v是w的一个内邻点. 图(V, E)上的一条从v[1]到v[k]的路径是一个顶点集合V中的非空序列v[1], v[2], ..., v[k] , 其中对于1 <= i < k存在一条属于集合E的边(v[i],v[i+1]). 路径P的长度为k-1. 除了第一个和最后一个顶点可能相同外，其他顶点都不同的路径称为简单的 如果P的长度不为零且v[1] = v[k]则称P为一个环. 自环 是一个长度为一的环. 一个既是简单的又是环的路径称为简单环. 没有环的图称为无环图.

digraph()

A digraph as returned by new/0,1.

一个由new/0,1返回的图.

 edge() vertex()

Functions:

add_edge(G, V1, V2) -> edge() | {'error', add_edge_err_rsn()}

G = digraph(),
V1 = vertex(),
V2 = vertex()

add_edge(G, V1, V2, Label) -> edge() | {'error', add_edge_err_rsn()}

G = digraph(),
V1 = vertex(),
V2 = vertex(),
Label = label()

add_edge(G, E, V1, V2, Label) -> edge() | {'error', add_edge_err_rsn()}

G = digraph(),
E = edge(),
V1 = vertex(),
V2 = vertex(),
Label = label()

add_edge/5 creates (or modifies) the edge E of the digraph G, using Label as the (new) label of the edge. The edge is emanating from V1 and incident on V2. Returns E.

add_edge/5 使用Label作为(新) 标签 创建(或修改)图 G的边E. 这条边从V1发出 并且 传入 到 V2. 返回E.

add_edge(G, V1, V2, Label) is equivalent to add_edge(G, E, V1, V2, Label), where E is a created edge. The created edge is represented by the term ['$e' | N], where N is an integer >= 0.

add_edge(G, V1, V2, Label) 等同于 add_edge(G, E, V1, V2, Label), where E is a created edge. 创建的边由项['$e' | N]代表, 其中N是大于等于0的整数.

add_edge(G, V1, V2) is equivalent to add_edge(G, V1, V2, []).

add_edge(G, V1, V2) 等同于add_edge(G, V1, V2, []).

If the edge would create a cycle in an acyclic digraph, then {error, {bad_edge, Path}} is returned. If either of V1 or V2 is not a vertex of the digraph G, then {error, {bad_vertex, V}} is returned, V = V1 or V = V2.

如果要边在一个无环图中产生环, 那么返回{error, {bad_edge, Path}}. 如果V1 或 V2不是G的顶点, 则返回{error, {bad_vertex, V}}, V = V1 或 V = V2.

add_vertex(G) -> vertex()

G = digraph()

add_vertex(G, V) -> vertex()

G = digraph(),
V = vertex()

add_vertex(G, V, Label) -> vertex()

G = digraph(),
V = vertex(),
Label = label()

add_vertex/3 creates (or modifies) the vertex V of the digraph G, using Label as the (new) label of the vertex. Returns V.

add_vertex/3 创建(或修改)图G的顶点V , using Label as the (new) label of the vertex. Returns V.

add_vertex(G, V) is equivalent to add_vertex(G, V, []).

add_vertex(G, V) 等同于add_vertex(G, V, []).

add_vertex/1 creates a vertex using the empty list as label, and returns the created vertex. The created vertex is represented by the term ['$v' | N], where N is an integer >= 0.

add_vertex/1 使用空列表作为标签创建一个顶点, 并且返回创建好的顶点. 新顶点由项['$v' | N]表示, 其中N是一个大于等于零的整数.

del_edge(G, E) -> 'true'

G = digraph(),
E = edge()

Deletes the edge E from the digraph G.

从图G中删除边E.

del_edges(G, Edges) -> 'true'

G = digraph(),
Edges = [edge()]

Deletes the edges in the list Edges from the digraph G.

从图G中删除列表Edges从的边 .

del_path(G, V1, V2) -> 'true'

G = digraph(),
V1 = vertex(),
V2 = vertex()

Deletes edges from the digraph G until there are no paths from the vertex V1 to the vertex V2.

从图G中删除边直到从顶点V1到顶点V2不再有路径 .

A sketch of the procedure employed: Find an arbitrary simple path v[1], v[2], ..., v[k] from V1 to V2 in G. Remove all edges of G emanating from v[i] and incident to v[i+1] for 1 <= i < k (including multiple edges). Repeat until there is no path between V1 and V2.

del_vertex(G, V) -> 'true'

G = digraph(),
V = vertex()

Deletes the vertex V from the digraph G. Any edges emanating from V or incident on V are also deleted.

从图G中删除顶点V. 任何从V发出并传入 到 V 的边也被删除.

del_vertices(G, Vertices) -> 'true'

G = digraph(),
Vertices = [vertex()]

Deletes the vertices in the list Vertices from the digraph G.

从图G中删除列表Vertices里的顶点.

delete(G) -> 'true'

G = digraph()

Deletes the digraph G. This call is important because digraphs are implemented with ETS. There is no garbage collection of ETS tables. The digraph will, however, be deleted if the process that created the digraph terminates.

删除图G. 这个调用很重要，因为图是通过ETS实现的. 没有针对ETS表的垃圾回收. 然而，如果创建图的进程终止，那么图也自然被删除.

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

G = digraph(),
E = edge(),
V1 = vertex(),
V2 = vertex(),
Label = label()

Returns {E, V1, V2, Label} where Label is the label of the edge E emanating from V1 and incident on V2 of the digraph G. If there is no edge E of the digraph G, then false is returned.

返回{E, V1, V2, Label} 其中 Label 是图G中从 V1发出并且传入 到 V2的边E的标签. 如果图G中没有边E, 那么返回 false.

edges(G) -> Edges

G = digraph(),
Edges = [edge()]

Returns a list of all edges of the digraph G, in some unspecified order.

以一个列表的形式返回图G的所有边.(列表元素顺序未指定)

edges(G, V) -> Edges

G = digraph(),
V = vertex(),
Edges = [edge()]

Returns a list of all edges emanating from or incident on V of the digraph G, in some unspecified order.

以一个列表的形式返回图G顶点V上所有发出 和传入的边.(列表元素顺序未指定).

get_cycle(G, V) -> Vertices | 'false'

G = digraph(),
V = vertex(),
Vertices = [vertex(),...]

If there is a simple cycle of length two or more through the vertex V, then the cycle is returned as a list [V, ..., V] of vertices, otherwise if there is a loop through V, then the loop is returned as a list [V]. If there are no cycles through V, then false is returned.

如果有一个长度大于等于2的简单环通过顶点V, 那么环以一个顶点的列表[V, ..., V]返回, 否则如果有一个自环 通过 V, 那么自环以一个列表[V]返回. 如果没有环通过V, 则返回false.

get_path/3 is used for finding a simple cycle through V.

get_path/3 用于寻找一个通过V的简单环.

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

G = digraph(),
V1 = vertex(),
V2 = vertex(),
Vertices = [vertex(),...]

Tries to find a simple path from the vertex V1 to the vertex V2 of the digraph G. Returns the path as a list [V1, ..., V2] of vertices, or false if no simple path from V1 to V2 of length one or more exists.

在图G中尝试寻找一个从顶点V1 到顶点V2的简单路径. 以一个顶点列表[V1, ..., V2]的形式返回路径, 或者如果没有从V1 到 V2长度大于等于1的简单路径则返回false.

The digraph G is traversed in a depth-first manner, and the first path found is returned.

以深度优先的方式遍历图G, 并且返回找到的第一条路径.

get_short_cycle(G, V) -> Vertices | 'false'

G = digraph(),
V = vertex(),
Vertices = [vertex(),...]

Tries to find an as short as possible simple cycle through the vertex V of the digraph G. Returns the cycle as a list [V, ..., V] of vertices, or false if no simple cycle through V exists. Note that a loop through V is returned as the list [V, V].

在图G中尝试寻找一个通过V且尽可能短的简单环. 以一个顶点列表[V1, ..., V2]的形式返回路径, 或者如果没有从V1 到 V2长度大于等于1的简单路径则返回false. 注意，一个通过V的自环 以列表[V, V]的形式返回.

get_short_path/3 is used for finding a simple cycle through V.

get_short_path/3用以寻找一个通过V的简单环.

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

G = digraph(),
V1 = vertex(),
V2 = vertex(),
Vertices = [vertex(),...]

Tries to find an as short as possible simple path from the vertex V1 to the vertex V2 of the digraph G. Returns the path as a list [V1, ..., V2] of vertices, or false if no simple path from V1 to V2 of length one or more exists.

在图G中尝试寻找一个从顶点V1 到顶点V2尽可能短的简单路径. 以一个顶点列表[V1, ..., V2]的形式返回路径, 或者如果没有从V1 到 V2长度大于等于1的简单路径则返回false.

The digraph G is traversed in a breadth-first manner, and the first path found is returned.

以广度优先的方式遍历图G, 并且返回找到的第一条路径.

in_degree(G, V) -> non_neg_integer()

G = digraph(),
V = vertex()

Returns the in-degree of the vertex V of the digraph G.

返回图G中顶点V的入度.

in_edges(G, V) -> Edges

G = digraph(),
V = vertex(),
Edges = [edge()]

Returns a list of all edges incident on V of the digraph G, in some unspecified order.

以列表的形式, 返回在图G中顶点V的所有入度.(列表中元素顺序未指定)

in_neighbours(G, V) -> Vertex

G = digraph(),
V = vertex(),
Vertex = [vertex()]

Returns a list of all in-neighbours of V of the digraph G, in some unspecified order.

以列表的形式,返回在图G中顶点V的所有内邻点.(列表元素顺序未指定).

info(G) -> InfoList

G = digraph(),
InfoList = [{'cyclicity', Cyclicity = d_cyclicity()} |
{'memory', NoWords = non_neg_integer()} |
{'protection', Protection = d_protection()}]

Returns a list of {Tag, Value} pairs describing the digraph G. The following pairs are returned:

返回一个{Tag, Value}对的列表来描述图G. 返回下列对:

{cyclicity, Cyclicity}, where Cyclicity is cyclic or acyclic, according to the options given to new.

{cyclicity, Cyclicity}, 其中, 根据给new的选项, Cyclicity 是 cyclic 或 acyclic.

{memory, NoWords}, where NoWords is the number of words allocated to the ETS tables.

{memory, NoWords}, 其中 NoWords 是分配给该ETS表"字"的数量(内存大小).

{protection, Protection}, where Protection is protected or private, according to the options given to new.

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

new() -> digraph()

Equivalent to new([]).

等同于new([]).

new(Type) -> digraph()

Type = [d_type()]

Returns an empty digraph with properties according to the options in Type:

根据以下在Type中的选项返回一个具有相关特性的空图:

cyclic

Allow cycles in the digraph (default).

在图中有环(默认).

acyclic

The digraph is to be kept acyclic.

图将会一直保持无环.

protected

Other processes can read the digraph (default).

其他进程可以读取该图(默认).

private

The digraph can be read and modified by the creating process only.

该图只能由创建它的进程读取和修改.

If an unrecognized type option T is given or Type is not a proper list, there will be a badarg exception.

如果给定一个不可识别的选项T 或者 Type不是一个[TODO]完全列表, 将会产生一个badarg异常.

no_edges(G) -> non_neg_integer()

G = digraph()

Returns the number of edges of the digraph G.

返回图G中边的数量.

no_vertices(G) -> non_neg_integer()

G = digraph()

Returns the number of vertices of the digraph G.

返回图G中顶点的数量.

out_degree(G, V) -> non_neg_integer()

G = digraph(),
V = vertex()

Returns the out-degree of the vertex V of the digraph G.

返回图G中顶点V的出度.

out_edges(G, V) -> Edges

G = digraph(),
V = vertex(),
Edges = [edge()]

Returns a list of all edges emanating from V of the digraph G, in some unspecified order.

以列表的形式, 返回图G中从V发出的所有边.(列表元素顺序未指定).

out_neighbours(G, V) -> Vertices

G = digraph(),
V = vertex(),
Vertices = [vertex()]

Returns a list of all of of the digraph G, in some unspecified order.

以列表的形式, 返回图G中的V所有外邻点.(列表元素顺序未指定)

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

G = digraph(),
V = vertex(),
Label = label()

Returns {V, Label} where Label is the label of the vertex V of the digraph G, or false if there is no vertex V of the digraph G.

返回{V, Label}, 其中 Label是图G中顶点V的标签, 或者, 如果图G中没有顶点V则返回false.

vertices(G) -> Vertices

G = digraph(),
Vertices = [vertex()]

Returns a list of all vertices of the digraph G, in some unspecified order.

以列表的形式, 返回图G的所有顶点.(列表元素顺序未指定)

See Also

digraph_utils(3), ets(3)