Skip to main content

Another fast graph algorithms library

Project description

Leafy Graph Library

Leafy is a python graph library written in cython. This mix gives the speed of writing the library in c with the benefit of python bindings.

Usage

Graph Objects

Leafy supports two types of graphs: Dense and Sparse. These are represented by the classes leafy.graph.Graph and leafy.graph.SparseGraph.

To instantiate a graph object we need to know the number of nodes (verticies) in the graph, and if the graph is directed. Graphs defualt to undirected.

>>> from leafy.graph import Graph
>>> from pprint import pprint
>>> g = Graph(4)
>>> g.add_edge(0, 1)
>>> g.add_edge(2, 3)
>>> g.add_edge(2, 1)
>>> pprint(g.matrix)
[[1000001.0, 1.0, 1000001.0, 1000001.0],
 [1.0, 1000001.0, 1.0, 1000001.0],
 [1000001.0, 1.0, 1000001.0, 1.0],
 [1000001.0, 1000001.0, 1.0, 1000001.0]]

the same edges can be defined as a directed SparseGraph

>>> from leafy.graph import SparseGraph
>>> g = SparseGraph(4, True)
>>> g.add_edge(0, 1)
>>> g.add_edge(2, 3)
>>> g.add_edge(2, 1)
>>> g.list
[[1], [], [3, 1], []]

Search

Leafy can run Depth First Search (DFS) and Breadth First Search (BFS) on a graph and return the graph search properties.

To run a search we need to define the graph to search and the node to start from. Before you can view the properties we must call .run().

>>> from leafy.search import DFS
>>> graph = small_graph(request.param)
>>> dfs = DFS(graph, 0)
>>> dfs.run()
>>> dfs.simple_path(12)
[0, 1, 2, 11, 12]
>>> dfs.bridges
[(1, 3), (3, 4), (3, 5), (2, 11), (11, 12)]

Digraphs

For diagraphs leafy supports DFS which can be imported from leafy.digraph

>>> from leafy.digraph import DFS
>>> dag = small_dag()
>>> dfs = DFS(dag, 0)
>>> dfs.run()
>>> dfs.is_dag
True
>>> dfs.topological_order()
[0, 6, 2, 3, 5, 4, 9, 11, 12, 10, 1]

Shortest Distance

For network shortest path leafy supports single source Dijkstra which can be imported from leafy.shortest_path

>>> from leafy.shortest_path import Dijkstra
>>> dag = small_network()
>>> dij = Dijkstra(dag, 0)
>>> dij.run()
>>> dij.path(3)
[3, 7, 2, 1, 0]

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for leafy, version 0.1.3
Filename, size File type Python version Upload date Hashes
Filename, size leafy-0.1.3-cp37-cp37m-macosx_10_9_x86_64.whl (135.0 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size leafy-0.1.3-cp37-cp37m-manylinux1_x86_64.whl (569.6 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size leafy-0.1.3-cp37-cp37m-win32.whl (125.5 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size leafy-0.1.3-cp37-cp37m-win_amd64.whl (146.0 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size leafy-0.1.3-cp38-cp38-macosx_10_9_x86_64.whl (137.1 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size leafy-0.1.3-cp38-cp38-manylinux1_x86_64.whl (599.0 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size leafy-0.1.3-cp38-cp38-win32.whl (128.4 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size leafy-0.1.3-cp38-cp38-win_amd64.whl (149.0 kB) File type Wheel Python version cp38 Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page