5 type Vertex = Integer
\r
6 type MaxVertexNo = Integer
\r
7 type Edge = (Vertex,Cost,Vertex)
\r
10 data ALgraph = ALg [(Vertex,[(Vertex,Cost)])] deriving (Eq,Show)
\r
11 data ELgraph = ELg MaxVertexNo [Edge] deriving (Eq,Show)
\r
12 data AMgraph = AMg [Row] deriving (Eq,Show)
\r
14 type Inp = (MaxVertexNo, [(Vertex,Vertex,Cost)])
\r
18 isValid :: Inp -> Bool
\r
19 isValid (max,edges) | (max<0) = False
\r
20 | otherwise = checkEdges edges [] max
\r
22 checkEdges :: [(Vertex,Vertex,Cost)] -> [(Vertex,Vertex)] -> MaxVertexNo -> Bool
\r
23 checkEdges ((v1,v2,c):[]) edges max | (elem (v1,v2) edges) = False
\r
24 | ((v1<=max)&&(v1>=0)&&(v2<=max)&&(v2>=0)&&(c>0)) = True
\r
26 checkEdges ((v1,v2,c):xs) edges max | (elem (v1,v2) edges) = False
\r
27 | ((v1<=max)&&(v1>=0)&&(v2<=max)&&(v2>=0)&&(c>0)) = checkEdges xs ([(v1,v2)]++edges) max
\r
32 inp2el :: Inp -> ELgraph
\r
33 inp2el (max, edges) = ELg max (createEdges edges)
\r
35 createEdges :: [(Vertex,Vertex,Cost)] -> [Edge]
\r
37 createEdges ((v1,v2,c):xs) = [(v1,c,v2)] ++ createEdges xs
\r
41 al2am :: ALgraph -> AMgraph
\r
42 al2am (ALg al) = AMg(transformAL2AM (sortBy sortALEdges al) 0 (getLengthAL al 0))
\r
44 sortALEdges :: (Vertex,[(Vertex,Cost)]) -> (Vertex,[(Vertex,Cost)]) -> Ordering
\r
45 sortALEdges (a,_) (b,_) | a<b = LT
\r
48 sortList :: (Vertex,Cost) -> (Vertex,Cost) -> Ordering
\r
49 sortList (a,_) (b,_) | a<b = LT
\r
52 transformAL2AM :: [(Vertex,[(Vertex,Cost)])] -> Integer -> Integer -> [Row]
\r
53 transformAL2AM [] i max= []
\r
54 transformAL2AM ((v,list):xs) i max | (v==i) = [getRow (sortBy sortList list) 0 max] ++ transformAL2AM xs (i+1) max
\r
55 | otherwise = [getRow [] 0 max] ++ transformAL2AM ([(v,list)]++xs) (i+1) max
\r
57 getRow :: [(Vertex,Cost)] -> Integer -> Integer-> Row
\r
58 getRow [] i max | (i==max) = [0]
\r
59 | otherwise = [0] ++ getRow [] (i+1) max
\r
60 getRow ((v,c):xs) i max | (i==max)&&(v==i) = [c]
\r
62 | (v==i) = [c] ++ getRow xs (i+1) max
\r
63 | otherwise = [0] ++ getRow ([(v,c)]++xs) (i+1) max
\r
67 al2el :: ALgraph -> ELgraph
\r
68 al2el (ALg al) = ELg (getLengthAL al 0) (splitAL al)
\r
70 getLengthAL :: [(Vertex,[(Vertex,Cost)])] -> Integer -> Integer
\r
71 getLengthAL [] max = max
\r
72 getLengthAL ((v,list):xs) max | ((getMaxfromList list 0)>v)&&((getMaxfromList list 0)>max) = getLengthAL xs (getMaxfromList list 0)
\r
73 | (v>max) = getLengthAL xs v
\r
74 | otherwise = getLengthAL xs max
\r
76 getMaxfromList :: [(Vertex,Cost)] -> Integer -> Integer
\r
77 getMaxfromList [] max = max
\r
78 getMaxfromList ((v,c):xs) max | (v>max) = getMaxfromList xs v
\r
79 | otherwise =getMaxfromList xs max
\r
81 --transformAL2EL :: ALgraph -> [Edge]
\r
82 --transformAL2EL (ALg al)= splitAL al
\r
84 splitAL :: [(Vertex,[(Vertex,Cost)])] -> [Edge]
\r
86 splitAL (row:xs) = splitALRow row ++ splitAL xs
\r
88 splitALRow :: (Vertex,[(Vertex,Cost)]) -> [Edge]
\r
89 splitALRow (v,list) = getEdges v list
\r
91 getEdges :: Vertex -> [(Vertex,Cost)] -> [Edge]
\r
93 getEdges v1 ((v2,c):[]) = [(v1,c,v2)]
\r
94 getEdges v1 ((v2,c):xs) = [(v1,c,v2)] ++ getEdges v1 xs
\r
98 am2al :: AMgraph -> ALgraph
\r
99 am2al (AMg am) = ALg (changeAL (transformAM2AL am 0))
\r
101 changeAL :: [(Vertex,[(Vertex,Cost)])] -> [(Vertex,[(Vertex,Cost)])]
\r
103 changeAL ((x,list):xs) | (list==[]) = changeAL xs
\r
104 | otherwise = [(x,list)] ++ changeAL xs
\r
106 transformAM2AL :: [Row] -> Vertex -> [(Vertex,[(Vertex,Cost)])]
\r
107 transformAM2AL (row:[]) v = [(v,(getList v row 0))]
\r
108 transformAM2AL (row:xs) v = [(v,(getList v row 0))] ++ transformAM2AL xs (v+1)
\r
110 getList :: Vertex -> Row -> Integer -> [(Vertex,Cost)]
\r
111 getList v [] i = []
\r
112 getList v (x:xs) i | (x==0) = getList v xs (i+1)
\r
113 | otherwise = [(i,x)] ++ getList v xs (i+1)
\r
117 am2el :: AMgraph -> ELgraph
\r
118 am2el (AMg am) = ELg (fromIntegral(length am)-1) (transformAM2EL am 0)
\r
120 transformAM2EL :: [Row] -> Vertex -> [Edge]
\r
121 transformAM2EL (row:[]) v = [] ++ getEdges v (getList v row 0)
\r
122 transformAM2EL (row:xs) v = getEdges v (getList v row 0) ++ transformAM2EL xs (v+1)
\r
126 sortELEdges :: (Vertex,Cost,Vertex) -> (Vertex,Cost,Vertex) -> Ordering
\r
127 sortELEdges (a,_,_) (b,_,_) | a<b = LT
\r
130 el2al :: ELgraph -> ALgraph
\r
131 el2al (ELg max el) = ALg(changeAL(transformEL2AL 0 (sortBy sortELEdges el) max))
\r
133 transformEL2AL :: Vertex -> [(Vertex,Cost,Vertex)] -> MaxVertexNo -> [(Vertex,[(Vertex,Cost)])]
\r
134 transformEL2AL v el max | (v<=max) = [(v,getALEdges v el False)] ++ (transformEL2AL (v+1) el max)
\r
137 getALEdges :: Vertex -> [(Vertex,Cost,Vertex)] -> Bool -> [(Vertex,Cost)]
\r
138 getALEdges v [] b = []
\r
139 getALEdges v ((v1,c,v2):xs) b | (v1==v) = [(v2,c)] ++ getALEdges v xs True
\r
140 | ((v1/=v)&&(not b)) = getALEdges v xs False
\r
141 | ((v1/=v)&&(b)) = []
\r
145 el2am :: ELgraph -> AMgraph
\r
146 el2am el = al2am (el2al el)
\r
150 isNeighbourOf :: ELgraph -> Vertex -> Vertex -> Bool
\r
151 isNeighbourOf el v1 v2 = elem v2 (allNeighboursOf el v1)
\r
155 allNeighboursOf :: ELgraph -> Vertex -> [Vertex]
\r
156 allNeighboursOf el v = splitAL3 (el2al el) v
\r
158 splitAL3 :: ALgraph -> Vertex -> [Vertex]
\r
159 splitAL3 (ALg al) v = splitAL2 al v
\r
161 splitAL2 :: [(Vertex,[(Vertex,Cost)])] -> Vertex -> [Vertex]
\r
162 splitAL2 al v = getNeighbours al v
\r
164 getNeighbours :: [(Vertex,[(Vertex,Cost)])] -> Vertex -> [Vertex]
\r
165 getNeighbours [] v = []
\r
166 getNeighbours ((v1,list):xs) v | (v==v1) = list2neighbour list
\r
167 | otherwise = getNeighbours xs v
\r
169 list2neighbour :: [(Vertex,Cost)] -> [Vertex]
\r
170 list2neighbour [] = []
\r
171 list2neighbour ((v,c):xs) = [v] ++ list2neighbour xs
\r
175 numberOfEdges :: AMgraph -> Integer
\r
176 numberOfEdges am = getEdgeCount (am2el am)
\r
178 getEdgeCount :: ELgraph -> Integer
\r
179 getEdgeCount (ELg max el) = fromIntegral (length el)
\r
183 isOnCycle :: ALgraph -> Vertex -> Cost -> Bool
\r
184 isOnCycle g v cost = path g v v cost
\r
185 -- isOnCycle (ALg al) v c = checkCycle al v c
\r
187 -- checkCycle :: [(Vertex,[(Vertex,Cost)])] -> Vertex -> Cost
\r
188 -- checkCycle ((v,list):xs) vs c | (v==vs) = searchNeighbours list vs c 0
\r
189 -- | otherwise = checkCycle xs vs c
\r
191 -- searchNeighbours [(Vertex,Cost)] -> Vertex -> Cost -> Integer ->
\r
192 -- searchNeighbours ((v,c):xs) vs c max =
\r
198 type MyGraph = [(Vertex,[(Vertex,Cost)])]
\r
199 castGraph :: ALgraph -> MyGraph
\r
200 castGraph (ALg xs) = xs
\r
202 exist :: [Vertex] -> Vertex -> Bool
\r
203 exist mypath node = isNothing (find (==node) mypath) == False
\r
205 getedges :: MyGraph -> Vertex -> [(Vertex,Cost)]
\r
208 | otherwise = snd ((maybeToList e)!!0)
\r
209 where e = find (\n -> (fst n) == k) g
\r
211 findPath :: MyGraph -> Vertex -> Vertex -> [Vertex] -> Int -> Integer -> Integer -> Bool -> [Vertex]
\r
212 findPath g von zu mypath pos max cur first
\r
213 | von == zu && cur <= max && first == False = mypath ++ [von]
\r
214 | von == zu && first == False = []
\r
215 | (length edges) <= pos = []
\r
216 | pos == 0 && (exist mypath von) = []
\r
217 | (length current /= 0) = current
\r
218 | pos < (length edges) = next_sibling
\r
221 next_sibling = findPath g von zu mypath (pos+1) max cur first
\r
222 edges = getedges g von
\r
223 weight = cur + snd (edges!!pos)
\r
224 current = findPath g (fst (edges!!pos)) zu (mypath++[von]) 0 max weight False
\r
226 path :: ALgraph -> Vertex -> Vertex -> Cost -> Bool
\r
227 path graph von zu max
\r
228 | (length mypath) == 0 = False
\r
231 mypath = (findPath g von zu [] 0 max 0) True
\r
232 g = castGraph graph
\r