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 BellmanFord 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 minigmp (which is included).
There are two flavors of fastpath
. The first is the default fastpath
, which will work
for 99% of needed cases. It's limitation is that it uses the Ctype long double for edge
weights, which can cause rounding errors if you have extremely large/small numbers for edge
weights (ie 1E50 or 1E50).
This is because during the path relaxation step of the Bellmanford code, C cannot distinguish
a difference between 1E50 and 1E50 + 1
If your numbers are extremely large/small, then you can use the fastpathz
version, which
uses infiniteprecision integers as edge weights. The downside of using fastpathz
is that
decimal places get dropped, so the C code does not distinguish between 1 and 1.1. This
limitation can partially be overcome by just multiplying all your weights by an arbitrary
number.
Fastpath Example
Run either flavor on the included sample data:
fastpath source A target Z < edges.txt
fastpathz source A target Z < edges.txt
The output of either command is the path of nodes, and should look like
A
B
D
E
Z
The structure of the graph looks like:
A > B > C < F
 
 
v v
D > E > Z
 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 also available as a PIP package available at pypi.org
It 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="Z"):
print(edge)
Output is the path of nodes, and should look like
$ python example.py
A
B
D
E
Z
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 fastpath1.9cp36cp36mmanylinux1_x86_64.whl
Algorithm  Hash digest  

SHA256  d4c3e9110570b29235b55d7dcd3ee3df3ff1397e80ec364daf074e36376f3e1b 

MD5  bfb9b99d3223fb6295bea3ce1dc0cc17 

BLAKE2b256  b8d7cff0e1b323a1dd3b8395b01b336f0f343eb288fde87634e6438dfaf78519 