$14\mathrm{.}14$ PA$12$: Graph Manipulation

Objectives

Learn how to build and manipulate graph data structures

Getting Started

The following files are included with this assignment:

P$8/$

$$ resources

$$ MileagesLarge.csv

$$ MileagesSmall.csv

$$ MileagesExtraSmall.csv

$$ src

$$ GraphAbstract.java

$$ GraphImplementation.java

Part One

Implement the readGraph$()$ method

Testing

Enter an input mileages file and a starting city in your run configurations, such as below:

MileagesSmall.csv

Fort Collins

This is the graph of MileagesSmall.csv for reference:

alt text

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. The cities are ordered alphabetically in each input file. Make sure to traverse through the cities based on their mileages. You should visit cities with a smaller distance before cities with a greater distance.

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

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\mathrm{.}8.$

Submit your program on zyBooks.

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:

testing DFS and BFS on MileagesExtraSmall.csv with two different start cities $(20$ points$)$

testing DFS and BFS on MileagesSmall.csv with four different start cities $(40$ points$)$

testing DFS and BFS on MileagesLarge.csv with four different start cities $(40$ points$)$