Не могу понять, как вводить и выводить код Беллманфорда, написанный на Haskell.

Я новичок в Хаскеле. Я скомпилировал код, и открывается основная оболочка. Я не знаю, как ввести края графика и получить результат. Любая помощь будет оценена по достоинству.

Имея граф и исходную вершину src в графе, найти кратчайшие пути от src ко всем вершинам данного графа. Граф может содержать ребра с отрицательным весом.

{-# 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

person walt3rwhite    schedule 28.05.2017    source источник
comment
Я так понимаю, «Беллманфорд» — это алгоритм Беллмана-Форда? Не полный ответ, потому что это звучит как домашнее задание, но: указывает ли задание формат ввода?   -  person Davislor    schedule 28.05.2017
comment
Вы хотели бы создать входной файл, содержащий данные, назовем его input.txt в том же каталоге, что и программа, запустить консоль и запустить вашу программу (если исполняемый файл называется bellmanford) как bellmanford < input.txt. (В Linux вы должны запустить программу в текущем каталоге как ./bellmanford.)   -  person Davislor    schedule 28.05.2017


Ответы (1)


Судя по всему, вам нужен файл с представлением графа. Хотя я не смог проверить это сам, я бы сказал, что входным данным нужен заголовок с количеством вершин графа, а затем тройка в каждой строке, которая описывает каждое ребро: исходная вершина, конечная вершина и вершина вес этого края.

Например, набор данных, описывающий граф с тремя вершинами, будет выглядеть примерно так:

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
...

(Обратите внимание, что комментарии, которые я только что написал, не могут быть проанализированы программой, они просто нужны для более ясного объяснения)

Кроме того, примите во внимание, что (вероятно) вы не можете использовать для этого ghci, поскольку в REPL содержимое потребляется с использованием hGetContents, и это, вероятно, испортит ввод. Лучший способ сделать это, как Дэвислор, записать входной график в текстовый файл (скажем, graph.txt), скомпилировать программу, используя ghc -o bellman-ford <your-file>.hs, а затем ввести текстовый файл в исполняемый файл, используя ./bellman-ford < graph.txt.

И опять же, как говорит Дэвислор, это выглядит как какое-то домашнее задание, так что попробуйте перепроверить, не требуется ли уже какой-то входной файл в задании или что-то в этом роде.

person Diego Vicente    schedule 28.05.2017