C++ Reference: class BlossomGraph

Note: 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_t
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.