1digraph(3) Erlang Module Definition digraph(3)
2
6 digraph - Directed graphs.
7
9 This module provides a version of labeled directed graphs ("digraphs").
10 The digraphs managed by this module are stored in ETS tables. That im‐
12 plies the following:
13 * Only the process that created the digraph is allowed to update it.
15 * Digraphs will not be garbage collected. The ETS tables used for a
17 digraph will only be deleted when delete/1 is called or the process
18 that created the digraph terminates.
19 * A digraph is a mutable data structure.
21 What makes the graphs provided here non-proper directed graphs is that
23 multiple edges between vertices are allowed. However, the customary
24 definition of directed graphs is used here.
25 * A directed graph (or just "digraph") is a pair (V, E) of a finite
27 set V of vertices and a finite set E of directed edges (or just
28 "edges"). The set of edges E is a subset of V x V (the Cartesian
29 product of V with itself).
30 In this module, V is allowed to be empty. The so obtained unique
32 digraph is called the empty digraph. Both vertices and edges are
33 represented by unique Erlang terms.
34 * Digraphs can be annotated with more information. Such information
36 can be attached to the vertices and to the edges of the digraph. An
37 annotated digraph is called a labeled digraph, and the information
38 attached to a vertex or an edge is called a label. Labels are Er‐
39 lang terms.
40 * An edge e = (v, w) is said to emanate from vertex v and to be inci‐
42 dent on vertex w.
43 * The out-degree of a vertex is the number of edges emanating from
45 that vertex.
46 * The in-degree of a vertex is the number of edges incident on that
48 vertex.
49 * If an edge is emanating from v and incident on w, then w is said to
51 be an out-neighbor of v, and v is said to be an in-neighbor of w.
52 * A path P from v[1] to v[k] in a digraph (V, E) is a non-empty se‐
54 quence v[1], v[2], ..., v[k] of vertices in V such that there is an
55 edge (v[i],v[i+1]) in E for 1 <= i < k.
56 * The length of path P is k-1.
58 * Path P is simple if all vertices are distinct, except that the
60 first and the last vertices can be the same.
61 * Path P is a cycle if the length of P is not zero and v[1] = v[k].
63 * A loop is a cycle of length one.
65 * A simple cycle is a path that is both a cycle and simple.
67 * An acyclic digraph is a digraph without cycles.
69
71 d_type() = d_cyclicity() | d_protection()
72 d_cyclicity() = acyclic | cyclic
74 d_protection() = private | protected
76 graph()
78 A digraph as returned by new/0,1.
80 edge()
82 label() = term()
84 vertex()
86
88 add_edge(G, V1, V2) -> edge() | {error, add_edge_err_rsn()}
89 add_edge(G, V1, V2, Label) -> edge() | {error, add_edge_err_rsn()}
91 add_edge(G, E, V1, V2, Label) ->
93 edge() | {error, add_edge_err_rsn()}
94 Types:
96 G = graph()
98 E = edge()
99 V1 = V2 = vertex()
100 Label = label()
101 add_edge_err_rsn() =
102 {bad_edge, Path :: [vertex()]} | {bad_vertex, V :: vertex()}
103 add_edge/5 creates (or modifies) edge E of digraph G, using La‐
105 bel as the (new) label of the edge. The edge is emanating from
106 V1 and incident on V2. Returns E.
107 add_edge(G, V1, V2, Label) is equivalent to add_edge(G, E, V1,
109 V2, Label), where E is a created edge. The created edge is rep‐
110 resented by term ['$e' | N], where N is an integer >= 0.
111 add_edge(G, V1, V2) is equivalent to add_edge(G, V1, V2, []).
113 If the edge would create a cycle in an acyclic digraph, {error,
115 {bad_edge, Path}} is returned. If G already has an edge with
116 value E connecting a different pair of vertices, {error,
117 {bad_edge, [V1, V2]}} is returned. If either of V1 or V2 is not
118 a vertex of digraph G, {error, {bad_vertex, V}} is returned, V =
119 V1 or V = V2.
120 add_vertex(G) -> vertex()
122 add_vertex(G, V) -> vertex()
124 add_vertex(G, V, Label) -> vertex()
126 Types:
128 G = graph()
130 V = vertex()
131 Label = label()
132 add_vertex/3 creates (or modifies) vertex V of digraph G, using
134 Label as the (new) label of the vertex. Returns V.
135 add_vertex(G, V) is equivalent to add_vertex(G, V, []).
137 add_vertex/1 creates a vertex using the empty list as label, and
139 returns the created vertex. The created vertex is represented by
140 term ['$v' | N], where N is an integer >= 0.
141 del_edge(G, E) -> true
143 Types:
145 G = graph()
147 E = edge()
148 Deletes edge E from digraph G.
150 del_edges(G, Edges) -> true
152 Types:
154 G = graph()
156 Edges = [edge()]
157 Deletes the edges in list Edges from digraph G.
159 del_path(G, V1, V2) -> true
161 Types:
163 G = graph()
165 V1 = V2 = vertex()
166 Deletes edges from digraph G until there are no paths from ver‐
168 tex V1 to vertex V2.
169 A sketch of the procedure employed:
171 * Find an arbitrary simple path v[1], v[2], ..., v[k] from V1
173 to V2 in G.
174 * Remove all edges of G emanating from v[i] and incident to
176 v[i+1] for 1 <= i < k (including multiple edges).
177 * Repeat until there is no path between V1 and V2.
179 del_vertex(G, V) -> true
181 Types:
183 G = graph()
185 V = vertex()
186 Deletes vertex V from digraph G. Any edges emanating from V or
188 incident on V are also deleted.
189 del_vertices(G, Vertices) -> true
191 Types:
193 G = graph()
195 Vertices = [vertex()]
196 Deletes the vertices in list Vertices from digraph G.
198 delete(G) -> true
200 Types:
202 G = graph()
204 Deletes digraph G. This call is important as digraphs are imple‐
206 mented with ETS. There is no garbage collection of ETS tables.
207 However, the digraph is deleted if the process that created the
208 digraph terminates.
209 edge(G, E) -> {E, V1, V2, Label} | false
211 Types:
213 G = graph()
215 E = edge()
216 V1 = V2 = vertex()
217 Label = label()
218 Returns {E, V1, V2, Label}, where Label is the label of edge E
220 emanating from V1 and incident on V2 of digraph G. If no edge E
221 of digraph G exists, false is returned.
222 edges(G) -> Edges
224 Types:
226 G = graph()
228 Edges = [edge()]
229 Returns a list of all edges of digraph G, in some unspecified
231 order.
232 edges(G, V) -> Edges
234 Types:
236 G = graph()
238 V = vertex()
239 Edges = [edge()]
240 Returns a list of all edges emanating from or incident on V of
242 digraph G, in some unspecified order.
243 get_cycle(G, V) -> Vertices | false
245 Types:
247 G = graph()
249 V = vertex()
250 Vertices = [vertex(), ...]
251 If a simple cycle of length two or more exists through vertex V,
253 the cycle is returned as a list [V, ..., V] of vertices. If a
254 loop through V exists, the loop is returned as a list [V]. If no
255 cycles through V exist, false is returned.
256 get_path/3 is used for finding a simple cycle through V.
258 get_path(G, V1, V2) -> Vertices | false
260 Types:
262 G = graph()
264 V1 = V2 = vertex()
265 Vertices = [vertex(), ...]
266 Tries to find a simple path from vertex V1 to vertex V2 of di‐
268 graph G. Returns the path as a list [V1, ..., V2] of vertices,
269 or false if no simple path from V1 to V2 of length one or more
270 exists.
271 Digraph G is traversed in a depth-first manner, and the first
273 found path is returned.
274 get_short_cycle(G, V) -> Vertices | false
276 Types:
278 G = graph()
280 V = vertex()
281 Vertices = [vertex(), ...]
282 Tries to find an as short as possible simple cycle through ver‐
284 tex V of digraph G. Returns the cycle as a list [V, ..., V] of
285 vertices, or false if no simple cycle through V exists. Notice
286 that a loop through V is returned as list [V, V].
287 get_short_path/3 is used for finding a simple cycle through V.
289 get_short_path(G, V1, V2) -> Vertices | false
291 Types:
293 G = graph()
295 V1 = V2 = vertex()
296 Vertices = [vertex(), ...]
297 Tries to find an as short as possible simple path from vertex V1
299 to vertex V2 of digraph G. Returns the path as a list [V1, ...,
300 V2] of vertices, or false if no simple path from V1 to V2 of
301 length one or more exists.
302 Digraph G is traversed in a breadth-first manner, and the first
304 found path is returned.
305 in_degree(G, V) -> integer() >= 0
307 Types:
309 G = graph()
311 V = vertex()
312 Returns the in-degree of vertex V of digraph G.
314 in_edges(G, V) -> Edges
316 Types:
318 G = graph()
320 V = vertex()
321 Edges = [edge()]
322 Returns a list of all edges incident on V of digraph G, in some
324 unspecified order.
325 in_neighbours(G, V) -> Vertex
327 Types:
329 G = graph()
331 V = vertex()
332 Vertex = [vertex()]
333 Returns a list of all in-neighbors of V of digraph G, in some
335 unspecified order.
336 info(G) -> InfoList
338 Types:
340 G = graph()
342 InfoList =
343 [{cyclicity, Cyclicity :: d_cyclicity()} |
344 {memory, NoWords :: integer() >= 0} |
345 {protection, Protection :: d_protection()}]
346 d_cyclicity() = acyclic | cyclic
347 d_protection() = private | protected
348 Returns a list of {Tag, Value} pairs describing digraph G. The
350 following pairs are returned:
351 * {cyclicity, Cyclicity}, where Cyclicity is cyclic or
353 acyclic, according to the options given to new.
354 * {memory, NoWords}, where NoWords is the number of words al‐
356 located to the ETS tables.
357 * {protection, Protection}, where Protection is protected or
359 private, according to the options given to new.
360 new() -> graph()
362 Equivalent to new([]).
364 new(Type) -> graph()
366 Types:
368 Type = [d_type()]
370 d_type() = d_cyclicity() | d_protection()
371 d_cyclicity() = acyclic | cyclic
372 d_protection() = private | protected
373 Returns an empty digraph with properties according to the op‐
375 tions in Type:
376 cyclic:
378 Allows cycles in the digraph (default).
379 acyclic:
381 The digraph is to be kept acyclic.
382 protected:
384 Other processes can read the digraph (default).
385 private:
387 The digraph can be read and modified by the creating process
388 only.
389 If an unrecognized type option T is specified or Type is not a
391 proper list, a badarg exception is raised.
392 no_edges(G) -> integer() >= 0
394 Types:
396 G = graph()
398 Returns the number of edges of digraph G.
400 no_vertices(G) -> integer() >= 0
402 Types:
404 G = graph()
406 Returns the number of vertices of digraph G.
408 out_degree(G, V) -> integer() >= 0
410 Types:
412 G = graph()
414 V = vertex()
415 Returns the out-degree of vertex V of digraph G.
417 out_edges(G, V) -> Edges
419 Types:
421 G = graph()
423 V = vertex()
424 Edges = [edge()]
425 Returns a list of all edges emanating from V of digraph G, in
427 some unspecified order.
428 out_neighbours(G, V) -> Vertices
430 Types:
432 G = graph()
434 V = vertex()
435 Vertices = [vertex()]
436 Returns a list of all out-neighbors of V of digraph G, in some
438 unspecified order.
439 vertex(G, V) -> {V, Label} | false
441 Types:
443 G = graph()
445 V = vertex()
446 Label = label()
447 Returns {V, Label}, where Label is the label of the vertex V of
449 digraph G, or false if no vertex V of digraph G exists.
450 vertices(G) -> Vertices
452 Types:
454 G = graph()
456 Vertices = [vertex()]
457 Returns a list of all vertices of digraph G, in some unspecified
459 order.
460
462 digraph_utils(3), ets(3)
463Ericsson AB stdlib 5.1.1 digraph(3)