topSort {ggm}

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.

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.

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.

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)

Kevin P. Murphy, 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, isAcyclic

Examples

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