Skip to content

Graph + Espresso = Caffeinated Python graph data structure library!

License

Notifications You must be signed in to change notification settings

kdevo/grapresso

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

39 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Grapresso Logo

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...

  1. Object-oriented instead of using dicts for everything
  2. Abstracted and modular through separation of concerns
  3. 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

# Build a fully connected graph using InMemoryBackend (default if no backend is given):
graph = Graph() \
    .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)

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(
    # Map ISO codes to the nodes so that the text fits in the boundaries:
    labels={'Aachen': 'AC', 'Amsterdam': 'AMS', 'Brussels': 'BR', 'Luxembourg': 'LUX'},
    # Show cost as label:
    edge_label_selector='cost',
    # Mark edges that are actually in the tour
    mark_edges=tour.edges,
)

The resulting image:

Plotted graph using NetworkX backend

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 GitHub stars button. Thanks!

About

Graph + Espresso = Caffeinated Python graph data structure library!

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages