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]