I have data that I would like to represent as a non-binary tree, or perhaps
a graph, but I'm not sure how to do that. The sample data looks like this:
A->B
B->C,D
C->E
D->E
Here the number of subnodes from B are just two, but they may be any number,
which is the source of my confusion. Binary trees are easy to construct, but
non-binary trees?
A graphical representation may look something like this:
A
|
B
/ \
C D
\ /
E
Or perhaps:
A
|
B
/ \
C D
| |
E E
I also considered a simple map with weights:
{:A 0, :B 1, :C 2, :D 2, :E 3}
Any ideas?
Once I have a data structure, I want to traverse it in order to find the
shortest path from A to E. In this example there will be two: [A B C E] and
[A B D E].
Here is some (incomplete) code for one of my attempts:
(ns graph.core
(:refer-clojure :exclude [symbol]))
(defn make-leaf [symbol]
[:leaf symbol])
(defn leaf? [x]
(= :leaf (first x)))
(defn symbol-leaf [x]
(second x))
(defn make-tree [symbol subtrees]
[symbol subtrees])
(defn symbol [tree]
(if (leaf? tree)
(symbol-leaf tree)
(first tree)))
(defn children [tree]
(when (not (leaf? tree))
(second tree)))
(defn parse-tree [tree]
(if (leaf? tree)
(symbol tree)
(cons (symbol tree) (for [c (children tree)] (parse-tree c)))))
(def sample-tree
(make-tree "A"
[(make-tree "B"
[(make-tree "C"
[(make-leaf "E")])
(make-tree "D"
[(make-leaf "E")])])]))
*graph.core>* (parse-tree sample-tree)
("A" ("B" ("C" "E") ("D" "E")))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
