pedmod (version 0.2.4)

biconnected_components: 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)

Value

A list with vectors of vertices in each biconnected component. An attribute called "cut_verices" contains the cut vertices in each biconnected component.

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 NA if it is missing.

mother.id

integer vector with the mother id. May be NA if it is missing.

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)