Partition Generation

Initial feasible partition generators and helpers.

Internal helper for building components given pairwise constraints.

Parameters:

  • N (int) – Number of nodes.

  • must_link (sequence of tuple of int, optional) – Pairwise must-link constraints.

  • cannot_link (sequence of tuple of int, optional) – Pairwise cannot-link constraints.

Returns:

Computed result.

Return type:

Optional[Dict[str, Any]]

asunder.base.utils.partition_generation._component_order_from_node_order(order_idx, cid, C)

Internal helper for building a component visitation order induced by a node visitation order.

Parameters:

  • order_idx (List[int]) – Node indices in the desired traversal order.

  • cid (np.ndarray) – Component ID for each node; cid[i] gives the component containing node i.

  • C (int) – Total number of components.

Returns:

comp_order – Component IDs in the order they first appear in order_idx, followed by any components not encountered (in increasing component ID).

Return type:

List[int]

asunder.base.utils.partition_generation._greedy_color_fixed_K(comp_order, forb, K_used, rng, jitter_top=1)

Internal helper for greedy coloring given a fixed K.

Parameters:

  • comp_order (List[int]) – Ordered list of must-link component IDs to assign (e.g., in the sequence they will be colored/placed).

  • forb (List[set]) – Component-level cannot-link adjacency; forb[c] is the set of component IDs that component c is forbidden to share a group with.

  • K_used (int) – Number of communities.

  • rng (np.random.Generator) – Random number generator.

  • jitter_top (int) – If 0 or 1: no real randomness (always pick the single best). If 2: randomly choose between the top 2 candidates. Larger values → more diversity across runs but can limit freedom when K is fixed.

Returns:

comp2g – Component-to-group assignment vector of length C. Entry comp2g[c] is the group/color ID assigned to component c.

Return type:

Optional[np.ndarray]

asunder.base.utils.partition_generation._greedy_color_unbounded_K(comp_order, forb)

Internal helper for greedy coloring given an unbounded K.

Parameters:

  • comp_order (List[int]) – Ordered list of must-link component IDs to assign (e.g., in the sequence they will be colored/placed).

  • forb (List[set]) – Component-level cannot-link adjacency; forb[c] is the set of component IDs that component c is forbidden to share a group with.

Returns:

comp2g – Component-to-group assignment vector of length C. Entry comp2g[c] is the group/color ID assigned to component c.

Return type:

Optional[np.ndarray]

Returns a partition given an order, pairwise constraints and other parameters.

Parameters:

  • order_idx (List[int]) – Input parameter.

  • N (int) – Number of nodes.

  • K (int or None, optional) – Target number of communities.

  • must_link (sequence of tuple of int, optional) – Pairwise must-link constraints.

  • cannot_link (sequence of tuple of int, optional) – Pairwise cannot-link constraints.

  • max_K_increase (int, optional) – Maximum allowed increase above the requested K when additional partitions are needed to satisfy the cannot-link structure. If 0, the routine enforces the requested K exactly.

  • max_restarts (int) – maximum number of restarts.

  • jitter_top (int) – If 0 or 1: no real randomness (always pick the single best). If 2: randomly choose between the top 2 candidates. Larger values → more diversity across runs but can limit freedom when K is fixed.

  • seed (int, optional) – Random seed used to initialize the sampling procedure.

Returns:

Partition vector and metadata.

Return type:

Optional[Tuple[np.ndarray, Dict[str, int]]]

asunder.base.utils.partition_generation._pairs_to_indices(pairs, node_to_idx)

Internal helper for mapping the names of node pairs to indices.

Parameters:

  • pairs (Optional[Sequence[Tuple[Hashable, Hashable]]]) – Sequence of node pairs.

  • node_to_idx (Dict[Hashable, int]) – Node to index map.

Returns:

Sequence of node pairs with integer identifiers.

Return type:

Optional[List[Tuple[int, int]]]

Generates partly ordered feasible partitions subject to only pairwise link constraints.

Parameters:

  • G (nx.Graph) – NetworkX graph.

  • K (int or None, optional) – Target number of communities.

  • must_link (sequence of tuple of int, optional) – Pairwise must-link constraints.

  • cannot_link (sequence of tuple of int, optional) – Pairwise cannot-link constraints.

  • n_cols (int, optional) – Number of columns.

  • seed (int, optional) – Random seed used to initialize the sampling procedure.

  • nodes (array-like, optional) – List of Graph nodes.

  • max_K_increase (int, optional) – Maximum allowed increase above the requested K` when additional partitions are needed to satisfy the cannot-link structure. If 0, the routine enforces the requested K exactly.

Returns:

Z_star – List of generated partitions.

Return type:

list(array)

Generate random feasible partitions subject only to pairwise link constraints.

Parameters:

  • N (int) – Number of nodes.

  • K (int or None, optional) – Target number of communities.

  • must_link (sequence of tuple of int, optional) – Pairwise must-link constraints.

  • cannot_link (sequence of tuple of int, optional) – Pairwise cannot-link constraints.

  • seed (int, optional) – Random seed used to initialize the sampling procedure.

  • return_Z (bool, optional) – Boolean that determines if the (N, N) partition matrix Z is returned or not.

  • max_K_increase (int, optional) – Maximum allowed increase above the requested K when additional partitions are needed to satisfy the cannot-link structure. If 0, the routine enforces the requested K exactly.

  • n_parts (int, optional) – Number of feasible random partitions to generate.

Returns:

List of feasible random partitions.

If return_Z is True, each element is a partition assignment matrix, typically of shape (N, N).

If return_Z is False, each element is a dict with keys that refer to the name of the partition, a 1D representation of the partition and the number of communities in it.

Return type:

list

asunder.base.utils.partition_generation.make_simple_partition(N, cannot_link=None, seed=42)

Create a single all-ones partition matrix with cannot-link zeroed pairs.

Parameters:

  • N (int) – Number of nodes.

  • cannot_link (Sequence[tuple[int, int]] | None) – List of nodes that cannot be linked.

Returns:

Generated partition.

Return type:

list[array]