topSort {ggm}R Documentation

Topological sort

Description

Permutates the nodes of a directed acyclic graph in such a way its edge matrix is upper triangular.

Usage

topSort(gmat)

Arguments

gmat a square Boolean matrix with dimnames representing the edge matrix of a directed acyclic graph.

Details

The edge matrix of a directed acyclic graph (DAG) can always transformed into an upper triangular matrix by a permutation applied both to rows and columns. The ordering needs not to be unique. The algorithm to perform the ordering of the nodes is called topological sort.

Value

triu the sorted edge matrix in upper triangular form. If the edge matrix is already in upper triangular form it is leaved untrasformed.
perm the vector of the permutation.

Note

The order of the nodes defined by DAG is that of their first appearance in the model formulae (from left to right).

Author(s)

Giovanni M. Marchetti

References

Aho, A.V., Hopcrtoft, J.E. & Ullman, J.D. (1983). Data structures and algorithms. Reading: Addison-Wesley.

Lauritzen, S. (1996). Graphical models. Oxford: Clarendon Press.

See Also

DAG, is.acyclic

Examples

## A simple example
dag <- DAG(a ~ b, c ~ a + b, d ~ c + b)
dag
m <- topSort(dag)
m
dag[m$perm, m$perm]

[Package Contents]