biconnected_components {pedmod} | R Documentation |
Finds the Biconnected Components
Description
Finds the biconnected components and the cut vertices (articulation points) using the methods suggested by Hopcroft et al. (1973).
Usage
biconnected_components(from, to)
biconnected_components_pedigree(id, father.id, mother.id)
Arguments
from |
integer vector with one of the vertex ids. |
to |
integer vector with one of the vertex ids. |
id |
integer vector with the child id. |
father.id |
integer vector with the father id. May be |
mother.id |
integer vector with the mother id. May be |
Value
A list with vectors of vertices in each biconnected component. An
attribute called "cut_verices"
contains the cut vertices in each
biconnected component.
References
Hopcroft, J., & Tarjan, R. (1973). Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6), 372-378.
See Also
block_cut_tree
and
max_balanced_partition
.
Examples
# example of a data set in pedigree and graph form
library(pedmod)
dat_pedigree <- data.frame(
id = 1:48,
mom = c(
NA, NA, 2L, 2L, 2L, NA, NA, 7L, 7L, 7L, 3L, 3L, 3L, 3L, NA, 15L, 15L, 43L,
18L, NA, NA, 21L, 21L, 9L, 9L, 9L, 9L, NA, NA, 29L, 29L, 29L, 30L, 30L, NA,
NA, 36L, 36L, 36L, 38L, 38L, NA, NA, 43L, 43L, 43L, 32L, 32L),
dad = c(NA, NA, 1L, 1L, 1L, NA, NA, 6L, 6L, 6L, 8L, 8L, 8L, 8L, NA, 4L, 4L,
42L, 5L, NA, NA, 20L, 20L, 22L, 22L, 22L, 22L, NA, NA, 28L, 28L, 28L,
23L, 23L, NA, NA, 35L, 35L, 35L, 31L, 31L, NA, NA, 42L, 42L, 42L,
45L, 45L),
sex = c(1L, 2L, 2L, 1L, 1L, 1L, 2L, 1L, 2L, 2L, 2L, 1L, 1L, 1L, 2L, 2L, 2L,
2L, 1L, 1L, 2L, 1L, 1L, 2L, 1L, 1L, 2L, 1L, 2L, 2L, 1L, 2L, 2L, 2L,
1L, 2L, 1L, 2L, 1L, 2L, 1L, 1L, 2L, 2L, 1L, 1L, 2L, 2L))
dat <- list(
to = c(
3L, 4L, 5L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 16L, 17L, 18L, 19L, 22L, 23L,
24L, 25L, 26L, 27L, 30L, 31L, 32L, 33L, 34L, 37L, 38L, 39L, 40L, 41L, 44L,
45L, 46L, 47L, 48L, 3L, 4L, 5L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 16L, 17L,
18L, 19L, 22L, 23L, 24L, 25L, 26L, 27L, 30L, 31L, 32L, 33L, 34L, 37L, 38L,
39L, 40L, 41L, 44L, 45L, 46L, 47L, 48L),
from = c(
1L, 1L, 1L, 6L, 6L, 6L, 8L, 8L, 8L, 8L, 4L, 4L, 42L, 5L, 20L, 20L, 22L, 22L,
22L, 22L, 28L, 28L, 28L, 23L, 23L, 35L, 35L, 35L, 31L, 31L, 42L, 42L, 42L,
45L, 45L, 2L, 2L, 2L, 7L, 7L, 7L, 3L, 3L, 3L, 3L, 15L, 15L, 43L, 18L, 21L,
21L, 9L, 9L, 9L, 9L, 29L, 29L, 29L, 30L, 30L, 36L, 36L, 36L, 38L, 38L, 43L,
43L, 43L, 32L, 32L))
# they give the same
out_pedigree <- biconnected_components_pedigree(
id = dat_pedigree$id, father.id = dat_pedigree$dad,
mother.id = dat_pedigree$mom)
out <- biconnected_components(dat$to, dat$from)
all.equal(out_pedigree, out)
[Package pedmod version 0.2.4 Index]