2

scala の相互再帰型と同様に、Scala で相互再帰型を作成しようとしています。

このタイプで定義されたグラフを作成しようとしています（コンパイルします）：

 case class Node(val id : Int, val edges : Set[Node])

しかし、このタイプで実際に何かを作成する方法がわかりません。ノード A をエッジ B と C で初期化するには、少なくとも B と C への遅延参照が必要ですが、同時に作成することはできません。それらのエッジセット。

この再帰型を実装することは可能ですか?

編集：

これは、明示的な隣接リストを自己参照リストに変換するために現在使用しているソリューションです。

def mapToGraph(edgeMap : Map[Int, mutable.Set[Int]]) : List[Node] = {
  lazy val nodeMap = edgeMap map  (kv => (kv._1, new Node(kv._1, futures.get(kv._1).get)))
  lazy val futures : Map[Int, Set[Node]] = edgeMap map (kv => {
    val edges = (kv._2 map (e => nodeMap.get(e).get)).toSet
    (kv._1, edges)
  })
  val eval = nodeMap.values.toList
  eval //to force from lazy to real - don't really like doing this
}

または代わりに、エッジリストから

//reads an edgeList into a graph
def readEdgelist(filename : String) : List[Node] = {
  lazy val nodes = new mutable.HashMap[Int, Node]()
  lazy val edges = new mutable.HashMap[Int, mutable.Buffer[Node]]()
  Source.fromFile(filename).getLines() filter (x => x != None) foreach {edgeStr =>
    val edge = edgeStr.split('\t')
    if (edge.size != 2) goodbye("Not a well-formed edge : " + edgeStr + " size: " + edge.size.toString)
    val src = edge(0).toInt
    val des = edge(1).toInt
    if (!(nodes.contains(src))) nodes.put(src, new Node(src, futures.get(src).get))
    if (!(nodes.contains(des))) nodes.put(des, new Node(des, futures.get(des).get))
    edges.put(src, edges.getOrElse(src, mutable.Buffer[Node]()) += nodes.get(des).get)
  }
  lazy val futures : Map[Int, Set[Node]] = nodes map {node => (node._1, edges.getOrElse(node._1, mutable.Buffer[Node]()).toSet)} toMap
  val eval = nodes.values.toList
  eval
}

みんなアドバイスありがとう！

4

2 に答える 2

3

下から上に向かって作業する必要があるようですね

val b = Node(1, Set.empty)
val c = Node(2, Set.empty)
val a = Node(3, Set(b, c))

お役に立てば幸い

于 2012-10-12T20:51:37.990 に答える
3

チキン＆エッグ...3つのオプションがあります：

  1. グラフを有向非巡回グラフ (DAG) に制限し、RKumsher の提案を使用します。

  2. 不変性を維持するには、ノード インスタンスをエッジ セットから分離する必要があります (2 つの異なるクラス: ノードの作成、次にエッジ セット/グラフの作成)。

  3. 緊密な相関を好む場合は、すべてのノードが作成された後に戻って設定できるように、エッジ セットにセッターを使用することを検討してください。

于 2012-10-12T21:09:48.393 に答える