Skip to main content

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distributions

No source distribution files available for this release.See tutorial on generating distribution archives.

Built Distributions

leafy-0.1.2-cp38-cp38-win_amd64.whl (148.9 kB view hashes)

Uploaded CPython 3.8 Windows x86-64

leafy-0.1.2-cp38-cp38-win32.whl (128.3 kB view hashes)

Uploaded CPython 3.8 Windows x86

leafy-0.1.2-cp38-cp38-manylinux1_x86_64.whl (599.0 kB view hashes)

Uploaded CPython 3.8

leafy-0.1.2-cp38-cp38-macosx_10_9_x86_64.whl (137.0 kB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

leafy-0.1.2-cp37-cp37m-win_amd64.whl (146.0 kB view hashes)

Uploaded CPython 3.7m Windows x86-64

leafy-0.1.2-cp37-cp37m-win32.whl (125.5 kB view hashes)

Uploaded CPython 3.7m Windows x86

leafy-0.1.2-cp37-cp37m-manylinux1_x86_64.whl (569.6 kB view hashes)

Uploaded CPython 3.7m

leafy-0.1.2-cp37-cp37m-macosx_10_9_x86_64.whl (134.9 kB view hashes)

Uploaded CPython 3.7m macOS 10.9+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page