views:

37

answers:

1

Having had success with my last CLRS question, here's another:

In Introduction to Algorithms, Second Edition, p. 501-502, a linked-list representation of disjoint sets is described, wherein each list member the following three fields are maintained:

  • set member
  • pointer to next object
  • pointer back to first object (the set representative).

Although linked lists could be implemented by using only a single "Link" object type, the textbook shows an auxiliary "Linked List" object that contains a pointer to the "head" link and the "tail" link. Having a pointer to the "tail" facilitates the Union(x, y) operation, so that one need not traverse all of the links in a larger set x in order to start appending the links of the smaller set y to it.

However, to obtain a reference to the tail link, it would seem that each link object needs to maintain a fourth field: a reference to the Linked List auxiliary object itself. In that case, why not drop the Linked List object entirely and use that fourth field to point directly to the tail?

Would you consider this an omission in the text?

A: 

I just opened the text and the textbook description seems fine to me.

From what I understand the data-structure is something like:

struct Set {
    LinkedListObject * head;
    LinkedListObject * tail;
};

struct LinkedListObject {
    Value set_member;
    Set *representative;
    LinkedListObject * next;
};

The textbook does not talk of any "auxillary" linked list structure in the book I have (second edition). Can you post the relevant paragraph?

Doing a Union would be something like:

// No error checks.
Set * Union(Set *x, Set *y) {

    x->tail->next = y->head;    
    x->tail = y->tail;

    LinkedListObject *tmp = y->head;

    while (tmp) {

        tmp->representative = x;
        tmp = tmp->next;

    }
    return x;
}
Moron
The object that you call `Set` is the one I considered as the auxiliary "Linked List" object (my choice of term was poor). However, each `LinkedListObject` in your implementation would need to maintain a reference to its `Set` object, would it not? Consider the algorithm `MST-Kruskal` on p. 569, where `Find-Set(u)` must execute in O(1) time. The `MST-Kruskal` algorithm needs a handle to the `Set` object to perform `Union`.
kostmo
@kostmo: Isn't that the representative? I have edited the struct/code to make that clear. You don't really need a 4th field. The book talks about a Set pointer being the LinkedList head. It seems cleaner to have an extra Set object, I agree, but you don't need a 4th field as you claim.
Moron
In Figure 21.2, (p. 502), the `representative` field of each `Link` object points back to the *first* `Link` object, implying they are of the same type.
kostmo
@kostmo: You could alway maintain separate tails pointers and head pointers, in which case the book description is right. Having them in a struct just keeps them together and seems cleaner. For instance you could have two arrays, one with the heads and the other with the tails etc. I would not call it an omission.
Moron
Each `head` and `tail` pointer *must* be bound to a particular set, so using a `struct` is certainly a logical way to organize them. If maintained as two separate arrays, the index into those arrays still must be associated with the set somehow (by storing it where?). What I find troublesome is how the book treats the `representative` not as a `Set` object, but as a `Link` object. In that scheme, there is no pointer back to the `Set` object so that `tail` can be dereferenced. I prefer your implementaion, where `representative` is the `Set` itself.
kostmo
@Kostmo: You could have Head[i] and Tail[i] correspond, the mapping value being i or some setId or whatever depending on the use case. The book has made clear what the structure is, in the abstract. How you choose to implement it, is not the authors' problem :-) Going into details of the implementation only adds noise (at least in this case) and will only confuse the reader. The main point comes across pretty fine I think. Imagine if the book started going into irrelevant details at each point, the book would be twice as thick!
Moron
To the extent that they've gone into implementation detail in Figure 21.2, I would agree that even presently it causes confusion to the reader; that is, depicting a `Link` with three fields, none of them providing a way to access the `tail` pointer. Regardless of whether `head` and `tail` are implemented as `structs` or independent arrays, there is no mapping value (be it `i`, a `setId`, or `struct` pointer) in the depicted scheme that allows one to determine the `tail` (in O(1) time), given a `Link`.
kostmo
@kostmo: Figure 21.1 is not 'implementation details'. How else would one show this kind of a linked list? Also, all they said was 'also maintain the tail', without going into details on how (and why should they?). The confusion is in your mind, IMO. Instead of thinking in abstract you seem to be thinking in terms of implementation. IMO, it is perfectly clear. Anyway, this discussion is getting pointless, and I guess we both could be right from different perspectives. Also, you are free to write to them, I suppose :-).
Moron
Well, thanks for the sounding board anyway. I guess I had to talk out the confusion.
kostmo
@kostmo: No problem :-). It is good that you are trying to work out the implementation.
Moron