Úloha Graph

Mějme hranově ohodnocený orientovaný graf, jehož součásti jsou definovány následovně:

newtype Vertex = Vertex Int deriving (Show, Read, Eq, Ord)

Typ Vertex reprezentuje vrchol (uzel) grafu, tedy očíslovaný prvek množiny. Dá se znázornit jako bod v rovině.

data Link = Link { edge :: (Vertex, Vertex)
                 , weight :: Double
                 } deriving (Show, Read)

Datová struktura Link představuje spojení mezi dvěma vrcholy, což je ohodnocená hrana mezi dvěma vrcholy. Můžeme si ho představit jako „šipku“ mezi dvěma body v rovině, která má k sobě přiřazené reálné číslo. Na to můžeme nahlížet jako na vzdálenost mezi těmito vrcholy.

instance Eq Link where
    (==) = (==) `on` edge

instance Ord Link where
    compare = compare `on` edge

Toto spojení má implementovanou rovnost a uspořádání podle hran, abychom s ním mohli dále pracovat. Pomocná funkce on se nachází v modulu Data.Function.

type Graph = (Set Vertex, Set Link)

A konečně, typové synonymum Graph je dvojice množin vrcholů a spojení (ohodnocených hran). Všechny vrcholy, které jsou použity v konstrukci hran, jsou obsaženy i v množině vrcholů.

Funkce pro práci s grafem

Vašim úkolem je napsat následující funkce: [každá za 1 bod]

-- Vytvoří prázdný graf.
graph :: Graph

-- Přidá do grafu nový vrchol.
-- Pokud vrchol je již v grafu přítomen, přepíše se.
addVertex :: Vertex -> Graph -> Graph

-- Přidá do grafu novou hranu s daným ohodnocením.
-- Pokud hrana je již v grafu přítomna, přepíše se.
-- Pokud nějaký z vrcholů není v grafu obsažen,
-- přidá se do seznamu vrcholů.
addLink :: (Vertex, Vertex) -> Double -> Graph -> Graph

-- Odstraní vrchol z grafu spolu se všemi hranami,
-- ve kterých je obsažen. Pokud vrchol není v grafu
-- obsažen, vypíše se chybová hláška.
deleteVertex :: Vertex -> Graph -> Graph

-- Odstraní hranu z grafu; množinu vrcholů nemodifikuje.
-- Pokud hrana není v grafu obsažena, vypíše se chybová hláška.
deleteLink :: (Vertex, Vertex) -> Graph -> Graph

-- Nalezne všechny hrany, které obsahují daný vrchol.
findVertex :: Vertex -> Graph -> Set Link

-- Zjistí počet hran v grafu.
linkCount :: Graph -> Int

-- Celkové ohodnocení hran v grafu.
totalWeight :: Graph -> Double

-- Průměrné ohodnocení hran v grafu;
-- v případě grafu bez hran se vypíše chybová hláška.
averageWeight :: Graph -> Double

-- Medián ohodnocení hran v grafu;
-- v případě grafu bez hran se vypíše chybová hláška.
medianWeight :: Graph -> Double

Poznámky

Snažte se v co nejvyšší možné míře využít funkce z modulu Data.Set a další již napsané funkce.
Průměrem se má na mysli aritmetický průměr, mediánem hodnota prostředního prvku.
Nezapomeňte ověřit, že se graf udržuje v konzistentním stavu, tedy že například po odebrání vrcholu nezůstanou v grafu hrany obsahující tento vrchol.

Příklady

> graph
(fromList [],fromList [])
> addVertex (Vertex 1) graph
(fromList [Vertex 1],fromList [])
> addVertex (Vertex 2) $ addVertex (Vertex 1) graph
(fromList [Vertex 1,Vertex 2],fromList [])
> addLink (Vertex 1, Vertex 2) 10 graph
(fromList [Vertex 1,Vertex 2],fromList [Link {edge = (Vertex 1,Vertex 2), weight = 10.0}])
> addLink (Vertex 1, Vertex 2) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
(fromList [Vertex 1,Vertex 2],fromList [Link {edge = (Vertex 1,Vertex 2), weight = 20.0}])
> addLink (Vertex 2, Vertex 1) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
(fromList [Vertex 1,Vertex 2],fromList [Link {edge = (Vertex 1,Vertex 2), weight = 10.0},Link {edge = (Vertex 2,Vertex 1), weight = 20.0}])
> addLink (Vertex 1, Vertex 2) 10 $ addVertex (Vertex 3) graph
(fromList [Vertex 1,Vertex 2,Vertex 3],fromList [Link {edge = (Vertex 1,Vertex 2), weight = 10.0}])
> deleteVertex (Vertex 3) . addLink (Vertex 1, Vertex 2) 10 $ addVertex (Vertex 3) graph
(fromList [Vertex 1,Vertex 2],fromList [Link {edge = (Vertex 1,Vertex 2), weight = 10.0}])
> deleteVertex (Vertex 1) . addLink (Vertex 1, Vertex 2) 10 $ addVertex (Vertex 3) graph
(fromList [Vertex 2,Vertex 3],fromList [])
> deleteVertex (Vertex 4) . addLink (Vertex 1, Vertex 2) 10 $ addVertex (Vertex 3) graph
*** Exception: There is no such vertex in the graph.
> deleteLink (Vertex 1, Vertex 2) $ addLink (Vertex 1, Vertex 2) 10 graph
(fromList [Vertex 1,Vertex 2],fromList [])
> deleteLink (Vertex 1, Vertex 2) . addLink (Vertex 2, Vertex 1) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
(fromList [Vertex 1,Vertex 2],fromList [Link {edge = (Vertex 2,Vertex 1), weight = 20.0}])
> deleteLink (Vertex 2, Vertex 1) $ addLink (Vertex 1, Vertex 2) 10 graph
*** Exception: There is no such edge in the graph.
> findVertex (Vertex 2) . addLink (Vertex 2, Vertex 1) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
fromList [Link {edge = (Vertex 1,Vertex 2), weight = 10.0},Link {edge = (Vertex 2,Vertex 1), weight = 20.0}]
> findVertex (Vertex 3) . addLink (Vertex 2, Vertex 1) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
fromList []
> linkCount . addLink (Vertex 2, Vertex 1) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
2
> totalWeight . addLink (Vertex 2, Vertex 1) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
30.0
> averageWeight . addLink (Vertex 3, Vertex 4) 18 . addLink (Vertex 2, Vertex 1) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
16.0
> medianWeight . addLink (Vertex 3, Vertex 4) 18 . addLink (Vertex 2, Vertex 1) 20 $ addLink (Vertex 1, Vertex 2) 10 graph
18.0
> averageWeight graph
*** Exception: The graph doesn't contain any edges.
> medianWeight graph
*** Exception: The graph doesn't contain any edges.

Nejkratší cesta v grafu

Vašim dalším úkolem je napsat tuto funkci: [10 bodů]

-- Zjistí nejkratší cestu z jednoho vrcholu do druhého;
-- jestliže mezi vrcholy neexistuje cesta nebo vrcholy
-- nejsou v grafu přítomny, vypíše se chybová hláška.
shortestPath :: Vertex -> Vertex -> Graph -> Double

Pro nejkratší cestu v grafu existuje mnoho algoritmů, mezi nejznámější patří Dijkstrův algoritmus, algoritmus A*, Floydův-Warshallův algoritmus a Bellmanův-Fordův algoritmus. Můžete však použít jakýkoliv jiný vhodný algoritmus, případně si vymyslet vlastní. Tento algoritmus by měl dát odpověď v polynomiálním čase vzhledem k počtu hran.

Poznámky

V případě, že si vyberete Dijkstrův algoritmus či jeho variantu, vypište chybovou hlášku, pokud algoritmus obsahuje záporné ohodnocení. Tehdy totiž algoritmus nemusí nutně poskytovat správné výsledky.
Pokud si myslíte, že je zadaná datová struktura pro vámi použitý algoritmus nevhodná, můžete si definovat vlastní strukturu, do které si před samotným výpočtem graf převedete. V takovém připadě ale typ funkce shortestPath musí zůstat nezměněn.
Můžete si také definovat maximální hodnotu („nekonečno“), která bude znázorňovat nedosažitelný vrchol, případně využít datový typ Maybe z modulu Data.Maybe.
Nejspíš se vám také bude hodit funkce minimumBy z modulu Data.Foldable.
Jako motivační úvod může posloužit přednáška Getting from A to B: Fast Route Finding Using Slow Computers (prezentance), ve které je vysvětleno, jak lze psát (nejen v Haskellu) algoritmy pro nejkratší cestu v grafu.

Příklady

> shortestPath (Vertex 1) (Vertex 3) $ addLink (Vertex 1, Vertex 2) 10 graph
*** Exception: There is no such vertex in the graph.
> shortestPath (Vertex 2) (Vertex 1) $ addLink (Vertex 1, Vertex 2) 10 graph
*** Exception: The path doesn't exist in the graph.
> shortestPath (Vertex 1) (Vertex 2) $ addLink (Vertex 1, Vertex 2) 10 graph
10.0
> shortestPath (Vertex 1) (Vertex 3) . addLink (Vertex 2, Vertex 3) 10 $ addLink (Vertex 1, Vertex 2) 10 graph
20.0
> shortestPath (Vertex 1) (Vertex 3) . addLink (Vertex 1, Vertex 3) 100 . addLink (Vertex 2, Vertex 3) 10 $ addLink (Vertex 1, Vertex 2) 10 graph
20.0
> shortestPath (Vertex 1) (Vertex 3) . addLink (Vertex 1, Vertex 3) 5 . addLink (Vertex 2, Vertex 3) 10 $ addLink (Vertex 1, Vertex 2) 10 graph
5.0

Vypracování úlohy

Řešení úlohy uložte do souboru graph.hs a nahrajte do druhé odevzdávárny. Nejzazší termín pro vypracování je 27. 3. 2011, 23:59, později již není možné soubor s řešením odevzdat pomocí IS.

← IB016