Graph Manipulation
-
Learn how to build and manipulate graph data structures
Create a project called P8 and import GraphManipulation-starter.jar
Your directory should now look like this:
P8/
├── resources
│ ├── MileagesLarge.csv
│ └── MileagesSmall.csv
└── src
├── GraphAbstract.java
└── GraphImplementation.java
-
Implement the readGraph() method
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
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
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.
-
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)
-