Matching Class Reference

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 More...
std::list< Vertex * > | ExposedVertices
| the std::list of all exposed vertices More...
std::list< Edge * > | MatchingEdges
| the std::list of all edges in the matching More...
unsigned long | Cardinality
| the number of edges in the matching More...
Graph * | TheGraph
| the graph underlying this Matching More...
ProgressOutput * | PrOut
| the ProgressOutput object that will print the number of matched vertices (as percentage) 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::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

inline

does this matching include the edge e ?

Returns
  true iff the edge e is element of this matching

## includesEdge() [2/2]

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

## 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:

- Matching.h
- Matching.cc