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.3-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5ebb081d6c92ecda2ad3f3b67acf238d596782906e60d0e3eebe6cd9227dd761 |
|
MD5 | 8393d0113a868204c4728095bbadd3ec |
|
BLAKE2b-256 | ebf1336c87081a81cb188e1b7eb96715c2986993f70df5a475f771cddefe8dec |
Hashes for leafy-0.1.3-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3971dd64107d350a0e9ca03e9037844bd7f4431b17f0eb2173284b1f97a69378 |
|
MD5 | ec1fdc9f0898620e8f9b65953d4a4c5e |
|
BLAKE2b-256 | 405c978f3e480314fb0f4569a8fc320f640a253f18e65cd1fdc6ff4586a24280 |
Hashes for leafy-0.1.3-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 49f82d49ebf0eacb78e4fa47c07690c9f83cecc9e2a7b5aa907538e4dfaa3c51 |
|
MD5 | 154c5b0d6ecaa2ec0f017041fbdb4493 |
|
BLAKE2b-256 | ef4c9c71d5df43cbfe6b510a81d83e1a581c85bf045ac998678ab354ced9896a |
Hashes for leafy-0.1.3-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ebbf19b49dc379037aa5e0815a176f6e14a92aacfc3b2e67018cc5776f06b682 |
|
MD5 | bf064e5a4b83a88e5b3f8fbf9b35c0b8 |
|
BLAKE2b-256 | 5fc46cbf26a0bf2107709bee589e7417e4e8065c8f4899b79ab55c9eb220ae42 |
Hashes for leafy-0.1.3-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0412ee29e6a01b0a851f2764512de1ad1927d3968b1338e92024320c7d49a37a |
|
MD5 | a84425f40876be91c2224a65ba242dfb |
|
BLAKE2b-256 | b57159596a9fce60ac4d1d00260de71e3c58b52782a3162d612729b3955cb8fc |
Hashes for leafy-0.1.3-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5643d0da1d8dfcd44f0e48d92ecec38fd9cf9996c319cfd1b912fd7ee15dd33b |
|
MD5 | cb2e0bad2d5360c1302002093510e2f7 |
|
BLAKE2b-256 | 2945624876cd4c529384cf47554bacfc44ec5525304a7a3c6543f5aad020d0c1 |
Hashes for leafy-0.1.3-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ed548318f39a232fa238008ffe16b13a06a5db1052d1a62a69b4696a689930e4 |
|
MD5 | ee89af8d70827875e694c20c084f9b8d |
|
BLAKE2b-256 | 6777359a30c1e5826dd01dc2ef9e39edf10e1b6d7bdf05a1b040cac43a73bec5 |