nem (version 2.46.0)

transitive.reduction: Computes the transitive reduction of a graph

Description

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.

Usage

transitive.reduction(g)

Arguments

g

adjacency matrix

Value

returns an adjacency matrix with shortcuts removed

Details

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

References

R. Sedgewick, Algorithms, Pearson, 2002.

See Also

transitive.closure, infer.edge.type

Examples

   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")
  }