C++ Reference: class LinearSumAssignment

This documentation is automatically generated.

Method
ArcAnnotationCycleHandler

ArcCost

Return type: CostValue

Arguments: ArcIndex arc

Returns the original arc cost for use by a client that's iterating over the optimum assignment.

ComputeAssignment

Return type: bool

Computes the optimum assignment. Returns true on success. Return value of false implies the given problem is infeasible.

FinalizeSetup

Return type: bool

Completes initialization after the problem is fully specified. Returns true if we successfully prove that arithmetic calculations are guaranteed not to overflow. ComputeAssignment() calls this method itself, so only clients that care about obtaining a warning about the possibility of arithmetic precision problems need to call this method explicitly. Separate from ComputeAssignment() for white-box testing and for clients that need to react to the possibility that arithmetic overflow is not ruled out. FinalizeSetup() is idempotent.

GetAssignmentArc

Return type: inline ArcIndex

Arguments: NodeIndex left_node

Returns the arc through which the given node is matched.

GetAssignmentCost

Return type: inline CostValue

Arguments: NodeIndex node

Returns the cost of the assignment arc incident to the given node.

GetCost

Return type: CostValue

Returns the cost of the minimum-cost perfect matching. Precondition: success_ == true, signifying that we computed the optimum assignment for a feasible problem.

GetMate

Return type: inline NodeIndex

Arguments: NodeIndex left_node

Returns the node to which the given node is matched.

Graph

Return type: inline const GraphType&

Allows tests, iterators, etc., to inspect our underlying graph.

LinearSumAssignment

Arguments: const GraphType& graph, NodeIndex num_left_nodes

Constructor for the case in which we will build the graph incrementally as we discover arc costs, as might be done with any of the dynamic graph representations such as StarGraph or ForwardStarGraph.

LinearSumAssignment

Arguments: NodeIndex num_left_nodes, ArcIndex num_arcs

Constructor for the case in which the underlying graph cannot be built until after all the arc costs are known, as is the case with ForwardStarStaticGraph. In this case, the graph is passed to us later via the SetGraph() method, below.

~LinearSumAssignment

NumLeftNodes

Return type: NodeIndex

Returns the number of nodes on the left side of the given problem.

NumNodes

Return type: NodeIndex

Returns the total number of nodes in the given problem.

OptimizeGraphLayout

Return type: void

Arguments: GraphType* graph

Optimizes the layout of the graph for the access pattern our implementation will use. REQUIRES for LinearSumAssignment template instantiation if a call to the OptimizeGraphLayout() method is compiled: GraphType is a dynamic graph, i.e., one that implements the GroupForwardArcsByFunctor() member template method. If analogous optimization is needed for LinearSumAssignment instances based on static graphs, the graph layout should be constructed such that each node's outgoing arcs are sorted by head node index before the LinearSumAssignment::SetGraph() method is called.

SetArcCost

Return type: void

Arguments: ArcIndex arc, CostValue cost

Sets the cost of an arc already present in the given graph.

SetCostScalingDivisor

Return type: void

Arguments: CostValue factor

Sets the cost-scaling divisor, i.e., the amount by which we divide the scaling parameter on each iteration.

SetGraph

Return type: void

Arguments: const GraphType* graph

Sets the graph used by the LinearSumAssignment instance, for use when the graph layout can be determined only after arc costs are set. This happens, for example, when we use a ForwardStarStaticGraph.

StatsString

Return type: std::string