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

NAME

6       digraph - Directed graphs.
7

DESCRIPTION

9       This module provides a version of labeled directed graphs ("digraphs").
10
11       The  digraphs managed by this module are stored in ETS tables. That im‐
12       plies the following:
13
14         * Only the process that created the digraph is allowed to update it.
15
16         * 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
20         * A digraph is a mutable data structure.
21
22       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
26         * 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
31           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
35         * 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
41         * An edge e = (v, w) is said to emanate from vertex v and to be inci‐
42           dent on vertex w.
43
44         * The out-degree of a vertex is the number of  edges  emanating  from
45           that vertex.
46
47         * The  in-degree  of a vertex is the number of edges incident on that
48           vertex.
49
50         * 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
53         * 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
57         * The length of path P is k-1.
58
59         * Path  P  is  simple  if  all vertices are distinct, except that the
60           first and the last vertices can be the same.
61
62         * Path P is a cycle if the length of P is not zero and v[1] = v[k].
63
64         * A loop is a cycle of length one.
65
66         * A simple cycle is a path that is both a cycle and simple.
67
68         * An acyclic digraph is a digraph without cycles.
69

DATA TYPES

71       d_type() = d_cyclicity() | d_protection()
72
73       d_cyclicity() = acyclic | cyclic
74
75       d_protection() = private | protected
76
77       graph()
78
79              A digraph as returned by new/0,1.
80
81       edge()
82
83       label() = term()
84
85       vertex()
86

EXPORTS

88       add_edge(G, V1, V2) -> edge() | {error, add_edge_err_rsn()}
89
90       add_edge(G, V1, V2, Label) -> edge() | {error, add_edge_err_rsn()}
91
92       add_edge(G, E, V1, V2, Label) ->
93                   edge() | {error, add_edge_err_rsn()}
94
95              Types:
96
97                 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
104              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
108              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
112              add_edge(G, V1, V2) is equivalent to add_edge(G, V1, V2, []).
113
114              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
121       add_vertex(G) -> vertex()
122
123       add_vertex(G, V) -> vertex()
124
125       add_vertex(G, V, Label) -> vertex()
126
127              Types:
128
129                 G = graph()
130                 V = vertex()
131                 Label = label()
132
133              add_vertex/3  creates (or modifies) vertex V of digraph G, using
134              Label as the (new) label of the vertex. Returns V.
135
136              add_vertex(G, V) is equivalent to add_vertex(G, V, []).
137
138              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
142       del_edge(G, E) -> true
143
144              Types:
145
146                 G = graph()
147                 E = edge()
148
149              Deletes edge E from digraph G.
150
151       del_edges(G, Edges) -> true
152
153              Types:
154
155                 G = graph()
156                 Edges = [edge()]
157
158              Deletes the edges in list Edges from digraph G.
159
160       del_path(G, V1, V2) -> true
161
162              Types:
163
164                 G = graph()
165                 V1 = V2 = vertex()
166
167              Deletes edges from digraph G until there are no paths from  ver‐
168              tex V1 to vertex V2.
169
170              A sketch of the procedure employed:
171
172                * Find  an arbitrary simple path v[1], v[2], ..., v[k] from V1
173                  to V2 in G.
174
175                * Remove all edges of G emanating from v[i]  and  incident  to
176                  v[i+1] for 1 <= i < k (including multiple edges).
177
178                * Repeat until there is no path between V1 and V2.
179
180       del_vertex(G, V) -> true
181
182              Types:
183
184                 G = graph()
185                 V = vertex()
186
187              Deletes  vertex  V from digraph G. Any edges emanating from V or
188              incident on V are also deleted.
189
190       del_vertices(G, Vertices) -> true
191
192              Types:
193
194                 G = graph()
195                 Vertices = [vertex()]
196
197              Deletes the vertices in list Vertices from digraph G.
198
199       delete(G) -> true
200
201              Types:
202
203                 G = graph()
204
205              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
210       edge(G, E) -> {E, V1, V2, Label} | false
211
212              Types:
213
214                 G = graph()
215                 E = edge()
216                 V1 = V2 = vertex()
217                 Label = label()
218
219              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
223       edges(G) -> Edges
224
225              Types:
226
227                 G = graph()
228                 Edges = [edge()]
229
230              Returns  a  list  of all edges of digraph G, in some unspecified
231              order.
232
233       edges(G, V) -> Edges
234
235              Types:
236
237                 G = graph()
238                 V = vertex()
239                 Edges = [edge()]
240
241              Returns a list of all edges emanating from or incident on  V  of
242              digraph G, in some unspecified order.
243
244       get_cycle(G, V) -> Vertices | false
245
246              Types:
247
248                 G = graph()
249                 V = vertex()
250                 Vertices = [vertex(), ...]
251
252              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
257              get_path/3 is used for finding a simple cycle through V.
258
259       get_path(G, V1, V2) -> Vertices | false
260
261              Types:
262
263                 G = graph()
264                 V1 = V2 = vertex()
265                 Vertices = [vertex(), ...]
266
267              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
272              Digraph  G  is  traversed in a depth-first manner, and the first
273              found path is returned.
274
275       get_short_cycle(G, V) -> Vertices | false
276
277              Types:
278
279                 G = graph()
280                 V = vertex()
281                 Vertices = [vertex(), ...]
282
283              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
288              get_short_path/3 is used for finding a simple cycle through V.
289
290       get_short_path(G, V1, V2) -> Vertices | false
291
292              Types:
293
294                 G = graph()
295                 V1 = V2 = vertex()
296                 Vertices = [vertex(), ...]
297
298              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
303              Digraph G is traversed in a breadth-first manner, and the  first
304              found path is returned.
305
306       in_degree(G, V) -> integer() >= 0
307
308              Types:
309
310                 G = graph()
311                 V = vertex()
312
313              Returns the in-degree of vertex V of digraph G.
314
315       in_edges(G, V) -> Edges
316
317              Types:
318
319                 G = graph()
320                 V = vertex()
321                 Edges = [edge()]
322
323              Returns  a list of all edges incident on V of digraph G, in some
324              unspecified order.
325
326       in_neighbours(G, V) -> Vertex
327
328              Types:
329
330                 G = graph()
331                 V = vertex()
332                 Vertex = [vertex()]
333
334              Returns a list of all in-neighbors of V of digraph  G,  in  some
335              unspecified order.
336
337       info(G) -> InfoList
338
339              Types:
340
341                 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
349              Returns  a  list of {Tag, Value} pairs describing digraph G. The
350              following pairs are returned:
351
352                * {cyclicity,  Cyclicity},  where  Cyclicity  is   cyclic   or
353                  acyclic, according to the options given to new.
354
355                * {memory,  NoWords}, where NoWords is the number of words al‐
356                  located to the ETS tables.
357
358                * {protection, Protection}, where Protection is  protected  or
359                  private, according to the options given to new.
360
361       new() -> graph()
362
363              Equivalent to new([]).
364
365       new(Type) -> graph()
366
367              Types:
368
369                 Type = [d_type()]
370                 d_type() = d_cyclicity() | d_protection()
371                 d_cyclicity() = acyclic | cyclic
372                 d_protection() = private | protected
373
374              Returns  an  empty  digraph with properties according to the op‐
375              tions in Type:
376
377                cyclic:
378                  Allows cycles in the digraph (default).
379
380                acyclic:
381                  The digraph is to be kept acyclic.
382
383                protected:
384                  Other processes can read the digraph (default).
385
386                private:
387                  The digraph can be read and modified by the creating process
388                  only.
389
390              If  an  unrecognized type option T is specified or Type is not a
391              proper list, a badarg exception is raised.
392
393       no_edges(G) -> integer() >= 0
394
395              Types:
396
397                 G = graph()
398
399              Returns the number of edges of digraph G.
400
401       no_vertices(G) -> integer() >= 0
402
403              Types:
404
405                 G = graph()
406
407              Returns the number of vertices of digraph G.
408
409       out_degree(G, V) -> integer() >= 0
410
411              Types:
412
413                 G = graph()
414                 V = vertex()
415
416              Returns the out-degree of vertex V of digraph G.
417
418       out_edges(G, V) -> Edges
419
420              Types:
421
422                 G = graph()
423                 V = vertex()
424                 Edges = [edge()]
425
426              Returns a list of all edges emanating from V of  digraph  G,  in
427              some unspecified order.
428
429       out_neighbours(G, V) -> Vertices
430
431              Types:
432
433                 G = graph()
434                 V = vertex()
435                 Vertices = [vertex()]
436
437              Returns  a  list of all out-neighbors of V of digraph G, in some
438              unspecified order.
439
440       vertex(G, V) -> {V, Label} | false
441
442              Types:
443
444                 G = graph()
445                 V = vertex()
446                 Label = label()
447
448              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
451       vertices(G) -> Vertices
452
453              Types:
454
455                 G = graph()
456                 Vertices = [vertex()]
457
458              Returns a list of all vertices of digraph G, in some unspecified
459              order.
460

SEE ALSO

462       digraph_utils(3), ets(3)
463
464
465
466Ericsson AB                      stdlib 5.1.1                       digraph(3)
Impressum