2

Haskell でグラフを読み込む方法 (およびグラフを表す方法) を理解するのに非常に苦労しています。

ファイルからの入力は次のようになります

NODES 3
EDGE 1 2
EDGE 1 3
EDGE 2 3

以下を使用して、ファイルから入力の個々の行を取得する方法を見つけました。

loadFile :: String -> IO [[String]]
loadFile filename = do 
                contents <- readFile filename
                return $ map words $ lines contents

次のような出力が得られます。

loadFile "input.txt"
[["NODES","3"],["EDGE","1","2"],["EDGE","1","3"],["EDGE","2","3"]]

しかし、私が本当に理解する必要があるのは、このグラフ データをグラフとして表現する方法です。私はそれをエッジのリストとして設定することを考えていました:

type Edge = (Int,Int)
type Graph = [Edge]

しかし、その後、addNode、addEdge、getNodes、getEdges などの必要な関数の実装をどのように開始するかさえわかりません。

どんな助けでも正しい方向に私を向けることは素晴らしいでしょう! 注: これには、既に開発されたグラフ モジュールは使用できません。

したがって、tl;dr バージョンの場合:

  1. データを最良の方法で読み取っていますか?
  2. このデータを haskell でどのように表現すればよいですか?
  3. 上で概説したデータ構造を使用する場合、これらの関数の 1 つを実装するにはどうすればよいでしょうか。
4

1 に答える 1

7

ここでは、多くの興味深い懸念が進行中です。それらすべてを攻撃させてください。

  1. 行指向の言語では問題なくデータを読み込んでいます。後で、効率のために参照Data.ByteStringしてData.Text置き換えStringます。Parsec解析についても表示されます。ただし、それらは待つことができます。時間内にそれらを再訪してください。

  2. グラフ表現は問題ありません。隣接リストは、一般的で便利な表現です。

  3. さて、あなたが持っている本当のトリックはここにあります. addNodeとを見てみましょうaddEdge。それぞれがグラフを変更したいので、純粋な関数型言語で生成するのはやや難しい関数です...しかし、状態はありません。

状態なしで変更する最も重要な方法は、変更することです。あなたが探している機能の種類はこうです

addNode :: Node -> Graph -> Graph

ここで、返される は、もう 1 つのエッジがあることを除いてGraph、入力と同じです。Graphここで何か問題があることにすぐに注意してください。隣接リストは、孤立したノードがないと想定しています。グラフにノードを 1 つだけ追加することはできません。

解決策は 2 つあります。1 つ目は、ノードをグラフに「リンク」すること (これは実際addEdgeには偽装されています)、または 2 つ目は、孤立したノードを含めるようにグラフ表現を拡張することです。(2) しましょう。

data Graph = Graph [Edge] [Int] -- orphans

それでは、エッジの追加を実装しましょう。重複したエッジを持つことができると仮定すると、隣接リストにエッジを追加するのは簡単です。追加するだけです

addEdge0 :: Edge -> Graph -> Graph
addEdge0 e (Graph adj orph) = Graph (e:adj) orph

しかし、それだけでは十分ではありません。孤立したリストには、本当に孤立したノードのみを含める必要があります。フィルタリングします。

addEdge :: Edge -> Graph -> Graph
addEdge (n1,n2) (Graph adj orph) = 
  Graph ((n1,n2):adj) (filter (/=n1) . filter (/=n2) $ orph)

getEdgesすでにエッジのリストを保存しているので簡単です

getEdges :: Graph -> [Edge]
getEdges (Graph edges _) = edges

getNodes隣接リストから孤立リストにすべてのノードを追加するだけです。Data.List.nub一意のノードのみを取得するために使用できます。

getNodes :: Graph -> [Int]
getNotes (Graph adj orph) = nub (orph ++ adjNodes adj) where
  adjNodes [] = []
  adjNodes ((n1,n2):rest) = n1 : n2 : adjNodes rest

願わくば、これらが関数型言語でどのように考えるかを示してくれることを願っています。それらがどのように機能するかを確認するには、それらを少し掘り下げる必要がありますが、ここでは多数の興味深い概念を紹介しました。

ここでの次のステップには、Stateモナドを使用して命令型の状態変更を再取得し、これらのGraph変更機能を連鎖させることが含まれる場合があります。

于 2013-04-16T04:02:34.897 に答える