block_cut_tree: Creates a Block-cut Tree Like Object

In pedmod: Pedigree Models

Creates a Block-cut Tree Like Object

Description

Creates a block-cut tree like structure computed using the method suggested by Hopcroft et al. (1973).

Usage

block_cut_tree(from, to)

block_cut_tree_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 tree structure where each node is represented as list that contains the vertices in the biconnected component, the cut_vertices, and the node's leafs.

References

Hopcroft, J., & Tarjan, R. (1973). Algorithm 447: efficient algorithms for graph manipulation. Communications of the ACM, 16(6), 372-378.

See Also

biconnected_components 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 <- block_cut_tree_pedigree(
  id = dat_pedigree$id, father.id = dat_pedigree$dad,
  mother.id = dat_pedigree$mom)
out <- block_cut_tree(dat$to, dat$from)
all.equal(out_pedigree, out)

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