Due: as set in eClass.

May be done in groups of up to three students

TL;DR: implement one static method in one class. Submit that class. Cheating not allowed but some external code use is officially permitted.

Motivation

The purpose of this assignment is to implement a commonly used graph algorithm and use it to solve a related problem.

Introduction

Graph theory is the study of graphs, which are mathematical structures used to model  pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines).

The included skeleton implementation provides several methods to build a graph data      structure from a file, etc. It also provides an iterator that visits the elements. Note that not all of the functionality is implemented.

You are encouraged to review the textbook chapters on graphs. You may also use the      Java examples from the Algorithms textbook1 (please cite them if you do). A starter code is also supplied.

Description

In this assignment, you will have to write two implementations of graph algorithms. For  your convenience, some starting code is provided. Note that the starter code may either    not implement some of the required features, or might implement them improperly – e.g., via stubs. Note that the speed of your algorithms may strongly depend on the                    implementation of the missing methods and on the choice of auxiliary data structures you choose to utilize for your algorithms. You are permitted to use any java.util classes:  ArrayList, PriorityQueue, HashMap, etc.

The graph is implemented a class called Graph, implementing loading of the graph      content from a file. Take a look at the associated classed to confirm you understand the overall structure of the classes.

Part 1

Finish the implementation of the following method in the Graphs class (note the -s ending of the class name):

public static Set<String> nearby(Graph graph, String origin, int hops)

The method allows one to determine which cities are nearby a specified city, within a     specified number of edges, and returns a set of such cities as Strings, with the              corresponding distances (edge counts) appended to them after a comma. E.g., calling the method with Oshawa as origin, and 2 as the number of edges should produce a set with  the following items:

"Port Perry, 1", "Ajax, 1", "Bowmanville, 1", "Uxbridge, 2", and "Ajax, 2".

You will notice that the graph files contain the actual distances and possible travel times. For your algorithm, these will merely indicate that there is an edge present between a pair of vertices.

As usual, you are free to implement any private or protected methods and classes as you see fit. However, you should not modify the signatures of the existing methods in the     classes supplied if you choose to modify the method bodies. The main method in the      A4demo class should be able to print the mock results of your algorithm, to illustrate the API.

Part 2

Nothing needs to be submitted for this part.

Explore your implementation, by redesigning some methods or by modifying the input, to see if the graphs based on distances and those based on times can produce different           outputs. Three csv files are supplied with this assignment, one based on an Ontario map, and two more resembling graph examples in the SW textbook.

NOTES:

1.   Do not use package-s in your project. Using packages will cost you a 10 % deduction from the assignment mark.

2.   Some aspects of your code will be marked automatically (e.g., how it handles   boundary cases and error conditions), using a custom tester class and/or custom unit tests. It is also imperative you test your classes. If any of the java files that you submit do not compile, the whole submission will be given a grade of zero, regardless of how trivial the compiler error is. The code you submit should       compile using

javac *.java

command in either Windows, Linux, or macOS.

3.   Your code should include Javadoc comments.

Submission

Find all the java files in your project and submit them electronically via eClass (do not  zip, tar, rar, or 7z them). Submit only the file(s) you modified; you are expected to            change only the Graphs class. You may create other classes if you deem them necessary.

If working in a group, make only one submission per group and include a group.txt file containing the names and the student numbers of the group members. The deadline is