ordering: Compute vertex ordering for an undirected graph

Description Usage Arguments Details Value Author(s) References Examples

Description

Compute vertex ordering for an undirected graph

Usage

1
2
3

Arguments

g

an instance of the graph class with edgemode “undirected”

delta

Multiple elimination control variable. If it is larger than or equal to zero then multiple elimination is enabled. The value of delta specifies the difference between the minimum degree and the degree of vertices that are to be eliminated.

w1

First heuristic weight for the Sloan algorithm.

w2

Second heuristic weight for the Sloan algorithm.

Details

The following details were obtained from the documentation of these algorithms in Boost Graph Library and readers are referred their for even more detail. The goal of the Cuthill-Mckee (and reverse Cuthill-Mckee) ordering algorithm is to reduce the bandwidth of a graph by reordering the indices assigned to each vertex.

The minimum degree ordering algorithm is a fill-in reduction matrix reordering algorithm.

The goal of the Sloan ordering algorithm is to reduce the profile and the wavefront of a graph by reordering the indices assigned to each vertex.

The goal of the King ordering algorithm is to reduce the bandwidth of a graph by reordering the indices assigned to each vertex.

Value

cuthill.mckee.ordering

returns a list with elements:

reverse cuthill.mckee.ordering

the vertices in the new ordering

original bandwidth

bandwidth before reordering vertices

new bandwidth

bandwidth after reordering of vertices

minDegreeOrdering

return a list with elements:

inverse_permutation

the new vertex ordering, given as the mapping from the new indices to the old indices

permutation

the new vertex ordering, given as the mapping from the old indices to the new indices

sloan.ordering

returns a list with elements:

sloan.ordering

the vertices in the new ordering

bandwidth

bandwidth of the graph after reordering

profile

profile of the graph after reordering

maxWavefront

maxWavefront of the graph after reordering

aver.wavefront

aver.wavefront of the graph after reordering

rms.wavefront

rms.wavefront of the graph after reordering

Author(s)

Li Long <li.long@isb-sib.ch>

References

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

The Boost Graph Library: User Guide and Reference Manual; by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine; (Addison-Wesley, Pearson Education Inc., 2002), xxiv+321pp. ISBN 0-201-72914-8

Examples

1
2
3
4
5
6
7
8
con <- file(system.file("XML/dijkex.gxl",package="RBGL"), open="r")
coex <- fromGXL(con)
close(con)

coex <- ugraph(coex)
cuthill.mckee.ordering(coex)
minDegreeOrdering(coex)
sloan.ordering(coex)

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

$`reverse cuthill.mckee.ordering`
[1] "A" "B" "E" "C" "D"

$`original bandwidth`
[1] 4

$`new bandwidth`
[1] 3

$inverse_permutation
[1] "B" "A" "C" "E" "D"

$permutation
[1] "B" "A" "C" "E" "D"

$sloan.ordering
[1] "A" "E" "C" "B" "D"

$bandwidth
[1] 3

$profile
[1] 17

$maxWavefront
[1] 4

$aver.wavefront
[1] 2.6

$rms.wavefront
[1] 2.792848

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