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.