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. Regulation directions inferred via `infer.edge.type` are taken into account.

### Usage

    transitive.reduction(g)

### Arguments

`g` | adjacency matrix

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

### Value

returns an adjacency matrix with shortcuts removed

### Author(s)

Holger Froehlich

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

[Package nem version 2.60.0 Index]