[Haskell] 图的表示方法：邻接表

1. 图的表示

import Data.Array
import Data.Ix

-- adjacency list representation
type Graph n w = Array n [(n, w)]

mkGraph :: (Ix n, Num w) => Bool -> (n, n) -> [(n, n, w)] -> (Graph n w)
mkGraph dir bnds es = 
    accumArray (\xs x -> x:xs) [] bnds
               ([(x1, (x2, w)) | (x1, x2, w) <- es] ++
                if dir then []
                else [(x2, (x1, w)) | (x1, x2, w) <- es, x1 /= x2])

adjacent :: (Ix n, Num w) => (Graph n w) -> n -> [n]
adjacent g v = map fst $ g!v

nodes :: (Ix n, Num w) => (Graph n w) -> [n]
nodes g = indices g

edgeIn :: (Ix n, Num w) => (Graph n w) -> (n, n) -> Bool
edgeIn g (x, y) = elem y $ adjacent g x

weight :: (Ix n, Num w) => n -> n -> (Graph n w) -> w
weight x y g = head [c | (a, c) <- g!x, a == y]

edgesD :: (Ix n, Num w) => (Graph n w) -> [(n, n, w)]
edgesD g = [(v1, v2, w) | v1 <- nodes g, (v2, w) <- g!v1]

edgesU :: (Ix n, Num w) => (Graph n w) -> [(n, n, w)]
edgesU g = [(v1, v2, w) | v1 <- nodes g, (v2, w) <- g!v1, v1 < v2]

2. 用例

testGraph = mkGraph False (1, 5) 
                  [(1, 2, 12), (1, 3, 34), (1, 5, 78),
                   (2, 4, 55), (2, 5, 32), (3, 4, 61),
                   (3, 5, 44), (4, 5, 93)]
                   
testAdjacent = adjacent testGraph 1
-- [5,3,2]

testNodes = nodes testGraph 
-- [1,2,3,4,5]

testEdgeIn = edgeIn testGraph (1, 2)
-- True

testWeight = weight 1 2 testGraph
-- 12

testEdgesD = edgesD testGraph
-- [(1,5,78),(1,3,34),(1,2,12),(2,1,12),(2,5,32),(2,4,55),(3,1,34),(3,5,44),(3,4,61),(4,3,61),(4,2,55),(4,5,93),(5,4,93),(5,3,44),(5,2,32),(5,1,78)]

testEdgesU = edgesU testGraph
-- [(1,5,78),(1,3,34),(1,2,12),(2,5,32),(2,4,55),(3,5,44),(3,4,61),(4,5,93)]

参考

Algorithms: A Functional Programming Approach