operations_research::SimpleLinearSumAssignment Class Reference

#include <assignment.h>

Public Types
enum	Status { OPTIMAL , INFEASIBLE , POSSIBLE_OVERFLOW }

Public Member Functions
	SimpleLinearSumAssignment ()
	SimpleLinearSumAssignment (const SimpleLinearSumAssignment &)=delete
	This type is neither copyable nor movable.
SimpleLinearSumAssignment &	operator= (const SimpleLinearSumAssignment &)=delete
ArcIndex	AddArcWithCost (NodeIndex left_node, NodeIndex right_node, CostValue cost)
NodeIndex	NumNodes () const
ArcIndex	NumArcs () const
	Returns the current number of arcs in the graph.
NodeIndex	LeftNode (ArcIndex arc) const
NodeIndex	RightNode (ArcIndex arc) const
CostValue	Cost (ArcIndex arc) const
Status	Solve ()
CostValue	OptimalCost () const
NodeIndex	RightMate (NodeIndex left_node) const
CostValue	AssignmentCost (NodeIndex left_node) const

Detailed Description

Definition at line 57 of file assignment.h.

Member Enumeration Documentation

Status

enum operations_research::SimpleLinearSumAssignment::Status

Solves the problem (finds the perfect matching that minimizes the cost) and returns the solver status.

Enumerator
OPTIMAL
INFEASIBLE
POSSIBLE_OVERFLOW

Definition at line 95 of file assignment.h.

Constructor & Destructor Documentation

SimpleLinearSumAssignment() [1/2]

operations_research::SimpleLinearSumAssignment::SimpleLinearSumAssignment

(

)

The constructor takes no size. New node indices will be created lazily by AddArcWithCost().

Definition at line 25 of file assignment.cc.

SimpleLinearSumAssignment() [2/2]

operations_research::SimpleLinearSumAssignment::SimpleLinearSumAssignment ( const SimpleLinearSumAssignment & )

delete

This type is neither copyable nor movable.

Member Function Documentation

AddArcWithCost()

ArcIndex operations_research::SimpleLinearSumAssignment::AddArcWithCost	(	NodeIndex	left_node,
		NodeIndex	right_node,
		CostValue	cost )

Adds an arc from a left node to a right node with a given cost.

• Node indices must be non-negative (>= 0). For a perfect matching to exist on n nodes, the values taken by "left_node" must cover [0, n), same for "right_node".
• The arc cost can be any integer, negative, positive or zero.
• After the method finishes, NumArcs() == the returned ArcIndex + 1.

Definition at line 27 of file assignment.cc.

AssignmentCost()

CostValue operations_research::SimpleLinearSumAssignment::AssignmentCost ( NodeIndex left_node ) const

inline

Returns the cost of the arc used for "left_node"'s assignment. This works only if Solve() returned OPTIMAL.

Definition at line 121 of file assignment.h.

Cost()

CostValue operations_research::SimpleLinearSumAssignment::Cost

(

ArcIndex

arc

)

const

Definition at line 51 of file assignment.cc.

LeftNode()

NodeIndex operations_research::SimpleLinearSumAssignment::LeftNode

(

ArcIndex

arc

)

const

Returns user-provided data. The implementation will crash if "arc" is not in [0, NumArcs()).

Definition at line 43 of file assignment.cc.

NumArcs()

ArcIndex operations_research::SimpleLinearSumAssignment::NumArcs

(

)

const

Returns the current number of arcs in the graph.

Definition at line 41 of file assignment.cc.

NumNodes()

NodeIndex operations_research::SimpleLinearSumAssignment::NumNodes

(

)

const

Returns the current number of left nodes which is the same as the number of right nodes. This is one greater than the largest node index seen so far in AddArcWithCost().

Definition at line 39 of file assignment.cc.

operator=()

SimpleLinearSumAssignment & operations_research::SimpleLinearSumAssignment::operator= ( const SimpleLinearSumAssignment & )

delete

OptimalCost()

CostValue operations_research::SimpleLinearSumAssignment::OptimalCost ( ) const

inline

Returns the cost of an assignment with minimal cost. This is 0 if the last Solve() didn't return OPTIMAL.

Definition at line 104 of file assignment.h.

RightMate()

NodeIndex operations_research::SimpleLinearSumAssignment::RightMate ( NodeIndex left_node ) const

inline

Returns the right node assigned to the given left node in the last solution computed by Solve(). This works only if Solve() returned OPTIMAL.

Note

It is possible that there is more than one optimal solution. The algorithm is deterministic so it will always return the same solution for a given problem. There is no such guarantee from one code version to the next, but the code does not change often.

Definition at line 115 of file assignment.h.

RightNode()

NodeIndex operations_research::SimpleLinearSumAssignment::RightNode

(

ArcIndex

arc

)

const

Definition at line 47 of file assignment.cc.

Solve()

SimpleLinearSumAssignment::Status operations_research::SimpleLinearSumAssignment::Solve

(

)

HACK(user): Detect overflows early. In ./linear_assignment.h, the cost of each arc is internally multiplied by cost_scaling_factor_ (which is equal to (num_nodes + 1)) without overflow checking.

Todo

(user): Improve the LinearSumAssignment api to clearly define the error cases.

Definition at line 55 of file assignment.cc.

---

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

• ortools/graph/assignment.h
• ortools/graph/assignment.cc