class
AssignmentSolver extends AnyRef
Instance Constructors
-
new
AssignmentSolver(weights: la.Tensor2)
Value Members
-
final
def
!=(arg0: AnyRef): Boolean
-
final
def
!=(arg0: Any): Boolean
-
final
def
##(): Int
-
final
def
==(arg0: AnyRef): Boolean
-
final
def
==(arg0: Any): Boolean
-
final
def
asInstanceOf[T0]: T0
-
def
clone(): AnyRef
-
final
def
eq(arg0: AnyRef): Boolean
-
def
equals(arg0: Any): Boolean
-
def
finalize(): Unit
-
final
def
getClass(): Class[_]
-
def
hashCode(): Int
-
final
def
isInstanceOf[T0]: Boolean
-
final
def
ne(arg0: AnyRef): Boolean
-
final
def
notify(): Unit
-
final
def
notifyAll(): Unit
-
def
shortestPath(currentParents: Array[Int]): Set[(Int, Int)]
-
def
solve(): Seq[(Int, Int)]
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
-
def
toString(): String
-
final
def
wait(): Unit
-
final
def
wait(arg0: Long, arg1: Int): Unit
-
final
def
wait(arg0: Long): Unit
-
A solver for weighted bipartite matching, also known as the assignment problem.
This does not use the Hungarian algorithm; instead it uses the augmenting paths algorithm which works by finding in sequence a best matching with one edge, a best matching with two edges, etc, until it find a best matching with maximal size. Then it goes back and returns the best overall matching out of those.
Transforming the best matching with n nodes into the best matching with n+1 nodes is done by finding the best augmenting path: define a new graph with a source connected with zero weight edges to the unmatched nodes on the "left" side of the matching, and likewise a target connected to the unmatched nodes on the right side. For the bipartite graph, have the edges in the matching have positive weight equal to their cost and going from right to left, while edges not in the matching have negative weights equal to their costs and go from left to right.
Then a shortest path from the source to target will necessarily add one edge to the matching for each edge it removes, and add one more edge than that.
To see a proof of this algorithm see the lecture notes in http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/18-maxflowext.pdf
Note that we can't use Dijkstra for shortest-paths because of the negative-weighted edges. We can't have negatively weighted cycles because the existence of such a cycle would imply that the current state is not a maximal matching with its size.
This is useful for implementing the CEAF evaluation metrics in coreference resolution, which assign scores between pairs of truth and returned entities and define the precision and recall of a clustering as a function of the best possible matching between truth and returned clusters.