• 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.

• Scala
• sbt
• specs

> 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