Provided by: erlang-manpages_16.b.3-dfsg-1ubuntu2_all

**NAME**

digraph - Directed Graphs

**DESCRIPTION**

Thedigraphmodule 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. Adirectedgraph(or just "digraph") is a pair (V, E) of a finite set V ofverticesand a finite set E ofdirectededges(or just "edges"). The set of edges E is a subset of V x V (the Cartesian product of V with itself). In this module, V is allowed to be empty; the so obtained unique digraph is called theemptydigraph. Both vertices and edges are represented by unique Erlang terms. 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 alabeleddigraph, and the information attached to a vertex or an edge is called alabel. Labels are Erlang terms. An edge e = (v, w) is said toemanatefrom vertex v and to beincidenton vertex w. Theout-degreeof a vertex is the number of edges emanating from that vertex. Thein-degreeof 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 anout-neighbourof v, and v is said to be anin-neighbourof w. ApathP 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. Thelengthof the path P is k-1. P issimpleif all vertices are distinct, except that the first and the last vertices may be the same. P is acycleif the length of P is not zero and v[1] = v[k]. Aloopis a cycle of length one. Asimplecycleis a path that is both a cycle and simple. Anacyclicdigraphis a digraph that has no cycles.

**DATA** **TYPES**

d_type()=d_cyclicity()|d_protection()d_cyclicity()= acyclic | cyclicd_protection()= private | protecteddigraph()A digraph as returned bynew/0,1.edge()label()= term()vertex()

**EXPORTS**

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)->edge()|{error,add_edge_err_rsn()}Types: G = digraph() E =edge()V1 = V2 =vertex()Label =label()add_edge_err_rsn()= {bad_edge, Path :: [vertex()]} | {bad_vertex, V ::vertex()}add_edge/5creates (or modifies) the edgeEof the digraphG, usingLabelas the (new)labelof the edge. The edge isemanatingfromV1andincidentonV2. ReturnsE.add_edge(G,V1,V2,Label)is equivalent toadd_edge(G,E,V1,V2,Label), whereEis a created edge. The created edge is represented by the term['$e'|N], where N is an integer >= 0.add_edge(G,V1,V2)is equivalent toadd_edge(G,V1,V2,[]). If the edge would create a cycle in anacyclicdigraph, then{error,{bad_edge,Path}}is returned. If either ofV1orV2is not a vertex of the digraphG, then{error,{bad_vertex,V}}is returned, V =V1or V =V2.add_vertex(G)->vertex()add_vertex(G,V)->vertex()add_vertex(G,V,Label)->vertex()Types: G = digraph() V =vertex()Label =label()add_vertex/3creates (or modifies) the vertexVof the digraphG, usingLabelas the (new)labelof the vertex. ReturnsV.add_vertex(G,V)is equivalent toadd_vertex(G,V,[]).add_vertex/1creates 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.del_edge(G,E)->trueTypes: G = digraph() E =edge()Deletes the edgeEfrom the digraphG.del_edges(G,Edges)->trueTypes: G = digraph() Edges = [edge()] Deletes the edges in the listEdgesfrom the digraphG.del_path(G,V1,V2)->trueTypes: G = digraph() V1 = V2 =vertex()Deletes edges from the digraphGuntil there are nopathsfrom the vertexV1to the vertexV2. A sketch of the procedure employed: Find an arbitrarysimplepathv[1], v[2], ..., v[k] fromV1toV2inG. Remove all edges ofGemanatingfrom v[i] andincidentto v[i+1] for 1 <= i < k (including multiple edges). Repeat until there is no path betweenV1andV2.del_vertex(G,V)->trueTypes: G = digraph() V =vertex()Deletes the vertexVfrom the digraphG. Any edgesemanatingfromVorincidentonVare also deleted.del_vertices(G,Vertices)->trueTypes: G = digraph() Vertices = [vertex()] Deletes the vertices in the listVerticesfrom the digraphG.delete(G)->trueTypes: G = digraph() Deletes the digraphG. This call is important because digraphs are implemented withETS. There is no garbage collection ofETStables. The digraph will, however, be deleted if the process that created the digraph terminates.edge(G,E)->{E,V1,V2,Label}|falseTypes: G = digraph() E =edge()V1 = V2 =vertex()Label =label()Returns{E,V1,V2,Label}whereLabelis thelabelof the edgeEemanatingfromV1andincidentonV2of the digraphG. If there is no edgeEof the digraphG, thenfalseis returned.edges(G)->EdgesTypes: G = digraph() Edges = [edge()] Returns a list of all edges of the digraphG, in some unspecified order.edges(G,V)->EdgesTypes: G = digraph() V =vertex()Edges = [edge()] Returns a list of all edgesemanatingfrom orincidentonVof the digraphG, in some unspecified order.get_cycle(G,V)->Vertices|falseTypes: G = digraph() V =vertex()Vertices = [vertex(), ...] If there is asimplecycleof length two or more through the vertexV, then the cycle is returned as a list[V,...,V]of vertices, otherwise if there is aloopthroughV, then the loop is returned as a list[V]. If there are no cycles throughV, thenfalseis returned.get_path/3is used for finding a simple cycle throughV.get_path(G,V1,V2)->Vertices|falseTypes: G = digraph() V1 = V2 =vertex()Vertices = [vertex(), ...] Tries to find asimplepathfrom the vertexV1to the vertexV2of the digraphG. Returns the path as a list[V1,...,V2]of vertices, orfalseif no simple path fromV1toV2of length one or more exists. The digraphGis traversed in a depth-first manner, and the first path found is returned.get_short_cycle(G,V)->Vertices|falseTypes: G = digraph() V =vertex()Vertices = [vertex(), ...] Tries to find an as short as possiblesimplecyclethrough the vertexVof the digraphG. Returns the cycle as a list[V,...,V]of vertices, orfalseif no simple cycle throughVexists. Note that aloopthroughVis returned as the list[V,V].get_short_path/3is used for finding a simple cycle throughV.get_short_path(G,V1,V2)->Vertices|falseTypes: G = digraph() V1 = V2 =vertex()Vertices = [vertex(), ...] Tries to find an as short as possiblesimplepathfrom the vertexV1to the vertexV2of the digraphG. Returns the path as a list[V1,...,V2]of vertices, orfalseif no simple path fromV1toV2of length one or more exists. The digraphGis traversed in a breadth-first manner, and the first path found is returned.in_degree(G,V)->integer()>=0Types: G = digraph() V =vertex()Returns thein-degreeof the vertexVof the digraphG.in_edges(G,V)->EdgesTypes: G = digraph() V =vertex()Edges = [edge()] Returns a list of all edgesincidentonVof the digraphG, in some unspecified order.in_neighbours(G,V)->VertexTypes: G = digraph() V =vertex()Vertex = [vertex()] Returns a list of allin-neighboursofVof the digraphG, in some unspecified order.info(G)->InfoListTypes: G = digraph() InfoList = [{cyclicity, Cyclicity ::d_cyclicity()} | {memory, NoWords :: integer() >= 0} | {protection, Protection ::d_protection()}]d_cyclicity()= acyclic | cyclicd_protection()= private | protected Returns a list of{Tag,Value}pairs describing the digraphG. The following pairs are returned: *{cyclicity,Cyclicity}, whereCyclicityiscyclicoracyclic, according to the options given tonew. *{memory,NoWords}, whereNoWordsis the number of words allocated to theETStables. *{protection,Protection}, whereProtectionisprotectedorprivate, according to the options given tonew.new()->digraph()Equivalent tonew([]).new(Type)->digraph()Types: Type = [d_type()]d_type()=d_cyclicity()|d_protection()d_cyclicity()= acyclic | cyclicd_protection()= private | protected Returns anemptydigraphwith properties according to the options inType:cyclic: Allowcyclesin the digraph (default).acyclic: The digraph is to be keptacyclic.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 optionTis given orTypeis not a proper list, there will be abadargexception.no_edges(G)->integer()>=0Types: G = digraph() Returns the number of edges of the digraphG.no_vertices(G)->integer()>=0Types: G = digraph() Returns the number of vertices of the digraphG.out_degree(G,V)->integer()>=0Types: G = digraph() V =vertex()Returns theout-degreeof the vertexVof the digraphG.out_edges(G,V)->EdgesTypes: G = digraph() V =vertex()Edges = [edge()] Returns a list of all edgesemanatingfromVof the digraphG, in some unspecified order.out_neighbours(G,V)->VerticesTypes: G = digraph() V =vertex()Vertices = [vertex()] Returns a list of allout-neighboursofVof the digraphG, in some unspecified order.vertex(G,V)->{V,Label}|falseTypes: G = digraph() V =vertex()Label =label()Returns{V,Label}whereLabelis thelabelof the vertexVof the digraphG, orfalseif there is no vertexVof the digraphG.vertices(G)->VerticesTypes: G = digraph() Vertices = [vertex()] Returns a list of all vertices of the digraphG, in some unspecified order.

**SEE** **ALSO**

digraph_utils(3erl),ets(3erl)