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.
Method
AddEdge

Return type: void

Arguments: NodeIndex tail, NodeIndex head, CostValue cost

Same comment as MinCostPerfectMatching::AddEdgeWithCost() applies.

Augment

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.

BlossomGraph

Return type: explicit

Arguments: int num_nodes

Creates a BlossomGraph on the given number of nodes.

ComputeMaxCommonTreeDualDeltaAndResetPrimalEdgeQueue

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

DebugCheckNoPossiblePrimalUpdates

Return type: void

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

DebugDualsAreFeasible

Return type: bool

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

DebugEdgeIsTightAndExternal

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.

DebugString

Return type: std::string

DebugUpdateNodeDual

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.

DEFINE_INT_TYPE

Arguments: NodeIndex, int

Typed index used by this class.

DEFINE_INT_TYPE

Arguments: EdgeIndex, int

DEFINE_INT_TYPE

Arguments: CostValue, int64

DisplayStats

Return type: void

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

Dual

Return type: CostValue

Arguments: const Node& node

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

DualObjective

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.

EdgeDebugString

Return type: std::string

Arguments: EdgeIndex e

Expand

Return type: void

Arguments: NodeIndex to_expand

Expands a Blossom into its component.

ExpandAllBlossoms

Return type: void

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

GetEdge

Return type: const Edge&

Arguments: int e

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

GetNode

Return type: const Node&

Arguments: int n

Grow

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.

Initialize

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.

Match

Return type: NodeIndex

Arguments: NodeIndex n

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

NodeDebugString

Return type: std::string

Arguments: NodeIndex n

Display information for debugging.

NodeIsMatched

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.

NumMatched

Return type: int

Returns the current number of matched nodes.

PrimalUpdates

Return type: void

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

Shrink

Return type: void

Arguments: EdgeIndex e

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

Slack

Return type: CostValue

Arguments: const Edge& edge

Return the "slack" of the given edge.

UpdateAllTrees

Return type: void

Arguments: CostValue delta

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