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
