1"""
  2# BMSSPy
  3[![PyPI version](https://badge.fury.io/py/bmsspy.svg)](https://badge.fury.io/py/bmsspy)
  4[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
  5<!-- [![PyPI Downloads](https://img.shields.io/pypi/dm/bmsspy.svg?label=PyPI%20downloads)](https://pypi.org/project/bmsspy/) -->
  6
  7A pure python bmssp implementation.
  8
  9# Setup
 10
 11Make sure you have Python 3.11.x (or higher) installed on your system. You can download it [here](https://www.python.org/downloads/).
 12
 13### Installation
 14
 15```
 16pip install bmsspy
 17```
 18
 19### Documentation
 20
 21- Github: https://github.com/connor-makowski/bmsspy
 22- Docs: https://connor-makowski.github.io/bmsspy/bmsspy.html
 23- Paper: https://ssrn.com/abstract=5777186
 24
 25### How to Cite BMSSPy in your Research
 26
 27If you use BMSSPy for your research, please consider citing the following paper:
 28
 29> 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
 30
 31Or by using the BibTeX entry:
 32
 33```
 34@article{makowski2025bmsspy,
 35  title={BMSSPy: A Python Package and Empirical Comparison of Bounded Multi-Source Shortest Path Algorithm},
 36  author={Makowski, Connor and Guter, Willem and Russell, Tim and Saragih, Austin},
 37  journal={MIT Center for Transportation & Logistics Research Paper Series},
 38  number={2025-034},
 39  year={2025},
 40  url={https://ssrn.com/abstract=5777186}
 41}
 42```
 43
 44### Use
 45
 46The example use cases in this section are based on the following graph:
 47
 48![readme_graph](https://raw.githubusercontent.com/connor-makowski/bmsspy/main/static/readme_graph.png)
 49
 50```python
 51from bmsspy import Bmssp
 52
 53# Graph with 5 nodes: 0..4
 54# Adjacency-list representation with nonnegative weights
 55graph = [
 56    {1: 1, 2: 1},   # 0 -> 1 (1), 0 -> 2 (1)
 57    {2: 1, 3: 3},   # 1 -> 2 (1), 1 -> 3 (3)
 58    {3: 1, 4: 2},   # 2 -> 3 (1), 2 -> 4 (2)
 59    {4: 2},         # 3 -> 4 (2)
 60    {}              # 4 has no outgoing edges
 61]
 62
 63bmssp_graph = Bmssp(graph) # Initialize the graph as a Bmssp graph
 64
 65# Distances and predecessors from origin 0
 66res_0 = bmssp_graph.solve(origin_id=0)
 67print(res_0) #=>
 68# {
 69#     'origin_id': 0,
 70#     'destination_id': None,
 71#     'predecessor': [-1, 0, 0, 2, 2],
 72#     'distance_matrix': [0.0, 1.0, 1.0, 2.0, 3.0],
 73#     'path': None,
 74#     'length': None
 75# }
 76
 77# Shortest path from 0 to 4
 78res_0_4 = bmssp_graph.solve(origin_id=0, destination_id=4)
 79print(res_0_4) #=>
 80# {
 81#     'origin_id': 0,
 82#     'destination_id': 4,
 83#     'predecessor': [-1, 0, 0, 2, 2],
 84#     'distance_matrix': [0.0, 1.0, 1.0, 2.0, 3.0],
 85#     'path': [0, 2, 4],
 86#     'length': 3
 87# }
 88```
 89
 90In the example above, we only use a single orign, however multiple origins are supported if passed as a set:
 91
 92```python
 93# Pass orgin_id as a set of ids
 94res_02 = bmssp_graph.solve(origin_id={0,2})
 95print(res_02) #=>
 96# {
 97#     'origin_id': [0, 2],
 98#     'destination_id': None,
 99#     'predecessor': [-1, 0, -1, 2, 2],
100#     'distance_matrix': [0.0, 1.0, 0.0, 1.0, 2.0],
101#     'path': None,
102#     'length': None
103# }
104```
105
106By 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.
107
108Most 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.
109
110To skip the constant degree conversion:
111```python
112# Set use_constant_degree_graph=False
113bmssp_graph = Bmssp(graph=graph, use_constant_degree_graph=False)
114```
115
116
117
118## Development
119
120To avoid extra development overhead, we expect all developers to use a unix based environment (Linux or Mac). If you use Windows, please use WSL2.
121
122For development, we test using Docker so we can lock system deps and swap out python versions easily. However, you can also use a virtual environment if you prefer. We provide a test script and a prettify script to help with development.
123
124### Making Changes
125
1261) Fork the repo and clone it locally.
1272) Make your modifications.
1283) Use Docker or a virtual environment to run tests and make sure they pass.
1294) Prettify your code.
1305) **DO NOT GENERATE DOCS**.
131    - We will generate the docs and update the version number when we are ready to release a new version.
1326) Only commit relevant changes and add clear commit messages.
133    - Atomic commits are preferred.
1347) Submit a pull request.
135
136### Docker
137
138Make sure Docker is installed and running.
139
140- Create a docker container and drop into a shell
141    - `./run.sh`
142- Run all tests (see ./utils/test.sh)
143    - `./run.sh test`
144- Prettify the code (see ./utils/prettify.sh)
145    - `./run.sh prettify`
146
147- Note: You can and should modify the `Dockerfile` to test different python versions.
148
149### Virtual Environment
150
151- Create a virtual environment
152    - `python3.XX -m venv venv`
153        - Replace `3.XX` with your python version (3.11 or higher)
154- Activate the virtual environment
155    - `source venv/bin/activate`
156- Install the development requirements
157    - `pip install -r requirements/dev.txt`
158- Run Tests
159    - `./utils/test.sh`
160- Prettify Code
161    - `./utils/prettify.sh`"""
162
163from bmsspy.entrypoint import Bmssp