scala - Scala: フィールド内のサイクルを見つける (グラフ)

Question

このようなクラスがある場合:

class Component (val name, val description, var subElements : Set[Component])

コンポーネントに (ブール関数を使用して) 内部にサイクルが含まれているかどうか、およびこのサイクルを開始したユーザーをテストするにはどうすればよいですか。var の代わりに val を使用するとサイクルが回避されることはよくわかっていますが、val を使用することはできません。

Answer 1

Componentサイクルを開始するグラフ内のすべての要素を返すのメンバー。サイクルがない場合は空のセットを返します。

def descendantsWithCycle = {
  def findCycle(current: Component, checked: Set[Component]): Set[Component] =
    if (checked contains current) Set(current)
    else {
      val newChecked = checked + current
      current.subElements.flatMap(findCycle(_, newChecked))
    }

  findCycle(this, Set())
}

Answer 2

var が必要ない場合は、使用しないでください。val または var と同じです。

class Component (val name : String, val description : String,  val subElements : Set[Component]){
    def hasCyle(val seen) : Boolean = (seen contains this ||
                                       subElements.exists(item => item.hasCycle(seen + this)))
    def isCyclic = hasCycle(Set())
  }
}

表示されたリストに現在のアイテムが含まれている場合、または表示されたセットに現在のアイテムに加えてサブ要素のいずれかが含まれている場合は、サイクルがあるため、hasCycle を読み取ることができます。