Graph + Espresso = Caffeinated Python graph data structure library!
Project description
Caffeinated Python graph data structure library originated from an academical context (see Development).
Grapresso :coffee: is like a good espresso among other common graph libraries:
- Quickly consumed: Easy-to-learn and setup
- Selectable beans: Choose your purpose-dependent storage format (e.g. in-memory or file-based)
- Clean and lightweight: Written in pure Python 3, no external libraries needed
- Concentrated: Clear and concise algorithms
- Make your Macchiato: Extensible by design
- Well tested ingredients: Stress-integration-tested using huge graphs
There are many popular algorithms that are not yet implemented. Feel free to contribute! Make it feel like home for your own graph algorithms if you want to.
Usage
Want to get the shortest tour (round-trip) for TSP? Usage is easy:
from grapresso import UndirectedGraph
# Build a fully connected graph using InMemoryBackend (default if no backend is given):
graph = UndirectedGraph() \
.add_edge("Aachen", "Amsterdam", cost=230) \
.add_edge("Amsterdam", "Brussels", cost=200) \
.add_edge("Brussels", "Aachen", cost=142)
# Now also add Luxembourg - note that every city needs to be connected to it for the graph to stay fully connected:
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)
See tests directory for more examples!
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 |
---|---|---|
InMemoryBackend | In-Memory with Traits | {node_name: obj} |
PickleFileBackend | Pickle file-based | Files with ${hash(obj)}.node as filename |
:warning: Be careful, the
PickleFileBackend
is not properly tested and more of an experiment right now!
Development
This project has been created in the subject "Mathematical Methods for Computer Science" (translated from the German "Mathematische Methoden der Informatik") at the FH Aachen. Contributions are welcome!
Conventions
- :deciduous_tree: Project structure
- :beers: gitmoji - Semantic commit messages
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for grapresso-0.0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 87f11574c20f650df4c8f949907c235a8e4eed60bf757386b612870a70d8a28d |
|
MD5 | 71e36f77d5419b3f29227cd23e429ac5 |
|
BLAKE2b-256 | ff7d416fcdfb8409d6955e2c1e048bc2e53dd12a2d62ba598d900ba3b6fa235c |