Help me understand this while( ) statement

[euclid]

Hi, I know this is probably a silly question but I am having trouble understanding a piece of code i am looking at -

  while (labels[y] != y)
    y = labels[y];

What exactly does the while loop do here? Is this just equivalent to writing

  if (labels[y] != y)
    y = labels[y];

since there is no counter? Or is this some trick that i dont know?

If so, what is the advantage of the first way?

Thanks a lot!


(If you are wondering where its from, I'm trying to understand the hoshen-kopelman algorithm as implemented here, the larger code fragment is

int find(int x) {
 int y = x;
 while (labels[y] != y)
   y = labels[y];

 while (labels[x] != x) {
   int z = labels[x];
   labels[x] = y;
   x = z;
 }
 return y;
}

)

[stahta01]

The loop changes the value of "y" till it equals the value of "labels[y]".
So, it is NOT the same of the if statement in most cases.

Math note: This is NOT a math equation; it could never equal depending on the data in the array labels.

Tim S.

[euclid]

OK, thanks for getting back to me. Forgive me for being a bit slow, but I'm struggling to get my head around this. Let me try and explain my reasoning -

while(labels[y] != y) checks if the value stored at the y index of the array 'labels' is different to the variable 'y'. If it is indeed different, then y = labels[y] gives the variable y the value that is stored at the y index of the array 'labels'.. am i right so far?

So for example, if y=4 and labels[4]=5, the while() statement would be true, since 5 != 4. The variable y, which had previously stored the value of 4 would be assigned a new value, '5'.

Obviously I am going wrong here somewhere.

You say that "The loop changes the value of "y" till it equals the value of "labels[y]" ", which implies it will potentially change it more than once until the condition is met... but how would more than one change ever be needed? Isn't y = labels[y]; sort of definitive? It just sets it in one go. Thats why i thought that the statement might be equivalent to an if().


thanks for your time

[stahta01]

This is beyond me explaining in the time I have left at school today; you are thinking as a Math student does; not as a C programmer does.
To me it is obvious but; how to explain it is not obvious. I added the only example I can think of.

Assume labels is equal to 0,0,2,2,3,3 and you give it the value of 5 to find.
Remember array first index is zero.

Tim S.

[euclid]

This is beyond me explaining in the time I have left at school today; you are thinking as a Math student does; not as a C programmer does.
To me it is obvious but; how to explain it is not obvious.

Tim S.

haha, yes I am a physics student not a CS student, i guess i have a mathematical mindset.

Thanks anyway, you pointed me in the right direction im sure ill get it eventually

[euclid]

Well I spoke to my professor today and he couldn't understand it either, this is clearly some sort of CS black magic that is impenetrable for physicists!

I worked through the example stahta01 kindly provided though, and tried coding it (i'll include it below).

I think I understand a bit better now... setting y=labels[y] does not necessarily mean that labels[y]=y ??! I see what you meant about a mathematical mindset, consider my mind expanded lol.

Thanks a lot for your help, no doubt ill be back with more questions soon!

#include <stdio.h>

int labels[6] = {0,0,2,2,3,3};
int find(int x);

int main()
{
    int x=5, y=0;
    y = find(x);
    printf("find(x) returns %d.\n", y);
    return 0;
}

int find(int x) {
 int y = x;
 while (labels[y] != y){
    printf("loop called! y = %d\n", y);
    y = labels[y];
 }

 while (labels[x] != x) {
   int z = labels[x];
   labels[x] = y;
   x = z;
 }
 return y;
}

/* ******************** output **********************

loop called! y = 5
loop called! y = 3
find(x) returns 2.

Process returned 0 (0x0)   execution time : 0.087 s
Press any key to continue.

************************************************** */

[anduril462]

I was going to explain this using snippets of the code, the the forum doesn't seem to want me to post anything with an equal sign, so here's the all English version. Hope it's clear enough.

Think of it like a series of clues leading to a destination. y represents your current location. Setting it to x before the loop means you start at position x. The labels array is an array of clues at each location. You keep searching while you haven't arrive yet, i.e. while the clue at the current location tells you to go elsewhere. If you're not there, you "go to a new position" by assigning y the value of the clue at your current location. The if statement would only take you one step along this path.

Exactly why that is done depends on what the find algorithm is supposed to find, how the labels array is set up and what data it contains. That I can't tell you from your code sample

[iMalc]

Okay, I can see that the best way to explain this is going to be by example: So take this:

const int labels[] = {2, 4, 1, 3, 3};
int y = 0;
while (labels[y] != y)
   y = labels[y];

This table shows the values of y and labels[y] at the top of the loop.
y labels[y]
0 2 (not equal)
2 1 (not equal)
1 4 (not equal)
4 3 (not equal)
3 3 (equal, stop)

[euclid]

I was going to explain this using snippets of the code, the the forum doesn't seem to want me to post anything with an equal sign, so here's the all English version. Hope it's clear enough.

Cheers, thats very helpful.

(by the way, the code is used as part of a Hoshen-Kopelman Algorithm (i got it from here) to identify and label clusters of 1's in a 2d array of 1's and 0's. I am interested in this as I am doing a project using kinetic Monte Carlo simulations of molecules on a surface.)

[euclid]

This table shows the values of y and labels[y] at the top of the loop.
y labels[y]
0 2 (not equal)
2 1 (not equal)
1 4 (not equal)
4 3 (not equal)
3 3 (equal, stop)

Thanks a lot, that makes it very clear

[nonoob]

The 'while' and 'if' are equivalent since there is no increment operation inside the loop - therefore no implied traversing the array.
Unless y = labels[y] is not permanent.... labels[] may be some global variable that gets altered in another thread that's co-executing. I don't think that's expected to happen here though.

[anduril462]

The 'while' and 'if' are equivalent since there is no increment operation inside the loop - therefore no implied traversing the array.
Unless y = labels[y] is not permanent.... labels[] may be some global variable that gets altered in another thread that's co-executing. I don't think that's expected to happen here though.

While it's true that y isn't incremented, it is nevertheless changed in the loop body, by setting it equal to labels[y], which we know is not the same as y because of the loop condition. It's not a straight traversal, but you can see from the output section in post #6, that using Tim's example array, the while loop does "traverse".

[nonoob]

Yes indeed. Examples in post #6 do change 'y' within the loop. But not in the first post that started this thread. I was responding to the original issue as stated.

[anduril462]

Reread again my friend.

[euclid]

Just to say THANK YOU to everyone who replied, I understand it much better now. I did a little reading on union-find stuff (i found this pdf quite useful) and I've managed to use it correctly in my cluster finding program, I'm very pleased!