6 releases
0.1.33 


0.1.32 

0.1.0  Sep 24, 2023 
#486 in Math
58 downloads per month
1.5MB
1K
SLoC
Contains (ELF exe/lib, 5.5MB) target/release/speedicycle
A lightningfast, general purpose module for finding fixedcost circuits in weighted, undirected graphs.
Usage
The speedicycle binary (compiled on Linux, but expected to run on most Unixderived systems) is usable via the command line with the syntax:
speedicycle i ['path_to_input_file.txt'] s ['index of source node'] t ['target path cost']
Currently, the input file must contain the description of an undirected, weighted graph in DIMACS format. Specifically, the file should consist solely of plaintext, consisting of:
 A header line beginning with the character
p
and containing the number of nodes/vertices and edges in the graph, e.g.p 4000 5000
for a graph containing 4000 nodes and 5000 edges  One line for each vertex in the graph, beginning with the character
v
and containing a numerical label, e.g.v 11213
. These vertices will later be referred to by their position in this list, indexed starting at zero.  One line for each edge in the graph, beginning with the character
e
and containing a starting vertex, an ending vertex, and a numerical weight. Vertices here are referred to by their index position in the above vertex list. For example,e 0 1 25
, signifying an edge connecting the 0th and 1st vertex in the list with a weight of 25.
An example of this format is contained in DIMACS_sample.txt
. Support for additional formats is in the works, and contributions on that front are welcome!
Background
This tool was initially designed for the purpose of locating fixeddistance, closedcircuit walking paths in street grid data (and, by extension, walk routes of a predetermined time). The problem of locating circuits of specified cost, however, is more generally applicable.
The central algorithm here implements Lewis and Corcoran’s “doublepath heuristic” to locate viable circuits comprising two edgedisjoint paths from a source node s to a target node t, each with a cost of approximately k/2, where k is the desired total cost of traversing the circuit. By strategically selecting target nodes (and eliminating nonviable paths after each calculation), a suitable path (if one exists) can be located with impressive efficiency.
Implementation
Speedicycle is built atop petgraph, which provides both the underlying graph structure upon which the doublepath routine operates and implementations of essential graph traversal algorithms, including Dijkstra's and Moore's shortest path algorithms, both of which are used here.
Also contained here is an implementation of Ramesh Bhandari's method for finding two edgedisjoint paths between s and t. In brief, once the shortest path between the two nodes is located, directions are added along the path and weights adjusted to heavily penalize retraversal in the original direction. The new shortest path is located, and then the two are "unwoven" to produce the final circuit.
Finally, an implementation of Hierholzer's algorithm for locating an Eulerian circuit within an undirected graph is used to properly order the vertices in the resulting paths.
Final Notes
Your feedback, suggestions, and contributions are all welcome! If you spot an error, please open an issue, and feel free (but not compelled) to submit a PR with a fix. If you're just interested in discussing, please do reach out via LinkedIn or on my personal website. Talk soon!
Dependencies
~6.5MB
~132K SLoC