I am new to Haskell. I compiled the code and the main shell opens. I don't know how to input the edges of the graph and get the output. Any help would be appreciated.
Given a graph and a source vertex src in graph, find shortest paths from src to all vertices in the given graph. The graph may contain negative weight edges.
{-# LANGUAGE BangPatterns #-}
module Main where
import Control.DeepSeq
import Data.Functor
import Data.Int
import Data.Vector.Unboxed ((//))
import qualified Data.Vector.Unboxed as V
--import Debug.Trace
type Vertex = Int
type Dist = Int32
type Edge = (Vertex, Vertex, Dist)
type EdgeVec = V.Vector Edge
type CostVec = V.Vector Dist
readEdge :: String -> Edge
readEdge s = let [v1, v2, w] = words s
in (read v1, read v2, read w)
bfStep :: EdgeVec -> CostVec -> CostVec
bfStep edges !prev = V.unsafeAccumulate min prev $ V.map mincost edges
where
mincost :: Edge -> (Int, Int32)
mincost (s, h, c) = (h, cost s c)
cost w c = let precost = prev `V.unsafeIndex` w
in if precost == maxBound then maxBound else precost + c
mkEdgeVec :: Int -> [String] -> EdgeVec
mkEdgeVec nvert inp = V.unfoldr step (nvert, inp)
where
step (n, s:xs) = Just (readEdge s, (n, xs))
step (0, []) = Nothing
step (!n, []) = Just ((0, n, 0), (n - 1, []))
main :: IO()
main = do
header:body <- lines <$> getContents
let nvert = read $ head $ words header
let edgelist = mkEdgeVec nvert body
let bfbase = V.replicate (nvert + 1) maxBound // [(0, 0)]
print $ edgelist `deepseq` "running"
let bfout = iterate (bfStep edgelist) bfbase !! nvert
let bfcheck = bfStep edgelist bfout
let hasCycle = V.any id $ V.zipWith (/=) bfout bfcheck
putStrLn $ if hasCycle then "Cycle" else show $ V.minimum bfout
By the looks of it, you need a file with the representation of a graph. Although I haven't been able to test it myself, I would say that the input needs a header with the number of vertices of the graph and then a triple in each line that describes each edge: the origin vertex, the end vertex and the weight of that edge.
For example, a data set that describes an 3 vertices graph would be something like:
3 // The graph has 3 vertices
1 2 0 // The edge from vertex 1 to vertex 2 has a weight of 0
2 1 5 // The edges are directed, so 2 to 1 has a weight of 5
1 3 1
2 3 0
...
(Notice that the comments I just wrote cannot be parsed by the program, they are just to be more clear in the explanation)
Also, take into account that (probably) you can't use ghci
for this, since in the REPL the contents are consumed using hGetContents
and that's probably going to mess with the input. The best way to do it is, as Davislor, by writing your graph input in a text file (let's say, graph.txt), compiling the program using ghc -o bellman-ford <your-file>.hs
and then input the text file to the executable using ./bellman-ford < graph.txt
And again, as Davislor says, this looks like some kind of homework, so try to double-check if there is some kind of input file already required in the assignment or something like that.