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
>>> g = Graph(4)
>>> g.add_edge(0, 1)
>>> g.add_edge(2, 3)
>>> g.add_edge(2, 1)
>>> g.matrix
array([[0, 1, 0, 0],
[1, 0, 1, 0],
[0, 1, 0, 1],
[0, 0, 1, 0]], dtype=int32)
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
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 Distributions
Built Distributions
Hashes for leafy-0.1.2-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d8ec441fee2902433cd2119818302c027a43adfbcc5c6d1ca7e4d83cdaf33b87 |
|
MD5 | 8c6f15459d3a85a4d36d08535fa019a8 |
|
BLAKE2b-256 | 58472afc54e9cca7126f584c292ac44e3156b6dcd12c8d2f84e5bf0401378b7b |
Hashes for leafy-0.1.2-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7b9389bd91007d5746181b82996a86fee1d75559452993aa24655f9b5d7c2801 |
|
MD5 | e8420f7d5101f98e6d9e822dadc4016d |
|
BLAKE2b-256 | d8f818fcc55813e784606200f963091206de2138b382716b7a0cca4f9e08e09b |
Hashes for leafy-0.1.2-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8e7e2a162feb9e8366d7b33693b905c3f0daeadb19122f82d64c1914db9919d1 |
|
MD5 | 36ad51fbd0b4126959cb110aaf53d73a |
|
BLAKE2b-256 | 3b6ab648a2efa61566256218bd84a07fe363fbb436214836bffa4b354d79a09e |
Hashes for leafy-0.1.2-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9148857026540fe2532a6be9b1d0a3795daf35949beee7ef5c57e10d25e7a4bb |
|
MD5 | 904c68a1ec86bc68250fe85f2164034f |
|
BLAKE2b-256 | d3c7cdab25d12f87933e3944404f88c860241568d8204926e4d4449d183c7227 |
Hashes for leafy-0.1.2-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3766ac35a1fd8e54b748c87f41ef3f664aa20812d10ed56a7d2e3f39376835ef |
|
MD5 | 3493b55959e687056f1d0f15d159d9ab |
|
BLAKE2b-256 | f3ae957face3349684b511fc91a8dfe53028d898282772f88fcdd4f475458ff0 |
Hashes for leafy-0.1.2-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 588e39e4c30dc3aeac74d4247e5789e8850856e3c0b7b093f659e8f3d979ca73 |
|
MD5 | 32e1ba729427783ad2dac893eb455438 |
|
BLAKE2b-256 | 0830af0c820d8fd0239932e651afe29a6f608cbf3d764d011590a2f4e77afdf9 |
Hashes for leafy-0.1.2-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7e31e379f440a5d680aba7bb3a58b3c2d18cd72346a95c5a0eb3cffd70f7a264 |
|
MD5 | 2eb0b501b668e020f2b0e1ba33b6930c |
|
BLAKE2b-256 | 7891392e1d69cfb938a824ad68239934b43beeb88d39fc1a9bb9a1384555c039 |