- Find the start node: The node appears in the
map fst edges
list but not in themap 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) - Build your tree recursively from this start node. Be careful as you could still have cycles in the graph
Building a graph from a list of edges
-
04-04-2022 - |
Вопрос
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!
Решение
Другие советы
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])]
Не связан с StackOverflow