無法計算如何在Haskell編寫的Bellmanford代碼中輸入和輸出

我是Haskell的新手。我編譯了代碼並打開了主shell。我不知道如何輸入圖形的邊緣並獲得輸出。任何幫助，將不勝感激。無法計算如何在Haskell編寫的Bellmanford代碼中輸入和輸出

給出圖中的圖和源頂點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

來源

2017-05-28 walt3rwhite

我認爲「Bellmanford」是Bellman-Ford算法？不是一個完整的答案，因爲這聽起來像是作業，但是：作業是否指定了輸入格式？ – Davislor

你會想創建一個包含數據的輸入文件，我們在程序所在的同一個目錄下調用它'input.txt'，啓動一個控制檯，然後運行你的程序（如果可執行文件名爲'bellmanford'）爲'bellmanford Davislor

通過它的外觀，你需要一個帶有圖形表示的文件。雖然我沒有能夠自己測試它，但我會說輸入需要一個包含圖的頂點數的頭，然後在描述每條邊的每一行中都有一個三元組：起點頂點，結束頂點和該邊緣的重量。

例如，描述了3個頂點圖形會像一個數據集：

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消耗，這可能會混淆輸入。作爲Davislor，最好的方法是將你的圖形輸入寫入文本文件（比如說graph.txt），使用ghc -o bellman-ford <your-file>.hs編譯程序，然後使用./bellman-ford < graph.txt輸入文本文件

正如戴維斯勒所說，這看起來像某種家庭作業，所以試着仔細檢查一下，在作業中是否有某種類型的輸入文件需要或者類似的東西。

來源

2017-05-28 19:00:14

無法計算如何在Haskell編寫的Bellmanford代碼中輸入和輸出

回答

相關問題