ggm (version 2.5.1)

topSort: Topological sort

Description

topOrder returns the topological order of a directed acyclic graph (parents, before children). topSort permutates the adjacency matrix according to the topological order.

Usage

topSort(amat)
topOrder(amat)

Value

topOrder(amat) returns a vector of integers representing the permutation of the nodes. topSort(amat) returns the adjacency matrix with rows and columns permutated.

Arguments

amat

a square Boolean matrix with dimnames, representing the adjacency matrix of a directed acyclic graph.

Author

Kevin P. Murphy, Giovanni M. Marchetti

Details

The topological order needs not to be unique. After the permutation the adjacency matrix of the graph is upper triangular. The function is a translation of the Matlab function topological_sort in Toolbox BNT written by Kevin P. Murphy.

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, isAcyclic

Examples

## A simple example
dag <- DAG(a ~ b, c ~ a + b, d ~ c + b)
dag
topOrder(dag)
topSort(dag)