Data.Graphを試そう

Haskell 30分プログラム

30分プログラム、その710。Haskellでグラフを扱いたかったので、Data.Graphを試してみました。

mkGraphの返すグラフの型が、具体的な型ではなく、grになっています。

*Main> :t mkGraph
mkGraph :: (Graph gr) => [LNode a] -> [LEdge b] -> gr a b

これはこれで便利なんでしょうが、今回は面倒なのでGrに束縛しています。

*main> :i Gr
data Gr a b
  = ....
...
instance [overlap ok] Graph Gr
  -- Defined in Data.Graph.Inductive.Tree
...

ソースコード

import Data.Graph.Inductive.Query.BFS
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Tree

-- ノードとエッジの準備
ns = zip [1..] ["A","B","C","D","E"]
es = [(1,2,"A->B"), (1,3,"A->C"), (3,4,"C->D"), (1,4,"A->D"),(4,5,"D->E")]

-- 型を与えてやらないとダメ
graph :: Gr String String
graph = mkGraph ns es

-- [(1,"A->D"),(4,"A->D"),(5,"D->E")]になる
shortPath = lesp 1 5 graph

参考