Provided by: erlang-manpages_22.2.7+dfsg-1_all

**NAME**

digraph - Directed graphs.

**DESCRIPTION**

This module provides a version of labeled directed graphs ("digraphs"). The digraphs managed by this module are stored inETStables. That implies the following: * Only the process that created the digraph is allowed to update it. * Digraphs will not be garbage collected. The ETS tables used for a digraph will only be deleted whendelete/1is called or the process that created the digraph terminates. * A digraph is a mutable data structure. What makes the graphs provided here non-proper directed graphs is that multiple edges between vertices are allowed. However, the customary definition of directed graphs is used here. * 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 more information. Such information can be attached to the vertices and to the edges of the digraph. An annotated digraph 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 an edge is emanating from v and incident on w, then w is said to be anout-neighborof v, and v is said to be anin-neighborof 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 path P is k-1. * Path P issimpleif all vertices are distinct, except that the first and the last vertices can be the same. * Path 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 without cycles.

**DATA** **TYPES**

d_type()=d_cyclicity()|d_protection()d_cyclicity()= acyclic | cyclicd_protection()= private | protectedgraph()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 =graph()E =edge()V1 = V2 =vertex()Label =label()add_edge_err_rsn()= {bad_edge, Path :: [vertex()]} | {bad_vertex, V ::vertex()}add_edge/5creates (or modifies) edgeEof 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 term['$e'|N], whereNis an integer >= 0.add_edge(G,V1,V2)is equivalent toadd_edge(G,V1,V2,[]). If the edge would create a cycle in anacyclicdigraph,{error,{bad_edge,Path}}is returned. IfGalready has an edge with valueEconnecting a different pair of vertices,{error,{bad_edge,[V1,V2]}}is returned. If either ofV1orV2is not a vertex of digraphG,{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 =graph()V =vertex()Label =label()add_vertex/3creates (or modifies) vertexVof 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 term['$v'|N], whereNis an integer >= 0.del_edge(G,E)->trueTypes: G =graph()E =edge()Deletes edgeEfrom digraphG.del_edges(G,Edges)->trueTypes: G =graph()Edges = [edge()] Deletes the edges in listEdgesfrom digraphG.del_path(G,V1,V2)->trueTypes: G =graph()V1 = V2 =vertex()Deletes edges from digraphGuntil there are nopathsfrom vertexV1to 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 =graph()V =vertex()Deletes vertexVfrom digraphG. Any edgesemanatingfromVorincidentonVare also deleted.del_vertices(G,Vertices)->trueTypes: G =graph()Vertices = [vertex()] Deletes the vertices in listVerticesfrom digraphG.delete(G)->trueTypes: G =graph()Deletes digraphG. This call is important as digraphs are implemented with ETS. There is no garbage collection of ETS tables. However, the digraph is deleted if the process that created the digraph terminates.edge(G,E)->{E,V1,V2,Label}|falseTypes: G =graph()E =edge()V1 = V2 =vertex()Label =label()Returns{E,V1,V2,Label}, whereLabelis thelabelof edgeEemanatingfromV1andincidentonV2of digraphG. If no edgeEof digraphGexists,falseis returned.edges(G)->EdgesTypes: G =graph()Edges = [edge()] Returns a list of all edges of digraphG, in some unspecified order.edges(G,V)->EdgesTypes: G =graph()V =vertex()Edges = [edge()] Returns a list of all edgesemanatingfrom orincidentonVof digraphG, in some unspecified order.get_cycle(G,V)->Vertices|falseTypes: G =graph()V =vertex()Vertices = [vertex(), ...] If asimplecycleof length two or more exists through vertexV, the cycle is returned as a list[V,...,V]of vertices. If aloopthroughVexists, the loop is returned as a list[V]. If no cycles throughVexist,falseis returned.get_path/3is used for finding a simple cycle throughV.get_path(G,V1,V2)->Vertices|falseTypes: G =graph()V1 = V2 =vertex()Vertices = [vertex(), ...] Tries to find asimplepathfrom vertexV1to vertexV2of digraphG. Returns the path as a list[V1,...,V2]of vertices, orfalseif no simple path fromV1toV2of length one or more exists. DigraphGis traversed in a depth-first manner, and the first found path is returned.get_short_cycle(G,V)->Vertices|falseTypes: G =graph()V =vertex()Vertices = [vertex(), ...] Tries to find an as short as possiblesimplecyclethrough vertexVof digraphG. Returns the cycle as a list[V,...,V]of vertices, orfalseif no simple cycle throughVexists. Notice that aloopthroughVis returned as list[V,V].get_short_path/3is used for finding a simple cycle throughV.get_short_path(G,V1,V2)->Vertices|falseTypes: G =graph()V1 = V2 =vertex()Vertices = [vertex(), ...] Tries to find an as short as possiblesimplepathfrom vertexV1to vertexV2of digraphG. Returns the path as a list[V1,...,V2]of vertices, orfalseif no simple path fromV1toV2of length one or more exists. DigraphGis traversed in a breadth-first manner, and the first found path is returned.in_degree(G,V)->integer()>=0Types: G =graph()V =vertex()Returns thein-degreeof vertexVof digraphG.in_edges(G,V)->EdgesTypes: G =graph()V =vertex()Edges = [edge()] Returns a list of all edgesincidentonVof digraphG, in some unspecified order.in_neighbours(G,V)->VertexTypes: G =graph()V =vertex()Vertex = [vertex()] Returns a list of allin-neighborsofVof digraphG, in some unspecified order.info(G)->InfoListTypes: G =graph()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 digraphG. The following pairs are returned: *{cyclicity,Cyclicity}, whereCyclicityiscyclicoracyclic, according to the options given tonew. *{memory,NoWords}, whereNoWordsis the number of words allocated to the ETS tables. *{protection,Protection}, whereProtectionisprotectedorprivate, according to the options given tonew.new()->graph()Equivalent tonew([]).new(Type)->graph()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: Allowscyclesin 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 specified orTypeis not a proper list, abadargexception is raised.no_edges(G)->integer()>=0Types: G =graph()Returns the number of edges of digraphG.no_vertices(G)->integer()>=0Types: G =graph()Returns the number of vertices of digraphG.out_degree(G,V)->integer()>=0Types: G =graph()V =vertex()Returns theout-degreeof vertexVof digraphG.out_edges(G,V)->EdgesTypes: G =graph()V =vertex()Edges = [edge()] Returns a list of all edgesemanatingfromVof digraphG, in some unspecified order.out_neighbours(G,V)->VerticesTypes: G =graph()V =vertex()Vertices = [vertex()] Returns a list of allout-neighborsofVof digraphG, in some unspecified order.vertex(G,V)->{V,Label}|falseTypes: G =graph()V =vertex()Label =label()Returns{V,Label}, whereLabelis thelabelof the vertexVof digraphG, orfalseif no vertexVof digraphGexists.vertices(G)->VerticesTypes: G =graph()Vertices = [vertex()] Returns a list of all vertices of digraphG, in some unspecified order.

**SEE** **ALSO**

digraph_utils(3erl),ets(3erl)