# FreeBSD Manual Pages

digraph_utils(3) Erlang Module Definition digraph_utils(3)NAMEdigraph_utils - Algorithms for directed graphs.DESCRIPTIONThis module provides algorithms based on depth-first traversal of di- rected graphs. For basic functions on directed graphs, see thedi-graph(3)module. * 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). * 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. * An edge e = (v, w) is said toemanatefrom vertex v and to beinci-denton vertex w. * 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 se- quence 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 is acycleif the length of P is not zero and v[1] = v[k]. * Aloopis a cycle of length one. * Anacyclicdigraphis a digraph without cycles. * Adepth-firsttraversalof a directed digraph can be viewed as a process that visits all vertices of the digraph. Initially, all vertices are marked as unvisited. The traversal starts with an ar- bitrarily chosen vertex, which is marked as visited, and follows an edge to an unmarked vertex, marking that vertex. The search then proceeds from that vertex in the same fashion, until there is no edge leading to an unvisited vertex. At that point the process backtracks, and the traversal continues as long as there are unex- amined edges. If unvisited vertices remain when all edges from the first vertex have been examined, some so far unvisited vertex is chosen, and the process is repeated. * Apartialorderingof a set S is a transitive, antisymmetric, and reflexive relation between the objects of S. * The problem oftopologicalsortingis to find a total ordering of S that is a superset of the partial ordering. A digraph G = (V, E) is equivalent to a relation E on V (we neglect that the version of di- rected graphs provided by thedigraphmodule allows multiple edges between vertices). If the digraph has no cycles of length two or more, the reflexive and transitive closure of E is a partial order- ing. * AsubgraphG' of G is a digraph whose vertices and edges form sub- sets of the vertices and edges of G. * G' ismaximalwith respect to a property P if all other subgraphs that include the vertices of G' do not have property P. * Astronglyconnectedcomponentis a maximal subgraph such that there is a path between each pair of vertices. * Aconnectedcomponentis a maximal subgraph such that there is a path between each pair of vertices, considering all edges undi- rected. * Anarborescenceis an acyclic digraph with a vertex V, theroot, such that there is a unique path from V to every other vertex of G. * Atreeis an acyclic non-empty digraph such that there is a unique path between every pair of vertices, considering all edges undi- rected.EXPORTSarborescence_root(Digraph)->no|{yes,Root}Types: Digraph =digraph:graph()Root =digraph:vertex()Returns{yes,Root}ifRootis therootof the arborescenceDi-graph, otherwiseno.components(Digraph)->[Component]Types: Digraph =digraph:graph()Component = [digraph:vertex()] Returns a list ofconnectedcomponents.. Each component is rep- resented by its vertices. The order of the vertices and the or- der of the components are arbitrary. Each vertex of digraphDi-graphoccurs in exactly one component.condensation(Digraph)->CondensedDigraphTypes: Digraph = CondensedDigraph =digraph:graph()Creates a digraph where the vertices are thestronglyconnectedcomponentsofDigraphas returned bystrong_components/1. If X and Y are two different strongly connected components, and ver- tices x and y exist in X and Y, respectively, such that there is an edgeemanatingfrom x andincidenton y, then an edge emanat- ing from X and incident on Y is created. The created digraph has the same type asDigraph. All vertices and edges have the defaultlabel[]. Eachcycleis included in some strongly connected component, which implies that atopologicalorderingof the created digraph always exists.cyclic_strong_components(Digraph)->[StrongComponent]Types: Digraph =digraph:graph()StrongComponent = [digraph:vertex()] Returns a list ofstronglyconnectedcomponents. Each strongly component is represented by its vertices. The order of the ver- tices and the order of the components are arbitrary. Only ver- tices that are included in somecycleinDigraphare returned, otherwise the returned list is equal to that returned bystrong_components/1.is_acyclic(Digraph)->boolean()Types: Digraph =digraph:graph()Returnstrueif and only if digraphDigraphisacyclic.is_arborescence(Digraph)->boolean()Types: Digraph =digraph:graph()Returnstrueif and only if digraphDigraphis anarborescence.is_tree(Digraph)->boolean()Types: Digraph =digraph:graph()Returnstrueif and only if digraphDigraphis atree.loop_vertices(Digraph)->VerticesTypes: Digraph =digraph:graph()Vertices = [digraph:vertex()] Returns a list of all vertices ofDigraphthat are included in someloop.postorder(Digraph)->VerticesTypes: Digraph =digraph:graph()Vertices = [digraph:vertex()] Returns all vertices of digraphDigraph. The order is given by adepth-firsttraversalof the digraph, collecting visited ver- tices in postorder. More precisely, the vertices visited while searching from an arbitrarily chosen vertex are collected in postorder, and all those collected vertices are placed before the subsequently visited vertices.preorder(Digraph)->VerticesTypes: Digraph =digraph:graph()Vertices = [digraph:vertex()] Returns all vertices of digraphDigraph. The order is given by adepth-firsttraversalof the digraph, collecting visited ver- tices in preorder.reachable(Vertices,Digraph)->ReachableTypes: Digraph =digraph:graph()Vertices = Reachable = [digraph:vertex()] Returns an unsorted list of digraph vertices such that for each vertex in the list, there is apathinDigraphfrom some vertex ofVerticesto the vertex. In particular, as paths can have length zero, the vertices ofVerticesare included in the re- turned list.reachable_neighbours(Vertices,Digraph)->ReachableTypes: Digraph =digraph:graph()Vertices = Reachable = [digraph:vertex()] Returns an unsorted list of digraph vertices such that for each vertex in the list, there is apathinDigraphof length one or more from some vertex ofVerticesto the vertex. As a conse- quence, only those vertices ofVerticesthat are included in somecycleare returned.reaching(Vertices,Digraph)->ReachingTypes: Digraph =digraph:graph()Vertices = Reaching = [digraph:vertex()] Returns an unsorted list of digraph vertices such that for each vertex in the list, there is apathfrom the vertex to some ver- tex ofVertices. In particular, as paths can have length zero, the vertices ofVerticesare included in the returned list.reaching_neighbours(Vertices,Digraph)->ReachingTypes: Digraph =digraph:graph()Vertices = Reaching = [digraph:vertex()] Returns an unsorted list of digraph vertices such that for each vertex in the list, there is apathof length one or more from the vertex to some vertex ofVertices. Therefore only those ver- tices ofVerticesthat are included in somecycleare returned.strong_components(Digraph)->[StrongComponent]Types: Digraph =digraph:graph()StrongComponent = [digraph:vertex()] Returns a list ofstronglyconnectedcomponents. Each strongly component is represented by its vertices. The order of the ver- tices and the order of the components are arbitrary. Each vertex of digraphDigraphoccurs in exactly one strong component.subgraph(Digraph,Vertices)->SubGraphsubgraph(Digraph,Vertices,Options)->SubGraphTypes: Digraph = SubGraph =digraph:graph()Vertices = [digraph:vertex()] Options = [{type, SubgraphType} | {keep_labels, boolean()}] SubgraphType = inherit | [digraph:d_type()] Creates a maximalsubgraphofDigraphhaving as vertices those vertices ofDigraphthat are mentioned inVertices. If the value of optiontypeisinherit, which is the default, the type ofDigraphis used for the subgraph as well. Otherwise the option value oftypeis used as argument todigraph:new/1. If the value of optionkeep_labelsistrue, which is the de- fault, thelabelsof vertices and edges ofDigraphare used for the subgraph as well. If the value isfalse, default label[]is used for the vertices and edges of the subgroup.subgraph(Digraph,Vertices)is equivalent tosubgraph(Digraph,Vertices,[]). If any of the arguments are invalid, abadargexception is raised.topsort(Digraph)->Vertices|falseTypes: Digraph =digraph:graph()Vertices = [digraph:vertex()] Returns atopologicalorderingof the vertices of digraphDi-graphif such an ordering exists, otherwisefalse. For each ver- tex in the returned list, noout-neighborsoccur earlier in the list.SEE ALSOdigraph(3)Ericsson AB stdlib 3.8 digraph_utils(3)

NAME | DESCRIPTION | EXPORTS | SEE ALSO

Want to link to this manual page? Use this URL:

<https://www.freebsd.org/cgi/man.cgi?query=digraph_utils&sektion=3&manpath=FreeBSD+13.0-RELEASE+and+Ports>