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

从一个 Set [ArchitecturalElement]，我派生一个 Set [Component]？而 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属性而不是vars 来阻止一个人成为他自己的后代。如果集合sons是不可变的，则无法在图中创建循环，因为您需要sons在创建父级之前做好准备，并且无法将父级添加到任何现有后代的儿子集合中。请注意，我必须保留sonsavar才能编译上述测试代码。

至少我是这么看的——但是可能有一些技巧可以解决这个问题，例如使用我还不太熟悉的惰性评估。所以如果我错了，请有人纠正我。

更新 2

类型不匹配; 找到：a0Dominio.ArchitecturalElement需要：a0Dominio.SAComponent

我认为这里可能有一个错字：根据您的方法的声明，SAComponent应该Component不是吗？

无论如何，问题在于您声明subElements为 a Set[ArchitecturalElement]，因此它的元素显然是 type ArchitecturalElement，而不是 a Component（继承关系是相反的）。因此，要么更改为subElementsa Set[Component]，要么将函数参数声明ancestor为。currentArchitecturalElement

更新 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 回答