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
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.5-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 795869ad0789091ff0448bd98cdb6695a39072864eeaa9e26baffe8466d3c97b |
|
MD5 | 934d939c60799113961b48d628093aab |
|
BLAKE2b-256 | fca70e928b9e8ee6fb5197c25aa21f785ed34c91e7657fbedb7956ea0b0bb026 |
Hashes for leafy-0.1.5-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5dc027b3f75fe558c68fccb23317e46a1cb27bf848acb272261fb2630b851000 |
|
MD5 | 9742196be6aa6cbf133d6df6b242387d |
|
BLAKE2b-256 | 95e9ff33118359506b9e963b20ff58418706a4f3805ac4fd1067505ea0bb79e9 |
Hashes for leafy-0.1.5-cp311-cp311-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b794db7722eee88d5544fc95ef3dbd8497d2e555201bc3f4b39cbc4f474334d3 |
|
MD5 | 92ea3f20a99075af47799f68fb0f7035 |
|
BLAKE2b-256 | fa0fafbe6efded4a7f68147dda40843301477686af72d3c05aa9b7b1b252a8f7 |
Hashes for leafy-0.1.5-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9066e0eb3fd0eafab3f02ca094d6b601e6dbb1498a70758aaf1e883c0451fa28 |
|
MD5 | 464ab108408623bc8b9c534a1b70f534 |
|
BLAKE2b-256 | 5417147d5b13beb94d6bc35161a0d5d1848db453f1cfcd426c24c6479a8b97b3 |
Hashes for leafy-0.1.5-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fe433f102676a03aca638d1653292063216f224ff898200a8df0b45e088f6492 |
|
MD5 | 2cc6ae8796f89a871844bba77f1864a2 |
|
BLAKE2b-256 | 68ffc616a3f3b2c56bafa416479ee3bc653cb210431bc50302e83e9a08d9832d |
Hashes for leafy-0.1.5-cp310-cp310-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 93109719b993380c6d7474c82a7f6adffc06db163f90af13b9c061a017fd1d17 |
|
MD5 | 2d980886c82d1ecb92efe1b0c8163069 |
|
BLAKE2b-256 | 219f643af881aadb8f39fb14702b9264100a9e8168ce8b688bded6ba05532074 |
Hashes for leafy-0.1.5-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d5692e63bbbe08ffd9ca97ba7420fbed15a07345fbb5a9a5b3906abc650787df |
|
MD5 | 4e3c52001fbd46653235026027de3bc1 |
|
BLAKE2b-256 | 7031c23c61471b837ddca7a8a78f3fb693e8e4aefe0380abafabea1ad309b1ed |
Hashes for leafy-0.1.5-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e129bf71949199540757905a9d2accf048463d77b6bf7236a22f00c796273a49 |
|
MD5 | 3f6551122920cc18edc3d7553d7ede70 |
|
BLAKE2b-256 | 34a933dbf7a9fc014271a1d090d56472433603a8959e5865d9ee3af0b354e067 |
Hashes for leafy-0.1.5-cp39-cp39-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 97d9f26c809564a7da69d0f4e8ce3d5b8e25d57c1a3d3e0512a2b030723c16ea |
|
MD5 | 0fdfa9efb0ff590bb61687863cfd8d3b |
|
BLAKE2b-256 | 86867b2297b11146172aa0ff606225b55020413cac15fe1f210232cf5a7cb57e |
Hashes for leafy-0.1.5-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9f32b8c8371e17cb48615041d0d726443840702057b00e983206c75f90a6f489 |
|
MD5 | 6f6937f006ae6fc8af8909d8a6a803eb |
|
BLAKE2b-256 | a557d8ed2f9c3c31bc3c7c2f1846eeeee28d79312986f474ecd601258e9ca016 |
Hashes for leafy-0.1.5-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e7d4d8846069155f26bb968d5159d882d8205c7816111048555f37840ac06437 |
|
MD5 | 724b93ad0fe38ee0356e96bbc44d7157 |
|
BLAKE2b-256 | e69dd469233994c16047ecbd1680ebb46a2dbef20348c8fb5b10e893047177c2 |
Hashes for leafy-0.1.5-cp38-cp38-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1c15aae5cb0aef49a477980ae3c9e5d75d00cb3ea124ff6d6d1341e1d7c32b8e |
|
MD5 | cb1e6d27c54d9e540af1613466e11df4 |
|
BLAKE2b-256 | 0addbcbf855043e52b65ce306f209604e5343ea5bab12770c321d3b6261325cf |
Hashes for leafy-0.1.5-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9af8c5ca9aa6fdd9a2eec3d6f82c34458caca4a07c3c2dd7b3323acfe4b58fc5 |
|
MD5 | 76847db996471dc8fa8417cdc0da283d |
|
BLAKE2b-256 | 65395d650130a4c9eb542f8fda942a492bfa8dce742053918a8d2a2b71db9ea0 |
Hashes for leafy-0.1.5-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0101c2d460a2381de18f834ba107dc6a48236118e2c1105d14bc37a78f0affd3 |
|
MD5 | 10336049c0daa64afd788650f00f7e11 |
|
BLAKE2b-256 | 26a65454fa23e86f2bb3dc43fa67fc4caa0a45d34bc88bad8cc008d0cf3a8e8c |
Hashes for leafy-0.1.5-cp37-cp37m-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 45e5a86d75b44099976e2d31362b6e729c0002b5712e348ae2591d0800de59fc |
|
MD5 | 5a29cb858777bf88beb50a9fcf492c93 |
|
BLAKE2b-256 | fed21b14d263bdf4cd97143e40c6aee10e2f728ca9198baa2585b4ca8b092da4 |