Re: discuss dancing links

chenyan wrote:
> "gcrhoads@xxxxxxxxx" <gcrhoads@xxxxxxxxx> wrote in message news:
>>
>> The point of the technique is that you can back up to previous
>> states without having to make independent copies of all the
>> intermediate states. In your program with the adjacency list
>> representation, are you able to easily (i.e. without searching
>> through the adjacency lists) able to back up to previous states
>> of your graph without making independent copies of each successive
>> graph? If so, then there is no reason to go to the doubly-linked
>> list method described in Knuth's "dancing links" paper. In such
>> a case, the singly-linked adjacency list method is likely to be
>> faster because the doubly-linked list has twice as many links to
>> set and reset.
>
> I think the advantage of this technique is we don't have to check
> whether a node is valid or not. When choosing a node we can delete
all
> the adjacent nodes so that we can sure all the remaining nodes are
> valid. While in adjacency lists deleting a node and then add it when
> backtracing can be time-consuming. So in my program, I delete
adjacent
> nodes in dancing links while checking whether a node is valid in
> adjacency list representation. I don't know whether saving the
> checking time compensates for the waste of maintaining the
> doubly-linked list. Can it be efficient in some graphs with special
> structure?

So in one program you mark nodes as invalid while in the
other you splice the nodes out. Right?

When you delete a node, what do you do about the deleted/invalid
edges? A deleted node will typically have non-deleted neighbors
and the adjacency lists of these neighbors will now have edges
pointing to the deleted node. You can quickly splice these edges
out via "dancing links" and quickly update the degree of the node.
Otherwise you would have to traverse all the (valid) adjacency
lists to determine the current degrees of the nodes which is a
more time consuming operation -- note that the degree of the
node makes a useful heuristic when deciding which node you want
to delete next. Also, splicing the items out of the adjacency
lists saves you from having to check for edges to invalid/deleted
nodes. Doing what I've suggested via "dancing links" is very
much like that exact cover example in Knuth's paper. For each
node you would have one "column". The column header would
correspond to the node (and have fields for the node data such
as the degree of the node) and the doubly-linked list of items
in that column would be the doubly-linked adjacency list. Each
doubly-linked "row" would contain exactly two items; the two
adjacency list items that correspond to the same edge (edge (x,y)
is on the adjacency list for x and for y). Now deleting a node
is like "covering a column." Splice out the column header
(i.e. the node), traverse down the adjacency list and for each
item in the list, look down its "row" to find the other item
for this edge and splice this other item out of its adjacency
list (and update the neighbors degree). Is this what you are
doing? Are you using the degree of the node to determine which
node you next want to add to your independent set (and hence
the next node to delete)?

.