#include <perfect_matching.h>

Classes
struct	Edge
	An undirected edge between two nodes: tail <-> head. More...

struct	Node

Public Member Functions
	DEFINE_INT_TYPE (NodeIndex, int)
	Typed index used by this class.

	DEFINE_INT_TYPE (EdgeIndex, int)

	DEFINE_INT_TYPE (CostValue, int64_t)

	BlossomGraph (int num_nodes)
	Creates a BlossomGraph on the given number of nodes.

void	AddEdge (NodeIndex tail, NodeIndex head, CostValue cost)
	Same comment as MinCostPerfectMatching::AddEdgeWithCost() applies.

ABSL_MUST_USE_RESULT bool	Initialize ()

void	PrimalUpdates ()

CostValue	ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue ()

void	UpdateAllTrees (CostValue delta)

bool	NodeIsMatched (NodeIndex n) const

NodeIndex	Match (NodeIndex n) const

void	Grow (EdgeIndex e, NodeIndex tail, NodeIndex head)

void	Augment (EdgeIndex e)

void	Shrink (EdgeIndex e)

void	Expand (NodeIndex to_expand)
	Expands a Blossom into its component.

int	NumMatched () const
	Returns the current number of matched nodes.

CostValue	DualObjective () const

void	ExpandAllBlossoms ()
	This must be called at the end of the algorithm to recover the matching.

CostValue	Slack (const Edge &edge) const
	Return the "slack" of the given edge.

CostValue	Dual (const Node &node) const
	Returns the dual value of the given node (which might be a pseudo-node).

void	DisplayStats () const
	Display to VLOG(1) some statistic about the solve.

void	DebugCheckNoPossiblePrimalUpdates ()

bool	DebugDualsAreFeasible () const

void	DebugUpdateNodeDual (NodeIndex n, CostValue delta)

bool	DebugEdgeIsTightAndExternal (const Edge &edge) const

const Edge &	GetEdge (int e) const

const Node &	GetNode (int n) const

std::string	NodeDebugString (NodeIndex n) const
	Display information for debugging.

std::string	EdgeDebugString (EdgeIndex e) const

std::string	DebugString () const

Static Public Attributes
static const NodeIndex	kNoNodeIndex

static const EdgeIndex	kNoEdgeIndex

static const CostValue	kMaxCostValue

Detailed Description

Class containing the main data structure used by the Blossom algorithm.

At the core is the original undirected graph. During the algorithm execution we might collapse nodes into so-called Blossoms. A Blossom is a cycle of external nodes (which can be blossom nodes) of odd length (>= 3). The edges of the cycle are called blossom-forming eges and will always be tight (i.e. have a slack of zero). Once a Blossom is created, its nodes become "internal" and are basically considered merged into the blossom node for the rest of the algorithm (except if we later re-expand the blossom).

Moreover, external nodes of the graph will have 3 possible types ([+], [-] and free [0]). Free nodes will always be matched together in pairs. Nodes of type [+] and [-] are arranged in a forest of alternating [+]/[-] disjoint trees. Each unmatched node is the root of a tree, and of type [+]. Nodes [-] will always have exactly one child to witch they are matched. [+] nodes can have any number of [-] children, to which they are not matched. All the edges of the trees will always be tight. Some examples below, double edges are used for matched nodes:

A matched pair of free nodes: [0] === [0]

A possible rooted tree: [+] – [-] ==== [+] \ [-] ==== [+] -— [-] === [+] \ [-] === [+]

A single unmatched node is also a tree: [+]

Todo: (user): For now this class does not maintain a second graph of edges between the trees nor does it maintains priority queue of edges.

Todo: (user): For now we use CHECKs in many places to facilitate development. Switch them to DCHECKs for speed once the code is more stable.

Definition at line 165 of file perfect_matching.h.

Constructor & Destructor Documentation

◆ BlossomGraph()

operations_research::BlossomGraph::BlossomGraph ( int num_nodes )

explicit

Creates a BlossomGraph on the given number of nodes.

Definition at line 130 of file perfect_matching.cc.

Member Function Documentation

◆ AddEdge()

void operations_research::BlossomGraph::AddEdge	(	NodeIndex	tail,
		NodeIndex	head,
		CostValue	cost )

Same comment as MinCostPerfectMatching::AddEdgeWithCost() applies.

Definition at line 140 of file perfect_matching.cc.

◆ Augment()

void operations_research::BlossomGraph::Augment ( EdgeIndex e )

Merges two tree and augment the number of matched nodes by 1. This is the only functions that change the current matching.

Compute the path from root_a to root_b.

Todo: (user): Check all dual/slack same after primal op?

Make all the nodes from both trees free while keeping the current matching.

Todo: (user): It seems that we may waste some computation since the part of the tree not in the path between roots can lead to the same Grow() operations later when one of its node is ratched to a new root.

Todo: (user): Reduce this O(num_nodes) complexity. We might be able to even do O(num_node_in_path) with lazy updates. Note that this operation will only be performed at most num_initial_unmatched_nodes / 2 times though.

If the other end is not in one of the two trees, and it is a plus node, we add it the plus_free queue. All previous [+]–[0] and [+]–[+] edges need to be removed from the queues.

Change the matching of nodes along node_path.

Update unmatched_nodes_.

Todo: (user): This could probably be optimized if needed. But we do usually iterate a lot more over it than we update it. Note that as long as we use the same delta for all trees, this is not even needed.

Definition at line 561 of file perfect_matching.cc.

◆ ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue()

CostValue operations_research::BlossomGraph::ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue ( )

Computes the maximum possible delta for UpdateAllTrees() that keeps the dual feasibility. Dual update approach (2) from the paper. This also fills primal_update_edge_queue_.

Todo: (user): Avoid this linear loop.

This code only works because all tree_dual_delta are the same.

This means infeasible, and returning zero will abort the search.

Initialize primal_update_edge_queue_ with all the edges that will have a slack of zero once we apply the update.

NOTE(user): If we want more "determinism" and be independent on the PQ algorithm, we could std::sort() the primal_update_edge_queue_ here.

Definition at line 273 of file perfect_matching.cc.

◆ DebugCheckNoPossiblePrimalUpdates()

void operations_research::BlossomGraph::DebugCheckNoPossiblePrimalUpdates ( )

Checks that there is no possible primal update in the current configuration.

Meant to only be used in DEBUG to make sure our queue in PrimalUpdates() do not miss any potential edges.

Make sure tail is a plus node if possible.

Definition at line 361 of file perfect_matching.cc.

◆ DebugDualsAreFeasible()

bool operations_research::BlossomGraph::DebugDualsAreFeasible ( ) const

Tests that the dual values are currently feasible. This should ALWAYS be the case.

The slack of all edge must be non-negative.

The dual of all Blossom must be non-negative.

Definition at line 464 of file perfect_matching.cc.

◆ DebugEdgeIsTightAndExternal()

bool operations_research::BlossomGraph::DebugEdgeIsTightAndExternal ( const Edge & edge ) const

Returns true iff this is an external edge with a slack of zero. An external edge is an edge between two external nodes.

Definition at line 477 of file perfect_matching.cc.

◆ DebugString()

std::string operations_research::BlossomGraph::DebugString ( ) const

Definition at line 1217 of file perfect_matching.cc.

◆ DebugUpdateNodeDual()

void operations_research::BlossomGraph::DebugUpdateNodeDual	(	NodeIndex	n,
		CostValue	delta )

In debug mode, we maintain the real slack of each edges and the real dual of each node via this function. Both Slack() and Dual() checks in debug mode that the value computed is the correct one.

Definition at line 1228 of file perfect_matching.cc.

◆ DEFINE_INT_TYPE() [1/3]

operations_research::BlossomGraph::DEFINE_INT_TYPE	(	CostValue	,
		int64_t	)

◆ DEFINE_INT_TYPE() [2/3]

operations_research::BlossomGraph::DEFINE_INT_TYPE	(	EdgeIndex	,
		int	)

◆ DEFINE_INT_TYPE() [3/3]

operations_research::BlossomGraph::DEFINE_INT_TYPE	(	NodeIndex	,
		int	)

Typed index used by this class.

◆ DisplayStats()

void operations_research::BlossomGraph::DisplayStats ( ) const

Display to VLOG(1) some statistic about the solve.

Definition at line 1281 of file perfect_matching.cc.

◆ Dual()

CostValue operations_research::BlossomGraph::Dual ( const Node & node ) const

Returns the dual value of the given node (which might be a pseudo-node).

Definition at line 1260 of file perfect_matching.cc.

◆ DualObjective()

CostValue operations_research::BlossomGraph::DualObjective ( ) const

Returns the current dual objective which is always a valid lower-bound on the min-cost matching. Note that this is capped to kint64max in case of overflow. Because all of our cost are positive, this starts at zero.

Definition at line 1269 of file perfect_matching.cc.

◆ EdgeDebugString()

std::string operations_research::BlossomGraph::EdgeDebugString ( EdgeIndex e ) const

Definition at line 1207 of file perfect_matching.cc.

◆ Expand()

void operations_research::BlossomGraph::Expand ( NodeIndex to_expand )

Expands a Blossom into its component.

First, restore the saved fields.

Restore the edges Head()/Tail().

Now we try to find a 'blossom path' that will replace the blossom node in the alternating tree: the blossom's parent [+] node in the tree will be attached to a blossom subnode (the "path start"), the blossom's child in the tree will be attached to a blossom subnode (the "path end", which could be the same subnode or a different one), and, using the blossom cycle, we'll get a path with an odd number of blossom subnodes to connect the two (since the cycle is odd, one of the two paths will be odd too). The other subnodes of the blossom will then be made free nodes matched pairwise.

Split the cycle in two halves: nodes in [start..end] in path1, and nodes in [end..start] in path2. Note the inclusive intervals.

Reverse path2 to also make it go from start to end.

Swap if necessary so that path1 is the odd-length one.

Use better aliases than 'path1' and 'path2' in the code below.

Strip path2 from the start and end, which aren't needed.

Restore the path in the tree, note that we append the blossom_matched_node to simplify the code: <-— Blossom ----> [-] === [+] — [-] === [+]

Update the parent.

This is the path start and its parent is either itself or the parent of to_expand if there was one.

Update the types and matches.

Ignore the blossom_matched_node for the code below.

Update the duals, depending on whether we have a new [+] or [-] node.

Note: this is also needed for the 'root' blossom node (i=0), because we've restored its pseudo-dual from its old saved value above.

non-internal edges used to be attached to the [-] node_to_expand, so we adjust their dual.

This was an internal edges. For the PQ code below to be correct, we wait for its other end to have been processed by this loop already. We detect that using the fact that the type of unprocessed internal node is still zero.

Update edge queues.

Update free nodes.

Update edges slack and priority queue for the adjacent edges.

non-internal edges used to be attached to the [-] node_to_expand, so we adjust their dual.

Update PQ. Note that since this was attached to a [-] node it cannot be in any queue. We will also never process twice the same edge here.

Matches the free pair together.

Mark all node as external. We do that last so we could easily detect old internal edges that are now external.

Definition at line 859 of file perfect_matching.cc.

◆ ExpandAllBlossoms()

void operations_research::BlossomGraph::ExpandAllBlossoms ( )

This must be called at the end of the algorithm to recover the matching.

Queue of blossoms to expand.

When this is called, there should be no more trees.

Todo: (user): remove duplication with expand?

Find the edge used to match to_expand with Match(to_expand).

Restore the saved data.

Restore the edges Head()/Tail().

Find the index of matched_node in the blossom list.

Amongst the node_to_expand.blossom nodes, internal_matched_index is matched with external_matched_node and the other are matched together.

Clear root/parent/type of all internal nodes.

Matches the internal node with external one.

Matches the free pair together.

Now that the expansion is done, add to the queue any sub-blossoms.

Definition at line 1068 of file perfect_matching.cc.

◆ GetEdge()

const Edge & operations_research::BlossomGraph::GetEdge ( int e ) const

inline

Getters to access node/edges from outside the class. Only used in tests.

Definition at line 390 of file perfect_matching.h.

◆ GetNode()

const Node & operations_research::BlossomGraph::GetNode ( int n ) const

inline

Definition at line 391 of file perfect_matching.h.

◆ Grow()

void operations_research::BlossomGraph::Grow	(	EdgeIndex	e,
		NodeIndex	tail,
		NodeIndex	head )

Adds to the tree of tail the free matched pair(head, Match(head)). The edge is only used in DCHECKs. We duplicate tail/head because the order matter here.

head was free and is now a [-] node.

leaf was free and is now a [+] node.

The edge switch from [+] – [0] to [+] – [+].

We have a new [+] – [0] edge.

Definition at line 484 of file perfect_matching.cc.

◆ Initialize()

bool operations_research::BlossomGraph::Initialize ( )

Heuristic to start with a dual-feasible solution and some matched edges. To be called once all edges are added. Returns false if the problem is detected to be INFEASIBLE.

Todo: (user): Code the more advanced "Fractional matching initialization" heuristic.

Todo: (user): Add a preprocessing step that performs the 'forced' matches?

Initialize the dual of each nodes to min_cost / 2.

Todo: (user): We might be able to do better for odd min_cost, but then we might need to scale by 4? think about it.

Starts with all nodes as tree roots.

Update the slack of each edges now that nodes might have non-zero duals.

Note: we made sure that all updated slacks are non-negative.

After this greedy update, there will be at least an edge with a slack of zero.

Match this node if possible.

Todo: (user): Optimize by merging this loop with the one above?

Initialize unmatched_nodes_.

Scale everything by 2 and update the dual cost. Note that we made sure that there cannot be an integer overflow at the beginning of Solve().

This scaling allows to only have integer weights during the algorithm because the slack of [+] – [+] edges will always stay even.

Todo: (user): Reduce the number of loops we do in the initialization. We could likely just scale the edge cost as we fill them.

Initialize the edge priority queues and the primal update queue. We only need to do that if we have unmatched nodes.

Definition at line 157 of file perfect_matching.cc.

◆ Match()

NodeIndex operations_research::BlossomGraph::Match ( NodeIndex n ) const

Returns the node matched to the given one, or n if this node is not currently matched.

Definition at line 350 of file perfect_matching.cc.

◆ NodeDebugString()

std::string operations_research::BlossomGraph::NodeDebugString ( NodeIndex n ) const

Display information for debugging.

Definition at line 1191 of file perfect_matching.cc.

◆ NodeIsMatched()

bool operations_research::BlossomGraph::NodeIsMatched ( NodeIndex n ) const

Returns true iff this node is matched and is thus not a tree root. This cannot live in the Node class because we need to know the NodeIndex.

An unmatched node must be a tree root.

Definition at line 343 of file perfect_matching.cc.

◆ NumMatched()

int operations_research::BlossomGraph::NumMatched ( ) const

inline

Returns the current number of matched nodes.

Definition at line 352 of file perfect_matching.h.

◆ PrimalUpdates()

void operations_research::BlossomGraph::PrimalUpdates ( )

Enters a loop that perform one of Grow()/Augment()/Shrink()/Expand() until a fixed point is reached.

Any Grow/Augment/Shrink/Expand operation can add new tight edges that need to be explored again.

Todo: (user): avoid adding duplicates?

First, we Grow/Augment as much as possible.

Because of the Expand() operation, the edge may have become un-tight since it has been inserted in the tight edges queue. It's cheaper to detect it here and skip it than it would be to dynamically update the queue to only keep actually tight edges at all times.

Shrink all potential Blossom.

Delay expand if any blossom was created.

Expand Blossom if any.

Todo: (user): Avoid doing a O(num_nodes). Also expand all blossom recursively? I am not sure it is a good heuristic to expand all possible blossom before trying the other operations though.

Definition at line 395 of file perfect_matching.cc.

◆ Shrink()

void operations_research::BlossomGraph::Shrink ( EdgeIndex e )

Creates a Blossom using the given [+] – [+] edge between two nodes of the same tree.

Find lowest common ancestor and the two node paths to reach it. Note that we do not add it to the paths.

Fill the cycle.

Save all values that will be needed if we expand this Blossom later.

Set the new dual of the node to zero.

Mark node as internal, but do not change their type to zero yet. We need to do that first to properly detect edges between two internal nodes in the second loop below.

Update the dual of all edges and the priority queueus.

Subtle: We update root_blossom_node_ while we loop, so for new internal edges, depending if an edge "other end" appear after or before, it will not be updated. We use this to only process internal edges once.

Skip edge that are already internal.

This internal edge was already processed from its other end, so we can just skip it.

This is a new-internal edge that we didn't process yet.

Todo: (user): It would be nicer to not to have to read the memory of the other node at all. It might be possible once we store the parent edge instead of the parent node since then we will only need to know if this edges point to a new-internal node or not.

Replace the parent of any child of n by lca_index.

Adjust when the edge used to be connected to a [-] node now that we attach it to a [+] node. Note that if the node was [+] then the non-internal incident edges slack and type do not change.

Add it to the correct PQ.

Definition at line 664 of file perfect_matching.cc.

◆ Slack()

CostValue operations_research::BlossomGraph::Slack ( const Edge & edge ) const

Return the "slack" of the given edge.

Definition at line 1242 of file perfect_matching.cc.

◆ UpdateAllTrees()

void operations_research::BlossomGraph::UpdateAllTrees ( CostValue delta )

Applies the same dual delta to all trees. Dual update approach (2) from the paper.

Reminder: the tree roots are exactly the unmatched nodes.

Definition at line 323 of file perfect_matching.cc.

Member Data Documentation

◆ kMaxCostValue

const BlossomGraph::CostValue operations_research::BlossomGraph::kMaxCostValue

static

Initial value:

=

BlossomGraph::CostValue(std::numeric_limits<int64_t>::max())

Definition at line 177 of file perfect_matching.h.

◆ kNoEdgeIndex

const BlossomGraph::EdgeIndex operations_research::BlossomGraph::kNoEdgeIndex

static

Initial value:

=

BlossomGraph::EdgeIndex(-1)

Definition at line 176 of file perfect_matching.h.

◆ kNoNodeIndex

const BlossomGraph::NodeIndex operations_research::BlossomGraph::kNoNodeIndex

static

Initial value:

=

BlossomGraph::NodeIndex(-1)

Basic constants. NOTE(user): Those can't be constexpr because of the or-tools export, which complains for constexpr DEFINE_INT_TYPE.

Definition at line 175 of file perfect_matching.h.

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

ortools/graph/perfect_matching.h
ortools/graph/perfect_matching.cc

Classes

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BlossomGraph()

Member Function Documentation

◆ AddEdge()

◆ Augment()

◆ ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue()

◆ DebugCheckNoPossiblePrimalUpdates()

◆ DebugDualsAreFeasible()

◆ DebugEdgeIsTightAndExternal()

◆ DebugString()

◆ DebugUpdateNodeDual()

◆ DEFINE_INT_TYPE() [1/3]

◆ DEFINE_INT_TYPE() [2/3]

◆ DEFINE_INT_TYPE() [3/3]

◆ DisplayStats()

◆ Dual()

◆ DualObjective()

◆ EdgeDebugString()

◆ Expand()

◆ ExpandAllBlossoms()

◆ GetEdge()

◆ GetNode()

◆ Grow()

◆ Initialize()

◆ Match()

◆ NodeDebugString()

◆ NodeIsMatched()

◆ NumMatched()

◆ PrimalUpdates()

◆ Shrink()

◆ Slack()

◆ UpdateAllTrees()

Member Data Documentation

◆ kMaxCostValue

◆ kNoEdgeIndex

◆ kNoNodeIndex