On Mar 16, 9:01 am, CuppoJava <patrickli_2...@hotmail.com> wrote:
> 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.
Use the node's metadata to annotate :visited as true and re-associate,
and do it recursively (likely with loop recur)?
Regards,
Shantanu
--
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
