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.5a0-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 88eedb7cd2ace592deb0ff87d95f3f5759065861d71eb3763078363ed77a47f8 |
|
MD5 | 1e120852276f748888f1d356542ba5b4 |
|
BLAKE2b-256 | e999744b6d77d07c7cafc32ad652f3b4781f550d7bd919944472919946b264ab |
Hashes for leafy-0.1.5a0-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2bc263fc86fdb2c1960917ace4f72f96ea07f94551b5f6d75837bacb300c5052 |
|
MD5 | 9470cfd5f50bb346b8b392173c45ef12 |
|
BLAKE2b-256 | 6b5206b141e332aa5dc235d14292ab3fc5d7ebfaaeece9a224316433cfc1518d |
Hashes for leafy-0.1.5a0-cp311-cp311-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ee56c545c5e50432795e99facfd84e6cee936566ebb6d92bed977bf07ba4e658 |
|
MD5 | 500b101adc759296bda84e045089eb42 |
|
BLAKE2b-256 | 188f51be5f12de84541f19514194c494fe9cc7396a8513b5fded104d402d928b |
Hashes for leafy-0.1.5a0-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 44a88527604cc3096d24094890d4d6e159e792c65ff9fbe9f70c46514aadc039 |
|
MD5 | 736e5fdd7c0e016ae6cde2b67c6e6248 |
|
BLAKE2b-256 | ad68fba68ac5617aac3ea30c12daeb76b8b2f5646c1f4e9200cc97f83f9a8406 |
Hashes for leafy-0.1.5a0-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e0dd204ca9bab4126f17e76c68d5ef442ef1f9e4636b6d310c532f2de6d076d5 |
|
MD5 | a8a5202af3e37870b45fc93e2ab1cb9e |
|
BLAKE2b-256 | e2551d8a0c99f26b6272fcba94ad3f3caa212a2d193a5e0a5798c5a57e8f66ed |
Hashes for leafy-0.1.5a0-cp310-cp310-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0e28049852de10c9e417fce8782efc5911b98d7d71d36342d8e5dd4d5145a172 |
|
MD5 | a42279304061ef7140e301e7ce63618f |
|
BLAKE2b-256 | 67fe3bd6512c4e5b09839ed71484e76d756d340998bd07a1ed071e7872112c4c |
Hashes for leafy-0.1.5a0-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c110cb5cb28f11e6b75c77eb09cda58d049572eb0edfe29491762cbf00f2ca44 |
|
MD5 | 10673759e356f07c8a5a834d1f3ad498 |
|
BLAKE2b-256 | 88a0c7ae1d87ea90e297fdfc3a8927a48b02b3e968d377015c074acf44dddff3 |
Hashes for leafy-0.1.5a0-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c3aab8743aac24b6bb7abf40657b162ff9cd7b582c8aa5929dc418208cc05124 |
|
MD5 | d0e446cb570a8022fe55c49fbf8bda00 |
|
BLAKE2b-256 | 750040b892a5bc19af45d8a64ca36d8d4bbff9434c30c341c030d70d185d4f5e |
Hashes for leafy-0.1.5a0-cp39-cp39-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d682fd81e1001366727ae919683745b68b970bd1c741f4f12272354847a71c96 |
|
MD5 | 41bcdfd18cc1e1b3b4160f4834876027 |
|
BLAKE2b-256 | 8f3c1b8e35e505cb89be7342c46d75e3e3bb9ff3a3a6b09606fd28ee53e9e7c1 |
Hashes for leafy-0.1.5a0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4f634a5e328723f073d8f720441b8c72478980ba1be4a82f1d546411b0f8969 |
|
MD5 | 9fe0b2f96e1ac6ef5e8c358f6a9b4dae |
|
BLAKE2b-256 | 1e07f0930b01a2c0e82077722cba3b4cc433e3bcc44105bb938c430fe3d288e0 |
Hashes for leafy-0.1.5a0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4329838c8189e1a44cbc04a4a19890458a3d12d2ebd71f22ca2585acb3fafad |
|
MD5 | 99af310c9184d2ba531e29dfb2940174 |
|
BLAKE2b-256 | 3c39d9a891e475e7f1a79bf7ab0e1b75c4afe77c687c08212c147a6d438ae517 |
Hashes for leafy-0.1.5a0-cp38-cp38-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e417842962970a6c7caafe3fa8cf87688ab71886cbfaa0b777fea82e986e1750 |
|
MD5 | e3f36064f8770f6b9c29f6ca9d5d50c2 |
|
BLAKE2b-256 | bbbfd6d7f0c2ce19ef1f22cc1bac142a6f29a55a4c4a94853d16d0c662dbaaba |
Hashes for leafy-0.1.5a0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 349294f152a911d1cb1dfcfe426d891f84dc87dee6f155a64e6989fc9f87b5c7 |
|
MD5 | c5f543a2ad394a4c3bb7c13615a2b0a3 |
|
BLAKE2b-256 | add4a6ba5a5c57fec7305b7b18ec4bb7f072eac792acea8c562ec65f63b1468d |
Hashes for leafy-0.1.5a0-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fa2dbec34bce455bd05f99e6a7358dbd87707df24a083ac3cb0a3787910b3a50 |
|
MD5 | 5a894a56f35ae8ecd0ef505adebc9aeb |
|
BLAKE2b-256 | 725b3238b30619b9a88b039eff808448e5f99b6632436638af9de4fc6210bcad |
Hashes for leafy-0.1.5a0-cp37-cp37m-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 908545ed6005b4e12e3741df7e666f3ac9fc247be97bb44365cc120ab742d99f |
|
MD5 | 05000460ebe67d87526d3ceadf0b399e |
|
BLAKE2b-256 | e487c2b78915ea565eacc89a1fb88f3cfd3fe002c7a82a376ac2d3692149d807 |