One thing that many algorithm books overlook is the cost of setting the markers back to false/nil when done. One nice aspect of a hashset/vector approach is that you can just throw it away when done, and use a fresh one each time.
If you want to learn a whole bunch of low-level tricks for handling graphs with optimal performance, check out Knuth's book about the Stanford GraphBase. It's been a while since I've read it, but I believe that each node in the graph has four general-purpose marker slots that different algorithms use for different purposes. At the beginning, he allocates a large chunk of consecutive memory for the markers, which he calls a "region". I do not remember whether it is one region for all the markers, or one region for each of the four markers. The key here is that the node marker is actually a pointer to a location in the marker region of memory. This added level of indirection (versus storing the marker directly within the node) means that he can clear the markers by bit-wiping the entire marker region of memory -- a fast operation. Of course, this means that a bit of extra work needs to be done when creating each node. A pointer is maintained into the marker region, and is given out to the next node that is created and then the region's pointer is incremented so that it points to a fresh location (for use by the next node added to the graph). Clever stuff, but doling out pointers into a region seems roughly equivalent to the work involved with assigning a unique, incrementing numeric id to each node upon creation (and numeric ids don't run out, whereas you run into problems if your region is insufficiently big for the number of nodes). And once you've assigned unique numeric ids, you can use the vector approach I described and have no threading conflict, and marker cleanup is handled automatically by garbage collection. So why not use that approach? --Mark -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
