Matt Fowles <[EMAIL PROTECTED]> wrote: > Leo~ > Nice summary of the issues, but I have a few nits to pick....
Thanks. I'll only look at DFS. It more cache-friendly. > Thus I don't think that BFS works. Now lets consider DFS of both sets. > A refs C,B; B refs D, E; C refs E; D refs G; E refs A Ah, some referential loops, that ought to come :) > DFS using root of A for (a): > A > C > E > B > D > G Well, freezing that yields: A > C > E > A* > B > D > G > DFS for freezing B for (b): > B > D > G > E > A > C And B > D > G > E > A > C > E* > B* The nodes with an asterix are of course denoting duplicates. When you now follow the chain beginning at A: A > C > (E* := E) > A* > (B* := B) > D > G the first one is contained in the second one. If a duplicate is detected it's just noted, but not followed further. > It has occurred to me that you might mean the implicit graph of all > objects rather than the explicit linked list of objects that (a) and > (b) create. It ought to be the explicit graph, at least for non-self-referential structures, which I consider being the normal case. For self-referential ones the question is possibly: can we use the graphs (by reordering like above) or is it just cheaper to rebuild. And yes, I'm really thinking of inserting these A* nodes. Freezing an object does need it. DOD of course not really. > Hope that made sense, Yep, a lot. > Matt leo
