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.2.0-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d1fb4ed1738d5bc99e55e51ea624ba4372e4ae072141f2c9a8b9122dcd2ddc29 |
|
MD5 | 2b1f5678e714f9f919ad0749f39a6496 |
|
BLAKE2b-256 | adbda99a3f175764d92c3e092c834d49b901491dde2aef53be8b2d8e722fcf74 |
Hashes for leafy-0.2.0-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 17abc72d46e239adca46faf3917100573b4efbf22ad6d73a05db999dbd7cc5f0 |
|
MD5 | 6cb78c4f296fd9f7716c54cad528e66d |
|
BLAKE2b-256 | 27b65c1f96429aa3030aef0b98b093288e53be22673a368f5f5da91ce65724b2 |
Hashes for leafy-0.2.0-cp311-cp311-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2c929fbe4655863d1bc86c87dcbb7995d3de9ca3edf9dcc2da7b40417805e4d6 |
|
MD5 | 4f3d127a230ae68a30f5883fbe9fac8e |
|
BLAKE2b-256 | 2e64875794b4a854307c149bca4ef535d7ed834b5edc82b74cfb8244a5ee7c32 |
Hashes for leafy-0.2.0-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 19f250a4f69bb0584da3dcebeb9704fc103df961467223e8fbcdb30ceea82ed9 |
|
MD5 | 3d4ffd36aa01fe1135969a4ccfbe8953 |
|
BLAKE2b-256 | 5cc0858862b4cc5233cd8705e27213577b3e522d2c38098ef0779c16bc7ede19 |
Hashes for leafy-0.2.0-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cba805fd1b7515c09b6abcd3f90b7cf41a718e79b7ff2889153b4a70a4fc8a68 |
|
MD5 | 43c9b03e3cce0f12d9b2fcb62a5d7039 |
|
BLAKE2b-256 | 0010fe72b964595594e17ff62ff488f311e2c37fc0b01f8cd9566b448a7612d7 |
Hashes for leafy-0.2.0-cp310-cp310-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b4b64536f24fe4edf738f4dd8362ab301e7ac726a35755e813b77ab161578987 |
|
MD5 | dda546a529d48e92c9a4979c054d32d9 |
|
BLAKE2b-256 | 8c2786f5e083725b00877ad08b39ea1fa9a7f8edc90d53788efa1ffc9b14fe44 |
Hashes for leafy-0.2.0-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3391df08fe7fa2148ae934ea280a26864e0839d80aa88c063a6326bd691dfb13 |
|
MD5 | 5cd6373b56928738f15ad531e95199df |
|
BLAKE2b-256 | 1d4b1963d8601bea9cdc50427a5d8ccc99e1336cb3c35f148bc08859d7bd98e1 |
Hashes for leafy-0.2.0-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 850808f212050646171336f5330411421d8cac3328b0a14454cf4f0ff92a36ef |
|
MD5 | 5029c893777567282b4ccf8353c609f7 |
|
BLAKE2b-256 | 59bf82537e82696d80d5515479cf15afc85a2d2a90cfefa313513f0f9caf2ad4 |
Hashes for leafy-0.2.0-cp39-cp39-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c6c2db8e6c134f0f5933eb83f9776ae2033ccb07b1b4f096c0ce80ac7dee0e36 |
|
MD5 | e4bd1b456f41987e569db92a26a16980 |
|
BLAKE2b-256 | a17fb09524f5ac987b7cbeedb9c72e896063f7e30a4fc6c1cb3f6a2a9030b118 |
Hashes for leafy-0.2.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8d040296bec64826d5ad8c9e06b15781307220452fcc9d0739b8f965c3313b43 |
|
MD5 | 12cff2dc79557451ee1848b0b2612347 |
|
BLAKE2b-256 | 51b00e78f29d67e4b1278b941a825b7d5adc3c0bd96ead949b5fb6133b47e60f |
Hashes for leafy-0.2.0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eadb5a3cb868db91ea7fead3ec22fb4f1275419a37bf7216aaeecc78839bf665 |
|
MD5 | cc85066944aede2c8f3f1e9b5e6b61c6 |
|
BLAKE2b-256 | e1fe1d5c973284f64f7db9d6efd9c67afda38ed95c599c3c499675e17446bc68 |
Hashes for leafy-0.2.0-cp38-cp38-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 48091ca2c9824dbcd4e2bad1012eee16576a05c127700258c2a5a6793165a865 |
|
MD5 | ce66248ccecffb91972ad95f107c1cd5 |
|
BLAKE2b-256 | 408bcfafbfb7ca7b2fb0e512839b3c621cf81b15d4051837f06951d72c730665 |
Hashes for leafy-0.2.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9b06355cfa2f6159ea8a29234e50979370a18d212e7d64f9c2fa0e2e136b3cea |
|
MD5 | 40c4d05a6211ae4b39e0d6f21d56e799 |
|
BLAKE2b-256 | e9413567eb43aa5e4be6a9040cf95194f29380fef8a73ad564a46159c6642e78 |
Hashes for leafy-0.2.0-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_28_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ea5473571cc3086c805133d69fc75566b6ae4f65d3aa3332a0a207b35632761d |
|
MD5 | 50a5db2d72a125069fa3f532e79f4a2b |
|
BLAKE2b-256 | b714d53672eec8c2573c07b54fd41823c4738ed064a0548ed6e77fddf0044c78 |
Hashes for leafy-0.2.0-cp37-cp37m-macosx_11_0_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cc6f5e8ca4433434c1de499c036c82923a05a2f276c0e266bc43e9a740a40fff |
|
MD5 | 1fbe6822463e79335bde1e34e5eaa88e |
|
BLAKE2b-256 | 894d91b724aadf21b128cf7e1f43579529f307896607a25228a4c7a834dade3c |