operations_research::SimpleLinearSumAssignment Class Reference

#include <assignment.h>

Public Types
enum	Status { OPTIMAL , INFEASIBLE , POSSIBLE_OVERFLOW }
typedef int32_t	NodeIndex
typedef int32_t	ArcIndex
typedef int64_t	CostValue

Public Member Functions
	SimpleLinearSumAssignment ()
	SimpleLinearSumAssignment (const SimpleLinearSumAssignment &)=delete
	This type is neither copyable nor movable.
SimpleLinearSumAssignment &	operator= (const SimpleLinearSumAssignment &)=delete
void	ReserveArcs (ArcIndex num_arcs)
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 56 of file assignment.h.

Member Typedef Documentation

ArcIndex

typedef int32_t operations_research::SimpleLinearSumAssignment::ArcIndex

Definition at line 59 of file assignment.h.

CostValue

typedef int64_t operations_research::SimpleLinearSumAssignment::CostValue

Definition at line 60 of file assignment.h.

NodeIndex

typedef int32_t operations_research::SimpleLinearSumAssignment::NodeIndex

Definition at line 58 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 106 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 24 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()

SimpleLinearSumAssignment::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 26 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 132 of file assignment.h.

Cost()

SimpleLinearSumAssignment::CostValue operations_research::SimpleLinearSumAssignment::Cost

(

ArcIndex

arc

)

const

Definition at line 56 of file assignment.cc.

LeftNode()

SimpleLinearSumAssignment::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 46 of file assignment.cc.

NumArcs()

SimpleLinearSumAssignment::ArcIndex operations_research::SimpleLinearSumAssignment::NumArcs

(

)

const

Returns the current number of arcs in the graph.

Definition at line 42 of file assignment.cc.

NumNodes()

SimpleLinearSumAssignment::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 37 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 115 of file assignment.h.

ReserveArcs()

void operations_research::SimpleLinearSumAssignment::ReserveArcs ( ArcIndex num_arcs )

inline

Reserves space for the given number of arcs, to avoid reallocation in `AddArcWithCost().

Definition at line 75 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 126 of file assignment.h.

RightNode()

SimpleLinearSumAssignment::NodeIndex operations_research::SimpleLinearSumAssignment::RightNode

(

ArcIndex

arc

)

const

Definition at line 51 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 61 of file assignment.cc.

---

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

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