Thread: Path Finding Using Adjacency List.

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    265

    Path Finding Using Adjacency List.

    Background: Im not trying to impliment any particular algorithm, but id like to do a little pathfinding. Im storing several things in several places while testing different ideas. Each node object has a list of adjacencies (std::list<Node*>), and the Network object has a list of all nodes, and a map of lists of adjacencies sorted by node name (std::map<std::string, std::list<Node*> >).

    My question: How do i go about taking the current stored information and go about finding paths from one node to another? Right now im simply interested in shortest path implimentations. Im interested in real code here, not abstract imagery. If i wanted that id read a book.

    The current working (although not SHORTEST path) function im using is something like this:
    Code:
    Node* NodeNetwork::FindBestNextHopBetween(Node* Current, Node* Destination, int depth)
    {
    	if(depth>NetworkNodes.size()) { return NULL; }//failure due to routing loop.
    	std::list<Node*>::iterator AdjacenciesIter;
    	for(AdjacenciesIter=Current->Adjacencies.begin();AdjacenciesIter!=Current->Adjacencies.end();AdjacenciesIter++)
    	{
    		if((*AdjacenciesIter)==Destination)
    		{
    			return Current;
    		}
    		Node* NextBestHopTemp = FindBestNextHopBetween((*AdjacenciesIter), Destination, depth+1);
    		if(NextBestHopTemp==(*AdjacenciesIter))
    		{
    			if(depth==0) {return NextBestHopTemp; } //we are at the top, return our next found hop.
    			if(depth!=0) {
    				return Current; //we are deep, go up a level.
    			}
    		}
    	}
    	return NULL;//failure
    }
    Anyways, any imput you could offer would be a great help. Eventually id like to impliment a possible weighting system for adjacencies, however im saving the complicated stuff for another day =P.

    Edit: After a little testing, i believe my code always takes the longest path lol. it will even bounce back and forth until it finds a path exactly as long as the node list. Thats to be expected i suppose. The problem i have with "shortest path" is that to find the shortest path, i have to find all the paths and then pick the shortest one. Seems kinda wasteful of resources. Oh well, ill get it eventually. =P
    Last edited by Geolingo; 05-15-2005 at 08:44 PM.

  2. #2
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Hum.. you need Dijkstra's algorithm for graphs shortest path.
    http://ciips.ee.uwa.edu.au/~morris/Y.../dijkstra.html
    This link has what you need. The algorithm is very simple. Click the "Run animation" button in the bottom for a Java applet animation. It's very clear what happens.
    In your case, just asume that every link has cost 1.

    I've already done a Java application with a very cool GUI that calculates shortest paths between node in graphs. I could upload it if you want :P

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    265
    Im afraid i dont know java, and have had alot of trouble in the past extrapolating information from applications writen in it. There are arbitrary objects, like Graph. What is a graph? how is it stored and accessed. Id like to do this with the current datastructures I have if possible.

    Thanks for your help, ill try and watch the animation when my browser decides to let java work. Maybe that will pound into my head the solution.

  4. #4
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    you don't need to know java.. just have the java vm installed on your computer
    Get it herre http://java.sun.com/j2se/1.5.0/download.jsp
    Choose Downlaod JRE 5.0 Update 3
    Second.. a graph is just a data structure, which matches perfectly to what you're doing
    Nodes connected to each other. Each node has a collection of links to other nodes...
    Look at the animation, each ball is a node. At the end you have the shortest path.
    Last edited by xErath; 05-16-2005 at 01:16 PM.

  5. #5
    Registered User
    Join Date
    Feb 2003
    Posts
    265
    I watched the animation, and im more confused than ever. This is why i need code and not theory. Id really like to see code in a language i knew without the use of a bunch of structures that are in librarys i dont know about.

  6. #6
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    No.. you definetly need theory... You're not going to draft around chuncks of code waiting that something comes up (expontaneous generation)... with theory, the algorithm is easily built

  7. #7
    Registered User
    Join Date
    Feb 2003
    Posts
    265
    Different people learn in different ways. Some people read books to learn how to build bridges, others build bridges to learn how to build bridges.

    I learn far better looking at working code and then derive the theory behind it, and if i make alot of mistakes through trial and error trying to write my own, all the better.

  8. #8
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    trivial stuff works that way...

    Here it goes: your objective it to go from node A to Z through the shortest path (smaller number of visited nodes). Dijkstra algorithm has a small extra - there can be a cost from a node P to Q which can be anything, and the point is to find the path with lower cost.
    Because you want to store the path, each node will have a collection (stl vector will do) of nodes which represents the path taken from the origin to that node. Also each node must have a variable to store the cost of reaching it. In your case, all connections have cost 1.

    First you need to setup up the cost of all nodes. For the first set it to 0, for all others set them to infinite (INT_MAX, FLOAT_MAX, or a number greater than the number of nodes).

    Second you need to have 2 globals vars for the algorithm to work, which should be 2 set's, to ease up a bit. The first set stores the non-visited nodes, which costs must be calculated. The second set stores the already visited nodes, with no need for calculations.

    Now the algorithm works like this:
    Select the node with lower cost from the not-visited ones. We'll call it A. Foreach adjacent node X, consider the cost it has stored. If the cost from X is lower or equal than the cost from A+1, do nothing. Else set the cost of X to A+1, and set the path it stores to the path of A + node X.
    Then all nodes X are removed from the visited node's set, and placed in the not-visited node's set, which means that their adjacent nodes have to be also recalculated. And place node A
    in the visited node's one. Note that if you're working with a set it'll automaticly discard inserting of a already present node.

    In something like peseudo-code it'll be like:
    Code:
    list<Node*> all_nodes;
    list<Node*>::iterator lni;
    
    int infinity = INT_MAX;//something
    
    for(lni = all_nodes.begin();lni<all_nodes.end();lni++)
    	(*lni)->cost = infinity;
    
    all_nodes[initial_node_index]->cost = 0;
    
    set<Node*> notvis = all_nodes;
    set<Node*> vis;
    
    while(notvis.size()>0){//while there are nodes to process
    	Node *n = find_min_node(notvis);//get the node with lower cost
    
    	for(lni = n->Adjacencies.begin();lni<n->Adjacencies.end();lni++){
    		if( (*lni)->cost > n->cost+1){
    			//set new cost
    			(*lni)->cost = n->cost+1;
    
    			//set new path
    			(*lni)->path = n->path;
    			(*lni)->path.insert(*lni);
    
    			vis.remove(*lni);
    			notvis.insert(*lni);
    		}
    	}
    	notvis.remove(n);
    	vis.insert(n);	
    }
    Last edited by xErath; 05-16-2005 at 08:56 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 03:19 PM
  2. urgent please please..
    By peter_hii in forum C++ Programming
    Replies: 4
    Last Post: 10-30-2006, 06:35 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 05:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM