topSort {ggm} | R Documentation |
Permutates the nodes of a directed acyclic graph in such a way its edge matrix is upper triangular.
topSort(gmat)
gmat |
a square Boolean matrix with dimnames representing the edge matrix of a directed acyclic graph. |
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.
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. |
The order of the nodes defined by DAG
is that of their first
appearance in the model formulae (from left to right).
Giovanni M. Marchetti
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.
## A simple example dag <- DAG(a ~ b, c ~ a + b, d ~ c + b) dag m <- topSort(dag) m dag[m$perm, m$perm]