Stay organized with collections Save and categorize content based on your preferences.

C++ Reference: class LinearSumAssignment

Note: This documentation is automatically generated.



Return type: CostValue

Arguments: ArcIndex arc

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


Return type: bool

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


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.


Return type: inline ArcIndex

Arguments: NodeIndex left_node

Returns the arc through which the given node is matched.


Return type: inline CostValue

Arguments: NodeIndex node

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


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.


Return type: inline NodeIndex

Arguments: NodeIndex left_node

Returns the node to which the given node is matched.


Return type: inline const GraphType&

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


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.


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.



Return type: NodeIndex

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


Return type: NodeIndex

Returns the total number of nodes in the given problem.


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.


Return type: void

Arguments: ArcIndex arc, CostValue cost

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


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.


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.


Return type: std::string