1digraph_utils(3) Erlang Module Definition digraph_utils(3)
2
6 digraph_utils - Algorithms for directed graphs.
7
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 * 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 * 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 * An edge e = (v, w) is said to emanate from vertex v and to be inci‐
24 dent on vertex w.
25 * 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 * 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 * The length of path P is k-1.
34 * Path P is a cycle if the length of P is not zero and v[1] = v[k].
36 * A loop is a cycle of length one.
38 * An acyclic digraph is a digraph without cycles.
40 * 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 * A partial ordering of a set S is a transitive, antisymmetric, and
54 reflexive relation between the objects of S.
55 * 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 * A subgraph G' of G is a digraph whose vertices and edges form sub‐
65 sets of the vertices and edges of G.
66 * 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 * A strongly connected component is a maximal subgraph such that
71 there is a path between each pair of vertices.
72 * 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 * 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 * 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
85 arborescence_root(Digraph) -> no | {yes, Root}
86 Types:
88 Digraph = digraph:graph()
90 Root = digraph:vertex()
91 Returns {yes, Root} if Root is the root of the arborescence
93 Digraph, otherwise no.
94 components(Digraph) -> [Component]
96 Types:
98 Digraph = digraph:graph()
100 Component = [digraph:vertex()]
101 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 condensation(Digraph) -> CondensedDigraph
108 Types:
110 Digraph = CondensedDigraph = digraph:graph()
112 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 The created digraph has the same type as Digraph. All vertices
121 and edges have the default label [].
122 Each cycle is included in some strongly connected component,
124 which implies that a topological ordering of the created digraph
125 always exists.
126 cyclic_strong_components(Digraph) -> [StrongComponent]
128 Types:
130 Digraph = digraph:graph()
132 StrongComponent = [digraph:vertex()]
133 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 is_acyclic(Digraph) -> boolean()
142 Types:
144 Digraph = digraph:graph()
146 Returns true if and only if digraph Digraph is acyclic.
148 is_arborescence(Digraph) -> boolean()
150 Types:
152 Digraph = digraph:graph()
154 Returns true if and only if digraph Digraph is an arborescence.
156 is_tree(Digraph) -> boolean()
158 Types:
160 Digraph = digraph:graph()
162 Returns true if and only if digraph Digraph is a tree.
164 loop_vertices(Digraph) -> Vertices
166 Types:
168 Digraph = digraph:graph()
170 Vertices = [digraph:vertex()]
171 Returns a list of all vertices of Digraph that are included in
173 some loop.
174 postorder(Digraph) -> Vertices
176 Types:
178 Digraph = digraph:graph()
180 Vertices = [digraph:vertex()]
181 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 preorder(Digraph) -> Vertices
190 Types:
192 Digraph = digraph:graph()
194 Vertices = [digraph:vertex()]
195 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 reachable(Vertices, Digraph) -> Reachable
201 Types:
203 Digraph = digraph:graph()
205 Vertices = Reachable = [digraph:vertex()]
206 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 reachable_neighbours(Vertices, Digraph) -> Reachable
214 Types:
216 Digraph = digraph:graph()
218 Vertices = Reachable = [digraph:vertex()]
219 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 reaching(Vertices, Digraph) -> Reaching
227 Types:
229 Digraph = digraph:graph()
231 Vertices = Reaching = [digraph:vertex()]
232 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 reaching_neighbours(Vertices, Digraph) -> Reaching
239 Types:
241 Digraph = digraph:graph()
243 Vertices = Reaching = [digraph:vertex()]
244 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 strong_components(Digraph) -> [StrongComponent]
251 Types:
253 Digraph = digraph:graph()
255 StrongComponent = [digraph:vertex()]
256 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 subgraph(Digraph, Vertices) -> SubGraph
263 subgraph(Digraph, Vertices, Options) -> SubGraph
265 Types:
267 Digraph = SubGraph = digraph:graph()
269 Vertices = [digraph:vertex()]
270 Options = [{type, SubgraphType} | {keep_labels, boolean()}]
271 SubgraphType = inherit | [digraph:d_type()]
272 Creates a maximal subgraph of Digraph having as vertices those
274 vertices of Digraph that are mentioned in Vertices.
275 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 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 subgraph(Digraph, Vertices) is equivalent to subgraph(Digraph,
286 Vertices, []).
287 If any of the arguments are invalid, a badarg exception is
289 raised.
290 topsort(Digraph) -> Vertices | false
292 Types:
294 Digraph = digraph:graph()
296 Vertices = [digraph:vertex()]
297 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
304 digraph(3)
305Ericsson AB stdlib 3.10 digraph_utils(3)