dominatorTree: Compute dominator tree from a vertex in a directed graph

In RBGL: An interface to the BOOST graph library

Description

Compute dominator tree from a vertex in a directed graph

Usage

dominatorTree(g, start=nodes(g)[1])
lengauerTarjanDominatorTree(g, start=nodes(g)[1])

Arguments

g	a directed graph, one instance of the graph class
start	a vertex in graph g

Details

As stated in documentation on Lengauer Tarjan dominator tree in Boost Graph Library:

A vertex u dominates a vertex v, if every path of directed graph from the entry to v must go through u.

This function builds the dominator tree for a directed graph.

Value

Output is a vector, giving each node its immediate dominator.

Author(s)

Li Long <[e-mail]>

References

Boost Graph Library ( www.boost.org/libs/graph/doc/index.html )

Examples

con1 <- file(system.file("XML/dominator.gxl",package="RBGL"), open="r")
g1 <- fromGXL(con1)
close(con1)

dominatorTree(g1)
lengauerTarjanDominatorTree(g1)

Example output

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, basename, cbind, colMeans, colSums, colnames,
    dirname, 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

  0   1   2   3   4   5   6   7 
"0" "0" "1" "1" "3" "4" "4" "1" 
  0   1   2   3   4   5   6   7 
"0" "0" "1" "1" "3" "4" "4" "1" 

RBGL documentation built on Nov. 8, 2020, 5 p.m.