|
|
Welcome to the Java Forums.
You are currently viewing our boards as a guest which gives you limited access to view most discussions and access our other features. By joining our free community, you will:
- have access to post topics
- communicate privately with other members (PM)
- not see advertisements between posts
- have the possibility to earn one of our surprises if you are an active member
- access many other special features that will be introduced later.
Registration is fast, simple and absolutely free so please, join our community today!
If you have any problems with the registration process or your account login, please contact us.
|
|
03-18-2008, 10:04 PM
|
|
Member
|
|
Join Date: Jan 2008
Posts: 12
|
|
|
Help with a Graph Data Structure and the Shortest Path
Alright before I begin, let me be clear I am very green to Java and programming in general. I am taking this class online, and I am having a very hard time. The professor will not actually teach which makes this very very hard for me. When I ask him for help he will either A. send me website links that have very little to do with my actual question or B. Tell me to read the textbook. But, even doing all that he says to do the textbook doesn't explain everything how I can understand it and the links are vague. So in short I need help.
I have been tasked with making a navigation system that will prompt a user for a starting and ending city and then report back the shortest path. I thought I was getting close but I realized that my plan had two major flaws. Here is the code so far
import java.util.*;
public class NavigationSystem {
private Node myGraph[];
private String citylist[] = {"Birmingham", "Tuscaloosa", "Atlanta", "Montgomery", "Macon", "Mobile", "Tallahassee", "Ashburn", "Lake City", "Ocala", "Orlando", "Daytona Beach", "Jacksonville", "Savannah"};
//Build the Graph
public NavigationSystem(){
for(int i = 0; i < citylist.length; i++){
myGraph[i] = new Node(citylist[i], 0, null);
}
//Setting up the children of Birmingham
Node temp = myGraph[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 = myGraph[1];
temp.setPointer(new Node("Birmingham", 58, null));
//Setting up the children of Atlanta
temp = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[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 = myGraph[13];
temp.setPointer(new Node(citylist[12], 139, null));
temp = temp.getPointer();
temp.setPointer(new Node(citylist[4], 165, null));
}
public int findPosition(String s){
//Cycle through the city list and find the location of the start city
int position = -1;
for(int i = 0; i < citylist.length; i++){
if(myGraph[i].getCity() == s){
position = i;
break;
}
}
return position;
}
public int DFS(String Start, String End){
int startposition = findPosition(Start);
int currentpath = 0;
int bestpath = 0;
String current, best, tempstring;
Node travelnode, tempnode;
Stack DFSstack = new Stack();
ArrayList<String> closedlist = new ArrayList<String>();
//Expanding the start position to the stack, adding it to the closedlist.
travelnode = myGraph[startposition];
closedlist.add(travelnode.getCity());
while(travelnode.getPointer() != null){
travelnode = travelnode.getPointer();
DFSstack.add(travelnode);
}
//Cycling through all the edges using a stack
while(!DFSstack.isEmpty()){
tempnode = (Node)DFSstack.peek();
currentpath += tempnode.getDistance();
if(!closedlist.contains(tempnode.getCity())){
tempstring = tempnode.getCity();
travelnode = myGraph[findPosition(tempstring)];
closedlist.add(travelnode.getCity()); //Adding the city to the closedlist
while(travelnode.getPointer() != null){
travelnode = travelnode.getPointer();
DFSstack.add(travelnode);
}
DFSstack.pop();
}
else
DFSstack.pop();
currentpath -= tempnode.getDistance();//removes the distance if we have to backtrack
}
}
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){
pointer=null;
City=s;
distance=0;
}
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 static void main(String[] args) {
// TODO Auto-generated method stub
}
}
Here is the problem. I have it set up now to only push the nodes to a stack if the node has not been expanded before, to prevent it from running forever. I didn't see this problem until after I had it in place but the problem is that if I am trying to find the best route from Birmingham to Mobile for example the code will do the following:
Expand Birmingham
Push - 146 Atlanta, 90 Montgomery, 58 Tuscaloosa to the Stack
Add Birmingham to the closed list
Expand Atlanta
Push - 161 Montgomery, 146 Birmingham, 84 Macon to the Stack
Add Atlanta to the Closed list
Pop 146 Atlanta from the Stack
Expand Montgomery
Push- 170 Mobile, 161 Atlanta, 90 Birmingham to the Stack
Add Montgomery to the closed list
Pop 161 Montgomery from the stack
The problem I see here is that with the next step we will have found one route to Mobile(Birmingham - Atlanta - Montgomery - Mobile) but we will have destroyed the edge connecting mobile and montgomery. So, even though the best route is from Birmingham - Montgomery - Mobile, we will never find it. The other problem is when I reach a point in the graph where I have already added the distance from say Atlanta to Macon and I have already expanded Ashburn and Savannah, how can I tell the program to remove the distance from Atlanta to Macon when I have already poppped the node that contains that data? 
Please help, I feel so stupid.
|
|
03-21-2008, 04:14 PM
|
|
Senior Member
|
|
Join Date: Jul 2007
Posts: 1,022
|
|
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);
}
}
}
|
|
| Thread Tools |
|
|
| Display Modes |
 Linear Mode
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|
