Hello everyone,
This has been a long-time software engineering issue that I've never
solved happily. It concerns implementing marking algorithms without
making a kludge of your software structure.
eg. Say I have a binary graph:
Where each node in the graph is like this:
class Node{
Node[] children;
}
And now I'm going to implement another static function somewhere to
print out all the nodes in a graph, but without repeating elements.
This is the header:
void print(Node graph);
The print function must print out each node, and then recurse down
it's children. It also must have some way of remembering which Nodes
it has already printed so as not to print it again.
The simplest, and most performant way of doing this is to have a
special field in Node that indicates whether it has been visited or
not:
class Node{
Node[] children;
boolean visited;
}
The print function can then use this field to mark which nodes have
been visited.
However, the visited field has nothing to do with the actual Node
class. It's simply for other functions to use as a marker.
This solution is kludgy, but I cannot see any other *performant* way
of doing this. Hashmaps are out of the question because of the
unnecessary space waste.
If someone knows of a better way of implementing these "marking"
algorithms, or a nice way of organizing these "marker" fields, I would
love to hear your workarounds.
Thanks
-Patrick
--
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
