1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
|
<HTML>
<HEAD>
<!-- refpage -->
<TITLE>digraph_utils</TITLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<CENTER>
<A HREF="http://www.erlang.se"><IMG BORDER=0 ALT="[Erlang Systems]" SRC="min_head.gif"></A>
<H1>digraph_utils</H1>
</CENTER>
<H3>MODULE</H3>
<UL>
digraph_utils</UL>
<H3>MODULE SUMMARY</H3>
<UL>
Algorithms for Directed Graphs</UL>
<H3>DESCRIPTION</H3>
<UL>
<P>The <CODE>digraph_utils</CODE> module implements some algorithms
based on depth-first traversal of directed graphs. See the
<CODE>digraph</CODE> module for basic functions on directed graphs.
<P>A <A NAME="digraph"><!-- Empty --></A><STRONG>directed graph</STRONG> (or just
"digraph") is a pair (V, E) of a finite set V of <A NAME="vertex"><!-- Empty --></A><STRONG>vertices</STRONG> and a finite set E of <A NAME="edge"><!-- Empty --></A><STRONG>directed edges</STRONG> (or just "edges"). The set of
edges E is a subset of V × V (the Cartesian
product of V with itself).
<P>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 a
<STRONG>labeled digraph</STRONG>, and the information attached to a
vertex or an edge is called a <A NAME="label"><!-- Empty --></A><STRONG>label</STRONG>.
<P>An edge e = (v, w) is said to <A NAME="emanate"><!-- Empty --></A><STRONG>emanate</STRONG> from vertex v and to be <A NAME="incident"><!-- Empty --></A><STRONG>incident</STRONG> on vertex w. If there is an edge
emanating from v and incident on w, then w is is said to be an
<A NAME="out_neighbour"><!-- Empty --></A><STRONG>out-neighbour</STRONG> of v. A
<A NAME="path"><!-- Empty --></A><STRONG>path</STRONG> P 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. The <A NAME="length"><!-- Empty --></A><STRONG>length</STRONG> of the path P is k-1. P is a <A NAME="cycle"><!-- Empty --></A><STRONG>cycle</STRONG> if the length of P is not zero and
v[1] = v[k]. A <A NAME="loop"><!-- Empty --></A><STRONG>loop</STRONG> is a cycle of
length one. An <A NAME="acyclic_digraph"><!-- Empty --></A><STRONG>acyclic
digraph</STRONG> is a digraph that has no cycles.
<P>A <A NAME="depth_first_traversal"><!-- Empty --></A><STRONG>depth-first
traversal</STRONG> of 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
arbitrarily 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 unexamined edges. If there remain unvisited vertices
when all edges from the first vertex have been examined, some
hitherto unvisited vertex is chosen, and the process is
repeated.
<P>A <A NAME="partial_ordering"><!-- Empty --></A><STRONG>partial ordering</STRONG> of a
set S is a transitive, antisymmetric and reflexive relation
between the objects of S. The problem of <A NAME="topsort"><!-- Empty --></A><STRONG>topological sorting</STRONG> is 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 the fact that the version of directed graphs
implemented in the <CODE>digraph</CODE> module allows multiple edges
between vertices). If the digraph has no cycles of length two or
more, then the reflexive and transitive closure of E is a
partial ordering.
<P>A <A NAME="subgraph"><!-- Empty --></A><STRONG>subgraph</STRONG> G' of G is a
digraph whose vertices and edges form subsets of the vertices
and edges of G. G' is <STRONG>maximal</STRONG> with respect to a
property P if all other subgraphs that include the vertices of
G' do not have the property P. A <A NAME="strong_components"><!-- Empty --></A><STRONG>strongly connected component</STRONG> is
a maximal subgraph such that there is a path between each pair
of vertices. A <A NAME="components"><!-- Empty --></A><STRONG>connected
component</STRONG> is a maximal subgraph such that there is a path
between each pair of vertices, considering all edges undirected.
</UL>
<H3>EXPORTS</H3>
<P><A NAME="components%1"><STRONG><CODE>components(Digraph) -> [Component]</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Component = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns a list of <A HREF="#components">connected
components</A>. Each component is represented by its
vertices. The order of the vertices and the order of the
components are arbitrary. Each vertex of the digraph
<CODE>Digraph</CODE>occurs in exactly one component.
</UL>
<P><A NAME="condensation%1"><STRONG><CODE>condensation(Digraph) -> CondensedDigraph</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = CondensedDigraph = digraph()</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Creates a digraph where the vertices are the <A HREF="#strong_components">strongly connected
components</A> of <CODE>Digraph</CODE> as returned by
<CODE>strong_components/1</CODE>. If X and Y are strongly
connected components, and there exist vertices x and y in X
and Y respectively such that there is an edge <A HREF="#emanate">emanating</A> from x and <A HREF="#incident">incident</A> on y, then an edge
emanating from X and incident on Y is created.
<P>The created digraph has the same type as <CODE>Digraph</CODE>.
All vertices and edges have the default <A HREF="#label">label</A> <CODE>[]</CODE>.
<P>Each and every <A HREF="#cycle">cycle</A> is
included in some strongly connected component, which implies
that there always exists a <A HREF="#topsort">topological ordering</A> of the
created digraph.
</UL>
<P><A NAME="cyclic_strong_components%1"><STRONG><CODE>cyclic_strong_components(Digraph) -> [StrongComponent]</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>StrongComponent = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns a list of <A HREF="#strong_components">strongly connected
components</A>. Each strongly component is represented
by its vertices. The order of the vertices and the order of
the components are arbitrary. Only vertices that are
included in some <A HREF="#cycle">cycle</A> in
<CODE>Digraph</CODE> are returned, otherwise the returned list is
equal to that returned by <CODE>strong_components/1</CODE>.
</UL>
<P><A NAME="is_acyclic%1"><STRONG><CODE>is_acyclic(Digraph) -> bool()</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns <CODE>true</CODE> if and only if the digraph
<CODE>Digraph</CODE> is <A HREF="#acyclic_digraph">acyclic</A>.
</UL>
<P><A NAME="loop_vertices%1"><STRONG><CODE>loop_vertices(Digraph) -> Vertices</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns a list of all vertices of <CODE>Digraph</CODE> that are
included in some <A HREF="#loop">loop</A>.
</UL>
<P><A NAME="postorder%1"><STRONG><CODE>postorder(Digraph) -> Vertices</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns all vertices of the digraph <CODE>Digraph</CODE>. The
order is given by a <A HREF="#depth_first_traversal">depth-first
traversal</A> of the digraph, collecting visited
vertices 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.
</UL>
<P><A NAME="preorder%1"><STRONG><CODE>preorder(Digraph) -> Vertices</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns all vertices of the digraph <CODE>Digraph</CODE>. The
order is given by a <A HREF="#depth_first_traversal">depth-first
traversal</A> of the digraph, collecting visited
vertices in pre-order.
</UL>
<P><A NAME="reachable%2"><STRONG><CODE>reachable(Vertices, Digraph) -> Vertices</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns an unsorted list of digraph vertices such that for
each vertex in the list, there is a <A HREF="#path">path</A> in <CODE>Digraph</CODE> from some
vertex of <CODE>Vertices</CODE> to the vertex. In particular,
since paths may have length zero, the vertices of
<CODE>Vertices</CODE> are included in the returned list.
</UL>
<P><A NAME="reachable_neighbours%2"><STRONG><CODE>reachable_neighbours(Vertices, Digraph) -> Vertices</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns an unsorted list of digraph vertices such that for
each vertex in the list, there is a <A HREF="#path">path</A> in <CODE>Digraph</CODE> of length
one or more from some vertex of <CODE>Vertices</CODE> to the
vertex. As a consequence, only those vertices of
<CODE>Vertices</CODE> that are included in some <A HREF="#cycle">cycle</A> are returned.
</UL>
<P><A NAME="reaching%2"><STRONG><CODE>reaching(Vertices, Digraph) -> Vertices</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns an unsorted list of digraph vertices such that for
each vertex in the list, there is a <A HREF="#path">path</A> from the vertex to some vertex
of <CODE>Vertices</CODE>. In particular, since paths may have
length zero, the vertices of <CODE>Vertices</CODE> are included in
the returned list.
</UL>
<P><A NAME="reaching_neighbours%2"><STRONG><CODE>reaching_neighbours(Vertices, Digraph) -> Vertices</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns an unsorted list of digraph vertices such that for
each vertex in the list, there is a <A HREF="#path">path</A> of length one or more from the
vertex to some vertex of <CODE>Vertices</CODE>. As a consequence,
only those vertices of <CODE>Vertices</CODE> that are included in
some <A HREF="#cycle">cycle</A> are returned.
</UL>
<P><A NAME="strong_components%1"><STRONG><CODE>strong_components(Digraph) -> [StrongComponent]</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>StrongComponent = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns a list of <A HREF="#strong_components">strongly connected
components</A>. Each strongly component is represented
by its vertices. The order of the vertices and the order of
the components are arbitrary. Each vertex of the digraph
<CODE>Digraph</CODE> occurs in exactly one strong component.
</UL>
<P><A NAME="subgraph%3"><STRONG><CODE>subgraph(Digraph, Vertices [, Options]) ->
Subgraph | {error, Reason}</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = Subgraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Options = [{type, SubgraphType}, {keep_labels, bool()}]</CODE></STRONG><BR>
<STRONG><CODE>Reason = {invalid_option, term()} | {unknown_type, term()}</CODE></STRONG><BR>
<STRONG><CODE>SubgraphType = inherit | type()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Creates a maximal <A HREF="#subgraph">subgraph</A> of <CODE>Digraph</CODE> having
as vertices those vertices of <CODE>Digraph</CODE> that are
mentioned in <CODE>Vertices</CODE>.
<P>If the value of the option <CODE>type</CODE> is <CODE>inherit</CODE>,
which is the default, then the type of <CODE>Digraph</CODE> is used
for the subgraph as well. Otherwise the option value of <CODE>type</CODE>
is used as argument to <CODE>digraph:new/1</CODE>.
<P>If the value of the option <CODE>keep_labels</CODE> is <CODE>true</CODE>,
which is the default, then the <A HREF="#label">labels</A> of vertices and edges
of <CODE>Digraph</CODE> are used for the subgraph as well. If the value
is <CODE>false</CODE>, then the default label, <CODE>[]</CODE>, is used
for the subgraph's vertices and edges.
<P><CODE>subgraph(Digraph, Vertices)</CODE> is equivalent to
<CODE>subgraph(Digraph, Vertices, [])</CODE>.
</UL>
<P><A NAME="topsort%1"><STRONG><CODE>topsort(Digraph) -> Vertices | false</CODE></STRONG></A><BR>
<P><UL>Types:
<UL>
<STRONG><CODE>Digraph = digraph()</CODE></STRONG><BR>
<STRONG><CODE>Vertices = [vertex()]</CODE></STRONG><BR>
</UL>
</UL>
<UL>
<P>Returns a <A HREF="#topsort">topological
ordering</A> of the vertices of the digraph
<CODE>Digraph</CODE> if such an ordering exists, <CODE>false</CODE>
otherwise. For each vertex in the returned list, there are
no <A HREF="#out_neighbour">out-neighbours</A>
that occur earlier in the list.
</UL>
<H3>See Also</H3>
<UL>
<P><A HREF="digraph.html">digraph</A>(3)
</UL>
<H3>AUTHORS</H3>
<UL>
Hans Bolinder - support@erlang.ericsson.se<BR>
</UL>
<CENTER>
<HR>
<FONT SIZE=-1>stdlib 1.10<BR>
Copyright © 1991-2001
<A HREF="http://www.erlang.se">Ericsson Utvecklings AB</A><BR>
<!--#include virtual="/ssi/otp_footer.html"-->
</FONT>
</CENTER>
</BODY>
</HTML>
|
