Aufgabe5_jj.hs

   1 type Cost = Integer
   2 type Vertex = Integer
   3 type MaxVertexNo = Integer
   4 type Edge = (Vertex,Cost,Vertex)
   5 type Row = [Integer]
   6
   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)
  10
  11 type Inp = (MaxVertexNo,[(Vertex,Vertex,Cost)])
  12
  13
  14 --Aufg 1
  15 isValid :: Inp -> Bool
  16 isValid (mvert,list) = (and( [ (checkValidEl (list!!index) mvert) | index <- [0..((min (fromEnum mvert) (length list))-1)] ] )) && (ckeckValidLinks list)
  17
  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
  22
  23 ckeckValidLinks :: [(Vertex,Vertex,Cost)] -> Bool
  24 ckeckValidLinks [] = True
  25 ckeckValidLinks xs = ((length xs) == (length (undup xs)))
  26
  27 undup :: [(Vertex,Vertex,Cost)] -> [(Vertex,Vertex,Cost)]
  28 undup [] = []
  29 undup ((f,t,c):xs) = (f,t,c) : undup (filter (\(x,y,z) -> not ((f == x) && (t == y))) xs)
  30
  31
  32
  33 --Aufg2
  34 inp2el :: Inp -> ELgraph
  35 inp2el (vnum, xs) = ELg vnum [ (inp2elConv x) | x <- xs]
  36
  37 inp2elConv :: (Vertex,Vertex,Cost) -> (Vertex,Cost,Vertex)
  38 inp2elConv (f,t,c) = (f,c,t)
  39
  40
  41
  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]])
  44
  45 el2alGet :: [Edge] -> Integer -> (Vertex,[(Vertex,Cost)])
  46 el2alGet e i = (i, concat([ (el2alRet el i) | el <- e]))
  47
  48 el2alRet :: Edge -> Integer -> [(Vertex,Cost)]
  49 el2alRet (f,c,t) i | (f == i) = [(t,c)]
  50 el2alRet _ _ = []
  51
  52
  53
  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)]]
  56
  57 al2amEl :: [(Vertex,[(Vertex,Cost)])] -> Integer -> Integer -> Integer
  58 al2amEl xs i j | ((toInteger (length xs)) > i) = al2amRow (xs!!(fromEnum i)) j
  59
  60 al2amRow :: (Vertex,[(Vertex,Cost)]) -> Integer -> Integer
  61 al2amRow (v,xs) j = al2amVal xs j
  62
  63 al2amVal :: [(Vertex,Cost)] -> Integer -> Integer
  64 al2amVal [] i = 0
  65 al2amVal ((v,c):xs) i | (v /= i) = al2amVal xs i
  66 al2amVal ((v,c):xs) i | (v == i) = c
  67
  68
  69
  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)]])
  72
  73 am2elC :: Cost -> Vertex -> Vertex -> [Edge]
  74 am2elC c f t | (c == 0) = []
  75 am2elC c f t = [(f,c,t)]
  76
  77
  78 -- abgeleitet
  79 el2am :: ELgraph -> AMgraph
  80 el2am eg = al2am (el2al eg)
  81
  82 al2el :: ALgraph -> ELgraph
  83 al2el ag = am2el (al2am ag)
  84
  85 am2al :: AMgraph -> ALgraph
  86 am2al am = el2al (am2el am)
  87
  88
  89
  90
  91 -- Aufg 3
  92 isNeighbourOf :: ELgraph -> Vertex -> Vertex -> Bool
  93 isNeighbourOf _ _ _ = True
  94
  95 isOnCycle :: ALgraph -> Vertex -> Cost -> Bool
  96 isOnCycle _ _ _ = False
  97
  98