Thread: Need help deciphering a line

I'm in an algorithms class working toward my BA, and the course text book writes this as a solution to generic quick-union algorithm. I'm having trouble though, because the for-loop lines I have highlighted below don't seem to execute any kind of loop, and almost seem to be being used as some kind of if-statement. Am I missing something? Is there a condition where these would actually loop, or is it the case that they are trying to using the for-loop as some kind of single-line if-statement for "readability"? I feel like it just obfuscates the code.

Code:

/* QUICK UNION ALGORITHM */

#include <stdio.h>

#define N 1000

int main(void)
{
  int p, q, i, j, id[N];

  for (i = 0; i < N; i++)
    id[i] = i;
  while (scanf("%d %d\n", &p, &q) == 2)
    {
      for (i = p; i != id[i]; i = id[i]);
     for (j = q; j != id[j]; j = id[j]);
      if (i == j)
	continue;
      id[i] = j;
      printf(" %d %d\n", p, q);
    }
  return 0;
}

No, the loops have a definite purpose.

If you look at the Wikipedia Disjoint-set data structure article, the loops essentially perform i = find(p); and j = find(q); .

Remember, id[p] tells you only the parent of p. To find the root of p, you need to first look at i = id[p], then at i = id[i] repeatedly, until i == id[i]. Only then you have found the root, i, for element p. This is how a disjoint set works, and the aforelinked Wikipedia article explains it pretty well.

An example illustrates the issue quite nicely, I believe.

Consider the following disjoint set:

0 1 2 3 4 5 6 7 8 9 (indexes)
0 0 2 3 2 3 4 5 8 9 (values in the id array)

Logically, 0 1 form one set, 2 4 6 form another set, 3 5 7 form yet another set, and 8 and 9 are their own sets too.

If we want to perform Union(6,7), we cannot just modify id[6] and id[7]; that would detach them from their current sets.

Instead, we must first find the root of 6, i.e. i = find(6):

i = id[6]; (so i == 4)
i = id[i]; (so i == 2)
i == id[i];

so the root of 6 is 2, i = find(6) = 3.
The root of 7 is j = find(7):

j = id[7]; (so j == 5)
j = id[j]; (so j == 3)
j == id[j];

so the root of 7 is 3, j = find(7) == 3.

The union only modifies the root entries. Your code uses

id[i] = j;

so the original disjoint set becomes

0 1 2 3 4 5 6 7 8 9 (indexes)
0 0 3 3 2 3 4 5 8 9 (values in the id array)

Now, entries 0 1 form one disjoint set, 2 3 4 5 6 7 for another set, and 8 and 9 are their own sets too.

If we perform path compression on all entries (as it happens, only need to do it on entries 6 and 7 in this particular case), the disjoint set becomes

0 1 2 3 4 5 6 7 8 9 (indexes)
0 0 3 3 3 3 3 3 8 9 (values in the id array)

and it is much easier to see which set each entry belongs to.

---

If you have graphviz -- it's available in repositories for all Linux distributions, no need to download from the web --, you can very easily illustrate disjoint sets. The .dot file for the two cases above are

Code:

digraph {
    rankdir=lr;
    splines=true;
    overlap=false;
    esep="0,1";

    "0" [ pos="0,0"; pin="true" ];
    "1" [ pos="1,0"; pin="true" ];
    "2" [ pos="2,0"; pin="true" ];
    "3" [ pos="3,0"; pin="true" ];
    "4" [ pos="4,0"; pin="true" ];
    "5" [ pos="5,0"; pin="true" ];
    "6" [ pos="6,0"; pin="true" ];
    "7" [ pos="7,0"; pin="true" ];
    "8" [ pos="8,0"; pin="true" ];
    "9" [ pos="9,0"; pin="true" ];

    "1" -> "0";
    "4" -> "2";
    "5" -> "3";
    "6" -> "4";
    "7" -> "5";
}

which neato renders as

and

Code:

digraph {
    rankdir=lr;
    splines=true;
    overlap=false;
    esep="0,1";

    "0" [ pos="0,0"; pin="true" ];
    "1" [ pos="1,0"; pin="true" ];
    "2" [ pos="2,0"; pin="true" ];
    "3" [ pos="3,0"; pin="true" ];
    "4" [ pos="4,0"; pin="true" ];
    "5" [ pos="5,0"; pin="true" ];
    "6" [ pos="6,0"; pin="true" ];
    "7" [ pos="7,0"; pin="true" ];
    "8" [ pos="8,0"; pin="true" ];
    "9" [ pos="9,0"; pin="true" ];

    "1" -> "0";
    "2" -> "3";
    "4" -> "2";
    "5" -> "3";
    "6" -> "4";
    "7" -> "5";
}

which neato renders as

It is trivial to add a function that outputs the final state of the id[] array describing the disjoint set data structure in Dot format. That is actually what I often do, with other abstract data structures, too. Graphviz has been an indispensable tool for me in exploring some horribly complicated structures. Even though it is free and open source, it is a top-notch tool.

This was a big help! Thanks! We jumped into this after looking at a quick-find algorithm which basically results in joining every pair to a single set/representative. In my head I was still seeing that, with each node ending up pointing to either itself or another node, and didn't interpret the part of the algorithm above that creates the tree-like structure.

Again, thanks! I'll have to show a class mate this.