operations_research::BlossomGraph::Node Struct Reference

#include <perfect_matching.h>

Public Member Functions
	Node (NodeIndex n)
bool	IsInternal () const
bool	IsFree () const
bool	IsPlus () const
bool	IsMinus () const
bool	IsBlossom () const

Public Attributes
int	type = 0
bool	is_internal = false
	Whether this node is part of a blossom.
NodeIndex	parent
NodeIndex	match
NodeIndex	root
CostValue	tree_dual_delta = CostValue(0)
CostValue	pseudo_dual = CostValue(0)
CostValue	dual = CostValue(0)
	The true dual of this node. We only maintain this in debug mode.
std::vector< NodeIndex >	blossom
CostValue	saved_dual
CostValue	saved_pseudo_dual
std::vector< NodeIndex >	saved_blossom

Detailed Description

Node related data. We store the edges incident to a node separately in the graph_ member.

Definition at line 181 of file perfect_matching.h.

Constructor & Destructor Documentation

Node()

operations_research::BlossomGraph::Node::Node ( NodeIndex n )

inlineexplicit

Definition at line 182 of file perfect_matching.h.

Member Function Documentation

IsBlossom()

bool operations_research::BlossomGraph::Node::IsBlossom ( ) const

inline

Is this node a blossom? if yes, it was formed by merging the node.blossom nodes together. Note that we reuse the index of node.blossom[0] for this blossom node. A blossom node can be of any type.

Definition at line 200 of file perfect_matching.h.

IsFree()

bool operations_research::BlossomGraph::Node::IsFree ( ) const

inline

Definition at line 193 of file perfect_matching.h.

IsInternal()

bool operations_research::BlossomGraph::Node::IsInternal ( ) const

inline

A node can be in one of these 4 exclusive states. Internal nodes are part of a Blossom and should be ignored until this Blossom is expanded. All the other nodes are "external". A free node is always matched to another free node. All the other external node are in alternating [+]/[-] trees rooted at the only unmatched node of the tree (always of type [+]).

Definition at line 189 of file perfect_matching.h.

IsMinus()

bool operations_research::BlossomGraph::Node::IsMinus ( ) const

inline

Definition at line 195 of file perfect_matching.h.

IsPlus()

bool operations_research::BlossomGraph::Node::IsPlus ( ) const

inline

Definition at line 194 of file perfect_matching.h.

Member Data Documentation

blossom

std::vector<NodeIndex> operations_research::BlossomGraph::Node::blossom

Non-empty for Blossom only. The odd-cycle of blossom nodes that form this blossom. The first element should always be the current blossom node, and all the other nodes are internal nodes.

Definition at line 241 of file perfect_matching.h.

dual

CostValue operations_research::BlossomGraph::Node::dual = CostValue(0)

The true dual of this node. We only maintain this in debug mode.

Definition at line 235 of file perfect_matching.h.

is_internal

bool operations_research::BlossomGraph::Node::is_internal = false

Whether this node is part of a blossom.

Definition at line 210 of file perfect_matching.h.

match

NodeIndex operations_research::BlossomGraph::Node::match

Itself if not matched, or this node match otherwise. Unused for internal nodes.

Definition at line 218 of file perfect_matching.h.

parent

NodeIndex operations_research::BlossomGraph::Node::parent

The parent of this node in its tree or itself otherwise. Unused for internal nodes.

Definition at line 214 of file perfect_matching.h.

pseudo_dual

CostValue operations_research::BlossomGraph::Node::pseudo_dual = CostValue(0)

See the formula in Dual() used to derive the true dual of this node. This is the equal to the "true" dual for free exterior node and internal node.

Definition at line 231 of file perfect_matching.h.

root

NodeIndex operations_research::BlossomGraph::Node::root

The root of this tree which never changes until a tree is disassambled by an Augment(). Unused for internal nodes.

Definition at line 222 of file perfect_matching.h.

saved_blossom

std::vector<NodeIndex> operations_research::BlossomGraph::Node::saved_blossom

Definition at line 253 of file perfect_matching.h.

saved_dual

CostValue operations_research::BlossomGraph::Node::saved_dual

This allows to store information about a new blossom node created by Shrink() so that we can properly restore it on Expand(). Note that we store the saved information on the second node of a blossom cycle (and not the blossom node itself) because that node will be "hidden" until the blossom is expanded so this way, we do not need more than one set of saved information per node.

Definition at line 250 of file perfect_matching.h.

saved_pseudo_dual

CostValue operations_research::BlossomGraph::Node::saved_pseudo_dual

Definition at line 252 of file perfect_matching.h.

tree_dual_delta

CostValue operations_research::BlossomGraph::Node::tree_dual_delta = CostValue(0)

The "delta" to apply to get the dual for nodes of this tree. This is only filled for root nodes (i.e unmatched nodes).

Definition at line 226 of file perfect_matching.h.

type

int operations_research::BlossomGraph::Node::type = 0

The type of this node. We use an int for convenience in the update formulas. This is 1 for [+] nodes, -1 for [-] nodes and 0 for all the others.

Internal node also have a type of zero so the dual formula are correct.

Definition at line 207 of file perfect_matching.h.

---

The documentation for this struct was generated from the following file:

• ortools/graph/perfect_matching.h