Skeleton file for the graph coloring assignment

DisOpt_ColoringSkeleton.hs

module Main where

import Data.List (intercalate)
import Control.Applicative((<$>))
import Control.Monad(forM)
import System.Environment(getArgs)
import System.IO (withFile, hGetLine, IOMode(ReadMode))

newtype Edge     = Edge (Int, Int)
                   deriving Show

data    Problem  = Problem
                   { nodeCount  :: Int
                   , edgeCount  :: Int
                   , edges      :: [Edge] 
                   } deriving Show
data    Solution = Solution
                   { isOptimal  :: Bool
                   , usedColors :: Int
                   , colorMap   :: [Int]
                   }

solve :: Problem -> Solution
solve = trivialSolution

trivialSolution :: Problem -> Solution
trivialSolution problem = Solution False nrColors colors
   where nrColors = nodeCount problem
         colors   = take nrColors [0..]


instance Show Solution where
   show sol =
      show (usedColors sol) ++ " " ++ optFlag ++ newLine ++
      colors
      where newLine = "\n"
            optFlag = if isOptimal sol then "1" else "0"
            colors  = intercalate " " . map show . colorMap $ sol 

readProblem :: FilePath -> IO Problem
readProblem file = do
   withFile file ReadMode (\h -> do
      [nrNodes, nrEdges] <- map read . words <$> hGetLine h
      eds <- forM [1..nrEdges] (const $ readEdge <$> hGetLine h)
      return $ Problem nrNodes nrEdges eds)
   where readEdge line = let [fromN, toN] = map read . words $ line in Edge (fromN, toN)

main :: IO ()
main = do
   args <- getArgs
   if length args /= 1 
   then putStrLn "Usage: coloring [inputFile]" 
   else do
      problem <- readProblem (args !! 0)
      let solution = solve problem
      putStrLn . show $ solution