represent a matching on a graph More...

#include <Matching.h>

Classes
class	VertexInfo
	contains information about a vertex that is possibly in a matching More...

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)

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::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::~Matching ( void )

Member Function Documentation

◆ addEdge() [1/2]

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,

◆ addEdge() [2/2]

void Matching::addEdge ( Edge * e )

inline

◆ augment() [1/2]

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.

◆ augment() [2/2]

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

◆ check()

bool Matching::check ( void ) const

◆ check_ExposedVertices_vs_VertexInformation()

bool Matching::check_ExposedVertices_vs_VertexInformation ( void ) const

◆ check_MatchingEdges_vs_VertexInformation()

bool Matching::check_MatchingEdges_vs_VertexInformation ( void ) const

◆ check_ValidAugPath()

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

◆ check_VertexInformation_Integrity()

bool Matching::check_VertexInformation_Integrity ( void ) const

◆ getAvgEdgeWeight()

float Matching::getAvgEdgeWeight ( void ) const

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

◆ getCardinality()

unsigned long Matching::getCardinality ( void ) const

inline

get the cardinality (the number of matched edges)

◆ getEdges()

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

inline

get the list of all edges in this matching

◆ getExposedVertices()

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

inline

◆ getExposedVerticesLink()

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.

◆ getMatchedRate()

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

◆ getMatchingEdge()

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

◆ includesEdge() [1/2]

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

◆ includesEdge() [2/2]

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

◆ isExposed() [1/2]

bool Matching::isExposed ( Vertex * v ) const

inline

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

◆ isExposed() [2/2]

bool Matching::isExposed ( VertexLabel vlbl ) const

inline

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

◆ isMatched() [1/2]

bool Matching::isMatched ( Vertex * v ) const

inline

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

◆ isMatched() [2/2]

bool Matching::isMatched ( VertexLabel vlbl ) const

inline

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

◆ printVerboseInfo()

void Matching::printVerboseInfo ( void ) const

◆ removeEdge()

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

◆ setCardinality()

void Matching::setCardinality ( unsigned long c )

private

set the cardinality (thereby updating PrOut)

Member Data Documentation

◆ Cardinality

unsigned long Matching::Cardinality

private

◆ ExposedVertices

std::list<Vertex*> Matching::ExposedVertices

private

◆ MatchingEdges

std::list<Edge*> Matching::MatchingEdges

private

◆ PrOut

ProgressOutput* Matching::PrOut

private

◆ TheGraph

Graph* Matching::TheGraph

private

◆ VertexInformation

std::vector<VertexInfo> Matching::VertexInformation

private

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

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Matching()

◆ ~Matching()

Member Function Documentation

◆ addEdge() [1/2]

◆ addEdge() [2/2]

◆ augment() [1/2]

◆ augment() [2/2]

◆ check()

◆ check_ExposedVertices_vs_VertexInformation()

◆ check_MatchingEdges_vs_VertexInformation()

◆ check_ValidAugPath()

◆ check_VertexInformation_Integrity()

◆ getAvgEdgeWeight()

◆ getCardinality()

◆ getEdges()

◆ getExposedVertices()

◆ getExposedVerticesLink()

◆ getMatchedRate()

◆ getMatchingEdge()

◆ includesEdge() [1/2]

◆ includesEdge() [2/2]

◆ isExposed() [1/2]

◆ isExposed() [2/2]

◆ isMatched() [1/2]

◆ isMatched() [2/2]

◆ printVerboseInfo()

◆ removeEdge()

◆ setCardinality()

Member Data Documentation

◆ Cardinality

◆ ExposedVertices

◆ MatchingEdges

◆ PrOut

◆ TheGraph

◆ VertexInformation