Metadata-Version: 2.4
Name: bmsspy
Version: 2.2.2
Summary: A pure python bmssp solver for python
Author-email: Connor Makowski <conmak@mit.edu>
Project-URL: Homepage, https://github.com/connor-makowski/bmsspy
Project-URL: Bug Tracker, https://github.com/connor-makowski/bmsspy/issues
Project-URL: Documentation, https://connor-makowski.github.io/bmsspy/bmsspy.html
Classifier: Programming Language :: Python :: 3
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Requires-Python: >=3.11
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: dev
Requires-Dist: pamda==2.8.1; extra == "dev"
Requires-Dist: scgraph<3.0.0,>=2.15.0; extra == "dev"
Requires-Dist: scgraph_data<3.0.0,>=2.0.0; extra == "dev"
Requires-Dist: pytest>=9.0.3; extra == "dev"
Requires-Dist: autoflake>=2.3.1; extra == "dev"
Requires-Dist: black>=25.1.0; extra == "dev"
Requires-Dist: build>=1.2.2; extra == "dev"
Requires-Dist: nox>=2026.4.10; extra == "dev"
Requires-Dist: nox-uv>=0.8.0; extra == "dev"
Requires-Dist: pdoc>=15.0.1; extra == "dev"
Requires-Dist: twine>=6.1.0; extra == "dev"
Dynamic: license-file

# BMSSPy
[![PyPI version](https://badge.fury.io/py/bmsspy.svg)](https://badge.fury.io/py/bmsspy)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
<!-- [![PyPI Downloads](https://img.shields.io/pypi/dm/bmsspy.svg?label=PyPI%20downloads)](https://pypi.org/project/bmsspy/) -->

A pure python bmssp implementation.

# Setup

Make sure you have Python 3.11.x (or higher) installed on your system. You can download it [here](https://www.python.org/downloads/).

### Installation

```
pip install bmsspy
```

### Documentation

- Github: https://github.com/connor-makowski/bmsspy
- Docs: https://connor-makowski.github.io/bmsspy/bmsspy.html
- Paper: https://ssrn.com/abstract=5777186

### How to Cite BMSSPy in your Research

If you use BMSSPy for your research, please consider citing the following paper:

> Makowski, Connor and Guter, Willem and Russell, Tim and Saragih, Austin, BMSSPy: A Python Package and Empirical Comparison of Bounded Multi-Source Shortest Path Algorithm (November 19, 2025). MIT Center for Transportation & Logistics Research Paper No. 2025/034, Available at SSRN: https://ssrn.com/abstract=5777186

Or by using the BibTeX entry:

```
@article{makowski2025bmsspy,
  title={BMSSPy: A Python Package and Empirical Comparison of Bounded Multi-Source Shortest Path Algorithm},
  author={Makowski, Connor and Guter, Willem and Russell, Tim and Saragih, Austin},
  journal={MIT Center for Transportation & Logistics Research Paper Series},
  number={2025-034},
  year={2025},
  url={https://ssrn.com/abstract=5777186}
}
```

### Use

The example use cases in this section are based on the following graph:

![readme_graph](https://raw.githubusercontent.com/connor-makowski/bmsspy/main/static/readme_graph.png)

```python
from bmsspy import Bmssp

# Graph with 5 nodes: 0..4
# Adjacency-list representation with nonnegative weights
graph = [
    {1: 1, 2: 1},   # 0 -> 1 (1), 0 -> 2 (1)
    {2: 1, 3: 3},   # 1 -> 2 (1), 1 -> 3 (3)
    {3: 1, 4: 2},   # 2 -> 3 (1), 2 -> 4 (2)
    {4: 2},         # 3 -> 4 (2)
    {}              # 4 has no outgoing edges
]

bmssp_graph = Bmssp(graph) # Initialize the graph as a Bmssp graph

# Distances and predecessors from origin 0
res_0 = bmssp_graph.solve(origin_id=0)
print(res_0) #=>
# {
#     'origin_id': 0,
#     'destination_id': None,
#     'predecessor': [-1, 0, 0, 2, 2],
#     'distance_matrix': [0.0, 1.0, 1.0, 2.0, 3.0],
#     'path': None,
#     'length': None
# }

# Shortest path from 0 to 4
res_0_4 = bmssp_graph.solve(origin_id=0, destination_id=4)
print(res_0_4) #=>
# {
#     'origin_id': 0,
#     'destination_id': 4,
#     'predecessor': [-1, 0, 0, 2, 2],
#     'distance_matrix': [0.0, 1.0, 1.0, 2.0, 3.0],
#     'path': [0, 2, 4],
#     'length': 3
# }
```

In the example above, we only use a single orign, however multiple origins are supported if passed as a set:

```python
# Pass orgin_id as a set of ids
res_02 = bmssp_graph.solve(origin_id={0,2})
print(res_02) #=>
# {
#     'origin_id': [0, 2],
#     'destination_id': None,
#     'predecessor': [-1, 0, -1, 2, 2],
#     'distance_matrix': [0.0, 1.0, 0.0, 1.0, 2.0],
#     'path': None,
#     'length': None
# }
```

By default graphs that are given are converted to constant degree such that worst case asymtotic run times are based on the constant degree converted graphs. Before returning a result, the constant degree conversion is undone such that the results are in the original passed graph format.

Most real world graphs are not constant degree. Converting to constant degree graphs can add substantial operational overhead during pre and post processing as well as during the actual algorithmic runtime.

To skip the constant degree conversion:
```python
# Set use_constant_degree_graph=False
bmssp_graph = Bmssp(graph=graph, use_constant_degree_graph=False)
```



# Contributing

Contributions are welcome! Please open an issue or submit a pull request.

## Development

To avoid extra development overhead, we expect all developers to use a unix based environment (Linux or Mac). If you use Windows, please use WSL2.

For development, we use [uv](https://docs.astral.sh/uv/) to manage dependencies and run tests.

## Making Changes

1) Fork the repo and clone it locally.
2) Make your modifications.
3) Run tests and make sure they pass.
4) Prettify your code.
5) **DO NOT GENERATE DOCS**.
    - We will generate the docs and update the version number when we are ready to release a new version.
6) Only commit relevant changes and add clear commit messages.
    - Atomic commits are preferred.
7) Submit a pull request.

## Development Commands

| Command | What it does |
|---|---|
| `uv run nox` | Run tests across Python 3.11, 3.12, 3.13, 3.14 |
| `uv run nox -s tests-3.14` | Run tests on a single Python version |
| `uv run pytest` | Run tests in the local venv |
| `uv run pytest -v` | Run tests with verbose output |
| `uv run python utils/prettify.py` | Format with autoflake + black |

Dev dependencies are in `[project.optional-dependencies] dev` in `pyproject.toml`. Install with `uv sync --extra dev`.
