edsger 0.1.7

Graph algorithms in Cython.

Edsger

Directed graph algorithms in Cython

Welcome to our Python library for graph algorithms. The library includes both Dijkstra's and Bellman-Ford's algorithms, with plans to add more common path algorithms later. It is also open-source and easy to integrate with other Python libraries. To get started, simply install the library using pip, and import it into your Python project.

Documentation : https://edsger.readthedocs.io/en/latest/

Small example : Dijkstra's Algorithm

To use Dijkstra's algorithm, you can import the Dijkstra class from the path module. The function takes a graph and a source node as input, and returns the shortest path from the source node to all other nodes in the graph.

import pandas as pd

from edsger.path import Dijkstra

# Create a DataFrame with the edges of the graph
edges = pd.DataFrame({
    'tail': [0, 0, 1, 2, 2, 3],
    'head': [1, 2, 2, 3, 4, 4],
    'weight': [1, 4, 2, 1.5, 3, 1]
})
edges

	tail	head	weight
0	0	1	1.0
1	0	2	4.0
2	1	2	2.0
3	2	3	1.5
4	2	4	3.0
5	3	4	1.0

# Initialize the Dijkstra object
dijkstra = Dijkstra(edges)

# Run the algorithm from a source vertex
shortest_paths = dijkstra.run(vertex_idx=0)
print("Shortest paths:", shortest_paths)

Shortest paths: [0.  1.  3.  4.5 5.5]

We get the shortest paths from the source node 0 to all other nodes in the graph. The output is an array with the shortest path length to each node. A path length is the sum of the weights of the edges in the path.

Installation

Standard Installation

pip install edsger

Development Installation

For development work, clone the repository and install in development mode:

git clone https://github.com/aetperf/Edsger.git
cd Edsger
pip install -r requirements-dev.txt
pip install -e .

Why Use Edsger?

Edsger is designed to be dataframe-friendly, providing seamless integration with pandas workflows for graph algorithms. Also it is rather efficient on Linux. Our benchmarks on the USA road network (23.9M vertices, 57.7M edges) demonstrate nice performance:

Note that benchmarks are run on slightly different Intel processors between Linux and Windows.

Contributing

We welcome contributions to the Edsger library. If you have any suggestions, bug reports, or feature requests, please open an issue on our GitHub repository.

License

Edsger is licensed under the MIT License. See the LICENSE file for more details.

Contact

For any questions or inquiries, please contact me at [e-mail].