<div dir="ltr"><div class="gmail_default" style="font-family:gulimche,monospace"><div class="gmail_default">Hi, all.</div><div class="gmail_default"><br></div><div class="gmail_default">I need to make graph/tree structure, </div><div class="gmail_default">the nodes of <span style="font-size:small">which are contained in _array_ </span></div><div class="gmail_default"><span style="font-size:small">to facilitate random access to </span><span style="font-size:small">that node.</span></div><div class="gmail_default"><br></div><div class="gmail_default">There is no problem in building an array of graph nodes from edge list.</div><div class="gmail_default"><br></div><div class="gmail_default">> -- Graphs</div><div class="gmail_default">> data Graph a = GNode a [Graph a]</div><div class="gmail_default">> mkGraph :: [(a,[Int])] -> Array Int (Graph a)</div><div class="gmail_default"><span style="font-size:small">></span><span style="font-size:small"> </span>mkGraph table = table'</div><div class="gmail_default"><span style="font-size:small">></span><span style="font-size:small"> </span>  where n      = length table</div><div class="gmail_default"><span style="font-size:small">></span><span style="font-size:small"> </span>        table' = listArray (0,n-1) $</div><div class="gmail_default"><span style="font-size:small">></span><span style="font-size:small"> </span>          map(\(x,adjs) -> GNode x (map (table' !) adjs)) table</div><div class="gmail_default"><br></div><div class="gmail_default">However, I cannot build tree from the same input,</div><div class="gmail_default">if given edge list is undirected one.</div><div class="gmail_default">The leaf node's edge has <span style="font-size:small">a link to parent node</span></div><div class="gmail_default">when edge list is undirected, and I cannot find way</div><div class="gmail_default">to cut that parent edge in building tree.</div><div class="gmail_default"><br></div><div class="gmail_default">For example, think of following simple tree:</div><div class="gmail_default"><div class="gmail_default"><span style="font-size:small">   A(0)</span><br></div><div class="gmail_default">  / \</div><div class="gmail_default">B(1) C(2)</div><div class="gmail_default"><br></div><div class="gmail_default">It's hard to build tree with following edge list:</div></div><div class="gmail_default"><div class="gmail_default">[('A',[1,2]),</div><div class="gmail_default"> ('B',[0]),</div><div class="gmail_default"> ('C',[0])]</div><div class="gmail_default"><div class="gmail_default"><div class="gmail_default">but it's easy when edge list is following:</div><div><div class="gmail_default">[('A',[1,2]),</div><div class="gmail_default"> ('B',[]),</div><div class="gmail_default"> ('C',[])]</div><div class="gmail_default"><br></div><div class="gmail_default">How can I build an array of tree nodes for the former?</div><div class="gmail_default">In other words, How can I build following mkTree function?</div><div class="gmail_default"><br></div><div class="gmail_default"><div class="gmail_default">data Tree a =  Node { value :: a</div><div class="gmail_default">                    , parent :: Tree a</div><div class="gmail_default">                    , level :: Int</div><div class="gmail_default">                    , children ::  [Tree a]</div><div class="gmail_default">                    } deriving Show</div><div class="gmail_default">mkTree :: [(a,[Int])] -> Array Int (Tree a)</div></div><div class="gmail_default"><br></div><div class="gmail_default">Any comments or helps will be deeply appreciated.</div><div class="gmail_default"><br></div><div class="gmail_default">Thank you.</div><div class="gmail_default"><br></div><div class="gmail_default">Chul-Woong Yang</div><div class="gmail_default"><br></div><div><br></div><div class="gmail_default"><div class="gmail_default"></div></div></div></div><div class="gmail_default"></div></div></div></div></div>