Multikolorowanie grafu w Haskellu

Ostatnio na studiach dostałem takie zadanie do zaimplementowania:

Część I:
Wygenerować plik w formacie GXL zawierający graf składający się ze stacji, które są losowe rozmieszczone wewnątrz miasta, w którym stacje są połączone krawędzią wtedy, gdy ich zasięg się pokrywa.

Wejście:

• Współrzędne środka koła (miasta)
• Promień koła (miasta)
• Liczba stacji
• Zasięg (promień) stacji

Wyjście:
Uzyskany graf w formacie GXL.

Część II
Należy wczytać wygenerowany wcześniej graf oraz zapotrzebowanie na częstotliwości dla każdej stacji. Stacje, których zasięg się pokrywa nie mogą uzyskać tych samych częstotliwości. Program powinien znaleźć jak najmniejszą liczbę różnych częstotliwości potrzebnych aby stacje mogły funkcjonować.

Przykład:
Mając prosty graf [1]->[2]->[3] i wiedząc, że stacja 1 potrzebuje 3 częstotliwości, stacja 2 potrzebuje 4 a stacja ostatnia 5. Wówczas powinniśmy przydzielić częstotliwości np. tak:

• Stacja nr 1: 4,5,6
• Stacja nr 2: 0,1,2,3
• Stacja nr 3: 4,5,6,7,8

i wynikiem działania programu powinna być liczba 9. Jak widać stacja pierwsza i ostatnia może korzystać z tych samych częstotliwości, ponieważ ich zasięg się nie pokrywa. Stacja druga natomiast musi korzystać z innych częstotliwości niż stacja 1 i 3.

Wejście:

• Plik GXL
• Zapotrzebowanie na częstotliwości dla każdej stacji

Wyjście:

• Liczba przydzielonych różnych częstotliwości

Problem postanowiłem rozwiązać w Haskellu z uwagi na możliwość operacji na listach nieskończonych co w tym przypadku bardzo ułatwia znajdowanie częstotliwości. W części II wykorzystałem algorytm SLF. Oczywiście problem jest NP zupełny więc nie ma idealnego algorytmu, który by przydzielił zawsze najmniejszą możliwą do uzyskania liczbę częstotliwości dla każdego przypadku.

Część I: gxl.hs
Część II: multicolor.hs
Plik do obsługi formatu GXL (wymagany aby skompilować poprzednie 2 pliki): gxl_dtd.hs