max_balanced_partition: Finds an Approximately Balanced Connected Partition

In pedmod: Pedigree Models

Finds an Approximately Balanced Connected Partition

Description

Uses the method suggested by Chlebíková (1996) to construct an approximate maximally balanced connected partition. A further refinement step can be made to reduce the cost of the cut edges. See vignette("pedigree_partitioning", package = "pedmod") for further details.

Usage

max_balanced_partition(
  from,
  to,
  weight_data = NULL,
  edge_weights = NULL,
  slack = 0,
  max_kl_it_inner = 50L,
  max_kl_it = 10000L,
  trace = 0L,
  check_weights = TRUE,
  do_reorder = FALSE
)

max_balanced_partition_pedigree(
  id,
  father.id,
  mother.id,
  id_weight = NULL,
  father_weight = NULL,
  mother_weight = NULL,
  slack = 0,
  max_kl_it_inner = 50L,
  max_kl_it = 10000L,
  trace = 0L,
  check_weights = TRUE,
  do_reorder = FALSE
)

Arguments

from	integer vector with one of the vertex ids.
to	integer vector with one of the vertex ids.
weight_data	list with two elements called "id" for the id and "weight" for the vertex weight. All vertices that are not in this list have a weight of one. Use NULL if all vertices have a weight of one.
edge_weights	numeric vector with weights for each edge. Needs to have the same length as from and to. Use NULL if all edges should have a weight of one.
slack	fraction between zero and 0.5 for the allowed amount of deviation from the balance criterion that is allowed to reduce the cost of the cut edges.
max_kl_it_inner	maximum number of moves to consider in each iteration when slack > 0.
max_kl_it	maximum number of iterations to use when reducing the cost of the cut edges. Typically the method converges quickly and this argument is not needed.
trace	integer where larger values yields more information printed to the console during the procedure.
check_weights	logical for whether to check the weights in each biconnected component. This may fail if the graph is not connected in which case the results will likely be wrong. It may also fail for large graphs because of floating-point arithmetic. The latter is not an error and the reason for this argument.
do_reorder	logical for whether the implementation should reorder the vertices. This may reduce the computation time for some data sets.
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.
id_weight	numeric vector with the weight to use for each vertex (individual). NULL yields a weight of one for all.
father_weight	weights of the edges created between the fathers and the children. Use NULL if all should have a weight of one.
mother_weight	weights of the edges created between the mothers and the children. Use NULL if all should have a weight of one.

Value

A list with the following elements:

balance_criterion	value of the balance criterion.
removed_edges	2D integer matrix with the removed edges.
set_1,set_2	The two sets in the partition.

References

Chlebíková, J. (1996). Approximating the maximally balanced connected partition problem in graphs. Information Processing Letters, 60(5), 225-230.

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

See Also

biconnected_components, block_cut_tree, and unconnected_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))

# the results may be different because of different orders!
out_pedigree <- max_balanced_partition_pedigree(
  id = dat_pedigree$id, father.id = dat_pedigree$dad,
  mother.id = dat_pedigree$mom)
out <- max_balanced_partition(dat$to, dat$from)

all.equal(out_pedigree$balance_criterion, out$balance_criterion)
all.equal(out_pedigree$removed_edges, out$removed_edges)

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