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]
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.0a2-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c3885fb78f7bc80e3faa2aae83a848aa73c1ffa538923f410ebc974a06eeb2de |
|
MD5 | a3b1004701a25a58cc28c2b8db4c2ac8 |
|
BLAKE2b-256 | a8d6b7408b181b25877c8636589d2cc08b96e4a6839c5d162218e8edd83961e0 |
Hashes for leafy-0.1.0a2-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4dce3a81f356f5dd1f98d0f3ae92d756f3a2bee0e6b98e23129ee183aba81a59 |
|
MD5 | 3db213e3f8190bf12bce91b6e882b79b |
|
BLAKE2b-256 | 11d311f00ed2310594d45c72c99e88e704abce78e29ca255bd5859688ab8fab4 |
Hashes for leafy-0.1.0a2-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f5f0bfdd18d231fa1be211366da3a56285a6676c4d806ea29a529f947184939b |
|
MD5 | 504c9e18640a7013888060c7d3e35bc7 |
|
BLAKE2b-256 | ae1159baf289d3c89e3cd3697bc753d64e24da657c8093f94e4b5ccd9b7a263d |
Hashes for leafy-0.1.0a2-cp36-cp36m-macosx_10_6_intel.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0e344f22cf4920bc542de9a72f81999f3e7dd4becb1f2c8e737800b678cc0e6f |
|
MD5 | 0123199650470ebf695166e25adea7cc |
|
BLAKE2b-256 | a51b8d26abb284602141eba59e9e112ac34259223503e84514d8d7635f7b4636 |