C++ Reference: class BlossomGraph

This documentation is automatically generated.

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.

Return type: void

Arguments: NodeIndex tail, NodeIndex head, CostValue cost

Same comment as MinCostPerfectMatching::AddEdgeWithCost() applies.


Return type: void

Arguments: EdgeIndex e

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


Return type: explicit

Arguments: int num_nodes

Creates a BlossomGraph on the given number of nodes.


Return type: CostValue

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


Return type: void

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


Return type: bool

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


Return type: bool

Arguments: const Edge& edge

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


Return type: std::string


Return type: void

Arguments: 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.


Arguments: NodeIndex, int

Typed index used by this class.


Arguments: EdgeIndex, int


Arguments: CostValue, int64


Return type: void

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


Return type: CostValue

Arguments: const Node& node

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


Return type: CostValue

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.


Return type: std::string

Arguments: EdgeIndex e


Return type: void

Arguments: NodeIndex to_expand

Expands a Blossom into its component.


Return type: void

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


Return type: const Edge&

Arguments: int e

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


Return type: const Node&

Arguments: int n


Return type: void

Arguments: 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.


Return type: ABSL_MUST_USE_RESULT bool

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.


Return type: NodeIndex

Arguments: NodeIndex n

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


Return type: std::string

Arguments: NodeIndex n

Display information for debugging.


Return type: bool

Arguments: NodeIndex n

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.


Return type: int

Returns the current number of matched nodes.


Return type: void

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


Return type: void

Arguments: EdgeIndex e

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


Return type: CostValue

Arguments: const Edge& edge

Return the "slack" of the given edge.


Return type: void

Arguments: CostValue delta

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