gRbase (version 1.6-12)

topoSort: Topological sort of vertices in directed

Description

A topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge (u->v), u comes before v in the ordering. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering.

Usage

topoSort(object, index = FALSE)

Arguments

object

A graph represented as a graphNEL object or an adjacency matrix. An adjacency matrix can either be a standard matrix or a sparse dgCMatrix matrix (from the Matrix package).

index

If FALSE, an ordering is returned if it exists and character(0) otherwise. If TRUE, the index of the variables in an adjacency matrix is returned and -1 otherwise.

Value

• If FALSE, an ordering is returned if it exists and character(0) otherwise. If TRUE, the index of the variables in an adjacency matrix is returned and -1 otherwise.

Note

The workhorse is the topoSortMAT function which takes an adjacency matrix as input

Warning

Do not use index=TRUE when the input is a graphNEL object; the result is unpredictable.

See Also

dag, ug

Examples

dagMAT  <- dag(~a:b:c+c:d:e, result="matrix")
dagMATS <- as(dagMAT, "Matrix")
dagNEL  <- dag(~a:b:c+c:d:e, result="NEL")

topoSort(dagMAT)
topoSort(dagMATS)
topoSort(dagNEL)