travelling salesman

[kewell]

Hi,

I'm trying to implement a version of the travelling salesman problem in c using the follwoing algorithm:

********************************************************

salesman (u)
begin
   if every node is now visited
   then
   begin
      put (u,start) in the circuit
      print the circuit and its weight
      remove (u,start) from the circuit
   end
   else
      for every node v other than u
         if v is not visited
         then
         begin
            put (u,v) in the circui
            set v to be visited
            call salesman (v)
            set v to be unvisited again
            take (u,v) out of the circuit again
         end
end

**********************************************************

And here is what i have in c for the above:

**********************************************************

char v[6];
char tempu[3];
char uv[6] = "vuuuu";
char temp[3];
int j;
strcpy(v, "ABCDE");

void Algorithm(char u[2])
{
   if (uv[0] == 'v' && uv[1] == 'v' && uv[2] == 'v' && uv[3] == 'v' && uv[4] == 'v')
   {
	strcpy(temp, u);
	strcat(temp, A);
	DrawPath(temp);
   }
   for (j=0; j<5; j++)
   {
        printf(&quot;\nj = %d&quot;, j);
	if (v[j] == u[0])
	{
		// Do Nothing
	}
	else if (uv[j] == 'u')
	{
		strcpy(temp, u);
		temp[1] = v[j];
		DrawPath(temp);
		uv[j] = 'v';
		tempu[0] = v[j];
		Algorithm(tempu);
		uv[j] = 'u';
	}
   }
}

************************************************************

The procedure is called with "Algorithm(A)", where A is char A[] = "A";.

When the program reaches the recursive call (Algorithm(tempu) it does the call and when it has finished the call it doesn't finish the for loop. I mean it just does the next line, uv[j] = 'u';, and then exits, it doesn't go back and continue as it had only done j=2 in the for loop.

Can anyone spot where i've gone wrong?

Could this be due to no memory allocation using malloc() or calloc()?

Any help will be appreciated.

Thanks.

Arfan.

 

[mbaranski]

It's not memory allocation, you're using arrays, which means you can ignore alloc and calloc.

You could be indexing an array out of bounds, so try printing the index of the array each time before you access it, and see if that helps.

MWB.


Disclaimer:
Beware: Studies have shown that research causes cancer in lab rats.

 

[kewell]

Thanks for the help MWB. I found out that the problem was due to me declaring "int j" as a global varaible when it needed to be declared as a local one.

My new problem is that i've implmented the above algorithm in C and have Mesa displaying it graphically on screen and then by pressing 'n' it runs through the algorithm, drawing out circuits.

Is there a way of making the algorithm execute line-by-line so that i can press say 'm' and one line of the algorithm is executed and so on. I hope you understand what i'm trying to do.

A.

 

[rbobbitt]

A debugger allows you to step through it line by line. If you're using gcc, you can compile your program with the -g flag and then run gdb program_name. If you're programming in an IDE of some sort, chances are that there's a built-in debugger.

Russ
bobbitts@hotmail.com

http://home.earthlink.net/~bobbitts

 

[kewell]

Thanks for that Russ.

I want to actually program that behaviour into the program.
I'm not trying to debug or anything.

I want to be able to go through the algorithm line-by-line by pressing a key. The algorithm is just one part of the program. The main part is that the algorithm is displayed using Mesa3d on screen and my program runs through it. So you can see a line being highlighted and then the next line as it is executed and so on.

Any ideas will be appreciated.

A.

 

[obscurifer]

One way to do that would be to have insert a getchar() (or whatever your favorite function of that nature is) into the loop so the loop would stop during each iteration and wait for a keypress. That would require a console, though. I'm not really up on programmin in graphical environments, so I don't know if there's a GUI command that handles keypress events.

I hope this helps.