This class does not take ownership of its underlying graph. More...

#include <linear_assignment.h>

Public Types
typedef GraphType::NodeIndex	NodeIndex

typedef GraphType::ArcIndex	ArcIndex

typedef CostValue	CostValueT

Public Member Functions
	LinearSumAssignment (const GraphType &graph, NodeIndex num_left_nodes)

	LinearSumAssignment (NodeIndex num_left_nodes, ArcIndex num_arcs)

	LinearSumAssignment (const LinearSumAssignment &)=delete
	This type is neither copyable nor movable.

LinearSumAssignment &	operator= (const LinearSumAssignment &)=delete

	~LinearSumAssignment ()

void	SetGraph (const GraphType *graph)

void	SetCostScalingDivisor (CostValue factor)

operations_research::PermutationCycleHandler< typename GraphType::ArcIndex > *	ArcAnnotationCycleHandler ()
	Passes ownership of the cycle handler to the caller.

const GraphType &	Graph () const
	Allows tests, iterators, etc., to inspect our underlying graph.

NodeIndex	Head (ArcIndex arc) const

CostValue	ArcCost (ArcIndex arc) const

void	SetArcCost (ArcIndex arc, CostValue cost)
	Sets the cost of an arc already present in the given graph.

bool	FinalizeSetup ()

bool	ComputeAssignment ()

CostValue	GetCost () const

NodeIndex	NumNodes () const
	Returns the total number of nodes in the given problem.

NodeIndex	NumLeftNodes () const

ArcIndex	GetAssignmentArc (NodeIndex left_node) const
	Returns the arc through which the given node is matched.

CostValue	GetAssignmentCost (NodeIndex node) const

NodeIndex	GetMate (NodeIndex left_node) const
	Returns the node to which the given node is matched.

std::string	StatsString () const

::util::IntegerRange< NodeIndex >	BipartiteLeftNodes () const
	Returns the range of valid left node indices.

bool	EpsilonOptimal () const
	Only for debugging.

Detailed Description

template<typename GraphType, typename CostValue = int64_t>
class operations_research::LinearSumAssignment< GraphType, CostValue >

This class does not take ownership of its underlying graph.

Definition at line 226 of file linear_assignment.h.

Member Typedef Documentation

◆ ArcIndex

template<typename GraphType, typename CostValue = int64_t>

typedef GraphType::ArcIndex operations_research::LinearSumAssignment< GraphType, CostValue >::ArcIndex

Definition at line 229 of file linear_assignment.h.

◆ CostValueT

template<typename GraphType, typename CostValue = int64_t>

typedef CostValue operations_research::LinearSumAssignment< GraphType, CostValue >::CostValueT

Definition at line 230 of file linear_assignment.h.

◆ NodeIndex

template<typename GraphType, typename CostValue = int64_t>

typedef GraphType::NodeIndex operations_research::LinearSumAssignment< GraphType, CostValue >::NodeIndex

Definition at line 228 of file linear_assignment.h.

Constructor & Destructor Documentation

◆ LinearSumAssignment() [1/3]

template<typename GraphType, typename CostValue>

operations_research::LinearSumAssignment< GraphType, CostValue >::LinearSumAssignment	(	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 ReverseArcListGraph.

Implementation of out-of-line LinearSumAssignment template member functions.

Definition at line 936 of file linear_assignment.h.

◆ LinearSumAssignment() [2/3]

template<typename GraphType, typename CostValue>

operations_research::LinearSumAssignment< GraphType, CostValue >::LinearSumAssignment	(	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 StaticGraph. In this case, the graph is passed to us later via the SetGraph() method, below.

Definition at line 959 of file linear_assignment.h.

◆ LinearSumAssignment() [3/3]

template<typename GraphType, typename CostValue = int64_t>

operations_research::LinearSumAssignment< GraphType, CostValue >::LinearSumAssignment ( const LinearSumAssignment< GraphType, CostValue > & )

delete

This type is neither copyable nor movable.

◆ ~LinearSumAssignment()

template<typename GraphType, typename CostValue = int64_t>

operations_research::LinearSumAssignment< GraphType, CostValue >::~LinearSumAssignment ( )

inline

Definition at line 247 of file linear_assignment.h.

Member Function Documentation

◆ ArcAnnotationCycleHandler()

template<typename GraphType, typename CostValue>

PermutationCycleHandler< typename GraphType::ArcIndex > * operations_research::LinearSumAssignment< GraphType, CostValue >::ArcAnnotationCycleHandler ( )

Passes ownership of the cycle handler to the caller.

Returns a permutation cycle handler that can be passed to the TransformToForwardStaticGraph method so that arc costs get permuted along with arcs themselves.

Passes ownership of the cycle handler to the caller.

Definition at line 1058 of file linear_assignment.h.

◆ ArcCost()

template<typename GraphType, typename CostValue = int64_t>

CostValue operations_research::LinearSumAssignment< GraphType, CostValue >::ArcCost ( ArcIndex arc ) const

inline

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

Definition at line 281 of file linear_assignment.h.

◆ BipartiteLeftNodes()

template<typename GraphType, typename CostValue = int64_t>

::util::IntegerRange< NodeIndex > operations_research::LinearSumAssignment< GraphType, CostValue >::BipartiteLeftNodes ( ) const

inline

Returns the range of valid left node indices.

Definition at line 350 of file linear_assignment.h.

◆ ComputeAssignment()

template<typename GraphType, typename CostValue>

bool operations_research::LinearSumAssignment< GraphType, CostValue >::ComputeAssignment ( )

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

Note: FinalizeSetup() might have been called already by white-box test code or by a client that wants to react to the possibility of overflow before solving the given problem, but FinalizeSetup() is idempotent and reasonably fast, so we call it unconditionally here.

Definition at line 1405 of file linear_assignment.h.

◆ EpsilonOptimal()

template<typename GraphType, typename CostValue>

bool operations_research::LinearSumAssignment< GraphType, CostValue >::EpsilonOptimal ( ) const

Only for debugging.

Returns true if and only if the current pseudoflow is epsilon-optimal. To be used in a DCHECK.

Visible for testing.

Get the implicit price of left_node and make sure the reduced costs of left_node's incident arcs are in bounds.

Note the asymmetric definition of epsilon-optimality that we use because it means we can saturate all admissible arcs in the beginning of Refine() just by unmatching all matched nodes.

The reverse arc is residual. Epsilon-optimality requires that the reduced cost of the forward arc be at most epsilon_.

The forward arc is residual. Epsilon-optimality requires that the reduced cost of the forward arc be at least zero.

Definition at line 1312 of file linear_assignment.h.

◆ FinalizeSetup()

template<typename GraphType, typename CostValue>

bool operations_research::LinearSumAssignment< GraphType, CostValue >::FinalizeSetup ( )

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.

epsilon_ must be greater than kMinEpsilon so that in the case where the largest arc cost is zero, we still do a Refine() iteration.

Initialize left-side node-indexed arrays and check incidence precondition.

Initialize right-side node-indexed arrays. Example: prices are stored only for right-side nodes.

Definition at line 1345 of file linear_assignment.h.

◆ GetAssignmentArc()

template<typename GraphType, typename CostValue = int64_t>

ArcIndex operations_research::LinearSumAssignment< GraphType, CostValue >::GetAssignmentArc ( NodeIndex left_node ) const

inline

Returns the arc through which the given node is matched.

Definition at line 328 of file linear_assignment.h.

◆ GetAssignmentCost()

template<typename GraphType, typename CostValue = int64_t>

CostValue operations_research::LinearSumAssignment< GraphType, CostValue >::GetAssignmentCost ( NodeIndex node ) const

inline

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

Definition at line 335 of file linear_assignment.h.

◆ GetCost()

template<typename GraphType, typename CostValue>

CostValue operations_research::LinearSumAssignment< GraphType, CostValue >::GetCost ( ) const

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

It is illegal to call this method unless we successfully computed an optimum assignment.

Definition at line 1430 of file linear_assignment.h.

◆ GetMate()

template<typename GraphType, typename CostValue = int64_t>

NodeIndex operations_research::LinearSumAssignment< GraphType, CostValue >::GetMate ( NodeIndex left_node ) const

inline

Returns the node to which the given node is matched.

Definition at line 340 of file linear_assignment.h.

◆ Graph()

template<typename GraphType, typename CostValue = int64_t>

const GraphType & operations_research::LinearSumAssignment< GraphType, CostValue >::Graph ( ) const

inline

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

Definition at line 271 of file linear_assignment.h.

◆ Head()

template<typename GraphType, typename CostValue = int64_t>

NodeIndex operations_research::LinearSumAssignment< GraphType, CostValue >::Head ( ArcIndex arc ) const

inline

These handy member functions make the code more compact, and we expose them to clients so that client code that doesn't have direct access to the graph can learn about the optimum assignment once it is computed.

Definition at line 277 of file linear_assignment.h.

◆ NumLeftNodes()

template<typename GraphType, typename CostValue = int64_t>

NodeIndex operations_research::LinearSumAssignment< GraphType, CostValue >::NumLeftNodes ( ) const

inline

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

Definition at line 325 of file linear_assignment.h.

◆ NumNodes()

template<typename GraphType, typename CostValue = int64_t>

NodeIndex operations_research::LinearSumAssignment< GraphType, CostValue >::NumNodes ( ) const

inline

Returns the total number of nodes in the given problem.

Return a guess that must be true if ultimately we are given a feasible problem to solve.

Definition at line 313 of file linear_assignment.h.

◆ operator=()

template<typename GraphType, typename CostValue = int64_t>

LinearSumAssignment & operations_research::LinearSumAssignment< GraphType, CostValue >::operator= ( const LinearSumAssignment< GraphType, CostValue > & )

delete

◆ SetArcCost()

template<typename GraphType, typename CostValue>

void operations_research::LinearSumAssignment< GraphType, CostValue >::SetArcCost	(	ArcIndex	arc,
		CostValue	cost )

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

Definition at line 982 of file linear_assignment.h.

◆ SetCostScalingDivisor()

template<typename GraphType, typename CostValue = int64_t>

void operations_research::LinearSumAssignment< GraphType, CostValue >::SetCostScalingDivisor ( CostValue factor )

inline

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

Definition at line 259 of file linear_assignment.h.

◆ SetGraph()

template<typename GraphType, typename CostValue = int64_t>

void operations_research::LinearSumAssignment< GraphType, CostValue >::SetGraph ( const GraphType * graph )

inline

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 StaticGraph.

Definition at line 252 of file linear_assignment.h.

◆ StatsString()

template<typename GraphType, typename CostValue = int64_t>

std::string operations_research::LinearSumAssignment< GraphType, CostValue >::StatsString ( ) const

inline

Definition at line 347 of file linear_assignment.h.

The documentation for this class was generated from the following file:

ortools/graph/linear_assignment.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ ArcIndex

◆ CostValueT

◆ NodeIndex

Constructor & Destructor Documentation

◆ LinearSumAssignment() [1/3]

◆ LinearSumAssignment() [2/3]

◆ LinearSumAssignment() [3/3]

◆ ~LinearSumAssignment()

Member Function Documentation

◆ ArcAnnotationCycleHandler()

◆ ArcCost()

◆ BipartiteLeftNodes()

◆ ComputeAssignment()

◆ EpsilonOptimal()

◆ FinalizeSetup()

◆ GetAssignmentArc()

◆ GetAssignmentCost()

◆ GetCost()

◆ GetMate()

◆ Graph()

◆ Head()

◆ NumLeftNodes()

◆ NumNodes()

◆ operator=()

◆ SetArcCost()

◆ SetCostScalingDivisor()

◆ SetGraph()

◆ StatsString()