Matching Class Reference

represent a matching on a graph More...

#include <Matching.h>

List of all members.

Public Member Functions
	Matching (Graph *g, ProgressOutput *po=NULL)
	~Matching (void)
bool	isMatched (Vertex *v) const
bool	isMatched (VertexLabel vlbl) const
bool	isExposed (Vertex *v) const
bool	isExposed (VertexLabel vlbl) const
const Edge *	getMatchingEdge (Vertex *v) const
bool	includesEdge (const Edge *e) const
bool	includesEdge (const Edge &e) const
unsigned long	getCardinality (void) const
const std::list< Vertex * > &	getExposedVertices (void) const
float	getMatchedRate (void) const
float	getAvgEdgeWeight (void) const
const std::list< Vertex * > *	getExposedVerticesLink (void) const
void	addEdge (const Edge &e)
void	addEdge (Edge *e)
void	removeEdge (const Edge &e)
const std::list< Edge * > &	getEdges (void) const
Matching &	augment (const Edge **path, unsigned long len)
Matching &	augment (const std::vector< Edge * > &path)
void	printVerboseInfo (void) const
bool	check (void) const
bool	check_MatchingEdges_vs_VertexInformation (void) const
bool	check_ExposedVertices_vs_VertexInformation (void) const
bool	check_VertexInformation_Integrity (void) const
bool	check_ValidAugPath (const std::vector< Edge * > &path) const
Private Member Functions
void	setCardinality (unsigned long c)
Private Attributes
std::vector< VertexInfo >	VertexInformation
	contains a VertexInfo object for every vertex
std::list< Vertex * >	ExposedVertices
	the std::list of all exposed vertices
std::list< Edge * >	MatchingEdges
	the std::list of all edges in the matching
unsigned long	Cardinality
	the number of edges in the matching
Graph *	TheGraph
	the graph underlying this Matching
ProgressOutput *	PrOut
	the ProgressOutput object that will print the number of matched vertices (as percentage)
Classes
class	VertexInfo
	contains information about a vertex that is possibly in a matching More...

---

Detailed Description

A Matching object will copy all Edges that are passed to it and will take care of them, i.e. delete them if they are no longer used. Edges do only "leave" a Matching object as const pointers.

---

Constructor & Destructor Documentation

Matching::Matching (  Graph *  g, ProgressOutput *  po = NULL )

create an empty matching that is ready for adding and augmenting Parameters: g  the underlying graph po  a ProgressOutput object that will print the number of matched vertices (in percent)

Matching::~Matching (  void   )

---

Member Function Documentation

void Matching::addEdge (  Edge *  e  )  [inline]

void Matching::addEdge (  const Edge &  e  )

add an edge to the matching Parameters: e  the edge to add. For e=(v1,v2): neither v1 nor v2 are allowed to be adjacent to an edge that is already in the matching,

Matching & Matching::augment (  const std::vector< Edge * > &  path  )

Matching & Matching::augment (  const Edge **  path, unsigned long  len )

augment this matching along the given augmenting path Parameters: path  an augmenting path len  the length (number of edges) of the augmenting path An augementing path is a path where edges with odd indices (the first, third,...) are not in the matching and edges with even indices are and the path has an odd length.

bool Matching::check (  void   )  const

bool Matching::check_ExposedVertices_vs_VertexInformation (  void   )  const

bool Matching::check_MatchingEdges_vs_VertexInformation (  void   )  const

bool Matching::check_ValidAugPath (  const std::vector< Edge * > &  path  )  const

bool Matching::check_VertexInformation_Integrity (  void   )  const

float Matching::getAvgEdgeWeight (  void   )  const

get the average weight of all edges that are in this matching

unsigned long Matching::getCardinality (  void   )  const [inline]

get the cardinality (the number of matched edges)

const std::list<Edge*>& Matching::getEdges (  void   )  const [inline]

get the list of all edges in this matching

const std::list<Vertex*>& Matching::getExposedVertices (  void   )  const [inline]

const std::list<Vertex*>* Matching::getExposedVerticesLink (  void   )  const [inline]

get access to the std::list of exposed vertices Returns: a pointer to the std::list of exposed vertices in this matching. The std::list that is pointed to by return value contains the exposed vertices even after augment has been called (it is the ExposedVertices member) an arbitrary number of times.

float Matching::getMatchedRate (  void   )  const

get the rate of vertices of the underlying graph that are currently matched in this matching Returns: a value between 0 and 1

const Edge* Matching::getMatchingEdge (  Vertex *  v  )  const [inline]

get the edge that is in the matching and adjacent to v Returns: the matched edge or NULL if v is exposed

bool Matching::includesEdge (  const Edge &  e  )  const

bool Matching::includesEdge (  const Edge *  e  )  const [inline]

does this matching include the edge e ? Returns: true iff the edge e is element of this matching

bool Matching::isExposed (  VertexLabel  vlbl  )  const [inline]

returns true iff the vertex with the label vlbl is exposed (not matched) in this matching.

bool Matching::isExposed (  Vertex *  v  )  const [inline]

returns true iff the vertex v is exposed (not matched) in this matching.

bool Matching::isMatched (  VertexLabel  vlbl  )  const [inline]

returns true iff the vertex with the label vlbl is matched in this matching.

bool Matching::isMatched (  Vertex *  v  )  const [inline]

returns true iff the vertex v is matched in this matching.

void Matching::printVerboseInfo (  void   )  const

void Matching::removeEdge (  const Edge &  e  )

remove an edge from the matching Parameters: e  the edge to remove The edge e _must_ be in this matching

void Matching::setCardinality (  unsigned long  c  )  [private]

set the cardinality (thereby updating PrOut)

---

Member Data Documentation

unsigned long Matching::Cardinality [private]

std::list<Vertex*> Matching::ExposedVertices [private]

std::list<Edge*> Matching::MatchingEdges [private]

ProgressOutput* Matching::PrOut [private]

Graph* Matching::TheGraph [private]

std::vector<VertexInfo> Matching::VertexInformation [private]

---

The documentation for this class was generated from the following files:

• Matching.h
• Matching.cc

---