Programming Assignment 9

Graph Manipulation

Objectives

Learn how to build and manipulate graph data structures

Getting Started

Create a project called P9 and import GraphManipulation-starter.jar

Your directory should now look like this:

P9/
├── resources
│   ├── MileagesLarge.csv
│   └── MileagesSmall.csv
└── src
    ├── GraphAbstract.java
    └── GraphImplementation.java

Part One

Implement the readGraph() method

Testing

Enter an input mileages file and an output graph file in your run configurations, such as below:

resources/MileagesSmall.csv MileageSmall.dot

Here is the output you should see from your program, when it is working correctly:

digraph BST {
    ratio = 1.0;
    node [style=filled]
    node [fillcolor=darkslateblue]
    node [fixedsize=true]
    node [shape=oval]
    node [width=6]
    node [height=4]
    node [fontname=Arial]
    node [fontsize=60]
    node [fontcolor=white]
    edge [dir=none]
    edge [penwidth=24]
    edge [fontname=Arial]
    edge [fontsize=110]
    Node0 [label="Aspen"]
    Node1 [label="Boulder"]
    Node2 [label="Breckenridge"]
    Node3 [label="Craig"]
    Node4 [label="Denver"]
    Node5 [label="Durango"]
    Node6 [label="Fort Collins"]
    Node7 [label="Pueblo"]
    Node8 [label="Snowmass"]
    Node9 [label="Telluride"]
    Node0 -> Node8 [label="8" color="green"]
    Node1 -> Node4 [label="28" color="green"]
    Node1 -> Node6 [label="55" color="green"]
    Node4 -> Node6 [label="64" color="green"]
    Node2 -> Node4 [label="81" color="green"]
    Node1 -> Node2 [label="99" color="green"]
    Node4 -> Node7 [label="112" color="blue"]
    Node5 -> Node9 [label="120" color="blue"]
    Node2 -> Node8 [label="136" color="blue"]
    Node1 -> Node7 [label="146" color="blue"]
    Node3 -> Node8 [label="156" color="blue"]
    Node0 -> Node3 [label="158" color="blue"]
    Node2 -> Node7 [label="190" color="blue"]
    Node3 -> Node4 [label="198" color="blue"]
    Node0 -> Node9 [label="248" color="magenta"]
}

And this is the image that it generates:

In recitation you were exposed to webgraphviz as a visualization tool. Another way to generate the png is via the terminal with using the following command:

$ cd path/to/MileageSmall.dot
$ dot -Tpng MileageSmall.dot > MileageSmall.png

Part Two

The second part of this assignment requires you to implement two graph algorithms:

Depth first search (DFS) starting at any arbitrary node.
Breadth first search (BFS) starting at any arbitrary node.

Check out the corresponding lecture slides for details on how to implement these algorithms.

Here is the expected output from the supplied chart for the depthFirst() and breadthFirst() methods, called with Fort Collins and Aspen as the starting cities:

Depth First Search:
Visited Fort Collins
Visited Boulder
Visited Denver
Visited Breckenridge
Visited Snowmass
Visited Aspen
Visited Craig
Visited Telluride
Visited Durango
Visited Pueblo

Breadth First Search:
Visited Aspen
Visited Snowmass
Visited Craig
Visited Telluride
Visited Breckenridge
Visited Denver
Visited Durango
Visited Boulder
Visited Pueblo
Visited Fort Collins

Shortest Path

Implement Dijkstra’s, or an algorithm of your choice, to find the shortest path and distance between two nodes in a graph. This is equivalent to the problem we need to solve on the mileage graph, which is to find the shortest distance between two cities in Colorado.

Your final output should show the shortest path from each city to every other city, organized alphabetically by the from and to cities. This is a total of 90 lines, the output for just Telluride is shown below:

Shortest Path: [Telluride, Aspen] (Mileage 248)
Shortest Path: [Telluride, Aspen, Snowmass, Breckenridge, Boulder] (Mileage 491)
Shortest Path: [Telluride, Aspen, Snowmass, Breckenridge] (Mileage 392)
Shortest Path: [Telluride, Aspen, Craig] (Mileage 406)
Shortest Path: [Telluride, Aspen, Snowmass, Breckenridge, Denver] (Mileage 473)
Shortest Path: [Telluride, Durango] (Mileage 120)
Shortest Path: [Telluride, Aspen, Snowmass, Breckenridge, Denver, Fort Collins] (Mileage 537)
Shortest Path: [Telluride, Aspen, Snowmass, Breckenridge, Pueblo] (Mileage 582)
Shortest Path: [Telluride, Aspen, Snowmass] (Mileage 256)

Specifications

Your program must meet the following specifications:

Work on your own, as always.
Submit the file GraphImplementation.java.
Assignments should be implemented using Java 1.8.
Make sure your code runs on machines in the COMCS 120 lab.
Submit your program to the Checkin tab.
Read the syllabus for the late policy.
We will be checking programs for plagiarism, so please don’t copy from anyone else.

Grading Criteria (Part A)

100 points for perfect submission.
0 points for no submission, will not compile, etc.
Preliminary Tests: a compilation check. Use the information we have provided for MileageSmall.csv mileage chart.
Final Tests:
- testDataSmall: Tests that the data structures are build correctly. (15 points)
- testGraphSmall: Tests that the output graph has the correct contents. (15 points)
- testDataLarge: Tests that the data structures are build correctly. (10 points)
- testGraphLarge: Tests that the output graph has the correct contents. (10 points)
- testDepth: Tests depth first starting at Fort Collins. (10 points)
- testBreadth: Tests breadth first starting at Fort Collins. (10 points)
- testDepth: Tests depth first with a city we choose. (15 points)
- testBreadth: Tests breadth first with a city we choose. (15 points)
- testShortest: Tests shortest path starting at a city we choose. (10 points extra credit)