transitive.reduction {nem}R Documentation

Computes the transitive reduction of a graph

Description

transitive.reduction removes direct edges, which can be explained by another path in the graph.

Usage

transitive.reduction(g)

Arguments

g graphNEL object

Details

transitive.reduction uses a modification of the classical algorithm from the Sedgewick book for computing transitive closures.

Value

returns a graph object with shortcuts removed

Author(s)

Holger Froehlich

References

R. Sedgewick, Algorithms, Pearson, 2002.

See Also

transitive.closure

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)
    
   par(mfrow=c(1,2))
   plot(gc,main="shortcut A->C")
   plot(g,main="shortcut removed")

[Package nem version 2.4.0 Index]