powergrid_synth.transmission.preprocessing

Preprocessing stage (Algorithm 1) for the Chung-Lu Chain (CLC) model.

Prepares the degree sequence, box assignments, and path vertex selections needed by EdgeCreator.

See Aksoy et al. (2018) (arXiv:1711.11098, Appendix A.2–A.3) for the full algorithm description.

Module Contents

class powergrid_synth.transmission.preprocessing.Preprocessor[source]

Preprocessing for a single same-voltage subgraph (Algorithm 1).

Given desired degrees \(\mathbf{d}\) and diameter \(\delta\), produces an inflated degree sequence, box assignments, and diameter/subdiameter path vertex sets used by the CLC edge generator.

See Aksoy et al. (2018), Section 4.3 and Appendix A.3.

assign_boxes(indices, boxes)[source]

Randomly assign vertices to boxes (Lines 43–49 of Algorithm 1).

Each vertex index is assigned to a uniformly random box from the provided list.

Parameters:

  • indices (numpy.ndarray) – Vertex indices to assign.

  • boxes (list of int) – Available box IDs.

Returns:

Mapping {vertex_index: box_id}.

Return type:

dict

run_setup(desired_degrees, input_diameter)[source]

Execute the Setup procedure (Algorithm 1).

The preprocessing performs five steps:

  1. Diameter adjustment (Line 3): \(\delta \leftarrow \text{round}\!\big(\delta - 2\log(\eta/(\delta+1))\big)\).

  2. Degree-sequence inflation (Lines 4–8): duplicate random nonzero-degree entries until the expected number of Chung-Lu isolated vertices \(\sum_i e^{-d_i}\) matches the number of zero-degree vertices \(n - \eta\).

  3. Box assignment (Lines 9–22): distribute non-isolated vertices into \(\delta+1\) boxes, optionally keeping some boxes empty so each non-empty box can support the maximum degree.

  4. Diameter path (Lines 25–35): select \(\delta+1\) vertices (degree \(\geq 3\) preferred) and place one in each box.

  5. Subdiameter path (Lines 37–45): select up to \(\delta+1\) additional vertices and assign to centred consecutive boxes.

Parameters:

  • desired_degrees (list of int) – Input degree sequence \(\mathbf{d}\).

  • input_diameter (int) – Desired diameter \(\delta\).

Returns:

  • d_prime (numpy.ndarray) – Inflated degree sequence \(\mathbf{d}'\).

  • v (numpy.ndarray) – Vertex-to-box mapping (v[i] = box ID; -1 = unassigned).

  • D (set of int) – Diameter path vertex indices.

  • S (set of int) – Subdiameter path vertex indices.

Return type:

Tuple[numpy.ndarray, numpy.ndarray, Set[int], Set[int]]