physdes.steiner_forest namespace

Submodules

physdes.steiner_forest.congestion_map module

physdes.steiner_forest.congestion_map.draw_congestion_map(grid, filename='congestion_map.svg')

Generate an SVG visualization of a network congestion map.

This function creates an SVG image showing a grid where each cell’s color represents its congestion level (0-100%), using a green-yellow-red gradient.

Parameters:

• grid (list[list[int]]) – A 2D list of integers representing congestion values (0-100).

• filename (str) – The output filename for the SVG file.

Examples

>>> grid = [[0, 50, 100], [25, 75, 50]]
>>> draw_congestion_map(grid, "test.svg")
Congestion map saved to test.svg

physdes.steiner_forest.steiner_forest_grid module

class physdes.steiner_forest.steiner_forest_grid.UnionFind(size)

Bases: object

A Union-Find (Disjoint Set Union) data structure with path compression and union by rank.

This implementation supports efficient union and find operations for managing connected components, commonly used in graph algorithms like Kruskal’s MST.

Examples

>>> uf = UnionFind(10)
>>> uf.union(1, 2)
True
>>> uf.union(2, 3)
True
>>> uf.find(1) == uf.find(3)
True
>>> uf.union(1, 3)
False

__init__(size)

Initialize the Union-Find structure.

Parameters:

size (int) – The number of elements in the set.

find(idx)

Find the representative (root) of the set containing idx.

Uses path compression to flatten the tree structure for faster future lookups.

Parameters:

idx (int) – The index to find.

Returns:

The representative (root) of the set.

Return type:

int

union(idx1, idx2)

Unite the sets containing idx1 and idx2.

Uses union by rank to keep the tree balanced.

Parameters:

• idx1 (int) – First index.

• idx2 (int) – Second index.

Returns:

True if a union was performed, False if already in same set.

Return type:

bool

physdes.steiner_forest.steiner_forest_grid.generate_svg(height, width, F_pruned, sources, terminals, steiner_nodes, cell_size, margin, filename)

Generate an SVG visualization of a Steiner forest on a grid.

This function creates an SVG image showing the grid with nodes (sources in red, terminals in green, Steiner nodes in blue) and selected edges highlighted.

Parameters:

• height (int) – Grid height.

• width (int) – Grid width.

• F_pruned (List[Tuple[int, int, float]]) – List of edges in the Steiner forest as (u, v, cost) tuples.

• sources (Set[int]) – Set of source node indices.

• terminals (Set[int]) – Set of terminal node indices.

• steiner_nodes (Set[int]) – Set of Steiner node indices.

• cell_size (int) – Size of each grid cell in pixels.

• margin (int) – Margin around the grid in pixels.

• filename (str) – Output SVG filename.

physdes.steiner_forest.steiner_forest_grid.main()

Main function to run the example.

physdes.steiner_forest.steiner_forest_grid.steiner_forest_grid(height, width, pairs)

Computes an approximate Steiner forest on a grid graph.

The algorithm is based on the primal-dual approach for the Steiner network problem. It iteratively pays for edges until all terminal pairs are connected.

The following diagram illustrates the concept of a Steiner tree, where ‘o’ represents terminals and ‘*’ represents Steiner points.

In our case, we are looking for a Steiner forest, which is a collection of Steiner trees connecting specified pairs of terminals.

The algorithm works by “growing” paths from terminals. Each active component (a connected component containing at least one terminal that needs to be connected to a terminal in another component) contributes to the cost of edges.

When the cost paid for an edge equals its weight, the edge is added to the forest.

The following diagrams illustrate the concept in 3D as well.

After the growing phase, a reverse-delete step is performed to remove redundant edges from the forest.

>>> h = 2
>>> w = 2
>>> pairs = [((0, 0), (1, 1))]
>>> F_pruned, total_cost, sources, terminals, steiner_nodes = steiner_forest_grid(h, w, pairs)
>>> sorted(F_pruned)
[(0, 1, 1.0), (1, 3, 1.0)]
>>> total_cost
2.0
>>> sources
{0}
>>> terminals
{3}
>>> steiner_nodes
{1}

Return type:

Tuple[List[Tuple[int, int, float]], float, Set[int], Set[int], Set[int]]