非常教程

Erlang 20参考手册

stdlib

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

 edge()| {error,add_edge_err_rsn()} Typesadd_edge / 5创建(或修改)图G的边E,使用Label作为边的(新)标签。边缘从V1发出并入射到V2。返回E.add_edge(G,V1,V2,Label)等价于add_edge(G,E,V1,V2,Label),其中E是创建的边。创建的边缘由术语['$ e'|表示N],其中N是> = 0.add_edge(G,V1,V2)的整数等于add_edge(G,V1,V2,[])。如果边在非循环有向图中创建循环,则返回{error,{bad_edge,Path}}。如果V1或V2中的任一个不是图G的顶点,则返回{error,{bad_vertex,V}},V = V1或V = V2.add_vertex(G) - > vertex()add_vertex(G,V) - > vertex()add_vertex(G,V,Label) - > vertex()Typesadd_vertex / 3创建(或修改)图G的顶点V,使用Label作为顶点的(新)标签。返回V.add_vertex(G,V)等价于add_vertex(G,V,[])。 add_vertex / 1使用空列表作为标签创建顶点,并返回创建的顶点。创建的顶点由term ['$ v'|表示N,其中N是> = 0的整数.del_edge(G,E) - > trueTypes根据图G删除边E.del_edges(G,Edges) - > trueTypes从图Gdedel_path(G,V1 ,V2) - > trueTypes删除图G的边,直到没有从顶点V1到顶点V2的路径。所用过程的草图:

  • 找到一个任意的simple pathv1,v2,...,vk from V1to V2in G
  • 删除G emanatingvi和incidentvi + 1的所有边,1 <= i <k(包括多条边)。
  • 重复,直到V1V2之间没有路径。

del_vertex(G, V) -> true

类型

V从有向图中删除顶点G。任何边缘emanatingVincidentV也被删除。

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},其中Labellabel边缘的E emanating距离V1,并incidentV2有向图的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如果没有简单的路径,从V1V2长一个或多个存在的。

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},其中Protectionprotectedprivate,根据给予的选项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)

Erlang 20

Erlang 是一种通用的面向并发的编程语言,可应付大规模开发活动的程序设计语言和运行环境。

主页 https://www.erlang.org/
源码 https://github.com/erlang/otp
版本 20
发布版本 20.1