1digraph(3) Erlang Module Definition digraph(3)
2
6 digraph - Directed graphs.
7
9 This module provides a version of labeled directed graphs. What makes
10 the graphs provided here non-proper directed graphs is that multiple
11 edges between vertices are allowed. However, the customary definition
12 of directed graphs is used here.
13 * A directed graph (or just "digraph") is a pair (V, E) of a finite
15 set V of vertices and a finite set E of directed edges (or just
16 "edges"). The set of edges E is a subset of V x V (the Cartesian
17 product of V with itself).
18 In this module, V is allowed to be empty. The so obtained unique
20 digraph is called the empty digraph. Both vertices and edges are
21 represented by unique Erlang terms.
22 * Digraphs can be annotated with more information. Such information
24 can be attached to the vertices and to the edges of the digraph. An
25 annotated digraph is called a labeled digraph, and the information
26 attached to a vertex or an edge is called a label. Labels are
27 Erlang terms.
28 * An edge e = (v, w) is said to emanate from vertex v and to be inci‐
30 dent on vertex w.
31 * The out-degree of a vertex is the number of edges emanating from
33 that vertex.
34 * The in-degree of a vertex is the number of edges incident on that
36 vertex.
37 * If an edge is emanating from v and incident on w, then w is said to
39 be an out-neighbor of v, and v is said to be an in-neighbor of w.
40 * A path P from v[1] to v[k] in a digraph (V, E) is a non-empty
42 sequence v[1], v[2], ..., v[k] of vertices in V such that there is
43 an edge (v[i],v[i+1]) in E for 1 <= i < k.
44 * The length of path P is k-1.
46 * Path P is simple if all vertices are distinct, except that the
48 first and the last vertices can be the same.
49 * Path P is a cycle if the length of P is not zero and v[1] = v[k].
51 * A loop is a cycle of length one.
53 * A simple cycle is a path that is both a cycle and simple.
55 * An acyclic digraph is a digraph without cycles.
57
59 d_type() = d_cyclicity() | d_protection()
60 d_cyclicity() = acyclic | cyclic
62 d_protection() = private | protected
64 graph()
66 A digraph as returned by new/0,1.
68 edge()
70 label() = term()
72 vertex()
74
76 add_edge(G, V1, V2) -> edge() | {error, add_edge_err_rsn()}
77 add_edge(G, V1, V2, Label) -> edge() | {error, add_edge_err_rsn()}
79 add_edge(G, E, V1, V2, Label) ->
81 edge() | {error, add_edge_err_rsn()}
82 Types:
84 G = graph()
86 E = edge()
87 V1 = V2 = vertex()
88 Label = label()
89 add_edge_err_rsn() =
90 {bad_edge, Path :: [vertex()]} | {bad_vertex, V :: vertex()}
91 add_edge/5 creates (or modifies) edge E of digraph G, using
93 Label as the (new) label of the edge. The edge is emanating from
94 V1 and incident on V2. Returns E.
95 add_edge(G, V1, V2, Label) is equivalent to add_edge(G, E, V1,
97 V2, Label), where E is a created edge. The created edge is rep‐
98 resented by term ['$e' | N], where N is an integer >= 0.
99 add_edge(G, V1, V2) is equivalent to add_edge(G, V1, V2, []).
101 If the edge would create a cycle in an acyclic digraph, {error,
103 {bad_edge, Path}} is returned. If G already has an edge with
104 value E connecting a different pair of vertices, {error,
105 {bad_edge, [V1, V2]}} is returned. If either of V1 or V2 is not
106 a vertex of digraph G, {error, {bad_vertex, V}} is returned, V =
107 V1 or V = V2.
108 add_vertex(G) -> vertex()
110 add_vertex(G, V) -> vertex()
112 add_vertex(G, V, Label) -> vertex()
114 Types:
116 G = graph()
118 V = vertex()
119 Label = label()
120 add_vertex/3 creates (or modifies) vertex V of digraph G, using
122 Label as the (new) label of the vertex. Returns V.
123 add_vertex(G, V) is equivalent to add_vertex(G, V, []).
125 add_vertex/1 creates a vertex using the empty list as label, and
127 returns the created vertex. The created vertex is represented by
128 term ['$v' | N], where N is an integer >= 0.
129 del_edge(G, E) -> true
131 Types:
133 G = graph()
135 E = edge()
136 Deletes edge E from digraph G.
138 del_edges(G, Edges) -> true
140 Types:
142 G = graph()
144 Edges = [edge()]
145 Deletes the edges in list Edges from digraph G.
147 del_path(G, V1, V2) -> true
149 Types:
151 G = graph()
153 V1 = V2 = vertex()
154 Deletes edges from digraph G until there are no paths from ver‐
156 tex V1 to vertex V2.
157 A sketch of the procedure employed:
159 * Find an arbitrary simple path v[1], v[2], ..., v[k] from V1
161 to V2 in G.
162 * Remove all edges of G emanating from v[i] and incident to
164 v[i+1] for 1 <= i < k (including multiple edges).
165 * Repeat until there is no path between V1 and V2.
167 del_vertex(G, V) -> true
169 Types:
171 G = graph()
173 V = vertex()
174 Deletes vertex V from digraph G. Any edges emanating from V or
176 incident on V are also deleted.
177 del_vertices(G, Vertices) -> true
179 Types:
181 G = graph()
183 Vertices = [vertex()]
184 Deletes the vertices in list Vertices from digraph G.
186 delete(G) -> true
188 Types:
190 G = graph()
192 Deletes digraph G. This call is important as digraphs are imple‐
194 mented with ETS. There is no garbage collection of ETS tables.
195 However, the digraph is deleted if the process that created the
196 digraph terminates.
197 edge(G, E) -> {E, V1, V2, Label} | false
199 Types:
201 G = graph()
203 E = edge()
204 V1 = V2 = vertex()
205 Label = label()
206 Returns {E, V1, V2, Label}, where Label is the label of edge E
208 emanating from V1 and incident on V2 of digraph G. If no edge E
209 of digraph G exists, false is returned.
210 edges(G) -> Edges
212 Types:
214 G = graph()
216 Edges = [edge()]
217 Returns a list of all edges of digraph G, in some unspecified
219 order.
220 edges(G, V) -> Edges
222 Types:
224 G = graph()
226 V = vertex()
227 Edges = [edge()]
228 Returns a list of all edges emanating from or incident onV of
230 digraph G, in some unspecified order.
231 get_cycle(G, V) -> Vertices | false
233 Types:
235 G = graph()
237 V = vertex()
238 Vertices = [vertex(), ...]
239 If a simple cycle of length two or more exists through vertex V,
241 the cycle is returned as a list [V, ..., V] of vertices. If a
242 loop through V exists, the loop is returned as a list [V]. If no
243 cycles through V exist, false is returned.
244 get_path/3 is used for finding a simple cycle through V.
246 get_path(G, V1, V2) -> Vertices | false
248 Types:
250 G = graph()
252 V1 = V2 = vertex()
253 Vertices = [vertex(), ...]
254 Tries to find a simple path from vertex V1 to vertex V2 of
256 digraph G. Returns the path as a list [V1, ..., V2] of vertices,
257 or false if no simple path from V1 to V2 of length one or more
258 exists.
259 Digraph G is traversed in a depth-first manner, and the first
261 found path is returned.
262 get_short_cycle(G, V) -> Vertices | false
264 Types:
266 G = graph()
268 V = vertex()
269 Vertices = [vertex(), ...]
270 Tries to find an as short as possible simple cycle through ver‐
272 tex V of digraph G. Returns the cycle as a list [V, ..., V] of
273 vertices, or false if no simple cycle through V exists. Notice
274 that a loop through V is returned as list [V, V].
275 get_short_path/3 is used for finding a simple cycle through V.
277 get_short_path(G, V1, V2) -> Vertices | false
279 Types:
281 G = graph()
283 V1 = V2 = vertex()
284 Vertices = [vertex(), ...]
285 Tries to find an as short as possible simple path from vertex V1
287 to vertex V2 of digraph G. Returns the path as a list [V1, ...,
288 V2] of vertices, or false if no simple path from V1 to V2 of
289 length one or more exists.
290 Digraph G is traversed in a breadth-first manner, and the first
292 found path is returned.
293 in_degree(G, V) -> integer() >= 0
295 Types:
297 G = graph()
299 V = vertex()
300 Returns the in-degree of vertex V of digraph G.
302 in_edges(G, V) -> Edges
304 Types:
306 G = graph()
308 V = vertex()
309 Edges = [edge()]
310 Returns a list of all edges incident on V of digraph G, in some
312 unspecified order.
313 in_neighbours(G, V) -> Vertex
315 Types:
317 G = graph()
319 V = vertex()
320 Vertex = [vertex()]
321 Returns a list of all in-neighbors of V of digraph G, in some
323 unspecified order.
324 info(G) -> InfoList
326 Types:
328 G = graph()
330 InfoList =
331 [{cyclicity, Cyclicity :: d_cyclicity()} |
332 {memory, NoWords :: integer() >= 0} |
333 {protection, Protection :: d_protection()}]
334 d_cyclicity() = acyclic | cyclic
335 d_protection() = private | protected
336 Returns a list of {Tag, Value} pairs describing digraph G. The
338 following pairs are returned:
339 * {cyclicity, Cyclicity}, where Cyclicity is cyclic or
341 acyclic, according to the options given to new.
342 * {memory, NoWords}, where NoWords is the number of words
344 allocated to the ETS tables.
345 * {protection, Protection}, where Protection is protected or
347 private, according to the options given to new.
348 new() -> graph()
350 Equivalent to new([]).
352 new(Type) -> graph()
354 Types:
356 Type = [d_type()]
358 d_type() = d_cyclicity() | d_protection()
359 d_cyclicity() = acyclic | cyclic
360 d_protection() = private | protected
361 Returns an empty digraph with properties according to the
363 options in Type:
364 cyclic:
366 Allows cycles in the digraph (default).
367 acyclic:
369 The digraph is to be kept acyclic.
370 protected:
372 Other processes can read the digraph (default).
373 private:
375 The digraph can be read and modified by the creating process
376 only.
377 If an unrecognized type option T is specified or Type is not a
379 proper list, a badarg exception is raised.
380 no_edges(G) -> integer() >= 0
382 Types:
384 G = graph()
386 Returns the number of edges of digraph G.
388 no_vertices(G) -> integer() >= 0
390 Types:
392 G = graph()
394 Returns the number of vertices of digraph G.
396 out_degree(G, V) -> integer() >= 0
398 Types:
400 G = graph()
402 V = vertex()
403 Returns the out-degree of vertex V of digraph G.
405 out_edges(G, V) -> Edges
407 Types:
409 G = graph()
411 V = vertex()
412 Edges = [edge()]
413 Returns a list of all edges emanating from V of digraph G, in
415 some unspecified order.
416 out_neighbours(G, V) -> Vertices
418 Types:
420 G = graph()
422 V = vertex()
423 Vertices = [vertex()]
424 Returns a list of all out-neighbors of V of digraph G, in some
426 unspecified order.
427 vertex(G, V) -> {V, Label} | false
429 Types:
431 G = graph()
433 V = vertex()
434 Label = label()
435 Returns {V, Label}, where Label is the label of the vertex V of
437 digraph G, or false if no vertex V of digraph G exists.
438 vertices(G) -> Vertices
440 Types:
442 G = graph()
444 Vertices = [vertex()]
445 Returns a list of all vertices of digraph G, in some unspecified
447 order.
448
450 digraph_utils(3), ets(3)
451Ericsson AB stdlib 3.4.5.1 digraph(3)