Matching Class Reference
represent a matching on a graph
More...
#include <Matching.h>
List of all members.
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
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:
-
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:
-
The edge e _must_ be in this matching
void Matching::setCardinality |
( |
unsigned long |
c |
) |
[private] |
set the cardinality (thereby updating PrOut)
Member Data Documentation
The documentation for this class was generated from the following files: