erlang digraph模块

digraph模块是对图结构的一种封装，主要的description请参考http://www.erlang.org/doc/man/digraph.html

下面来看看digraph的一些方法:

图结构无非就是由一些节点和边组成的，在digraph中有个Label的东西，这个其实就是图节点的附加信息，类似在C语言中在一个节点中放个指针，指向一些附加的信息。

那么要创建图，就必须要先创建一些图的基本结构出来

 

new() -> digraph()
new(Type) -> digraph()
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.

 cyclic表示的是有向有环图：如果一个有向图能从某个顶点出发经过若干条边回到该点，则这个图是一个有向有环图

 

 acyclic表示的是有向无环图：如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图

protected表示该图可以被其他进程访问

private表示只能被创建这个图的那个进程访问

那么可以看出图的信息应该是存储在ets表中的

 

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

 这个三个方法就是给某个图增加一个节点上去，同时可以给出这个节点的附带信息Label

 

 

add_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) ->

 这三个方法就是给V1节点和V2节点之间建立一条边，并且给出这个边的附带信息Label

 

 如果在一个有向无环图中创建一条边导致这个图可以构成有环图，那么就会抛出{error,{bad_edge,Path}}的错误，如果V1和V2节点中有任意一个不是图的节点，那么也会抛出{error,{bad_vertex,V}}的错误

还有一些删除图的边以及点，还有一些可以获取图中的点以及边的方法具体请参照官方文档

 

get_cycle(G, V) -> Vertices | false

Types:

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.

 上面的方法是在图中找出一条简单的可以构成环的路径出来，返回中间经过的点，请见例子

 

 

G = digraph:new([cyclic]).
digraph:add_vertex(G,1,{vertex1}).
digraph:add_vertex(G,2,{vertex2}).
digraph:add_vertex(G,3,{vertex3}).
digraph:add_edge(G,1,2).
digraph:add_edge(G,2,3).
digraph:add_edge(G,3,1). 
digraph:get_cycle(G,2). 输出为[2,3,1,2]

 

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

Types:

G = digraph()
V1 = 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.
 在途中找出一条从V1到V2的路径

 

 

digraph:get_path(G,1,2).
[1,2]

 

get_short_cycle(G, V) -> Vertices | false

Types:

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].
 跟get_cycle差不多，只不过这里要最短的环

 

 

 

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

Types:

G = digraph()
V1 = 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.
 与get_path同理

 

 

 

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

Types:

G = digraph()
V = vertex()
Returns the in-degree of the vertex V of the digraph G.
返回一个点的入度数量，图的入度，出度可以查阅图的知识

 

 

digraph:in_degree(G,1).
1

 

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

Types:

G = digraph()
V = vertex()
Returns the out-degree of the vertex V of the digraph G.
 与上面相对应，这个是计算某个节点出度的值

 

 

 

in_neighbours(G, V) -> Vertex

Types:

G = digraph()
V = vertex()
Vertex = [vertex()]
Returns a list of all in-neighbours of V of the digraph G, in some unspecified order.
通俗来说就是返回那些指向节点V的其他节点
digraph:in_neighbours(G,1).
[3]

 

out_neighbours(G, V) -> Vertices

Types:

G = digraph()
V = vertex()
Vertices = [vertex()]
Returns a list of all out-neighbours of V of the digraph G, in some unspecified order.
与上面的相反
digraph:out_neighbours(G,1).
[2]

 

info(G) -> InfoList
Returns a list of {Tag, Value} pairs describing the digraph G. The following pairs are returned:

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

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

{protection, Protection}, where Protection is protected or private, according to the options given to new.
这个方法的作用比较明显，不再累赘

 

erlang还提供digraph_util的工具模块，有兴趣的可以去查看，下面就看看rabbitmq用到了digraph_util的几个方法

方法一

 

reaching(Vertices, Digraph) -> Reaching

Types:

Digraph = digraph()
Vertices = Reaching = [digraph:vertex()]
Returns an unsorted list of digraph vertices such that for each vertex in the list, there is a path from the vertex to some vertex of Vertices. In particular, since paths may have length zero, the vertices of Vertices are included in the returned list.
返回这些节点之间在图中存在有path的点集

 方法二：

 

subgraph(Digraph, Vertices) -> SubGraph
subgraph(Digraph, Vertices, Options) -> SubGraph

Types:

Digraph = SubGraph = digraph()
Vertices = [digraph:vertex()]
Options = [{type, SubgraphType} | {keep_labels, boolean()}]
SubgraphType = inherit | [digraph:d_type()]
Creates a maximal subgraph of Digraph having as vertices those vertices of Digraph that are mentioned in Vertices.

If the value of the option type is inherit, which is the default, then the type of Digraph is used for the subgraph as well. Otherwise the option value of type is used as argument to digraph:new/1.

If the value of the option keep_labels is true, which is the default, then the labels of vertices and edges of Digraph are used for the subgraph as well. If the value is false, then the default label, [], is used for the subgraph's vertices and edges.

subgraph(Digraph, Vertices) is equivalent to subgraph(Digraph, Vertices, []).

There will be a badarg exception if any of the arguments are invalid.
返回这些节点的最大子图，最大子图就是在给出的节点中，从原图中构造出一个节点最多的子图

 方法三

 

topsort(Digraph) -> Vertices | false

Types:

Digraph = digraph()
Vertices = [digraph:vertex()]
Returns a topological ordering of the vertices of the digraph Digraph if such an ordering exists, false otherwise. For each vertex in the returned list, there are no out-neighbours that occur earlier in the list.
即是拓扑排序了。
一个简单的求拓扑排序的算法：首先要找到任意入度为0的一个顶点，删除它及所有相邻的边，再找入度为0的顶点，以此类推，直到删除所有顶点。顶点的删除顺序即为拓扑排序。