![[Erlang Systems]](min_head.gif)
The digraph_utils module implements some algorithms
based on depth-first traversal of directed graphs. See the
digraph module for basic functions on directed graphs.
A directed graph (or just "graph") is a pair (V, E) of a finite set V of vertices and a finite set E of directed edges (or just "edges"). The set of edges E is a subset of V × V (the Cartesian product of V with itself).
Graphs can be annotated with additional information. Such information may be attached to the vertices and to the edges of the graph. A graph which has been annotated is called a labeled graph, and the information attached to a vertex or an edge is called a label.
An edge e = (v, w) is said to emanate from vertex v and to be incident on vertex w. If there is an edge emanating from v and incident on w, then w is is said to be an out-neighbour of v. A path P from v[1] to v[k] in a graph (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 length of the path P is k-1. P is a cycle if the length of P is not zero and v[1] = v[k]. A loop is a cycle of length one. An acyclic graph is a graph that has no cycles.
A depth-first traversal of a directed graph can be viewed as a process that visits all vertices of the graph. 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.
A partial ordering of a
set S is a transitive, antisymmetric and reflexive relation
between the objects of S. The problem of topological sorting is to find a total
ordering of S that is a superset of the partial ordering. A
graph G = (V, E) is equivalent to a relation E on
V (we neglect the fact that the version of directed graphs
implemented in the digraph module allows multiple edges
between vertices). If the graph has no cycles of length
two or more, then the reflexive and transitive closure of E is a
partial ordering.
A subgraph G´ of G is a graph whose vertices and edges form subsets of the vertices and edges of G. G´ is maximal with respect to a property P if all other subgraphs that include the vertices of G´ do not have the property P. A strongly connected component is a maximal subgraph such that there is a path between each pair of vertices. A connected component is a maximal subgraph such that there is a path between each pair of vertices, considering all edges undirected.
components(Graph) -> [Component]
Graph = graph()Component = [vertex()]Returns a list of connected components. Each component is represented by its vertices. The order of vertices and the order of components are arbitrary. Each vertex of the graph is occurs in exactly one component.
strong_components(Graph) -> [StrongComponent]
Graph = graph()StrongComponent = [vertex()]Returns a list of strongly connected components. Each strongly component is represented by its vertices. The order of vertices and the order of components are arbitrary. Each vertex of the graph is occurs in exactly one strong component.
cyclic_strong_components(Graph) -> [StrongComponent]
Graph = graph()StrongComponent = [vertex()]Returns a list of strongly connected
components. Each strongly component is represented
by its vertices. The order of vertices and the order of
components are arbitrary. Only vertices that are included
in some cycle are
returned, otherwise the returned list is equal to that
returned by strong_components/1.
reachable(Vertices, Graph) -> Vertices
Graph = graph()Vertices = [vertex()]Returns an unsorted list of graph vertices such that for each vertex in the list, there is a path from some of the given vertices to the vertex. In particular, since paths may have length zero, all the given vertices are included in the returned list.
reachable_neighbours(Vertices, Graph) -> Vertices
Graph = graph()Vertices = [vertex()]Returns an unsorted list of graph vertices such that for each vertex in the list, there is a path of length one or more from some of the given vertices to the vertex. As a consequence, only those of the given vertices that are included in some cycle are returned.
reaching(Vertices, Graph) -> Vertices
Graph = graph()Vertices = [vertex()]Returns an unsorted list of graph vertices such that for each vertex in the list, there is a path from the vertex to some of the given vertices. In particular, since paths may have length zero, all the given vertices are included in the returned list.
reaching_neighbours(Vertices, Graph) -> Vertices
Graph = graph()Vertices = [vertex()]Returns an unsorted list of graph vertices such that for each vertex in the list, there is a path of length one or more from the vertex to some of the given vertices. As a consequence, only those of the given vertices that are included in some cycle are returned.
topsort(Graph) -> Vertices | false
Graph = graph()Vertices = [vertex()]Returns a topological
ordering of all the graph´s vertices if such an
ordering exists, false otherwise. For each vertex in
the list, there are no out-neighbours that occur
earlier in the list.
Graph = graph()Returns true if and only if the graph is acyclic.
loop_vertices(Graph) -> Vertices
Graph = graph()Vertices = [vertex()]Returns a list of all vertices that are included in some loop.
subgraph(Graph, Vertices, Options) -> Subgraph | {error, Reason}
subgraph(Graph, Vertices) -> Subgraph | {error, Reason}
Graph = Subgraph = graph()Options = [{type, SubgraphType}, {keep_labels, bool()}]Reason = {invalid_option, term()} | {unknown_type, term()}SubgraphType = inherit | type()Vertices = [vertex()]Creates a maximal subgraph of Graph having
as vertices those vertices of Graph that are
mentioned in Vertices.
If the value of the option type is inherit,
which is the default, then the type of Graph is used
for the subgraph as well. Otherwise the option value of type
is used as argument to digraph:new/1.
If the value of the option keep_labels is true,
which is the default, then the labels of vertices and edges
of Graph are used for the subgraph as well. If the value
is false, then the default label, [], is used
for the subgraph´s vertices and edges.
subgraph(Graph, Vertices) is equivalent to
subgraph(Graph, Vertices, []).
condensation(Graph) -> CondensedGraph
Graph = CondensedGraph = graph()Creates a graph where the vertices are the
strongly connected
components as returned by
strong_components/1. 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
emanating from x
and incident on y,
then an edge emanating from X and incident on Y is created.
The created graph has the same type as Graph. All
vertices and edges have the default
label [].
Each and every cycle is included in some strongly connected component, which implies that there always exists a topological ordering of the created graph.
Graph = graph()Vertices = [vertex()]Returns all vertices of the graph. The order is given by a depth-first traversal of the graph, collecting visited vertices in pre-order.
Graph = graph()Vertices = [vertex()]Returns all vertices of the graph. The order is given by a depth-first traversal of the graph, 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.
digraph(3)