Caution: As a special service "Fossies" has tried to format the requested manual source page into HTML format but links to other man pages may be missing or even errorneous.
Alternatively you can here view or download the uninterpreted manual source code.
A member file download can also be achieved by clicking within a package contents listing on the according byte size field. See also the latest Fossies "Diffs" side-by-side code changes report for "digraph_utils.3": 21.3_vs_22.0.

DESCRIPTION

EXPORTS

SEE ALSO

digraph_utils − Algorithms for directed graphs.

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

* |
A | ||

* |
Digraphs can be annotated with more information. Such
information can be attached to the vertices and to the edges
of the digraph. An annotated digraph is called a | ||

* |
An edge e = (v, w) is said to | ||

* |
If an edge is emanating from v and incident on w, then w
is said to be an | ||

* |
A | ||

* |
The | ||

* |
Path P is a | ||

* |
A | ||

* |
An | ||

* |
A | ||

* |
A | ||

* |
The problem of | ||

* |
A | ||

* |
G’ is | ||

* |
A | ||

* |
A | ||

* |
An | ||

* |
A |

**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.

*digraph(3)*