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