represent a matching on a graph
More...
#include <Matching.h>
|
class | VertexInfo |
| contains information about a vertex that is possibly in a matching More...
|
|
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.
◆ Matching()
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 |
| ) |
|
◆ addEdge() [1/2]
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,
◆ 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]
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]
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
-
The edge e must be in this matching
◆ setCardinality()
void Matching::setCardinality |
( |
unsigned long |
c | ) |
|
|
private |
set the cardinality (thereby updating PrOut)
◆ Cardinality
unsigned long Matching::Cardinality |
|
private |
◆ ExposedVertices
std::list<Vertex*> Matching::ExposedVertices |
|
private |
◆ MatchingEdges
std::list<Edge*> Matching::MatchingEdges |
|
private |
◆ PrOut
◆ TheGraph
Graph* Matching::TheGraph |
|
private |
◆ VertexInformation
std::vector<VertexInfo> Matching::VertexInformation |
|
private |
The documentation for this class was generated from the following files: