[thebeast] r721 committed - now testing projectiveness

[codesite...@google.com]

Revision: 721
Author: sebastian.riedel
Date: Thu Mar 18 09:34:31 2010
Log: now testing projectiveness
http://code.google.com/p/thebeast/source/detail?r=721

Modified:

/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Values.scala

/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala

/branches/thefuture-modules/thebeast-core/src/test/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraintSpecification.scala

=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Values.scala
Tue Mar 16 19:15:51 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/Values.scala
Thu Mar 18 09:34:31 2010
@@ -123,7 +123,7 @@

val signature = new FunctionValues(TupleValues2(domain,domain),Bools)

- def apply(pair:(T,T)): Boolean = false//domain.compare(pair._1,pair._2)
+ def apply(pair:(T,T)): Boolean = domain.compare(pair._1,pair._2)

def getSources(r: Option[Boolean]): Iterable[(T,T)] = null
}
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
Thu Mar 18 01:43:59 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
Thu Mar 18 09:34:31 2010
@@ -2,8 +2,7 @@

import org.riedelcastro.thebeast.env._
import doubles.{DoubleConstant, DoubleTerm}
-import collection.mutable.HashMap
-import collection.mutable.{HashSet, Stack}
+import collection.mutable.{HashSet, Stack, HashMap}

/**
* A SpanningTreeConstraint is a term that maps graphs to 1 if they are
@@ -74,22 +73,36 @@

}
}
+ //test projectiveness
val lessThan = EmptyEnv(this.order)

//sort vertices according to order
val sorted = v.toList.sort((x, y) => x == root || lessThan(x,
y)).toArray
val n = sorted.size
val vertex2index = Map() ++ (for (i <- 0 until n) yield sorted(i) -> i)
-
- //check projectiveness
- def projective(from:Int,to:Int) : Boolean = {
- //span of length 2 or smaller is always projective
- if (to - from == 2 || to - 2 < 0) return true
- val headOfRight = vertex2index(heads(sorted(to-2)))
- if (headOfRight == to - 1) return projective(from,to-1)
- return projective(from,headOfRight) && projective(headOfRight,to-1)
- }
- if (projective(0,n)) Some(1.0) else Some(0.0)
+ //mapping from vertex to children
+
+
+ def projective(from: Int, to: Int): Boolean = {
+ if (to - from <= 1) return true
+ var current = from + 1
+ while (current < to) {
+ val currentVertex = sorted(current)
+ val headVertex = heads(currentVertex)
+ val head = vertex2index(headVertex)
+ if (head < from || head > to) return false
+ if (head > current) {
+ if (!projective(current, head)) return false
+ current = head
+ } else {
+ current += 1
+ }
+ }
+ true
+ }
+
+
+ if (projective(0, n-1)) Some(1.0) else Some(0.0)
}

@@ -102,7 +115,7 @@
edges.variables ++ vertices.variables ++ root.variables ++
order.variables
}

- private def linkVariables: Set[FunAppVar[(V, V), Boolean]] = {
+ private def linkVariables: scala.collection.immutable.Set[FunAppVar[(V,
V), Boolean]] = {
val pred = edges.asInstanceOf[Predicate[(V, V)]]
val v = EmptyEnv(vertices).getSources(Some(true))
val r = EmptyEnv(root)
=======================================
---
/branches/thefuture-modules/thebeast-core/src/test/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraintSpecification.scala
Thu Mar 18 01:43:59 2010
+++
/branches/thefuture-modules/thebeast-core/src/test/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraintSpecification.scala
Thu Mar 18 09:34:31 2010
@@ -15,7 +15,10 @@
"return 1 if the the graph is a spanning tree" in {
val fixtures = new DependencyParsingFixtures
import fixtures._
- val sentence = createTheManIsFast
+ val sentence = createSentence(
+ List("Root", "The", "man", "is", "fast"),
+ List("Root", "DT", "NN", "VB", "AD"),
+ List((0, 3), (3, 2), (3, 4), (2, 1)))
val constraint = new SpanningTreeConstraint[Int](link, token, 0,
LessThan(Tokens))
sentence(constraint) must_== 1.0
}
@@ -23,9 +26,9 @@
val fixtures = new DependencyParsingFixtures
import fixtures._
val sentence = createSentence(
- List("root","the","man" ,"walks"),
- List("root","DT","NN", "VB"),
- List((0,3),(1,2),(2,1)))
+ List("root", "the", "man", "walks"),
+ List("root", "DT", "NN", "VB"),
+ List((0, 3), (1, 2), (2, 1)))
val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
sentence(constraint) must_== 0.0
}
@@ -33,9 +36,9 @@
val fixtures = new DependencyParsingFixtures
import fixtures._
val sentence = createSentence(
- List("root","the","man" ,"walks"),
- List("root","DT","NN", "VB"),
- List((0,3),(1,2),(3,2)))
+ List("root", "the", "man", "walks"),
+ List("root", "DT", "NN", "VB"),
+ List((0, 3), (1, 2), (3, 2)))
val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
sentence(constraint) must_== 0.0
}
@@ -43,9 +46,9 @@
val fixtures = new DependencyParsingFixtures
import fixtures._
val sentence = createSentence(
- List("root","the","man" ,"walks"),
- List("root","DT","NN", "VB"),
- List((0,3),(3,2)))
+ List("root", "the", "man", "walks"),
+ List("root", "DT", "NN", "VB"),
+ List((0, 3), (3, 2)))
val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
sentence(constraint) must_== 0.0
}
@@ -53,19 +56,18 @@
val fixtures = new DependencyParsingFixtures
import fixtures._
val sentence = createSentence(
- List("root","the","man" ,"walks"),
- List("root","DT","NN", "VB"),
- List((0,2),(2,3),(3,1)))
+ List("root", "the", "man", "walks"),
+ List("root", "DT", "NN", "VB"),
+ List((0, 2), (2, 3), (3, 1)))
val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
- true
- //sentence(constraint) must_== 0.0
+ sentence(constraint) must_== 0.0
}
"return only edge variables that could be part of a spanning tree if
root and vertices are grounded" in {
val fixtures = new DependencyParsingFixtures
import fixtures._
val sentence = createTheMan
val constraint = new SpanningTreeConstraint(link, token, 0,
LessThan(Tokens))
- val expected =
Set(FunAppVar(link,(0,1)),FunAppVar(link,(0,2)),FunAppVar(link,(1,2)),FunAppVar(link,(2,1)))
+ val expected = Set(FunAppVar(link, (0, 1)), FunAppVar(link, (0, 2)),
FunAppVar(link, (1, 2)), FunAppVar(link, (2, 1)))
val result = constraint.ground(sentence.mask(Set(link))).variables
result must_== expected
}