import java.util.ArrayList; import java.util.Arrays;

public class RoadNetwork {

private String [] data; private int size; public static int DEFAULT_CAPACITY = 500;

//Constructors public RoadNetwork() { data = new String[DEFAULT_CAPACITY]; size = 0; }

public RoadNetwork(int maxSize) { data = new String[maxSize]; size = 0; }

//Methods public boolean addCity(String name) { if(size >= data.length) { return false; } else { data[size] = name; size++; return true; }

}

public void removeCity(String name) { for(int i = 0; i < size; i ++) { if(name.equals(data[i])) { data[i] = data[size - 1]; data[size - 1] = null; size --; } } }

public boolean containsCity(String name) { for(int i = 0; i < size; i ++) { if(name.equals(data[i])) { return true; } } return false; }

public int getCityCount() { return size;

}

public String[] getCities() { return data;

} // return arrayList of all the cities that are directly connected public String[] getDirectlyConnectedCities(String name) {

return null;

} //create new arrayList of all the cities and put connected cities into the arrayList public boolean connect(String city1, String city2) {

return false; } //go to city1 list and remove city2 and go to city2 list and remove city1 public void disconnect(String city1, String city2) {

} //If there are any line that gets you from one city to another public boolean areConnected(String city1, String city2) {

return true; } // within the arrayList of the single city public boolean areDirectlyConnected(String city1, String city2) { return false; } //how far apart a city is from another city public int degreesOfSeparation(String city1, String city2) { return 0;

}

getDirectlyConnectedCities

public java.lang.String[] getDirectlyConnectedCities(java.lang.String name) 

Returns the directly connected cities of a particular city, sorted by name.

Parameters:

name - the name of the city

Returns:

an array of the directly connected cities of the specified city, sorted by name. Returns an array of size zero if the specified city does not exist, or if the city exists but has no connected cities.

connect

public boolean connect(java.lang.String city1, java.lang.String city2) 

If city1 and city2 are in the network, then connect them via a road. Returns true if, at the end of the method, id1 and id2 are connected (which could mean they were connected before this method was invoked), and returns false otherwise (which really would only happen if city1 or city2 were not a member in the network.

Parameters:

city1 - the name of one city

city2 - the name of another city

Returns:

true if city1 and city2 are connected directly in the network, and false otherwise.

disconnect

public void disconnect(java.lang.String city1, java.lang.String city2) 

Removes city1 from city2's directly connected city list, and removes city2 from city1's directly connected list. Does nothing city1 or city2 are not members, or if they are members but are not directly connected.

Parameters:

city1 - the name of one city

city2 - the name of another city

areDirectlyConnected

public boolean areDirectlyConnected(java.lang.String city1, java.lang.String city2) 

Determines whether two cities are connected directly via a road or not.

Parameters:

city1 - the name of one city

city2 - the name of another city

Returns:

true if cities are directly connected, and false otherwise

areConnected

public boolean areConnected(java.lang.String city1, java.lang.String city2) 

Determines whether two cities are connected directly or through a chain of roads or not.

Parameters:

city1 - the name of one city

city2 - the name of another city (not necessarily different)

Returns:

true if cities are connected, and false otherwise

degreesOfSeparation

public int degreesOfSeparation(java.lang.String city1, java.lang.String city2) 

Returns the degrees of separation between two (not necessarily distinct) cities. Returns -1 if there is no way to get to one city from another through a chain of roads. For example, if Oxford is directly connected to Cincinnati, and Cincinnati is directly connected to Dayton, then: The degrees of separation between Oxford and Cincinnati is 1. The degrees of separation between Oxford and Dayton is 2. The degrees of separation between Oxford and Oxford is 0. The degrees of separation between Oxford and Columbus is -1. Note that degrees of separation is commutative. So, if degreesOfSeparation("A", "B") is 5, then degreesOfSeparation("B", "A") must also be 5.

Parameters:

city1 - the name of one city

city2 - the name of another city (not necessarily different)

Returns:

The number of degrees of separation between city1 and city2, or -1 if the two are not connected directly or by a chain of roads.