gRbase (version 1.7-5)

topoSort: Topological sort of vertices in directed acyclic graph

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. Can hence be used for checking if a graph is a DAG.

Usage

topoSort(object, index = FALSE)

Arguments

object

An graph represented either as a graphNEL object, an igraph, a (dense) matrix, a (sparse) dgCMatrix.

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, "dgCMatrix")
dagNEL  <- as(dagMAT, "graphNEL")

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