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 Distribution
Built Distributions
Hashes for leafy-0.1.4-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d32500a207741e55db31be6861eeee1b08843bd2b44b1f6c9a9e226c43579305 |
|
MD5 | 82f555e72d8c60eef4e6f8dc52bd73e0 |
|
BLAKE2b-256 | 5be0587f2f261dc61198e51d416d1bebcf3d14d7311fc4018e95c5f49a85a2ff |
Hashes for leafy-0.1.4-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | daaf650d593cbe127e94f2703b415e1f8da477796eea5697084c79eca1d7a9d4 |
|
MD5 | f94a1610cc53db99421399c080de62ab |
|
BLAKE2b-256 | 42c0eebb4fd002cd4977bf26f28fc6d42025e853de714c1348b0f784280059de |
Hashes for leafy-0.1.4-cp311-cp311-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6c654bd5b8270bc39f8a4054810f0ed27c157a9c22e4bc01127e48ca463b581b |
|
MD5 | f4af3872cc44c3f69ff007be3178f201 |
|
BLAKE2b-256 | 63a90b6fba1511d8d328c9104be1ec92508120b4973a39af0e5bff81e4a6d6db |
Hashes for leafy-0.1.4-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7d8c91871690660b2d35bc9820cb6a8db654e8b306c0d2695e47462542107d5f |
|
MD5 | fe89ced5892ddff0a7ccdc04161cdca8 |
|
BLAKE2b-256 | 009acdc3943459d07cf3ad2cfd770566702b18bd19b9d44177e57e4632e04ae6 |
Hashes for leafy-0.1.4-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 68f44b566f63d621a4d223209e41b2b8fbfbd6965f6fc2d10c1d645b1134ffa3 |
|
MD5 | 3d47ec662ee27daa4110d48e5ecff20e |
|
BLAKE2b-256 | 8ec27a9195204ade209b555eda116cbd95274abe8cf8b3c37bba03f6ba53e5da |
Hashes for leafy-0.1.4-cp310-cp310-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4e171170f89c19c5d7f4a5408985ef423621767f4376c76156bb836a8de54593 |
|
MD5 | df5df640438147e2813f35a37b75c032 |
|
BLAKE2b-256 | 6448db9d21188eeb4a364c77a44b18e332a817560e9269367168bf5ef8f733b5 |
Hashes for leafy-0.1.4-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2a5c23b2312a4237a799193334e5e2d310ac40ce7b89f7593886aa519a97d4e2 |
|
MD5 | 5b709fa282beb69ce115921b8f4874a9 |
|
BLAKE2b-256 | c8a6929d83e32272f70ae5886acff2a31a65f58ad6e08c4154eedacc1c348ac9 |
Hashes for leafy-0.1.4-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 368a7f82e1a0254b4bacd193775a3fa5cc24805aa78611014b0a9146c9f0abdb |
|
MD5 | d57c8bcbda72401c57e7cae4f6a7c97a |
|
BLAKE2b-256 | 9e7c77ea72f337592afc60c51d3f58e077ce44039ee1adb65c42b5a2bb0ce1ed |
Hashes for leafy-0.1.4-cp39-cp39-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 703c6429fe5fa2bbe3a71aa23dcda27a3419466063acb51cebf7a62568f0ee51 |
|
MD5 | e6b642f23635e4ef3486a9773a7a9e6a |
|
BLAKE2b-256 | d1b2eb471cd307e9b01af35c44f486ca6982ce28d86899ea06701f3ea6bc6437 |
Hashes for leafy-0.1.4-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9cde048b744c1aef975f9d3e9c5e38f4337f65e5f6d163b578eb5e7b460bf941 |
|
MD5 | 01e42a3af5568139ab539a451e266592 |
|
BLAKE2b-256 | 09e57dde874ac7210a963c5f036034f9667a1a2b4e6e242c51de576ac47d49e5 |
Hashes for leafy-0.1.4-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e6dfa407b7588e2c6559d524fa93a09c7f2115d694ad49dccba153b882fa43f1 |
|
MD5 | 098580e7dbdcc7b2a277c298797f05d4 |
|
BLAKE2b-256 | 353ebdae70fade196456c48c3876638538384707178e5b2201132d1d6c38884c |
Hashes for leafy-0.1.4-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c7502806ad10f9540b00ebe692981f586e051f2ebb778660d6adad5221e8fd33 |
|
MD5 | 60d018fa42926587ccc4e7a315cc67f1 |
|
BLAKE2b-256 | 3dae4f58d738a9511248ca81e04b5b78c8e82df5140ee655d6064676f9ee94f4 |
Hashes for leafy-0.1.4-cp38-cp38-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2999aa8f9455bd82035d7d77f90a5f159433388d03d9e5a139ef470a836b25df |
|
MD5 | ae870958dba7d2b6d4da5c1702ec9e9a |
|
BLAKE2b-256 | 8c5183946e49761dbb517fe8f4aa4095521fa35b97c68d315442075adea55348 |
Hashes for leafy-0.1.4-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3034946e65eebec86952b43b19087192b447f342343cd13814443009b0d1cbc0 |
|
MD5 | 18a3ef20dac6c998de2adfd6073dcf81 |
|
BLAKE2b-256 | 99c453bb84cfb70457b366f262a814121ca19308b1419b9e71af5a601a6b7358 |
Hashes for leafy-0.1.4-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 85fc34094172232a18d40c03ba2f3aa569402d09f7bc72a4997856a3ae2d06d7 |
|
MD5 | 629f6c93daa7f04c21062cbc1ed85d94 |
|
BLAKE2b-256 | 2ce54d1adb00d42ee7c7c623928e1a44d9199b9146caad039bd817973acb50c7 |
Hashes for leafy-0.1.4-cp37-cp37m-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 153404e80f3b685fff6d750688c483e2aee89ca6d8421e928f80b1df738942c6 |
|
MD5 | 7d51c26b870758ed1f7bcf994cd79fa2 |
|
BLAKE2b-256 | b37e7b996e1367148e6569b5cff449bde7434906093a84b4ce9279245d718939 |
Hashes for leafy-0.1.4-cp37-cp37m-macosx_10_15_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 23e48ea719d2cb19d3bc6b0566669e99fb91cb0c0402873ee92e9c10f7100aef |
|
MD5 | 78a6d650f80a9204f6a427558beb5509 |
|
BLAKE2b-256 | 22c0a1e9a49dbbd1ef15a8041212fefa3477999c528daf79e73857ad9392a847 |