exhaustive graph search

This is a discussion on exhaustive graph search within the C++ Programming forums, part of the General Programming Boards category; My program reads vertices and edges in from a file and creates a graph. I need to create an exhaustive ...

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    exhaustive graph search

    My program reads vertices and edges in from a file and creates a graph. I need to create an exhaustive search that finds the shortest path (determined by weight) to visit all vertices starting with a designated vertex.
    A simple visual representation of the graph may look something like:
    Code:
              4
    %      G-----H
    %      |    /|
    %      |  1/ |
    %     8|  /  |8 
    %      | /   |      
    %      |/    |        
    %      A-----C
              4
    (The numbers are the weight of the edge)
    So, i would need to find the shortest path to visit all vertices starting with vertex G (the vertices are actually identified by their id. I used letters so they wouldn't be confused with the weights).
    I'm not sure how to do this. I know it is similar to a depth-first search. I was thinking about doing a depth-first search to visit all the vertices. Then, go one vertex back and call the depth first search again, and keep doing this until i'm back to the beginning.
    My program works with the depth-first search, so i just need to figure out how to do the exhaustive search, i'm just not sure how to go about it.

    Any help would be greatly appreciated.
    Thanks

    Btw, i think this is called the traveling sales person problem (or something like that)



    here is my depth-first search if needed:
    Code:
    int DepthSearch()
    {
    	cout << endl;
    	cout << "Depth-first Search:" << endl;
    	cout << endl;
    
    	vertex *currentVertex;
    
    	//Set all vertices color to white (not discovered)
    	for(unsigned int i = 0; i < vertexArray.size(); i++)
    	{
    		if(vertexArray[i] != NULL)
    		{
    			vertexArray[i]->color = "white";
    		}
    	}
    
    	int time = 0;
    
    	for(unsigned int i = 0; i < vertexArray.size(); i++)
    	{
    		if(vertexArray[i] != NULL)
    		{
    			if(vertexArray[i]->color == "white")
    			{
    				currentVertex = vertexArray[i];
    				DepthSearchVisit(currentVertex, time);
    			}
    		}
    	}
    
    	return 0;
    }
    int DepthSearchVisit(vertex *currentVertex, int &time)
    {
    	edge *adjEdge;
    	adjEdge = currentVertex->next;
    
    	currentVertex->color = "gray";
    	cout << "Discovered Vertex: " << " Id: " << setw(2) << left << currentVertex->id << "  Label: " << currentVertex->label << endl;
    
    	time = time + 1;
    	currentVertex->discovTime = time;
    
    	while(adjEdge != NULL)
    	{
    		if(vertexArray[adjEdge->target]->color == "white")
    		{			
    			DepthSearchVisit(vertexArray[adjEdge->target], time);
    			cout << setw(10) << left << "Visited" << " Vertex: " << " Id: " << setw(2) << currentVertex->id << "  Label: " << currentVertex->label << endl;
    		}
    		adjEdge = adjEdge->nextEdge;
    	}
    
    	currentVertex->color = "black";
    	cout << setw(10) << left << "Finished" << " Vertex: " << " Id: " << setw(2) << currentVertex->id << "  Label: " << currentVertex->label << endl;
    	time = time + 1;
    	currentVertex->finished = time;
    
    	return 0;
    }
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You have to visit all the vertices, correct? So you need to try all (n-1)! possible ways to order the n vertices. In your example, you need to check
    GACHG
    GAHCG
    GCAHG
    GCHAG
    GHACG
    GHCAG
    (4-1)! = 6. There are permutation-generating algorithms out there to generate permutations; once you have a permutation, you just add up all the edges (or call it infinity if an edge is missing, like GCAHG where you just can't do G->C).

  3. #3
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Btw, i think this is called the traveling sales person problem (or something like that)
    Yes, the "traveling salesman" problem is where you need to visit every vertex using the shortest path possible. If that is indeed what you're trying to do, then you'll want to take a look at this:

    Dijkstra's Algorithm

    Hope it helps!
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  4. #4
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Isn't Dijkstra's Algorithm used for finding the shortest distance from the source vertex to a target vertex? In this problem there isn't a designated target, because it must visit all vertices, and a different target may result in a shorter distance.
    IDE - Visual Studio 2005
    Windows XP Pro

  5. #5
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Ok, i got the permutation method to work for a small number of vertices (like 1-10). However, the number of vertices of my graphs may be up to 25. I can't get my permutation algorithm to work on a graph with that many vertices, because there are too many possible permutations (it now seems that it is working, just taking a long time. For example, with N=12, it takes 3 minutes to run). Is there a way to solve this problem?


    Here is the permutation algorithm i'm using. If i change N (the number of permutations) to a high number (like 20) it runs forever. Also, i couldn't figure out how to make it only generate permutations that begin with 1.
    Code:
    #include <iostream>
    using namespace std;
    
    
    void print(const int *v, const int size)
    {	
    	if (v != 0)
    	{	
    		for (int i = 0; i < size; i++)
    		{			
    			cout << v[i] << " ";
    		}
    		cout << endl;
    	}
    } 
    void visit(int *Value, int N, int k)
    {	
    	static int level = -1;
    	level = level+1; 
    	Value[k] = level;
    	
    	if (level == N)
    	{
    		print(Value, N);
    	}
    	else
    	{			
    		for (int i = 0; i < N; i++)
    		{			
    			if (Value[i] == 0)
    			{				
    				visit(Value, N, i);				
    			}
    		}
    	}
    	level = level-1; 
    	Value[k] = 0;	
    }
    int main()
    {
    	const int N = 4;
    	int Value[N] = {NULL};
    
    	visit(Value, N, 0);	
    	
    
    	return 0;
    }
    Thanks.

    *Edited
    Last edited by Cpro; 04-18-2008 at 04:54 AM.
    IDE - Visual Studio 2005
    Windows XP Pro

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Cpro View Post
    Ok, i got the permutation method to work for a small number of vertices (like 1-10). However, the number of vertices of my graphs may be up to 25. I can't get my permutation algorithm to work on a graph with that many vertices, because there are too many possible permutations (it now seems that it is working, just taking a long time.
    That's the point. There's a million dollars in it for you if you can find a way to solve it quickly.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Oh, and to get the permutations that start with 1, you print 1 before the loop, and generate a permutation on N-1 elements (and add 1 to the results from inside the permutation function). And of course you'll have to tack the 1 back onto the end too.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. error help making no sense
    By tunerfreak in forum C++ Programming
    Replies: 5
    Last Post: 04-17-2007, 07:55 PM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21