Results 1 to 2 of 2
  1. #1
    rhm54 is offline Member
    Join Date
    Jan 2008
    Posts
    12
    Rep Power
    0

    Default 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

    Java Code:
    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?:confused:

    Please help, I feel so stupid.

  2. #2
    hardwired's Avatar
    hardwired is offline Senior Member
    Join Date
    Jul 2007
    Posts
    1,576
    Rep Power
    8

    Default

    Java Code:
    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);
            }
        }
    }

Similar Threads

  1. Plot 2D graph in Java from RS-232 data
    By spratana in forum Java 2D
    Replies: 4
    Last Post: 02-11-2009, 06:49 PM
  2. Stack data structure in Java
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 10:34 PM
  3. Doubly-linked list with data structure
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 10:30 PM
  4. Queue data structure
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-14-2008, 08:35 PM
  5. data structure code
    By vgvt in forum New To Java
    Replies: 1
    Last Post: 01-17-2008, 02:49 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •