graph-toposort: Topological sort of vertices in directed acyclic graph In gRbase: A Package for Graphical Modelling in R

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

 ```1 2 3 4 5 6``` ```topoSort(object, index = FALSE) ## Default S3 method: 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.

Note

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

Author(s)

S<c3><b8>ren H<c3><b8>jsgaard, [email protected]

`dag`, `ug`
 ```1 2 3 4 5 6 7``` ```dagMAT <- dag(~a:b:c+c:d:e, result="matrix") dagMATS <- as(dagMAT, "dgCMatrix") dagNEL <- as(dagMAT, "graphNEL") topoSort(dagMAT) topoSort(dagMATS) topoSort(dagNEL) ```