V tomto příspěvku se podíváme, jak lze s využitím vlastností jazyka Haskell přímočaře implementovat výpočet tranzitivního uzávěru grafu pomocí Warshallova algoritmu.
Úvod
Tranzitivní uzávěr grafu je takový graf, kde pokud uzel j je v původním grafu dosažitelný z uzlu i, tak v uzávěru bude hrana spojující vrchol i s vrcholem j (tj. všechny uzly, které z nějakého uzlu v původním grafu dosažitelné přes libovolný počet hran, jsou v uzávěru dosažitelné přímo). Výpočet tranzitivního uzávěru grafu (či relace; princip je stejný) nachází uplatnění v řadách oblastí, např. při zjišťování dosažitelnosti v sítích, v překladačích, či jej lze využít při převodu konečného automatu na odpovídající regulární výraz. Mezi nejjednodušší způsob, jak jej vypočítat, patří Warshallův algoritmus. Pokud jej neznáte, mrkněte např. zde či zde, kde je krátce popsán, protože já ho tady vysvětlovat nebudu (nic složitého na něm není).
Implementace
Jdeme na to. Graf budeme reprezentovat maticí sousednosti, což je booleovská čtvercová matice (n, n), kde n je počet vrcholů a prvek (i, j) je True právě tehdy když je vrchol i spojen s vrcholem j (předpokládáme, že vrcholu jsou očíslovány 1..n). K implementaci použijeme dvourozměrné pole:
import Data.Array -- | A graph is represented as a boolean adjacency matrix. type Graph = Array (Int, Int) Bool
Při implementaci algoritmu využijeme toho, že většina implementací jazyka Hasell provádí tzv. líné vyhodnocování. To nám umožní, abychom definovali prvky výsledku na základě výsledku :). Nejdříve uvedu kompletní kód algoritmu, který následně okomentuji.
-- | Computes the transitive closure of a given graph using Warshall algorithm. transClosure :: Graph -> Graph transClosure g = array ((1, 1), (n, n)) [((i, j), d!(n, i, j)) | i <- [1..n], j <- [1..n]] where (_, (n, _)) = bounds g d = array ((0, 1, 1), (n, n, n)) [((k, i, j), val k i j) | k <- [0..n], i <- [1..n], j <- [1..n]] val 0 i j = g!(i, j) val k i j = (d!(k-1, i, j)) || ((d!(k-1, i, k)) && (d!(k-1, k, j)))
Na vstupu máme graf a výsledkem je graf, který reprezentuje tranzitivní uzávěr daného grafu. Pro zjištění počtu vrcholů použijeme funkci bounds:
(_, (n, _)) = bounds g
Celý výpočet nám bude reprezentovat "proměnná" d, což je trojrozměrné pole (všimněte si, že Warshallův algoritmus jsou tři vnořené cykly), kde v první dimenzi se nachází mezivýsledek (graf reprezentovaný dvourozměrnou maticí) pro každou z n iterací:
d = array ((0, 1, 1), (n, n, n)) [((k, i, j), val k i j) | k <- [0..n], i <- [1..n], j <- [1..n]]
A teď přijde to zajímavé. Pro výpočet hodnot v poli použijeme rekurzivní definice Warshallova algoritmu. Hodnoty pro nultou iteraci (k = 0) bereme přímo ze vstupního grafu (při k = 0 mohou být uzly spojeny pouze přímo):
val 0 i j = g!(i, j)
Hodnoty v k-té iteraci, kde k > 0, závisí na hodnotách z (k-1)-ní iterace a jsou dány následujícím vztahem, který vyplývá z definice algoritmu:
val k i j = (d!(k-1, i, j)) || ((d!(k-1, i, k)) && (d!(k-1, k, j)))
Všimněte si krásy této definice. Nemusíme postupovat odspodu (od k = 0, resp. 1), jako při implementaci v imperativních jazycích, ale prostě nadefinujeme výsledek rekurzivně a o samotný výpočet už se postará Haskell :). S využitím líného vyhodnocení jsme schopni se při definici d odkazovat na hodnoty v tomto poli.
Výsledek algoritmu je uložen v n-té iteraci, takže ho odtamtud vybereme:
transClosure g = array ((1, 1), (n, n)) [((i, j), d!(n, i, j)) | i <- [1..n], j <- [1..n]]
Zdrojáky
Kompletní zdrojáky jsou ke stažení zde.
Poznámky na závěr
Výhodou této implementace v Haskellu je její jednoduchost (jak z hlediska doby nutné k implementaci, tak z hlediska pochopení). Nevýhodou je to, že potřebujeme n-krát větší prostor, než pokud by naše implementace pracovala in situ (algoritmus takto naimplementovat lze, ale bude třeba využít měnitelná pole).