topSort function

Topological sort

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

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.

Returns

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).

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.

Author(s)

Kevin P. Murphy, Giovanni M. Marchetti

See Also

DAG, isAcyclic

Examples

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