digraph_utils.3erl - Man Page

Algorithms for directed graphs.

Description

This module provides algorithms based on depth-first traversal of directed graphs. For basic functions on directed graphs, see the digraph(3) module.

Exports

arborescence_root(Digraph) -> no | {yes, Root}
Types:

Digraph = digraph:graph()
Root = digraph:vertex()

Returns {yes, Root} if Root is the root of the arborescence Digraph, otherwise no.

components(Digraph) -> [Component]
Types:

Digraph = digraph:graph()
Component = [digraph:vertex()]

Returns a list of connected components. Each component is represented by its vertices. The order of the vertices and the order of the components are arbitrary. Each vertex of digraph Digraph occurs in exactly one component.

condensation(Digraph) -> CondensedDigraph
Types:

Digraph = CondensedDigraph = digraph:graph()

Creates a digraph where the vertices are the strongly connected components of Digraph as returned by strong_components/1. If X and Y are two different strongly connected components, and vertices x and y exist 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 digraph has the same type as Digraph. All vertices and edges have the default label [].

Each cycle is included in some strongly connected component, which implies that a topological ordering of the created digraph always exists.

cyclic_strong_components(Digraph) -> [StrongComponent]
Types:

Digraph = digraph:graph()
StrongComponent = [digraph:vertex()]

Returns a list of strongly connected components. 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 cycle in Digraph are returned, otherwise the returned list is equal to that returned by strong_components/1.

is_acyclic(Digraph) -> boolean()
Types:

Digraph = digraph:graph()

Returns true if and only if digraph Digraph is acyclic.

is_arborescence(Digraph) -> boolean()
Types:

Digraph = digraph:graph()

Returns true if and only if digraph Digraph is an arborescence.

is_tree(Digraph) -> boolean()
Types:

Digraph = digraph:graph()

Returns true if and only if digraph Digraph is a tree.

loop_vertices(Digraph) -> Vertices
Types:

Digraph = digraph:graph()
Vertices = [digraph:vertex()]

Returns a list of all vertices of Digraph that are included in some loop.

postorder(Digraph) -> Vertices
Types:

Digraph = digraph:graph()
Vertices = [digraph:vertex()]

Returns all vertices of digraph Digraph. The order is given by a depth-first traversal 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.

preorder(Digraph) -> Vertices
Types:

Digraph = digraph:graph()
Vertices = [digraph:vertex()]

Returns all vertices of digraph Digraph. The order is given by a depth-first traversal of the digraph, collecting visited vertices in preorder.

reachable(Vertices, Digraph) -> Reachable
Types:

Digraph = digraph:graph()
Vertices = Reachable = [digraph:vertex()]

Returns an unsorted list of digraph vertices such that for each vertex in the list, there is a path in Digraph from some vertex of Vertices to the vertex. In particular, as paths can have length zero, the vertices of Vertices are included in the returned list.

reachable_neighbours(Vertices, Digraph) -> Reachable
Types:

Digraph = digraph:graph()
Vertices = Reachable = [digraph:vertex()]

Returns an unsorted list of digraph vertices such that for each vertex in the list, there is a path in Digraph of length one or more from some vertex of Vertices to the vertex. As a consequence, only those vertices of Vertices that are included in some cycle are returned.

reaching(Vertices, Digraph) -> Reaching
Types:

Digraph = digraph:graph()
Vertices = Reaching = [digraph:vertex()]

Returns an unsorted list of digraph vertices such that for each vertex in the list, there is a path from the vertex to some vertex of Vertices. In particular, as paths can have length zero, the vertices of Vertices are included in the returned list.

reaching_neighbours(Vertices, Digraph) -> Reaching
Types:

Digraph = digraph:graph()
Vertices = Reaching = [digraph:vertex()]

Returns an unsorted list of digraph vertices such that for each vertex in the list, there is a path of length one or more from the vertex to some vertex of Vertices. Therefore only those vertices of Vertices that are included in some cycle are returned.

strong_components(Digraph) -> [StrongComponent]
Types:

Digraph = digraph:graph()
StrongComponent = [digraph:vertex()]

Returns a list of strongly connected components. Each strongly component is represented by its vertices. The order of the vertices and the order of the components are arbitrary. Each vertex of digraph Digraph occurs in exactly one strong component.

subgraph(Digraph, Vertices) -> SubGraph
subgraph(Digraph, Vertices, Options) -> SubGraph
Types:

Digraph = SubGraph = digraph:graph()
Vertices = [digraph:vertex()]
Options = [{type, SubgraphType} | {keep_labels, boolean()}]
SubgraphType = inherit | [digraph:d_type()]

Creates a maximal subgraph of Digraph having as vertices those vertices of Digraph that are mentioned in Vertices.

If the value of option type is inherit, which is the default, the type of Digraph 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 option keep_labels is true, which is the default, the labels of vertices and edges of Digraph are used for the subgraph as well. If the value is false, default label [] is used for the vertices and edges of the subgroup.

subgraph(Digraph, Vertices) is equivalent to subgraph(Digraph, Vertices, []).

If any of the arguments are invalid, a badarg exception is raised.

topsort(Digraph) -> Vertices | false
Types:

Digraph = digraph:graph()
Vertices = [digraph:vertex()]

Returns a topological ordering of the vertices of digraph Digraph if such an ordering exists, otherwise false. For each vertex in the returned list, no out-neighbors occur earlier in the list.

See Also

digraph(3)

Referenced By

digraph.3erl(3), xref.3erl(3).

stdlib 5.2.3.1 Ericsson AB Erlang Module Definition