operations_research::BlossomGraph::Edge Struct Reference

An undirected edge between two nodes: tail <-> head. More...

#include <perfect_matching.h>

Public Member Functions
	Edge (NodeIndex t, NodeIndex h, CostValue c)
NodeIndex	OtherEnd (NodeIndex n) const
	Returns the "other" end of this edge.
void	SetHeapIndex (int index)
int	GetHeapIndex () const
bool	operator> (const Edge &other) const

Public Attributes
CostValue	pseudo_slack
	See the formula is Slack() used to derive the true slack of this edge.
CostValue	slack
	We only maintain this in debug mode.
NodeIndex	tail
NodeIndex	head
int	pq_position = -1

Detailed Description

An undirected edge between two nodes: tail <-> head.

Definition at line 257 of file perfect_matching.h.

Constructor & Destructor Documentation

Edge()

operations_research::BlossomGraph::Edge::Edge ( NodeIndex t, NodeIndex h, CostValue c )

inline

Definition at line 258 of file perfect_matching.h.

Member Function Documentation

GetHeapIndex()

int operations_research::BlossomGraph::Edge::GetHeapIndex ( ) const

inline

Definition at line 276 of file perfect_matching.h.

operator>()

bool operations_research::BlossomGraph::Edge::operator> ( const Edge & other ) const

inline

Definition at line 277 of file perfect_matching.h.

OtherEnd()

NodeIndex operations_research::BlossomGraph::Edge::OtherEnd ( NodeIndex n ) const

inline

Returns the "other" end of this edge.

Definition at line 268 of file perfect_matching.h.

SetHeapIndex()

void operations_research::BlossomGraph::Edge::SetHeapIndex ( int index )

inline

AdjustablePriorityQueue interface. Note that we use std::greater<> in our queues since we want the lowest pseudo_slack first.

Definition at line 275 of file perfect_matching.h.

Member Data Documentation

head

NodeIndex operations_research::BlossomGraph::Edge::head

Definition at line 295 of file perfect_matching.h.

pq_position

int operations_research::BlossomGraph::Edge::pq_position = -1

Position of this Edge in the underlying std::vector<> used to encode the heap of one priority queue. An edge can be in at most one priority queue which allow us to share this amongst queues.

Definition at line 300 of file perfect_matching.h.

pseudo_slack

CostValue operations_research::BlossomGraph::Edge::pseudo_slack

See the formula is Slack() used to derive the true slack of this edge.

Definition at line 282 of file perfect_matching.h.

slack

CostValue operations_research::BlossomGraph::Edge::slack

We only maintain this in debug mode.

Definition at line 286 of file perfect_matching.h.

tail

NodeIndex operations_research::BlossomGraph::Edge::tail

These are the current tail/head of this edges. These are changed when creating or expanding blossoms. The order do not matter.

Todo

(user): Consider using node_a/node_b instead to remove the "directed" meaning. I do need to think a bit more about it though.

Definition at line 294 of file perfect_matching.h.

---

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

• ortools/graph/perfect_matching.h