biconnected_components: Finds the Biconnected Components

In pedmod: Pedigree Models

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 NA if it is missing.
mother.id	integer vector with the mother id. May be NA if it is missing.

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)

pedmod documentation built on Sept. 11, 2022, 5:05 p.m.