2

私がこのようなクラスを持っている場合：

class Person (var name:String, var surname:String, var sons: Set[Person])

私は、人が彼の息子と彼の息子の息子の間に自分自身を封じ込めることができないというコントロールを持ちたいです。これどうやってするの？

再帰検索を考えていました。ただし、サイクルを作成しないように注意する必要があります。ブール値をガードとして使用できますが、それ自体を含むアイテムを見つけるだけで検索が停止します。

どうすればこれを実装できますか？アイデアはありますか？どうもありがとうございます。

更新 ご協力ありがとうございます。良い答えですが、何よりも素晴らしいアイデアがありました。今、私は私の小さなプロジェクトでこのチェックをテストするために少し最後の助けが必要です。

私の実際の状況は次のとおりです。

trait ArchitecturalElement extends PropertyHolderElement with TypedElement{}

abstract class Component extends ConnectableElement with ArchitecturalElement {
  var subElements : Set[ArchitecturalElement]
  var interactionPoints : Set[InteractionPoint]
  //Here I put the control
  //A component cannot contain himself in his subElements and in subElements of it subelement
  def notHerOwnDescendant = {
  def notDescendant(ancestor: Component, current: Component, checked: Set[ArchitecturalElement]): Boolean =
  !current.subElements.contains(ancestor) && current.subElements.forall(
        p => checked.contains(p) || notDescendant(ancestor, p, checked + p))

  notDescendant(this, this, Set())
  }

 }//Component

abstract class InteractionPoint extends ConnectableElement{}

class SAInterface(  var name : String,
        var description : String = "empty",
        var direction : SAInterfaceDirection = null
        )extends InteractionPoint with ArchitecturalElement

class SAComponent ( var name :String,
        var description : String = "empty",
        var subElements : Set[ArchitecturalElement] = Set(),
        var interactionPoints : Set[InteractionPoint] = Set()
        ) extends Component

しかし、私には互換性のないタイプがあります：

型の不一致; 見つかった：a0Dominio.ArchitecturalElement必須：a0Dominio.SAComponent

p => checked.contains(p) || notDescendant(ancestor, p, checked + p)
                                                //  ^  here

セット[ArchitecturalElement]から、セット[コンポーネント]を派生させますか？一方、ComponentはArchitecturalElementから継承します。

4

2 に答える 2

2

次のメソッドは、現在の人のすべての子孫を生成しますが、サイクルで失われることはありません。

def descendants(stop: Set[Person] = Set()): Set[Person] = 
  if(stop contains this) Set() 
  else                   this.sons.flatMap(descendants(_,stop + this)) + this

あなたはあなたの状態をチェックするためにそれを使うことができます。任意のサイクルを検出するために、の最初のブランチに到達すると、肯定的な結果が得られますif。

別の方法は、コンストラクター/セッターでグラフを非循環にすることです。これにより、ストップセットなしで検索を使用できます。これは、既存のすべてのインスタンスがサイクルフリーであることが保証されており、条件を少し簡単で高速なアプローチでテストできるためです。

于 2012-11-26T11:55:17.590 に答える
1

私があなたを正しく理解しているなら、あなたはこのようなものが欲しいです：

class Person(...) {
  ...

  def notHerOwnDescendant = 
    !sons.contains(this) && sons.forall(!_.sons.contains(this))

  ...
}

または、最後まで行きたい場合は、次のようにします。

class Person(...) {
  ...

  def notDescendant(person: Person) = 
    !sons.contains(person) && sons.forall(_.notDescendant(person))

  def notHerOwnDescendant = 
    notDescendant(this)

  ...
}

免責事項：IDEでこのコードをテストできなかったため、コンパイルされて正しいという保証はありません。それにもかかわらず、私はそれが少なくとも思考の糧として役立つことを願っています:-)

アップデート

これは、@giladが言及した「グラフ彩色」ソリューションを使用してサイクルを処理する更新およびテスト済みのバージョンです。

class Person (val name:String, val surname:String, var sons: Set[Person]) {
  def notHerOwnDescendant = {
    def notDescendant(ancestor: Person, current: Person, checked: Set[Person]): Boolean =
      !current.sons.contains(ancestor)
          && current.sons.forall(
            p => checked.contains(p) || notDescendant(ancestor, p, checked + p))

    notDescendant(this, this, Set())
  }
}

いくつかのテストコード：

val abel = new Person("", "Abel", Set())
val cain = new Person("", "Cain", Set())
val adam = new Person("", "Adam", Set(abel, cain))

println("Adam is not his own descendant: " + adam.notHerOwnDescendant)
cain.sons += cain
println("Added Cain to his sons' set")
println("Adam is not his own descendant: " + adam.notHerOwnDescendant)
abel.sons += adam
println("Added Adam to his grandsons' set")
println("Adam is not his own descendant: " + adam.notHerOwnDescendant)

そして出力：

Adam is not his own descendant: true
Added Cain to his sons' set
Adam is not his own descendant: true
Added Adam to his grandsons' set
Adam is not his own descendant: false

より簡単な解決策？

valちなみに、sの代わりにプロパティに固執するだけで、人が自分の子孫になるのを防ぐことができると思いますvar。のセットsonsが不変である場合、親を作成する前に準備が必要であるため、グラフにサイクルを作成sonsできません。また、既存の子孫の息子のセットに親を追加することはできません。上記のテストコードをコンパイルするために、そのままにsonsしておく必要があることに注意してください。var

少なくともこれは私がそれを見る方法です-しかし、私がまだあまり経験していない遅延評価などを使用して、これを打ち負かすためのいくつかのトリックがあるかもしれません。ですから、私が間違っていたら誰かが私を訂正してください。

アップデート2

型の不一致; 見つかった：a0Dominio.ArchitecturalElement必須：a0Dominio.SAComponent

ここにタイプミスがあるかもしれないと思います：あなたのメソッドの宣言に基づいて、そうすSAComponentべきでComponentはありませんか？

とにかく、問題はあなたがsubElementsとして宣言することですSet[ArchitecturalElement]、それでその要素は明らかにタイプArchitecturalElementであり、それはそうではありませんComponent（継承関係はその逆です）。したがって、に変更subElementsするか、関数パラメータをとしてSet[Component]宣言します。ancestorcurrentArchitecturalElement

アップデート3

Personサイクルの一部である子孫グラフ内のすべての人を見つけるための新しいメンバーメソッド：

def descendantsWithCycle = {
  def findCycle(current: Person, checked: Set[Person]): Set[Person] =
    if (checked contains current) Set(current)
    else {
      val newChecked = checked + current
      current.sons.flatMap(p => findCycle(p, newChecked))
    }

  findCycle(this, Set())
}
于 2012-11-26T09:26:15.830 に答える