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
>>> g = Graph(4)
>>> g.add_edge(0, 1)
>>> g.add_edge(2, 3)
>>> g.add_edge(2, 1)
>>> g.matrix
array([[0, 1, 0, 0],
[1, 0, 1, 0],
[0, 1, 0, 1],
[0, 0, 1, 0]], dtype=int32)
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.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 397478d549d35c236c90d5208f43af412e5f93e49d2a990b3a48bfb6b69672a1 |
|
MD5 | bf9fa8b715005b35323cf0a93dcf5b71 |
|
BLAKE2b-256 | 891d094cd7af3710d9c1f2bdc0f6c4750dd7d34485d8d1fbf3f6e9c2375ba99b |
Hashes for leafy-0.1.1-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e98175ea09b36908b1462732608b0c2dfac665dbaf93e8bd893f9064d1e564d2 |
|
MD5 | ff07f40807be6072c8674b7a5ae25fd3 |
|
BLAKE2b-256 | f2402824c81d34d3e184c0811d2d42a70d3ecdfe993066f9375221df9abb0566 |
Hashes for leafy-0.1.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 85b268a20f5f29e8134591f5283b8ead0ae4c2f83a7b5d9b38354d0ee17ca1f2 |
|
MD5 | 0b55d2c90f363b063fe3e475e90d8b45 |
|
BLAKE2b-256 | 2152418837e7a3be123ea210f5e6895e35f28a794ba43c3fb5ad04c130d06ba0 |
Hashes for leafy-0.1.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4aad3d1c5db39ee96eb003811e992061827aae0e3c4a5407ba1978d1d8d7f0e |
|
MD5 | 85fb9aede3db8c2561b50d4f1c4b5f30 |
|
BLAKE2b-256 | aded278c09355eefd7458bbf855871a87d441864f1a6e6d3103680ecdb2cf3a6 |
Hashes for leafy-0.1.1-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d6771b7969abe2051545be97c2f954093139d4c005635a2a9abc36f633d55505 |
|
MD5 | e4443df4e238a8c7e7ceb7b5ff038278 |
|
BLAKE2b-256 | 568b7b42ab66bacb4a2f8c192dd15926acf53922db73463ef9d90e3256562e76 |
Hashes for leafy-0.1.1-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5c6a077a09959b026a127587ef7f566e24cde5d1d77d5c584abed61d82a507ad |
|
MD5 | 080a277b5be7c70abf1893ccb5383f4c |
|
BLAKE2b-256 | 532ad06ededdecde429c4d4acc3248ee33a1e237d241bafd6f714aef7ea89dae |
Hashes for leafy-0.1.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 395cbe3ac4acdbf1dd515f9b319d65fc85e234a27a35f91a799fa735e156c96f |
|
MD5 | 9007c8592882bef11a350520591e9bc7 |
|
BLAKE2b-256 | ef3198a27637350561afc5ecde16093697a4e2c69d6236dcb26733a2d4044849 |