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 Distribution
Built Distributions
Hashes for leafy-0.1.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7041aad770c3b1d8d9ae0de3bb9c06783524adb8edf180a649822c9dbfdc5260 |
|
MD5 | 1b7dbb86844e5e35d0f0b671aaa2ba87 |
|
BLAKE2b-256 | e60ab906d64bafb518f6ed7f74bc794d687f30e1b820161021cf88e50e1ffa04 |
Hashes for leafy-0.1.0-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9576e3c2f93850876ae8f472b827dc3677e024878aff6fb2be0ab6a1e880be2b |
|
MD5 | 06de05d0fd6d9bfbbba36809c3c7e9f6 |
|
BLAKE2b-256 | 210a510f561204a99c05179e3c70f490cbd10cfc8c4f51134fb45ba1632866b0 |
Hashes for leafy-0.1.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 10c0301e6cff176303c41c3e09c8594306afbc257e8eebcec1bf955db0598854 |
|
MD5 | 1aaaf5023a7f751b50ba0ec3801ba702 |
|
BLAKE2b-256 | 0170d68b3d5ca3f1f4c5ac298f9575e237ecbf11fb39347ffc33857621e5c69a |
Hashes for leafy-0.1.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 125e792643a014fd8e0c472ed1fc5dac605b29e6c9b04b786a710b4d1f4c2b74 |
|
MD5 | 58e891a0d65d4421864c4e8970557815 |
|
BLAKE2b-256 | a25033d405a6e65217ab4cd0fcfe416191afff36efe06ceb1c13977171fae784 |
Hashes for leafy-0.1.0-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ba5ab66e766ac59f20e1b4f0b23120edf10122c30131ba0a70e8cbad7b4af13e |
|
MD5 | 02cd3af840ec6f72abf150888ddbb186 |
|
BLAKE2b-256 | 1c79acd0d9e455399f9fb6363fd72536bb4959bc99b7bf99bde4c0e348e3cad0 |
Hashes for leafy-0.1.0-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8545a60fc57c7e4955c99826437512f72c2d560800b49945627248b68a20b1c6 |
|
MD5 | fca7ed84c9cc8729f563179022fb09d5 |
|
BLAKE2b-256 | 908a9a6e95c4623caada3da6947c2e6ca676068062512dba2f9c77fce59d0d27 |
Hashes for leafy-0.1.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9030bf42dcea985e5e60e98e91d10bfe919d422f454f5125f711497fd35ec1db |
|
MD5 | c88ac8e3161d74770b6ea7e4edfd98e3 |
|
BLAKE2b-256 | b662d2bc844cea86811bbf260e02d4bfee887622d55c3ccdb58b512a4ca623cd |