transitive.reduction: Computes the transitive reduction of a graph
In cbg-ethz/pcNEM: Probabilistic combinatorial nested effects model

Description Usage Arguments Details Value Author(s) References See Also Examples

transitive.reduction removes direct edges, which can be explained by another path in the graph. Regulation directions inferred via infer.edge.type are taken into account.

1	transitive.reduction(g)

`g`	adjacency matrix

transitive.reduction uses a modification of the classical algorithm from the Sedgewick book for computing transitive closures. The so-called "transitive reduction" is neither necessarily unique (only for DAGs) nor minimal in the number of edges (this could be improved).

returns an adjacency matrix with shortcuts removed

Holger Froehlich

R. Sedgewick, Algorithms, Pearson, 2002.

transitive.closure, infer.edge.type

   V <- LETTERS[1:3]
   edL <- list(A=list(edges=c("B","C")),B=list(edges="C"),C=list(edges=NULL))
   gc <- new("graphNEL",nodes=V,edgeL=edL,edgemode="directed")
   g <- transitive.reduction(gc)
    
   if(require(Rgraphviz)){
    par(mfrow=c(1,2))
    plot(gc,main="shortcut A->C")
    plot(as(g,"graphNEL"),main="shortcut removed")
  }