Graph Manipulation

Objectives
  • Learn how to build and manipulate graph data structures

Getting Started

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

Your directory should now look like this:

P10/
├── resources
│   ├── MileagesLarge.csv
│   └── MileagesSmall.csv
└── src
    ├── GraphAbstract.java
    └── GraphImplementation.java
Part One
  1. Implement the readGraph() method

  2. Implement the writeGraph() method

Testing

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"]
    Node0 -> Node2 [label="138" color="blue"]
    Node2 -> Node6 [label="142" color="blue"]
    Node1 -> Node7 [label="146" color="blue"]
    Node3 -> Node8 [label="156" color="blue"]
    Node0 -> Node3 [label="158" color="blue"]
    Node6 -> Node7 [label="181" color="blue"]
    Node2 -> Node7 [label="190" color="blue"]
    Node0 -> Node4 [label="198" color="blue"]
    Node3 -> Node4 [label="198" color="blue"]
    Node4 -> Node8 [label="201" color="magenta"]
    Node0 -> Node1 [label="210" color="magenta"]
    Node2 -> Node3 [label="213" color="magenta"]
    Node1 -> Node8 [label="214" color="magenta"]
    Node1 -> Node3 [label="216" color="magenta"]
    Node8 -> Node9 [label="246" color="magenta"]
    Node0 -> Node9 [label="248" color="magenta"]
    Node6 -> Node8 [label="256" color="magenta"]
    Node0 -> Node6 [label="259" color="magenta"]
    Node3 -> Node6 [label="259" color="magenta"]
    Node3 -> Node9 [label="271" color="magenta"]
    Node5 -> Node7 [label="272" color="magenta"]
    Node5 -> Node8 [label="287" color="magenta"]
    Node0 -> Node5 [label="289" color="magenta"]
    Node2 -> Node9 [label="303" color="red"]
    Node0 -> Node7 [label="307" color="red"]
    Node3 -> Node7 [label="307" color="red"]
    Node7 -> Node8 [label="307" color="red"]
    Node3 -> Node5 [label="312" color="red"]
    Node2 -> Node5 [label="344" color="red"]
    Node4 -> Node9 [label="368" color="red"]
    Node1 -> Node9 [label="381" color="red"]
    Node4 -> Node5 [label="409" color="red"]
    Node1 -> Node5 [label="422" color="red"]
    Node6 -> Node9 [label="424" color="red"]
    Node5 -> Node6 [label="465" color="red"]
    Node7 -> Node9 [label="474" color="red"]
}

And this is the image that it generates:

correct output

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:

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

  2. 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 Breckenridge
Visited Craig
Visited Denver
Visited Boulder
Visited Telluride
Visited Fort Collins
Visited Durango
Visited Pueblo
Extra Credit

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, Boulder] (Mileage 381)
Shortest Path: [Telluride, Breckenridge] (Mileage 303)
Shortest Path: [Telluride, Craig] (Mileage 271)
Shortest Path: [Telluride, Denver] (Mileage 368)
Shortest Path: [Telluride, Durango] (Mileage 120)
Shortest Path: [Telluride, Fort Collins] (Mileage 424)
Shortest Path: [Telluride, Durango, Pueblo] (Mileage 392)
Shortest Path: [Telluride, Snowmass] (Mileage 246)
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 and format. (15 points)

    • testDataLarge: Tests that the data structures are build correctly. (10 points)

    • testGraphLarge: Tests that the output graph has the correct contents and format. (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)