import java.util.*;
public class NavTest2 {
private Node[] graph;
private String[] citylist = {
"Birmingham", "Tuscaloosa", "Atlanta", "Montgomery", "Macon",
"Mobile", "Tallahassee", "Ashburn", "Lake City", "Ocala",
"Orlando", "Daytona Beach", "Jacksonville", "Savannah"
};
//Build the Graph
public NavTest2() {
graph = new Node[citylist.length];
for(int i = 0; i < citylist.length; i++) {
graph[i] = new Node(citylist[i], 0, null);
}
//Setting up the children of Birmingham
Node temp = graph[0];
temp.setPointer(new Node("Tuscaloosa", 58, null));
temp = temp.getPointer();
temp.setPointer(new Node("Montgomery", 90, null));
temp = temp.getPointer();
temp.setPointer(new Node("Atlanta", 146, null));
//Setting up the children of Tuscaloosa
temp = graph[1];
temp.setPointer(new Node("Birmingham", 58, null));
//Setting up the children of Atlanta
temp = graph[2];
temp.setPointer(new Node("Macon", 84, null));
temp = temp.getPointer();
temp.setPointer(new Node("Birmingham", 146, null));
temp = temp.getPointer();
temp.setPointer(new Node("Montgomery", 161, null));
//Setting up the children of Montgomery
temp = graph[3];
temp.setPointer(new Node(citylist[0], 90, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[2], 161, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[5], 170, null));
//Setting up the children of Macon
temp = graph[4];
temp.setPointer(new Node(citylist[2], 84, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[7], 84, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[13], 165, null));
//Setting up the children of Mobile
temp = graph[5];
temp.setPointer(new Node(citylist[3], 170, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[6], 243, null));
//Setting up the children of Tallahassee
temp = graph[6];
temp.setPointer(new Node(citylist[8], 111, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[5], 243, null));
//Setting up the children of Ashburn
temp = graph[7];
temp.setPointer(new Node(citylist[4], 84, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[8], 130, null));
//Setting up the children of Lake City
temp = graph[8];
temp.setPointer(new Node(citylist[12], 64, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[9], 83, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[6], 111, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[7], 130, null));
//Setting up the children of Ocala
temp = graph[9];
temp.setPointer(new Node(citylist[10], 80, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[8], 83, null));
//Setting up the children of Orlando
temp = graph[10];
temp.setPointer(new Node(citylist[11], 55, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[9], 80, null));
//Setting up the children of Daytona Beach
temp = graph[11];
temp.setPointer(new Node(citylist[10], 55, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[12], 93, null));
//Setting up the children of Jacksonville
temp = graph[12];
temp.setPointer(new Node(citylist[8], 64, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[11], 93, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[13], 139, null));
//Setting up the children of Savannah
temp = graph[13];
temp.setPointer(new Node(citylist[12], 139, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[4], 165, null));
}
private List<String> getShortestRoute(Node origin, Node dest) {
List<List<String>> routes = findRoutes(origin, dest);
int minDist = Integer.MAX_VALUE;
int index = -1;
for(int i = 0; i < routes.size(); i++) {
List<String> list = routes.get(i);
int distance = getDistance(list.toArray(new String[list.size()]));
if(distance < minDist) {
minDist = distance;
index = i;
}
//System.out.printf("route distance is %3d for %s%n",
// distance, list);
}
List<String> shortest = routes.get(index);
System.out.println("----------------------");
System.out.printf("shortest route = %s%n with distance = %d%n",
shortest, minDist);
System.out.println("----------------------");
return shortest;
}
private int getDistance(String[] cities) {
int totalDistance = 0;
for(int i = 0; i < cities.length-1; i++) {
Node node = getNode(cities[i]);
int distance = getDistanceTo(node, cities[i+1]);
totalDistance += distance;
}
return totalDistance;
}
private int getDistanceTo(Node node, String city) {
Node[] pointers = getPointers(node);
for(int i = 0; i < pointers.length; i++) {
Node pointer = pointers[i];
if(pointer.getCity().equals(city))
return pointer.getDistance();
}
return 0;
}
private List<List<String>> findRoutes(Node origin, Node dest) {
List<List<String>> allRoutes = new ArrayList<List<String>>();
Node[] pointers = getPointerNodes(origin);
for(int i = 0; i < pointers.length; i++) {
List<String> list = new ArrayList<String>();
list.add(origin.getCity());
list.add(pointers[i].getCity());
List<List<String>> routes = findRoute(list, pointers[i], dest);
for(int j = 0; j < routes.size(); j++) {
allRoutes.add(routes.get(j));
}
}
return allRoutes;
}
private List<List<String>> findRoute(List<String> list, Node from, Node to) {
List<List<String>> results = new ArrayList<List<String>>();
if(from.getCity().equals(to.getCity()))
results.add(list);
List<List<String>> lists = addPointer(list, from, to);
boolean haveMore = true;
do {
List<List<String>> subList = new ArrayList<List<String>>();
for(int i = 0; i < lists.size(); i++) {
haveMore = false;
List<String> next = lists.get(i);
String lastItem = next.get(next.size()-1);
Node n = getNode(lastItem);
List<List<String>> nextLists = addPointer(next, n, to);
if(nextLists != null) {
for(int j = 0; j < nextLists.size(); j++) {
next = nextLists.get(j);
if(next.get(next.size()-1).equals(to.getCity())) {
results.add(next);
haveMore = false;
break;
}
subList.add(nextLists.get(j));
}
}
}
if(subList.size() > 0) {
lists = subList;
haveMore = true;
}
} while(haveMore);
return results;
}
private List<List<String>> addPointer(List<String> list,
Node from, Node to) {
List<List<String>> lists = new ArrayList<List<String>>();
if(from.getCity().equals(to.getCity()))
lists.add(list);
Node[] pointers = getPointerNodes(from);
for(int i = 0; i < pointers.length; i++) {
List<String> next = new ArrayList<String>(list);
String nextCity = pointers[i].getCity();
if(list.contains(nextCity))
continue;
next.add(nextCity);
lists.add(next);
}
return (lists.size() != 0) ? lists : null;
}
private Node[] getPointerNodes(Node node) {
List<Node> list = new ArrayList<Node>();
String city = node.getCity();
for(int i = 0; i < graph.length; i++) {
Node next = graph[i];
Node pointer = next.getPointer();
while(pointer != null) {
if(pointer.getCity().equals(city))
list.add(next);
pointer = pointer.getPointer();
}
}
return list.toArray(new Node[list.size()]);
}
private Node[] getPointers(Node node) {
List<Node> list = new ArrayList<Node>();
Node pointer = node.getPointer();
while(pointer != null) {
list.add(pointer);
pointer = pointer.getPointer();
}
return list.toArray(new Node[list.size()]);
}
private Node getNode(String city) {
for(int i = 0; i < graph.length; i++) {
if(graph[i].getCity().equals(city))
return graph[i];
}
return null;
}
public class Node {
int distance;
String City;
Node pointer;
public Node(String s, int i, Node n) {
pointer=n;
City=s;
distance=i;
}
public Node(String s) {
this(s, 0, null);
}
public int getDistance() { return distance; }
public void setDistance(int distance) { this.distance = distance; }
public String getCity() { return City; }
public void setCity(String city) { City = city; }
public Node getPointer() { return pointer; }
public void setPointer(Node pointer) { this.pointer = pointer; }
public String toString() {
String point = (pointer != null) ? " pointer:" + pointer
: "";
String dist = (distance != 0) ? " distance:" + distance
: "";
return "Node[City:" + City + dist + point + "]";
}
}
public static void main(String[] args) {
// "Birmingham", "Tuscaloosa", "Atlanta", "Montgomery", "Macon",
// "Mobile", "Tallahassee", "Ashburn", "Lake City", "Ocala",
// "Orlando", "Daytona Beach", "Jacksonville", "Savannah"
int[][] indices = {
{ 4, 6 }, { 6, 9 }, { 3, 11 }, { 8, 5 },
{ 3, 13 }, { 3, 9 }, { 12, 5 }, { 2, 4 }
};
NavTest2 test = new NavTest2();
Node[] nodes = test.graph;
for(int i = 0; i < indices.length; i++) {
Node origin = nodes[indices[i][0]];
Node dest = nodes[indices[i][1]];
List<String> route = test.getShortestRoute(origin, dest);
//System.out.printf("shortest route = %s%n", route);
}
}
}