Building a graph from a list of edges

Question

Given a graph datatype as follows:

data Graph = Int :~> [Graph]
infixr :~>

and a list of edges like this:

edges = [(10,1), (10,5), (1,2), (2,3), (5,6), (5,9), (9,8)]

What is the function that will build the graph as follows:

result = 10 :~> [ 1 :~> [ 2 :~> 3 :~> [] ] 
                , 5 :~> [ 6 :~> [], 9 :~> 8 :~> [] ]
                ]

I'm sure it's right in front of my head, but I'm a bit exhausted and would appreciate the help. Thanks!

Answer 1

1. Find the start node: The node appears in the map fst edges list but not in the map snd edges list. As luqui remarked, you need to think about cases where you don't find such a node (or if you find more than one)
2. Build your tree recursively from this start node. Be careful as you could still have cycles in the graph

Answer 2

Not really what you want, but the Data.Graph module of the containers library could help.

import Data.Graph
bounds = (1,10) 
edges = [(10,1), (10,5), (1,2), (2,3), (5,6), (5,9), (9,8)]

> buildG bounds edges
array (1,10) [(1,[2]),(2,[3]),(3,[]),(4,[]),(5,[9,6]),(6,[]),(7,[]),(8,[]),(9,[8]),(10,[5,1])]