ggm (version 0.5)

topSort: 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.

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.

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.

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]