Computer Science Canada :: View topic - Help with algorithm in C

Computer Science Canada

Help with algorithm in C

Author:

Panphobia [ Wed Mar 05, 2014 8:34 pm ]

Post subject:

Help with algorithm in C

So I am using ncurses so that is probably why some of the functions will be strange. But basically I am trying to find the shortest path from one point to another on the terminal, and keep track of the path, so I used Dijkstra. Sufficed to say, it isn't working, I checked my code for the queue, and it works perfectly, so I can only think that there is a problem in the logic. But the problem there is that I translated the code to java and it worked perfectly there. So here is my code, can anyone see the problem?

/*while there are elements in the q*/
/*struct and pointer are passed*/
while(dq(qY,&uY)!=0 && dq(qX,&uX)!=0)
{
/*break if at the end*/
if(uX == xEnd && uY == yEnd)
{
break;
}

/*Neighbours around the current cell*/
for(i=0;i<4;++i)
{

vX = uX + neighbours[i][0];
vY = uY + neighbours[i][1];

/*If the new cell is out of bounds continue*/
if(vY<0||vX<0||vY>70-1||vX>150-1)
{
continue;
}
c = (char)mvinch(vY,vX);

/*If the new cell is over a cell which is a boundary continue*/
if(c=='|'||c=='-'||c=='.'||c=='+')
{
continue;
}

alt = p->minPath[uY][uX]+1;

if(alt < p->minPath[vY][vX])
{
p->minPath[vY][vX]=alt;
p->prev[vY][vX][1]=uX;
p->prev[vY][vX][0]=uY;

/*enqueue*/
eq(qX,vX);
eq(qY,vY);
}
}

}

Author:

Dreadnought [ Wed Mar 05, 2014 9:16 pm ]

Post subject:

Re: Help with algorithm in C

Panphobia wrote:

Sufficed to say, it isn't working

It might be useful to know how it isn't working?

Here's the only "potential problem" I noticed, but its probably nothing.

There is an inconsistency in the way you store (x, y) coordinates

vX = uX + neighbours[i][0];
vY = uY + neighbours[i][1];

p->prev[vY][vX][1]=uX;
p->prev[vY][vX][0]=uY;

Not necessarily an issue, but it might be the cause of some weird behavior. Personally, I would use a struct or at least preprocessor symbols. (#define)

On a different note, since the distance between neighboring nodes is always 1, any node you have already visited must have been visited by a shortest path.
This means that you could save some time by doing this. (and only have to calculate the length of the path at the end)

/*Neighbours around the current cell*/
for(i=0;i<4;++i)
{
vX = uX + neighbours[i][0];
vY = uY + neighbours[i][1];

if (visited[vX][vY])
continue;

// ...

As I said not much but maybe this will help.
Good luck!

Author:

Panphobia [ Wed Mar 05, 2014 9:20 pm ]

Post subject:

RE:Help with algorithm in C

Yea I have used the seen int/bool array, it didn't do anything but improve the space complexity. Also they aren't (x,y), in ncurses when you're looking on the screen, you have to search (y,x). Well when I say it isn't working, I say it is breaking after one round of en queuing and then dequeuing, so basically if this was the minpath array initialization
I = INFINITY

code:

I I I I
I I I I
I I I I
I I I I

it only does this

code:

0 1 I I
1 I I I
I I I I
I I I I

Author:

Dreadnought [ Wed Mar 05, 2014 9:51 pm ]

Post subject:

Re: Help with algorithm in C

Quote:

Also they aren't (x,y), in ncurses when you're looking on the screen, you have to search (y,x).

My point was that in one instance index 0 is X and index 1 is Y and in the second instance it is reversed, but that shouldn't cause a problem.

Quote:

Yea I have used the seen int/bool array, it didn't do anything but improve the space complexity.

Ya, it doesn't improve complexity, but it seems weird that you check the length of the path each time you look at a vertex except for the last vertex (where you break on the iteration after you reach it). But honestly that's just me quibbling about consistency.

Also, shouldn't you initialize to this?

code:

0 I I I
I I I I
I I I I
I I I I

I don't know what infinity + 1 will do, but it might be interesting.

Other than that I'm stumped, maybe if you can provide more details of the behavior (does it crash after the first enqueue/dequeue, or does it exit the while loop?), but otherwise I have no idea.

Sorry, Confused

Author:	Panphobia [ Wed Mar 05, 2014 9:57 pm ]
Post subject:	RE:Help with algorithm in C
By the way, I know what you're saying, and it first gets initialized to all infinity, but the start node gets set to 0 right before the while loop. Also the neighbors array where I switched it doesn't matter as you said, soooooo, this is bugging me. It doesn't make sense because the same code in Java works PERFECTLY.

Author:	Dreadnought [ Wed Mar 05, 2014 10:05 pm ]
Post subject:	Re: Help with algorithm in C
Well, it shouldn't be too hard to figure out where the problem occurs since its after the first enqueue/dequeue. Put some debug prints in (even better, use a debugger) and figure out where stuff goes wrong. It might not be fun, but debugging is at least half the work (usually much more than half )

Author:

Panphobia [ Thu Mar 06, 2014 1:55 am ]

Post subject:

Re: Help with algorithm in C

Yea I know debugging is a big part of coding. I think I got one bug, and a few others. I forgot to malloc the variables in the struct, and also I changed the queue so that it takes in 1D arrays instead of ints. But the algorithm works until the distance from the origin is more than 10, then it breaks down. Like for the distance from (0,0) to (10,10) it printed 414, but when it is (0,0) to (1,1) it says the distance is 2, it doesn't make sense. Here is the revised code, and I put the "isVisited" variable in this time.

p->minPath[yStart][xStart]=0;
u[0]=yStart;
u[1]=xStart;
eq(q,u);

/*while there are elements in the q*/
while(dq(q,&u))
{

uX = u[1];
uY = u[0];

/*break if at the end*/
if(uX == xEnd && uY == yEnd)
{
break;
}
seen[uY][uX]=1;

/*Neighbours around the current cell*/
for(i=0;i<4;++i)
{

vX = uX + neighbours[i][1];
vY = uY + neighbours[i][0];

/*If the new cell is out of bounds continue*/
if(vY>=0&&vX>=0&&vY<=70-1&&vX<=150-1&&seen[vY][vX]==0)
{
c = (char)mvinch(vY,vX);

/*If the new cell is over a cell which is a boundary continue*/
if(c!='|'&&c!='-'&&c!='.'&&c!='+')
{
alt = p->minPath[uY][uX]+1;

if(alt < p->minPath[vY][vX])
{
p->minPath[vY][vX]=alt;
p->prev[vY][vX][1]=uX;
p->prev[vY][vX][0]=uY;

u[0]=vY;
u[1]=vX;

/*enqueue*/
eq(q,u);
}
}
}
}
}

Author:	Dreadnought [ Thu Mar 06, 2014 9:44 pm ]
Post subject:	Re: Help with algorithm in C
Welp, in my boredom I coded your algorithm (in Turing ), as far as I know, it works. If you ask me the problem probably lies in the queue or in p (whatever kind of structure it is), unless I'm missing something. When you say things break when you hit (0,0) to (10,10). what happens for (0,0) to (9,9), (9, 10), (10,9) (9, 11), (11, 9) and basically any nearby case? Good luck.

Author:	Panphobia [ Thu Mar 06, 2014 10:17 pm ]
Post subject:	RE:Help with algorithm in C
The same thing happens for those too, I think it happens when the distance from (0,0) is > 10. I tested my queue A LOT and I know it is not the problem, I even went to my professor and she said it was fine. My structure just holds the minpath,and the prev array.

Author:

Panphobia [ Sat Mar 08, 2014 6:24 pm ]

Post subject:

Re: Help with algorithm in C

Let me show you the results of a 20 by 20 grid without any walls, this is just a pure shortest path to any point on a 20 by 20 grid.

code:

@ 1 140 141 142 143 282 283 284 285 424 425 426 427 566 567 568 569 708 709
1 2 139 140 143 144 281 282 285 286 423 424 427 428 565 566 569 570 707 708
2 3 138 139 144 145 280 281 286 287 422 423 428 429 564 565 570 571 706 707
3 4 137 138 145 146 279 280 287 288 421 422 429 430 563 564 571 572 705 706
4 5 136 137 146 147 278 279 288 289 420 421 430 431 562 563 572 573 704 705
5 6 135 136 147 148 277 278 289 290 419 420 431 432 561 562 573 574 703 704
6 7 134 135 148 149 276 277 290 291 418 419 432 433 560 561 574 575 702 703
7 8 133 134 149 150 275 276 291 292 417 418 433 434 559 560 575 576 701 702
8 9 132 133 150 151 274 275 292 293 416 417 434 435 558 559 576 577 700 701
9 10 131 132 151 152 273 274 293 294 415 416 435 436 557 558 577 578 699 700
10 11 130 131 152 153 272 273 294 295 414 415 436 437 556 557 578 579 698 699
11 12 129 130 153 154 271 272 295 296 413 414 437 438 555 556 579 580 697 698
12 13 128 129 154 155 270 271 296 297 412 413 438 439 554 555 580 581 696 697
13 14 127 128 155 156 269 270 297 298 411 412 439 440 553 554 581 582 695 696
14 15 126 127 156 157 268 269 298 299 410 411 440 441 552 553 582 583 694 695
15 16 125 126 157 158 267 268 299 300 409 410 441 442 551 552 583 584 693 694
16 17 124 125 158 159 266 267 300 301 408 409 442 443 550 551 584 585 692 693
17 18 123 124 159 160 265 266 301 302 407 408 443 444 549 550 585 586 691 692
18 19 122 123 160 161 264 265 302 303 406 407 444 445 548 549 586 587 690 691
19 20 121 122 161 162 263 264 303 304 405 406 445 446 547 548 587 588 689 690

As you can see, there is an actual problem, and I don't know what it is. The shortest path is accurate for the two leftmost columns, but that is it.

Author:	Dreadnought [ Sat Mar 08, 2014 10:39 pm ]
Post subject:	Re: Help with algorithm in C
Things I might try if I were debugging this: 1- What do p->prev tell you the shortest path is? (does it even make sense?) 2- What happens if you remove the seen array? (do the minpath values change? If they do you might be able to get an idea of what's happening) 3- What happens when you give it a 20x1 grid? (since things seem to go wrong in the horizontal direction) 4- (Probably one of the first things I would have tried, lots of prints (and if they don't tell me anything interesting, I put more!) You might have already tried some of these. I'm assuming you've tried 4 to some extent, but you should consider putting A LOT of prints and writing everything to a file. Then you can look through it and check what happens at important moments (like when you suddenly jump from 1 to 140 and stuff. Again, if I had to guess, I'd say something bad is happening in p. Good luck.

Author:

Panphobia [ Sat Mar 08, 2014 10:53 pm ]

Post subject:

Re: Help with algorithm in C

If I reduce the rows and the columns to 10 this is the output

code:

0 1 20 21 22 23 42 43 44 45
1 2 19 20 23 24 41 42 45 46
2 3 18 19 24 25 40 41 46 47
3 4 17 18 25 26 39 40 47 48
4 5 16 17 26 27 38 39 48 49
5 6 15 16 27 28 37 38 49 50
6 7 14 15 28 29 36 37 50 51
7 8 13 14 29 30 35 36 51 52
8 9 12 13 30 31 34 35 52 53
9 10 11 12 31 32 33 34 53 54

So the algorithm works for two columns at a time.

Author:	Dreadnought [ Sat Mar 08, 2014 11:06 pm ]
Post subject:	Re: Help with algorithm in C
What happens if you don't check the seen array?

Author:	Panphobia [ Sun Mar 09, 2014 12:46 am ]
Post subject:	RE:Help with algorithm in C
same thing

Author:	Panphobia [ Sun Mar 09, 2014 3:47 pm ]
Post subject:	RE:Help with algorithm in C
I figured it out, the C compiler I am using is weird, when building a propositional statement like a&&b == b && c you need brackets, (a && b) == (b && c), also I wasn't checking whether the index of the prev array was filled, so there were my problems. Thanks for the help!

Author:	Dreadnought [ Sun Mar 09, 2014 3:53 pm ]
Post subject:	Re: Help with algorithm in C
Panphobia wrote: I figured it out, the C compiler I am using is weird, when building a propositional statement like a&&b == b && c you need brackets, (a && b) == (b && c) That's not your compiler, that's the C standard, (look up operator precedence). Did that come up in the snippet you posted?

Author:	Insectoid [ Sun Mar 09, 2014 3:56 pm ]
Post subject:	RE:Help with algorithm in C
That's not an issue with the compiler, that's part of the C spec. == takes precedence over &&. In your situation, it evaluates b == b first, which of course is true, so your equation simplifies to a&&c. But yeah, the brackets would have fixed it. EDIT: Damnit, Dreadnaught.

Author:	Panphobia [ Sun Mar 09, 2014 3:59 pm ]
Post subject:	RE:Help with algorithm in C
No it was the other way around, a == b && b == c, sorry, as you can see the xEnd = uX && yEnd == uY, so I needed to change it to (xEnd == uX) && (yEnd == uY)

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy