#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) |
Matching::Matching | ( | Graph * | g, | |
ProgressOutput * | po = NULL | |||
) |
create an empty matching that is ready for adding and augmenting
g | the underlying graph | |
po | a ProgressOutput object that will print the number of matched vertices (in percent) |
Matching::~Matching | ( | void | ) |
void Matching::addEdge | ( | Edge * | e | ) | [inline] |
void Matching::addEdge | ( | const Edge & | e | ) |
add an edge to the matching
e | the edge to add. |
augment this matching along the given augmenting path
path | an augmenting path | |
len | the length (number of edges) of the augmenting path |
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
float Matching::getMatchedRate | ( | void | ) | const |
get the rate of vertices of the underlying graph that are currently matched in this matching
get the edge that is in the matching and adjacent to v
bool Matching::includesEdge | ( | const Edge & | e | ) | const |
bool Matching::includesEdge | ( | const Edge * | e | ) | const [inline] |
does this matching include the edge e ?
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
e | the edge to remove |
void Matching::setCardinality | ( | unsigned long | c | ) | [private] |
set the cardinality (thereby updating PrOut)
unsigned long Matching::Cardinality [private] |
std::list<Vertex*> Matching::ExposedVertices [private] |
std::list<Edge*> Matching::MatchingEdges [private] |
ProgressOutput* Matching::PrOut [private] |
Graph* Matching::TheGraph [private] |
std::vector<VertexInfo> Matching::VertexInformation [private] |