Metadata-Version: 2.4
Name: partigraph
Version: 0.1.0
Summary: Graph partitioning algorithms using random spanning trees
Author-email: Todd Proebsting <proebsting@arizona.edu>
License: MIT
Project-URL: Repository, https://github.com/proebsting/partigraph
Keywords: graph,partition,spanning-tree,redistricting
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: networkx
Provides-Extra: docs
Requires-Dist: sphinx>=7.0; extra == "docs"
Requires-Dist: sphinx-rtd-theme; extra == "docs"
Dynamic: license-file

# Partigraph

Graph partitioning algorithms using random spanning trees.

Partigraph implements algorithms for partitioning graphs into districts of approximately equal weight. It uses random spanning trees to find transfer moves between partitions and iteratively improve divisions to meet weight constraints.

## Features

- **Uniform Random Spanning Trees**: Implementation of Wilson's algorithm for generating uniformly random spanning trees
- **Weight-Balanced Partitioning**: Divide graphs into districts with configurable weight constraints
- **Iterative Improvement**: Refine partitions through random spanning tree-based transfers
- **Flexible Weight Functions**: Support for custom node weight functions or node attributes

## Installation

```bash
pip install partigraph
```



## Algorithm

Partigraph uses a divide-and-conquer approach:

1. Generate a random spanning tree of the graph using Wilson's algorithm
2. Find the edge cut that best divides the graph into the target weights
3. Recursively partition each side
4. Iteratively improve the partition by finding beneficial transfers between districts

The random spanning tree approach ensures good connectivity properties and helps avoid gerrymandering-like artifacts.

## Requirements

- Python >= 3.12
- NetworkX

## License

MIT License - see LICENSE file for details

## References

Wilson's algorithm for uniform random spanning trees:
- Wilson, D. B. (1996). "Generating Random Spanning Trees More Quickly than the Cover Time"
