transitive.reduction: Computes the transitive reduction of a graph

In nem: (Dynamic) Nested Effects Models and Deterministic Effects Propagation Networks to reconstruct phenotypic hierarchies

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

Example output

Loading required package: Rgraphviz
Loading required package: graph
Loading required package: BiocGenerics
Loading required package: parallel

Attaching package: 'BiocGenerics'

The following objects are masked from 'package:parallel':

    clusterApply, clusterApplyLB, clusterCall, clusterEvalQ,
    clusterExport, clusterMap, parApply, parCapply, parLapply,
    parLapplyLB, parRapply, parSapply, parSapplyLB

The following objects are masked from 'package:stats':

    IQR, mad, sd, var, xtabs

The following objects are masked from 'package:base':

    Filter, Find, Map, Position, Reduce, anyDuplicated, append,
    as.data.frame, cbind, colMeans, colSums, colnames, do.call,
    duplicated, eval, evalq, get, grep, grepl, intersect, is.unsorted,
    lapply, lengths, mapply, match, mget, order, paste, pmax, pmax.int,
    pmin, pmin.int, rank, rbind, rowMeans, rowSums, rownames, sapply,
    setdiff, sort, table, tapply, union, unique, unsplit, which,
    which.max, which.min

Loading required package: grid

nem documentation built on Oct. 31, 2019, 2:12 a.m.