ggm (version 2.3)

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)

Arguments

amat

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

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.

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

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