ShortestPath

Prints the shortest path and direction traveled (from the perspective of someone driving down the current road) between the cities named by the start and end attributes, where the length of the road is the Euclidean distance between the cities. Success is reported if such a path exists. (Generally we will only test this on connected graphs; we may test on disconnected graphs for extra credit later, however). The <success> element in response to this command is empty and has no message attribute. It has one child element, <path>, which itself has a sequence of road and direction elements (<right/>, <left/>, and <straight/>) as children. The <path> element has two attributes which must be set: length, which reports the double precision length of the total path, rounded to 3 decimal places, and hops which indicates the number of unique edges traveled to get from the start to the end.

To make things more fun, we are going to use CanvasPlus sometimes when calling shortestPath. If a saveMap attribute is present, you need to create a new CanvasPlus object containing the shortestPath and save it to an image file with the value of the saveMap attribute. Here’s what the shortest path should look like: You should include a black rectangle for the bounds of the spatial map just like in saveMap. All cities and roads contained by the path should be in this visual map. The start point should be green (java.awt.Color.GREEN). The end point should be red (java.awt.Color.RED). All cities in between and all connecting roads should be blue (java.awt.Color.BLUE). Since the customer doesn’t care about how the spatial map is stored, we don’t need to see the rest of the spatial map (partitions and other cities and roads). To reiterate, to keep it simple, just create a new CanvasPlus object and include on the cities and roads on the path. Lastly, remember to dispose of the CanvasPlus object when you are done with it.

Finally, to make things even make things even more fun, we are going to turn your shortestPath output into readable HTML. If a saveHTML attribute is present, you follow the same steps you did with the saveMap attribute instructions, but now name it the value of the saveHTML attribute. You need to do this because the HTML document will need your shortestPath image and your success node. But don’t worry about any extra work here, it’s all pretty much been done for you. First of all we need to make a new Document object and make a copy of our success node since it belongs to our results document. Then we just need to transform the XML using an XSLT (eXtensible Stylesheet Language Transformations–don’t worry if you’ve never heard of this) file that I wrote into a pretty HTML document. Since Java’s XML outputter prints attributes in alphabetical order it can be confusing to read them so hopefully this will make it easier for you to test your Dijkstra classes. The code for you to do this is below (and the XSLT file should be in the newest iteration of the JAR file):

   org.w3c.dom.Document shortestPathDoc = XmlUtility.getDocumentBuilder().newDocument();
   org.w3c.dom.Node spNode = shortestPathDoc.importNode(successNode, true);
   shortestPathDoc.appendChild(spNode);
   XmlUtility.transform(shortestPathDoc, new File("shortestPath.xsl"), new File(saveHTMLName + ".html"));

Note that both saveMap and saveHTML attributes could be present without a conflict, instead, two image files and an HTML file would be produced. As always, examples will be provided.

Parameters (In output order)

• start
• end

Possible <output>

A <path> tag with attributes length, hops will be contained in output and will contain 1 <road> tag, followed by zero or more sequences of a direction element followed by a road element. These should be in the order of the path taken and will appear as follows:

   <road start="road1" end="road2"/>

Possible <error> types (In priority order)

• nonExistentStart
• nonExistentEnd
• noPathExists

<success> Example

   <success>
       <command name="shortestPath" id="15">
       <parameters>
           <start value="Annapolis"/>
           <end value="Derwood"/>
       </parameters>
       <output>
           <path length="12.000" hops="4">
               <road start="Annapolis" end="Bowie"/>
               <left/>
               <road start="Bowie" end="Washington"/>
               <right/>
               <road start="Washington" end="Bethesda"/>
               <straight/>
               <road start="Bethesda" end="Derwood"/>
           </path>
       </output>
   </success>

Web Accessibility