Implementation of Dijkstra's algorithm to find the shortest (least costly) route between nodes in an undirected graph. Fork from github.com/bepcyc/dijkstra, clean it up a bit and bringing Scala versions up to date. The original author is Greg Seaton. All changes (C)opyright by Hanns Holger Rutz, published under the same license (Apache 2.0). Below is the original read-me.
The library has two limitations:
- nodes must have 2 dimensional coordinates, and weights are automatically derived from the Euclidean distance
- graph is assumed to be undirected
A quick hack around this limitation is to extend the Graph class and override lazy val net. That way the
problematic private methods neighborsOf and distanceBetween are not used. See DirectedGraphSpec for an example.
A future version of the library will remove these assumptions.
This project builds with sbt against Scala 2.12, 2.11.
To use this project as a library, use the following artifact:
libraryDependencies ++= "de.sciss" %% "dijkstra" % v
The current version v is "0.1.1"
- Retrieve project:
- by git clone (read-only):
<working-folder> $ git clone https://github.com/gseaton/dijkstra.git - -or- by download: * Navigate to Dijkstra repository and the Source tab (upper-left); * Click on the Downloads button on the upper-right portion of the page; * Save the compressed project file; * Uncompress project file to a working folder
- by git clone (read-only):
- Navigate to the
<working-folder>/dijkstrafolder in a terminal console. - Run sbt in the
dijkstra/folder:<working-folder>/dijkstra $ sbt- Execute an update to download all dependencies in sbt:
> update - Execute tests in sbt:
> test - Execute demo in sbt:
> demo* Review the generated graph image with illustrated traversal of shortest path:<working-path>/exported-graph-images/graph.23.0.11.<timestamp>.jpg - Generate scaladoc documentation in sbt:
> doc - Execute a run with a polygon graph with 7 sides and shortest path between "1" and "4" in sbt:
> run 7 1 4* Review the generated graph image:<working-path>/exported-graph-images/graph.7.1.4.<timestamp>.jpg
- Execute an update to download all dependencies in sbt:
- The shortest route calculation has both iterative and functional implementations:
- <graph-instance>.shortestPath(srcNodeId: String, targetNodeId: String)
- Graph.shortestPath(<graph-instance>, srcNodeId: String, targetNodeId: String)
- The code base is ready for scaladoc. In sbt, the action 'doc' will generate
scaladoc for the project located in the standard sbt location: ...<root>/target/scala_2.9.0/doc/main/api/index.html.
> run [<num-of-nodes> [<source-node-id> [<target-node-id> [<spike-node-enabled>]]]]
where
Arguments:
- num-of-nodes is the number of nodes generated in a regular polygon graph with edges forming the sides of regular polygon (defaults to 23)
- source-node-id is the node id of the starting node for calculating the shortest (least costly) route using Dijkstra's algorithm (defaults to 0)
- target-node-id is the node id of the ending node for calculating the shortest (least costly) route using Dijkstra's algorithm (defaults to 11)
- spike-enabled is a flag to add two (2) 'spike' nodes per polygon node (see below for more information) (defaults to false)
Argument notes
- If there are n number of nodes, the node ids are 0 to n-1 (e.g. "0","1","2",...,"n-1").
- The order of source and target nodes is irrelevant (other than affecting the direction of the shortest route (if any exist)).
To exercise the algorithm and generate a exported graph image with shortest route traversal:
In sbt:
> run 17 0 8
This command will create a graph as a 17-sided regular polygon with edges as sides, calculate the shortest route from node 0 to node 8, and then export the graph, with illustrated traversal, into the .../<root>/exported-graph-images/ folder as the file graph.17.0.8.<timestamp>.jpg.
An additional element to exercise the algorithm is to create 'spikes' on the regular polygon graph. Spikes are essentially two (2) additionally nodes associated/connected to each polygon node to create multiple terminal
nodes and also illustrate traversal that is not part of a closed graph.
Spike nodes have id's with an 'a' or 'b' appended to the polygon node id to which the spike node is associated.
For each polygon node, there is an 'a' and 'b' spike node (if spike nodes are turned on).
For example, for node "0" with spike nodes enabled, there will also be a "0a" and "0b" node with edges connecting "0" to "0a" and "0" to "0b", but no edge connecting "0a" and "0b" directly.
To exercise the algorithm with spikes and generate a graph image with the shortest route traversal:
In sbt:
> run 17 0a 8b true
This command will create a graph as a 17-sided regular polygon with edges as sides and associated spike nodes, calculate the shortest route from node 0a to node 8b, and then export the graph, with illustrated traversal, into the .../<root>/exported-graph-images/ folder as the file graph.17.0a.8b.<timestamp>.jpg.
The Demo program automatically exports an image representing the graph and illustrating the shortest route traversal.
The exported graph images are saved in the .../<root>/exported-graph-images/ folder.
The Graph class provides a representation of a graph via nodes with (x,y) Cartesian coordinates and edges between the nodes.
The Graph class provides a <graph-instance>.shortestPath(sourceNodeId, targetNodeId) iterative implementation of Dijkstra's algorthim.
The Graph companion object provides a few constants as well as the Graph.shortestRoute(graphInstance, sourceNodeId, targetNodeId) functional implementation of Dijkstra's algorthim
Provides utility functions to the Graph class illustrating the Dijkstra algorithm of finding the shortest (least costly) route between two (2) nodes.
The GraphUtil object generates a regular polygon (an n-sided polygon with each side of equal length).
This is done out of convenience since the Graph class can contain any number of nodes and edges in any configuration and still determine the shortest route.
Source code has scaladoc comment documentation for each method and variable.
To generate scaladoc in sbt:
> doc
The generated scaladoc documentation is in the standard sbt location: ...<root>/target/scala_2.9.0/doc/main/api/index.html
Unit testing uses the specs framework.
To run the tests in sbt:
> test