A package for finding the best path through a network graph
Project description
Introduction
Fastpath is a fast and lightweight tool for finding the shortest path in a weighted
graph. As input it only needs the starting node, the ending node, and the weights
of each node to node edge. For versatility it uses the Bellman-Ford algorithm, which
allows for negative weights. Future version will incorporate the Dijkstra algorithm
to speed up runtimes on graphs that do not contain negative edges.
To install fastpath
,
git clone git@github.com:deprekate/fastpath.git
cd fastpath; make
The only library dependency for fastpath is uthash (which is included). The fastpathz has the extra dependency of mini-gmp (which is included).
Fastpath Example
Run on included sample data:
fastpath --source a --target e < edges.txt
Output is the path of nodes, and should look like
a
c
d
e
The structure of the graph looks like:
a ─────▶ b ◀───── f
│ │
│ │
▼ ▼
c ─────▶ d ─────▶ e
- Strings can be used for the nodes, and the weights can be positive or negative long double numbers. The weights can even be in the form of scientific shorthand (1.6E+9).
Python Example
FastPath is now available as a pypi.org package, and is installable by simply using pip
pip install fastpath
To use in your python code, first import the module, write edges to the graph, and then provide a beginning node (source) and an end node (target)
import fastpath as fp
f = open("edges.txt", "r")
for line in f:
ret = fp.add_edge(line)
for edge in fp.get_path(source="a", target="e"):
print(edge)
Output is the path of nodes, and should look like
$ python example.py
a
c
d
e
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 Distribution
Hashes for fastpath-0.3-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3f2a1de80e1a89f07ae09986dca502e02046e30aebbd5366b4e2e8486a3e6a92 |
|
MD5 | 48b174e4017aa0c24eb46a190a82b459 |
|
BLAKE2b-256 | e8f82e3b2d2c36daa0bfbee3dbf8fc31c8552139db5212f9f146f4b2bec78897 |