3 type MaxVertexNo = Integer
4 type Edge = (Vertex,Cost,Vertex)
7 data ALgraph = ALg [(Vertex,[(Vertex,Cost)])] deriving (Eq,Show)
8 data ELgraph = ELg MaxVertexNo [Edge] deriving (Eq,Show)
9 data AMgraph = AMg [Row] deriving (Eq,Show)
11 type Inp = (MaxVertexNo,[(Vertex,Vertex,Cost)])
15 isValid :: Inp -> Bool
16 isValid (mvert,list) = (and( [ (checkValidEl (list!!index) mvert) | index <- [0..((min (fromEnum mvert) (length list))-1)] ] )) && (ckeckValidLinks list)
18 checkValidEl :: (Vertex,Vertex,Cost) -> MaxVertexNo -> Bool
19 checkValidEl (from,to,cost) mi | ((from > mi) || (to > mi)) = False
20 checkValidEl (from,to,cost) mi | (cost <= 0) = False
21 checkValidEl (_,_,_) _ = True
23 ckeckValidLinks :: [(Vertex,Vertex,Cost)] -> Bool
24 ckeckValidLinks [] = True
25 ckeckValidLinks xs = ((length xs) == (length (undup xs)))
27 undup :: [(Vertex,Vertex,Cost)] -> [(Vertex,Vertex,Cost)]
29 undup ((f,t,c):xs) = (f,t,c) : undup (filter (\(x,y,z) -> not ((f == x) && (t == y))) xs)
34 inp2el :: Inp -> ELgraph
35 inp2el (vnum, xs) = ELg vnum [ (inp2elConv x) | x <- xs]
37 inp2elConv :: (Vertex,Vertex,Cost) -> (Vertex,Cost,Vertex)
38 inp2elConv (f,t,c) = (f,c,t)
42 el2al :: ELgraph -> ALgraph
43 el2al (ELg maxV el) = ALg ([(el2alGet el (toInteger i)) | i <- [0..((length el)-1)]] ++ [(i,[]) | i <- [(toInteger (length el))..maxV]])
45 el2alGet :: [Edge] -> Integer -> (Vertex,[(Vertex,Cost)])
46 el2alGet e i = (i, concat([ (el2alRet el i) | el <- e]))
48 el2alRet :: Edge -> Integer -> [(Vertex,Cost)]
49 el2alRet (f,c,t) i | (f == i) = [(t,c)]
54 al2am :: ALgraph -> AMgraph
55 al2am (ALg al) = AMg [[ al2amEl al (toInteger i) (toInteger j) | j <- [0..((length al)-1)]] | i <- [0..((length al)-1)]]
57 al2amEl :: [(Vertex,[(Vertex,Cost)])] -> Integer -> Integer -> Integer
58 al2amEl xs i j | ((toInteger (length xs)) > i) = al2amRow (xs!!(fromEnum i)) j
60 al2amRow :: (Vertex,[(Vertex,Cost)]) -> Integer -> Integer
61 al2amRow (v,xs) j = al2amVal xs j
63 al2amVal :: [(Vertex,Cost)] -> Integer -> Integer
65 al2amVal ((v,c):xs) i | (v /= i) = al2amVal xs i
66 al2amVal ((v,c):xs) i | (v == i) = c
70 am2el :: AMgraph -> ELgraph
71 am2el (AMg m) = ELg (toInteger ((length m)-1)) (concat [ (concat [ am2elC ((m!!(fromEnum i))!!(fromEnum j)) (toInteger i) (toInteger j) | j <- [0..((length m)-1)]]) | i <- [0..((length m)-1)]])
73 am2elC :: Cost -> Vertex -> Vertex -> [Edge]
74 am2elC c f t | (c == 0) = []
75 am2elC c f t = [(f,c,t)]
79 el2am :: ELgraph -> AMgraph
80 el2am eg = al2am (el2al eg)
82 al2el :: ALgraph -> ELgraph
83 al2el ag = am2el (al2am ag)
85 am2al :: AMgraph -> ALgraph
86 am2al am = el2al (am2el am)
92 isNeighbourOf :: ELgraph -> Vertex -> Vertex -> Bool
93 isNeighbourOf _ _ _ = True
95 isOnCycle :: ALgraph -> Vertex -> Cost -> Bool
96 isOnCycle _ _ _ = False