Caffeinated object-oriented Python graph data structure library originated from an academical context.
Grapresso ☕ is like a good espresso among other graph libs:
Grapresso works wonderfully with PyPy and is up to up to 4x faster than your regular Python. ⚡
This project is in an early state. There are many popular algorithms that are not yet implemented (at least natively, read below)
Feel free to contribute! Make it feel like home for your own graph algorithms.
Goals
Grapresso vs. alternatives
There are many other good graph/network theory libraries.
The most popular Python one is probably NetworkX.
From an algorithmic perspective, Grapresso will never be able to beat this extremely versatile library with a long history.
Instead, it follows a different philosophy and aims to be...
- Object-oriented
instead of using dicts for everything
- Abstracted and modular through separation of concerns
- Finally, a meta library to handle other libraries via backends
💡 To fully demonstrate the power of abstraction, Grapresso can be used as a middleman for NetworkX.
Usage
Install from PyPI, for instance via pip (needs Python >= 3.6):
pip install grapresso
Want to get the cheapest tour (round-trip) for TSP? Usage is easy:
from grapresso import Graph
graph = Graph() \
.add_edge("Aachen", "Amsterdam", cost=230) \
.add_edge("Amsterdam", "Brussels", cost=200) \
.add_edge("Brussels", "Aachen", cost=142)
for city, dist in zip(("Aachen", "Brussels", "Amsterdam"), (200, 212, 420)):
graph.add_edge(city, "Luxembourg", cost=dist)
tour = graph.cheapest_tour("Aachen")
assert tour.cost == 842
print(tour)
Now, printing to console is not really visually appealing, is it?
Let's install a backend plugin
as an extra
that is also capable of drawing the graph:
pip install grapresso[backend-networkx]
Let's quickly draw our previous graph by first converting it to one that uses NetworkX in the background
and then utilizing NetworkX's natural drawing capabilities:
from grapresso.backends import NetworkXBackend
nx_graph = graph.copy_to(Graph(NetworkXBackend(directed=False)))
nx_graph.backend.quick_draw(
labels={'Aachen': 'AC', 'Amsterdam': 'AMS', 'Brussels': 'BR', 'Luxembourg': 'LUX'},
edge_label_selector='cost',
mark_edges=tour.edges,
)
The resulting image:
See tests directory for more examples and also have a look at the
integration tests!
Architecture
Grapresso provides a clean API so that you can easily extend it to store the graph's structure in your preferred storage format.
Algorithms are implemented completely independent from the backend.
Backends
Algorithms are performed on a so called "backend" which wraps the graph's internal data structure.
The API is defined in backend/api.py. Therewith, backends can easily be added provided that they carefully implement the defined API.
Implementations
Implementation | Type | Underlying data structure | Plugin installation |
---|
InMemoryBackend | In-Memory with Traits | {node_name: obj} with obj containing edges | Built-in |
NetworkXBackend | NetworkX compatible | nx.DiGraph with custom NetworkXNode/-Edge | pip install grapresso[backend-networkx] |
Development
This project has been originated in the subject Mathematical Methods for Computer Science (translated from the German "Mathematische Methoden der Informatik", abbreviated MMI)
in the study programme Information Systems Engineering (ISE) at the FH Aachen.
Contributing
Contributions are welcome, as long as the three goals are followed.
Otherwise, you can simply support this project by hitting the button.
Thanks!