1digraph_utils(3)           Erlang Module Definition           digraph_utils(3)
2
3
4

NAME

6       digraph_utils - Algorithms for directed graphs.
7

DESCRIPTION

9       This  module  provides  algorithms  based  on  depth-first traversal of
10       directed graphs. For  basic  functions  on  directed  graphs,  see  the
11       digraph(3) module.
12
13         * A  directed  graph (or just "digraph") is a pair (V, E) of a finite
14           set V of vertices and a finite set E of  directed  edges  (or  just
15           "edges").  The  set  of edges E is a subset of V x V (the Cartesian
16           product of V with itself).
17
18         * Digraphs can be annotated with more information.  Such  information
19           can be attached to the vertices and to the edges of the digraph. An
20           annotated digraph is called a labeled digraph, and the  information
21           attached to a vertex or an edge is called a label.
22
23         * An edge e = (v, w) is said to emanate from vertex v and to be inci‐
24           dent on vertex w.
25
26         * If an edge is emanating from v and incident on w, then w is said to
27           be an out-neighbor of v, and v is said to be an in-neighbor of w.
28
29         * A  path  P  from  v[1]  to  v[k] in a digraph (V, E) is a non-empty
30           sequence v[1], v[2], ..., v[k] of vertices in V such that there  is
31           an edge (v[i],v[i+1]) in E for 1 <= i < k.
32
33         * The length of path P is k-1.
34
35         * Path P is a cycle if the length of P is not zero and v[1] = v[k].
36
37         * A loop is a cycle of length one.
38
39         * An acyclic digraph is a digraph without cycles.
40
41         * A  depth-first  traversal  of a directed digraph can be viewed as a
42           process that visits all vertices of  the  digraph.  Initially,  all
43           vertices  are  marked  as  unvisited.  The traversal starts with an
44           arbitrarily chosen vertex, which is marked as visited, and  follows
45           an edge to an unmarked vertex, marking that vertex. The search then
46           proceeds from that vertex in the same fashion, until  there  is  no
47           edge  leading  to  an  unvisited  vertex. At that point the process
48           backtracks, and the traversal continues as long as there are  unex‐
49           amined  edges. If unvisited vertices remain when all edges from the
50           first vertex have been examined, some so far  unvisited  vertex  is
51           chosen, and the process is repeated.
52
53         * A  partial  ordering of a set S is a transitive, antisymmetric, and
54           reflexive relation between the objects of S.
55
56         * The problem of topological sorting is to find a total ordering of S
57           that is a superset of the partial ordering. A digraph G = (V, E) is
58           equivalent to a relation E on V (we neglect  that  the  version  of
59           directed  graphs  provided  by  the  digraph module allows multiple
60           edges between vertices). If the digraph has no cycles of length two
61           or  more,  the  reflexive  and transitive closure of E is a partial
62           ordering.
63
64         * A subgraph G' of G is a digraph whose vertices and edges form  sub‐
65           sets of the vertices and edges of G.
66
67         * G'  is  maximal with respect to a property P if all other subgraphs
68           that include the vertices of G' do not have property P.
69
70         * A strongly connected component is  a  maximal  subgraph  such  that
71           there is a path between each pair of vertices.
72
73         * A  connected  component  is a maximal subgraph such that there is a
74           path between each pair of vertices,  considering  all  edges  undi‐
75           rected.
76
77         * An  arborescence  is  an acyclic digraph with a vertex V, the root,
78           such that there is a unique path from V to every other vertex of G.
79
80         * A tree is an acyclic non-empty digraph such that there is a  unique
81           path  between  every  pair of vertices, considering all edges undi‐
82           rected.
83

EXPORTS

85       arborescence_root(Digraph) -> no | {yes, Root}
86
87              Types:
88
89                 Digraph = digraph:graph()
90                 Root = digraph:vertex()
91
92              Returns {yes, Root} if Root is  the  root  of  the  arborescence
93              Digraph, otherwise no.
94
95       components(Digraph) -> [Component]
96
97              Types:
98
99                 Digraph = digraph:graph()
100                 Component = [digraph:vertex()]
101
102              Returns  a list of connected components.. Each component is rep‐
103              resented by its vertices. The order  of  the  vertices  and  the
104              order  of  the  components are arbitrary. Each vertex of digraph
105              Digraph occurs in exactly one component.
106
107       condensation(Digraph) -> CondensedDigraph
108
109              Types:
110
111                 Digraph = CondensedDigraph = digraph:graph()
112
113              Creates a digraph where the vertices are the strongly  connected
114              components  of  Digraph as returned by strong_components/1. If X
115              and Y are two different strongly connected components, and  ver‐
116              tices x and y exist in X and Y, respectively, such that there is
117              an edge emanating from x and incident on y, then an edge emanat‐
118              ing from X and incident on Y is created.
119
120              The  created  digraph has the same type as Digraph. All vertices
121              and edges have the default label [].
122
123              Each cycle is included in  some  strongly  connected  component,
124              which implies that a topological ordering of the created digraph
125              always exists.
126
127       cyclic_strong_components(Digraph) -> [StrongComponent]
128
129              Types:
130
131                 Digraph = digraph:graph()
132                 StrongComponent = [digraph:vertex()]
133
134              Returns a list of strongly connected components.  Each  strongly
135              component  is represented by its vertices. The order of the ver‐
136              tices and the order of the components are arbitrary.  Only  ver‐
137              tices  that  are included in some cycle in Digraph are returned,
138              otherwise the  returned  list  is  equal  to  that  returned  by
139              strong_components/1.
140
141       is_acyclic(Digraph) -> boolean()
142
143              Types:
144
145                 Digraph = digraph:graph()
146
147              Returns true if and only if digraph Digraph is acyclic.
148
149       is_arborescence(Digraph) -> boolean()
150
151              Types:
152
153                 Digraph = digraph:graph()
154
155              Returns true if and only if digraph Digraph is an arborescence.
156
157       is_tree(Digraph) -> boolean()
158
159              Types:
160
161                 Digraph = digraph:graph()
162
163              Returns true if and only if digraph Digraph is a tree.
164
165       loop_vertices(Digraph) -> Vertices
166
167              Types:
168
169                 Digraph = digraph:graph()
170                 Vertices = [digraph:vertex()]
171
172              Returns  a  list of all vertices of Digraph that are included in
173              some loop.
174
175       postorder(Digraph) -> Vertices
176
177              Types:
178
179                 Digraph = digraph:graph()
180                 Vertices = [digraph:vertex()]
181
182              Returns all vertices of digraph Digraph. The order is given by a
183              depth-first  traversal  of  the digraph, collecting visited ver‐
184              tices in postorder. More precisely, the vertices  visited  while
185              searching  from  an  arbitrarily  chosen vertex are collected in
186              postorder, and all those collected vertices  are  placed  before
187              the subsequently visited vertices.
188
189       preorder(Digraph) -> Vertices
190
191              Types:
192
193                 Digraph = digraph:graph()
194                 Vertices = [digraph:vertex()]
195
196              Returns all vertices of digraph Digraph. The order is given by a
197              depth-first traversal of the digraph,  collecting  visited  ver‐
198              tices in preorder.
199
200       reachable(Vertices, Digraph) -> Reachable
201
202              Types:
203
204                 Digraph = digraph:graph()
205                 Vertices = Reachable = [digraph:vertex()]
206
207              Returns  an unsorted list of digraph vertices such that for each
208              vertex in the list, there is a path in Digraph from some  vertex
209              of  Vertices  to  the  vertex.  In particular, as paths can have
210              length zero, the  vertices  of  Vertices  are  included  in  the
211              returned list.
212
213       reachable_neighbours(Vertices, Digraph) -> Reachable
214
215              Types:
216
217                 Digraph = digraph:graph()
218                 Vertices = Reachable = [digraph:vertex()]
219
220              Returns  an unsorted list of digraph vertices such that for each
221              vertex in the list, there is a path in Digraph of length one  or
222              more  from  some  vertex  of Vertices to the vertex. As a conse‐
223              quence, only those vertices of Vertices  that  are  included  in
224              some cycle are returned.
225
226       reaching(Vertices, Digraph) -> Reaching
227
228              Types:
229
230                 Digraph = digraph:graph()
231                 Vertices = Reaching = [digraph:vertex()]
232
233              Returns  an unsorted list of digraph vertices such that for each
234              vertex in the list, there is a path from the vertex to some ver‐
235              tex  of  Vertices. In particular, as paths can have length zero,
236              the vertices of Vertices are included in the returned list.
237
238       reaching_neighbours(Vertices, Digraph) -> Reaching
239
240              Types:
241
242                 Digraph = digraph:graph()
243                 Vertices = Reaching = [digraph:vertex()]
244
245              Returns an unsorted list of digraph vertices such that for  each
246              vertex  in  the list, there is a path of length one or more from
247              the vertex to some vertex of Vertices. Therefore only those ver‐
248              tices of Vertices that are included in some cycle are returned.
249
250       strong_components(Digraph) -> [StrongComponent]
251
252              Types:
253
254                 Digraph = digraph:graph()
255                 StrongComponent = [digraph:vertex()]
256
257              Returns  a  list of strongly connected components. Each strongly
258              component is represented by its vertices. The order of the  ver‐
259              tices and the order of the components are arbitrary. Each vertex
260              of digraph Digraph occurs in exactly one strong component.
261
262       subgraph(Digraph, Vertices) -> SubGraph
263
264       subgraph(Digraph, Vertices, Options) -> SubGraph
265
266              Types:
267
268                 Digraph = SubGraph = digraph:graph()
269                 Vertices = [digraph:vertex()]
270                 Options = [{type, SubgraphType} | {keep_labels, boolean()}]
271                 SubgraphType = inherit | [digraph:d_type()]
272
273              Creates a maximal subgraph of Digraph having as  vertices  those
274              vertices of Digraph that are mentioned in Vertices.
275
276              If  the  value  of option type is inherit, which is the default,
277              the type of Digraph is used for the subgraph as well.  Otherwise
278              the option value of type is used as argument to digraph:new/1.
279
280              If  the  value  of  option  keep_labels  is  true,  which is the
281              default, the labels of vertices and edges of  Digraph  are  used
282              for  the  subgraph as well. If the value is false, default label
283              [] is used for the vertices and edges of the subgroup.
284
285              subgraph(Digraph, Vertices) is equivalent  to  subgraph(Digraph,
286              Vertices, []).
287
288              If  any  of  the  arguments  are  invalid, a badarg exception is
289              raised.
290
291       topsort(Digraph) -> Vertices | false
292
293              Types:
294
295                 Digraph = digraph:graph()
296                 Vertices = [digraph:vertex()]
297
298              Returns a  topological  ordering  of  the  vertices  of  digraph
299              Digraph  if  such  an ordering exists, otherwise false. For each
300              vertex in the returned list, no out-neighbors occur  earlier  in
301              the list.
302

SEE ALSO

304       digraph(3)
305
306
307
308Ericsson AB                     stdlib 3.4.5.1                digraph_utils(3)
Impressum