Segundo Projeto - Haskell

Data de entrega: 29/5 (3a feira) ate as 8:00 via email.

Individual ou em pares.

Uma técnica de clusterização (ou agrupamento) de dados num espaço cartesiano é montar a arvore geradora mínima dos dados. A arvore indica a forma de menor custo de ligar todos os pontos. Se quisermos quebrar o conjunto de dados em k grupos, basta remover as k-1 maiores arestas do arvore geradora mínima, e considerar que cada uma das k sub-arvores (agora não mais conectadas) é um grupo.

Escreva um programa em Haskel que recebe os dados no seguinte formato

k
a x1 x2 x3
b y1 y2 y3
e z1 z2 z3
...

onde k é o numero de grupos a serem construídos a (b etc.) são os "nomes" dos pontos, e x1 x2 x3 nesse caso são as coordenadas num espaço de 3 dimensões do ponto a, y1 y2 y3 são as coordenadas do ponto b e assim por diante.

O programa devera imprimir o nome dos pontos em cada grupo - um grupo por linha, ordenados alfabeticamente. Por exemplo se tivermos que dividir os dados em 3 grupos então a saída

a b e f r 
i j p q m n 
c g h 

indica os 3 grupos (a ordem que os grupos são impressos não é importante). A saída pode ser também no formato

["a", "b", "e", "f", "r"] 
["i", "j", "p", "q", "m", "n"] 
["c", "g", "h"] 

Não se preocupe com otimização de estruturas de dados no algoritmo de construção da arvore geradora mínima. Se seu programa for cúbico (no número de pontos) não tem problema. O algoritmo de achar os componentes conexos na arvore depois de remover as k-1 arestas maiores também não precisa ser otimizado.

O seu programa rodará como:

runhaskell projeto2.hs < dados.txt 

ou seja os dados devem ser lidos do standard input.