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/18maxflowext.pdf
Note that we can't use Dijkstra for shortestpaths because of the negativeweighted 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.