gRbase: graph-toposort – R documentation

Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!

graph-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

topo_sort(object, index = FALSE)

topo_sortMAT(amat, index = FALSE)

topoSort(object, index = FALSE)

topoSortMAT(amat, 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.
`amat`	Adjacency matrix.

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.

Synonymous functions

The functions 'topo_sort' / 'topoSort' are synonymous with 'topo_sortMAT' / 'topoSortMAT'. One of the groups may be deprecated in the future.

Note

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

Author(s)

Søren Højsgaard, sorenh@math.aau.dk

Examples

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

topo_sort(dagMAT)
topo_sort(dagMATS)
topo_sort(dagNEL)

gRbase

A Package for Graphical Modelling in R

v1.8-6.7

GPL (>= 2)

Authors

Søren Højsgaard <sorenh@math.aau.dk>

Initial release