6

無向グラフを作成する必要があります。あまり派手なことをする必要はありませんが、理想的には次のように機能します。

structure UDG = UndirectedGraph
val g = UDG.empty
val g = UDG.addEdges(g, n1, [n2, n4, n7]) (* n1 is connected to n2, n4, and n7 *)
val g = UDG.addEdge(g, n2, n3)
UDG.connected(g, n2) (* returns [n1, n3] *)

これらの関係をモデル化するための SML/NJ の適切なデータ構造はありますか? 私は自分で巻くべきですか？

アップデート

先に進んで自分でロールしようとしましたが、テストしようとすると型の不一致エラーが発生します。私の SML 構造とファンクターの経験はかなり基本的なものなので、明らかに間違ったことをしていると思います。これを機能させるにはどうすればよいですか？また、これを作るのを手伝ってもらえます'a graphか? 意味的には、それはより理にかなっているようです。

コード

signature ORD_NODE =
sig
  type node
  val compare : node * node -> order
  val format : node -> string
end

signature GRAPH =
sig
  structure Node : ORD_NODE
  type graph
  val empty : graph

  (* val addEdge : graph * Node.node * Node.node -> graph
  *  addEdge (g, x, y) => g with an edge added from x to y. *)
  val addEdge : graph * Node.node * Node.node -> graph

  val format : graph -> string
end

functor UndirectedGraphFn (Node : ORD_NODE) :> GRAPH =
struct
  structure Node = Node
  structure Key = struct
    type ord_key = Node.node
    val compare = Node.compare
  end
  structure Map = BinaryMapFn(Key)

  type graph = Node.node list Map.map (* Adjacency list *)
  val empty = Map.empty

  fun addEdge (g, x, y) = (* snip *)   
  fun format g = (* snip *)
end

structure UDG = UndirectedGraphFn(struct
  type node = int
  val compare = Int.compare
  val format = Int.toString
end)

エラー

私がする時

構造体 UDG = UndirectedGraphFn(構造体
  タイプ ノード = int
  val 比較 = Int.compare
  val 形式 = Int.toString
終わり）

UDG.addEdge (UDG.empty,1,2)

タイプの不一致が発生します：

エラー: 演算子とオペランドが一致しません [リテラル]
  オペレーター ドメイン: UDG.graph * ?.UDG.node * ?.UDG.node
  オペランド: UDG.graph * int * int
  式で：
    UDG.addEdge (UDG.empty,1,2)
4

4 に答える 4

4

グラフのさまざまな操作に適した長所と短所が異なるいくつかの可能性があります。 この素敵なイントロは、隣接リストと隣接行列の使用に関する背景と例を示しています。

それらを方向のない方法で使用すると、トレードオフ (スペースと速度) が伴います。このコースの資料では、隣接リストのスタイルについて詳しく説明し、無向の使用法で使用できる変更についていくつかの考えを提供します。

于 2009-09-08T23:17:26.767 に答える
1

非常に簡単なものは、ソース ノードとしてのキーと接続ノードのリストとしての値を持つハッシュテーブルです。次に、1 つは (src, tgt) として、もう 1 つは (tgt, src) として、2 つのハッシュテーブル挿入を行う add 関数を作成します。

ocaml で:

let add n1 n2 =
  let aux n1 n2 =
    match Hashtbl.find_option tbl n1 with
    | None -> Hashtbl.add tbl n1 [n2]
    | Some nodes -> Hashtbl.replace tbl n1 (n2::nodes)
  in
  let _ = aux n1 n2 in
  aux n2 n1

これは有向グラフになります。挿入時に両方向を追加するだけです。ハッシュテーブル ルックアップ関数は、関数としてconnected機能します。

(実際、Ocaml のハッシュテーブルは 1 つのキーに対して複数の値を提供するため、Hashtbl.find_all関数を使用してリストを保存するだけで済みます。しかし、これは SML に変換するのが最も簡単です。)

于 2009-09-08T23:26:14.083 に答える