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

bool Matching::isMatched

(

Vertex *

v

)

const [inline]

returns true iff the vertex v is 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::isExposed

(

Vertex *

v

)

const [inline]

returns true iff the vertex v is exposed (not matched) in 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.

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 [inline]

does this matching include the edge e ?

Returns:

true iff the edge e is element of this matching

bool Matching::includesEdge

(

const Edge &

e

)

const

unsigned long Matching::getCardinality

(

void

)

const [inline]

get the cardinality (the number of matched edges)

const std::list<Vertex*>& Matching::getExposedVertices

(

void

)

const [inline]

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

float Matching::getAvgEdgeWeight

(

void

)

const

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

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.

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,

void Matching::addEdge

(

Edge *

e

)

[inline]

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

const std::list<Edge*>& Matching::getEdges

(

void

)

const [inline]

get the list of all edges in this matching

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.

Matching & Matching::augment

(

const std::vector< Edge * > &

path

)

void Matching::printVerboseInfo

(

void

)

const

void Matching::setCardinality

(

unsigned long

c

)

[private]

set the cardinality (thereby updating PrOut)

bool Matching::check

(

void

)

const

bool Matching::check_MatchingEdges_vs_VertexInformation

(

void

)

const

bool Matching::check_ExposedVertices_vs_VertexInformation

(

void

)

const

bool Matching::check_VertexInformation_Integrity

(

void

)

const

bool Matching::check_ValidAugPath

(

const std::vector< Edge * > &

path

)

const

---

Member Data Documentation

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

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

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

unsigned long Matching::Cardinality [private]

Graph* Matching::TheGraph [private]

ProgressOutput* Matching::PrOut [private]

---

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

• Matching.h
• Matching.cc

---