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.5a1-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 42cb5ff68eaf3624f7e9190084ca39a1456da9b0dc70a6719a990005fa944434 |
|
MD5 | 21b3a733ac779762cd0a3d6e652b66a9 |
|
BLAKE2b-256 | 64062945e8f9f5fcb58352c08331a013d254f863bd9ee3a512d3d28e38b050e3 |
Hashes for leafy-0.1.5a1-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 791dd95bab2df04ffc27989b482be6e76467c5e2e1fbe86b3e741644c03f614b |
|
MD5 | c13b3f7eb89fad6ff1058ef21657ce35 |
|
BLAKE2b-256 | 09ec6a79a4e2b9e755330cb623c614a72c6509c54aa034c647e6883791b44090 |
Hashes for leafy-0.1.5a1-cp311-cp311-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2b1757c2dff8aa1a1e70ddf7086a53c482a187046396a8910e72c91797abd830 |
|
MD5 | 45e7dfcfe944ade2e035b824380b3965 |
|
BLAKE2b-256 | b8e2fbebe23f43ff9a82da32fd9393fc76ae0252ec7a7cd44386e834abca56c2 |
Hashes for leafy-0.1.5a1-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 211042e8e95ab4657cb313f5373c826cb59119d3fc39ea8716402afa393cde74 |
|
MD5 | e9feb6f871736a4df425031b0bd5fe3d |
|
BLAKE2b-256 | 30ab7b57b4031bb3c065dbf722357273977a672df1dc43fa7a542a3753b0cedd |
Hashes for leafy-0.1.5a1-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ab360a17f86a2cd88a20016c3c360cbd160a534e33d42585b6594b1ddeeb9da8 |
|
MD5 | d5682744a76ad09c9fcc303f37aa9808 |
|
BLAKE2b-256 | 30caed2d6146d818b3e984b3c65b0d219e01f78820cb4369f4deb06628876c31 |
Hashes for leafy-0.1.5a1-cp310-cp310-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 25051baefbb907f214f9385ffb3da7cec98a5351f0309c0ca412586642ccce7a |
|
MD5 | 0a7ef097d3289bd55b28265469f11aa5 |
|
BLAKE2b-256 | bccd59d013add5bed6e86bcde53533b6e6b1b1a3178b309c9f46cb6fb2de3a61 |
Hashes for leafy-0.1.5a1-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 30e851df66c78037a35bd15cda1d679e39596a54e561d535fa4e784a93335066 |
|
MD5 | 2a5bf0f6483e5436fc035211f9ba3f20 |
|
BLAKE2b-256 | 329bd5a96c144495ce48facbbe091ebae07d3272d08e1660d7add576cbb707ff |
Hashes for leafy-0.1.5a1-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d0c7b397fe7919d9d281cb7ce319705cdb6361e831839e68207faafe9adf8046 |
|
MD5 | ec63720178c7791af529ba345be76c65 |
|
BLAKE2b-256 | 334b5b21c207ee2b605e8a4d4b579fcd25c5b0a9a771e81aa03d4e4b2fc41c99 |
Hashes for leafy-0.1.5a1-cp39-cp39-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 57026dc49a6137b19367230c2e2fbb9adb66f2fa6641fa2b6f77ca62ceffa23a |
|
MD5 | a4a0cbdb61c22971b9b5a8db856951ef |
|
BLAKE2b-256 | 03e55013e850b613a0b9b20e25ecc53e8f601941312bee79016a1f8cee69ea0c |
Hashes for leafy-0.1.5a1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 130004f74154b9c602df7a46be3b3e0b754bd451798b2cf0b6a0c950d6387b1f |
|
MD5 | c1b646535cb38324cb6d758d90610724 |
|
BLAKE2b-256 | 00e4b5ad5a9b8325ac9fa070714361c55e458521caa5fa6438c8838bb5ce2b05 |
Hashes for leafy-0.1.5a1-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 823ce2d6f5a6a7c27e4b42f75d98f0299791fb9da7accea07b2c860321b27a75 |
|
MD5 | 2a005549c4d8f6a0256db51da04c373f |
|
BLAKE2b-256 | 69f0a4518e970c5654563e237aadb831d298b7e4caea99d5df0f024653d2b03b |
Hashes for leafy-0.1.5a1-cp38-cp38-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 576974db4505d3bf73ba499899a68b696256cbcb62e41c3e423d6397fc47883e |
|
MD5 | 0ead184324d9314ddf1c0ee8b573464c |
|
BLAKE2b-256 | ffb58761610368ad311c97f459ac228ec4387967bb188202e311856ed2f25e8f |
Hashes for leafy-0.1.5a1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ab3b301f119c01bfae4532889da89554e9e1189c99e612d6d4b822855eb139fe |
|
MD5 | 56e9cda88157618a384257850c290eb0 |
|
BLAKE2b-256 | f6ab5ea0cf6fe865495080512279515b3f39e52f09c73eb6256c4b03e641019f |
Hashes for leafy-0.1.5a1-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dff5c2361113c0fe426d4cfabf7a149c13433084c05d1a1ea4dcec7a69a0884c |
|
MD5 | 2610270122bd2a2ef971dfc681d3a96e |
|
BLAKE2b-256 | 1086cd5c800671d6100cf6c1a89729ed2e895b8817f6fff722a977d31a7a8e3a |
Hashes for leafy-0.1.5a1-cp37-cp37m-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c08f3e7b9a8251e004b55e206ca8aa284146029a38b5941d836d4ad348789610 |
|
MD5 | 9dbedbb7028fce36344bfd2c7f196981 |
|
BLAKE2b-256 | 83a6de3697fdd5f3ee41bf8e6d04de421d90f8a5dbd108bab0a9e6ab732d9743 |