<div><div>Thank you very much for your reply! I have been looking at the code, and there are two problems, as I can see. First, trying with the example</div><div><br></div><div>t1 :: Tree (Id, Cost)</div><div>t1 = Node (4,0)</div>
<div> [Node (3,2) [Node (1,12) []]</div><div> ,Node (2,3) [Node (5,1) [Node (6,2) [Node (7,2) [] ]]]]</div><div><br></div><div>printed as</div><div><br></div><div>(4,0)</div><div>|</div><div>+- (3,2)</div><div>| |</div>
<div>| `- (1,12)</div><div>|</div><div>`- (2,3)</div><div> |</div><div> `- (5,1)</div><div> |</div><div> `- (6,2)</div><div> |</div><div> `- (7,2)</div><div><br></div><div>your function 'cluster fst snd t1' returns</div>
<div><br></div><div>Many [Many [Many [Many [Many [One (0,[4]),One (1,[5])],One (2,[3])],One (2,[6,7])],One (3,[2])],One (12,[1])]</div><div><br></div><div>I can't see how this representation is giving the hierarchical clusters. The example above should resolve into</div>
<div><br></div><div>level 1: [[(2,3),(5,1)],[(6,2)],[(7,2)],[(4,0)], [(3,2)], [(1,12)]]</div><div><br></div><div>level 2: [[(2,3),(5,1),(6,2),(7,2)], [(4,0),(3,2)], [(1,12)]]</div><div><br></div><div>level 3: [[(2,3),(5,1),(6,2),(7,2),(4,0),(3,2)], [(1,12)]]</div>
<div><br></div><div>level 4 (or (cost) level 12): [[(2,3),(5,1),(6,2),(7,2),(4,0),(3,2),(1,12)]]</div><div><br></div><div>By doing it this way, we cluster all nodes connected with edges less than or equal x at (cost) level x. Clearly, we can have level 1: [[(1,1),(2,1)],[(3,1),(4,1)],...] if the edges between [(1,1),(2,1)] and [(3,1),(4,1)] are greater than 1.</div>
<div><br></div><div>Second, I don't think it is trivial to tree-i-fy the root path tree. I have done the function treeifyMST, which surely isn't efficient, since the list encounteredNodes is traversed as many times as the number of nodes (a binary search tree would be more efficient). But more important, the tree isn't correct, since each path is connected at the root of the tree.</div>
<div><br></div><div>Example (LRTree Int): [ [(1,0)],[(5,1),(1,0) ], [(2,2),(1,0)] , [(3,3),(2,2),(1,0)] , [(4,4),(2,2),(1,0)] ] -> [ [(5,1),(1,0) ] , [(3,3),(2,2),(1,0)] , [(4,4),(2,2),(1,0)] ]</div><div><br></div><div>
In my code, all 3 paths are branching at the root (1,0), but should for the last two paths branch at node (2,2). How should I cope with that in an efficient way?</div><div><br></div><div>I wonder if if it is easier to implement it from the ground using the approach given at <a href="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html">http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html</a> ?</div>
<div><br></div><div>---------------------------------------------------------------------</div><div>--TO DO: now all paths are connected at the root of the tree. Should be patched at the right places inside the tree. The search in the list encounteredNodes is not efficient.</div>
<div>treeifyMST :: LRTree Int -> Tree (Id,Cost)</div><div>treeifyMST rootpathtree = </div><div><span class="Apple-tab-span" style="white-space:pre"> </span>let</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>(LP rpt:rpts) = rootpathtree</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>root = head rpt</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>revrootpathtree = reverse rootpathtree</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>in</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>Node root (constructTree [] revrootpathtree)</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>where</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>constructTree :: [Int] -> LRTree Int -> [Tree (Id,Cost)]</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>constructTree encounteredNodes (LP x:[]) = []</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>constructTree encounteredNodes (LP x:xs) = </div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>let </div><div><span class="Apple-tab-span" style="white-space:pre"> </span>path1 = x !! 0</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>path2 = x !! 1</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>id1 = fst path1</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>id2 = fst path2</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>in</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>case (L.find (==id1) encounteredNodes) of</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>-- because we have encountered an already processed id, we can skip this sublist</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>Just _ -> constructTree (id2:encounteredNodes) xs</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>-- new id, meaning that we have encountered a new path</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>Nothing -> let</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>lenpath = length x</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>revpath = reverse $ take (lenpath-1) x</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>tree = listToNode revpath</div><div><span class="Apple-tab-span" style="white-space:pre"> </span> in</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>tree:constructTree (id2:encounteredNodes) xs</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>constructTree _ _ = []</div><div><br></div><div>listToNode (p:ps:[]) = Node p [Node ps []]</div><div>listToNode (p:ps) = Node p [listToNode ps]</div><div>
---------------------------------------------------------------------</div><div><br></div><div>Nikolas</div></div>