Aufgabe5.hs

   1 import Data.List\r
   2 import Maybe\r
   3 \r
   4 type Cost = Integer\r
   5 type Vertex = Integer\r
   6 type MaxVertexNo = Integer\r
   7 type Edge = (Vertex,Cost,Vertex)\r
   8 type Row = [Integer]\r
   9 \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
  13 \r
  14 type Inp = (MaxVertexNo, [(Vertex,Vertex,Cost)])\r
  15 \r
  16 -- Bsp 5.1\r
  17 \r
  18 isValid :: Inp -> Bool\r
  19 isValid (max,edges) | (max<0) = False\r
  20                     | otherwise = checkEdges edges [] max\r
  21 \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
  25                                     | otherwise = False\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
  28                                     | otherwise = False\r
  29 \r
  30 -- Bsp 5.2 a)\r
  31 \r
  32 inp2el :: Inp -> ELgraph\r
  33 inp2el (max, edges) = ELg max (createEdges edges)\r
  34 \r
  35 createEdges :: [(Vertex,Vertex,Cost)] -> [Edge]\r
  36 createEdges [] = []\r
  37 createEdges ((v1,v2,c):xs) = [(v1,c,v2)] ++ createEdges xs\r
  38 \r
  39 -- Bsp 5.2 b)\r
  40 \r
  41 al2am :: ALgraph -> AMgraph\r
  42 al2am (ALg al) = AMg(transformAL2AM (sortBy sortALEdges al) 0 (getLengthAL al 0))\r
  43 \r
  44 sortALEdges :: (Vertex,[(Vertex,Cost)]) -> (Vertex,[(Vertex,Cost)]) -> Ordering\r
  45 sortALEdges (a,_) (b,_) | a<b = LT\r
  46                         | otherwise = GT\r
  47 \r
  48 sortList :: (Vertex,Cost) -> (Vertex,Cost) -> Ordering\r
  49 sortList (a,_) (b,_) | a<b = LT\r
  50                      | otherwise =GT\r
  51 \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
  56 \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
  61                         | (i==max) = [0]\r
  62                         | (v==i) = [c] ++ getRow xs (i+1) max\r
  63                         | otherwise = [0] ++ getRow ([(v,c)]++xs) (i+1) max\r
  64 \r
  65 -- Bsp 5.2 c)\r
  66 \r
  67 al2el :: ALgraph -> ELgraph\r
  68 al2el (ALg al) = ELg (getLengthAL al 0) (splitAL al)\r
  69 \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
  75 \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
  80 \r
  81 --transformAL2EL :: ALgraph -> [Edge]\r
  82 --transformAL2EL (ALg al)= splitAL al\r
  83 \r
  84 splitAL :: [(Vertex,[(Vertex,Cost)])] -> [Edge]\r
  85 splitAL [] = []\r
  86 splitAL (row:xs) = splitALRow row ++ splitAL xs\r
  87 \r
  88 splitALRow :: (Vertex,[(Vertex,Cost)]) -> [Edge]\r
  89 splitALRow (v,list) = getEdges v list\r
  90 \r
  91 getEdges :: Vertex -> [(Vertex,Cost)] -> [Edge]\r
  92 getEdges v1 [] = []\r
  93 getEdges v1 ((v2,c):[]) = [(v1,c,v2)]\r
  94 getEdges v1 ((v2,c):xs) = [(v1,c,v2)] ++ getEdges v1 xs\r
  95 \r
  96 -- Bsp 5.2 d)\r
  97 \r
  98 am2al :: AMgraph -> ALgraph\r
  99 am2al (AMg am) = ALg (changeAL (transformAM2AL am 0))\r
 100 \r
 101 changeAL :: [(Vertex,[(Vertex,Cost)])] -> [(Vertex,[(Vertex,Cost)])]\r
 102 changeAL [] = []\r
 103 changeAL ((x,list):xs) | (list==[]) = changeAL xs\r
 104                        | otherwise = [(x,list)] ++ changeAL xs\r
 105 \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
 109 \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
 114 \r
 115 -- Bsp 5.2 e)\r
 116 \r
 117 am2el :: AMgraph -> ELgraph\r
 118 am2el (AMg am) = ELg (fromIntegral(length am)-1) (transformAM2EL am 0)\r
 119 \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
 123 \r
 124 -- Bsp 5.2 f)\r
 125 \r
 126 sortELEdges :: (Vertex,Cost,Vertex) -> (Vertex,Cost,Vertex) -> Ordering\r
 127 sortELEdges (a,_,_) (b,_,_) | a<b = LT\r
 128                             | otherwise = GT\r
 129 \r
 130 el2al :: ELgraph -> ALgraph\r
 131 el2al (ELg max el) = ALg(changeAL(transformEL2AL 0 (sortBy sortELEdges el) max))\r
 132 \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
 135                         | otherwise = []\r
 136 \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
 142 \r
 143 -- Bsp 5.2 g)\r
 144 \r
 145 el2am :: ELgraph -> AMgraph\r
 146 el2am el = al2am (el2al el)\r
 147 \r
 148 -- Bsp 5.3 a)\r
 149 \r
 150 isNeighbourOf :: ELgraph -> Vertex -> Vertex -> Bool\r
 151 isNeighbourOf el v1 v2 = elem v2 (allNeighboursOf el v1)\r
 152 \r
 153 -- Bsp 5.3 b)\r
 154 \r
 155 allNeighboursOf :: ELgraph -> Vertex -> [Vertex]\r
 156 allNeighboursOf el v = splitAL3 (el2al el) v\r
 157 \r
 158 splitAL3 :: ALgraph -> Vertex -> [Vertex]\r
 159 splitAL3 (ALg al) v = splitAL2 al v\r
 160 \r
 161 splitAL2 :: [(Vertex,[(Vertex,Cost)])] -> Vertex -> [Vertex]\r
 162 splitAL2 al v = getNeighbours al v\r
 163 \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
 168 \r
 169 list2neighbour :: [(Vertex,Cost)] -> [Vertex]\r
 170 list2neighbour [] = []\r
 171 list2neighbour ((v,c):xs) = [v] ++ list2neighbour xs\r
 172 \r
 173 -- Bsp 5.3 c)\r
 174 \r
 175 numberOfEdges :: AMgraph -> Integer\r
 176 numberOfEdges am = getEdgeCount (am2el am)\r
 177 \r
 178 getEdgeCount :: ELgraph -> Integer\r
 179 getEdgeCount (ELg max el) = fromIntegral (length el)\r
 180 \r
 181 -- Bsp 5.3 d)\r
 182 \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
 186 \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
 190 \r
 191 -- searchNeighbours [(Vertex,Cost)] -> Vertex -> Cost -> Integer -> \r
 192 -- searchNeighbours ((v,c):xs) vs c max = \r
 193 \r
 194 \r
 195 \r
 196 \r
 197 \r
 198 type MyGraph = [(Vertex,[(Vertex,Cost)])]\r
 199 castGraph :: ALgraph -> MyGraph\r
 200 castGraph (ALg xs) = xs\r
 201  \r
 202 exist :: [Vertex] -> Vertex -> Bool\r
 203 exist mypath node =  isNothing (find (==node) mypath) == False\r
 204  \r
 205 getedges :: MyGraph -> Vertex -> [(Vertex,Cost)]\r
 206 getedges g k\r
 207   | isNothing e   = []\r
 208   | otherwise     = snd ((maybeToList e)!!0)\r
 209  where e = find (\n -> (fst n) == k) g\r
 210 \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
 219   | otherwise                                 = []\r
 220  where\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
 225 \r
 226 path :: ALgraph -> Vertex -> Vertex -> Cost -> Bool\r
 227 path graph von zu max\r
 228   | (length mypath) == 0      = False\r
 229   | otherwise                 = True\r
 230  where\r
 231   mypath = (findPath g von zu [] 0 max 0) True\r
 232   g = castGraph graph\r
 233 \r
 234 \r
 235 \r