matching(3)
NAME
Matching - represent a matching on a graph
SYNOPSIS
#include <Matching.h> 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) Classes class VertexInfo contains information about a vertex that is possibly in a matching
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 (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 (void)
Member Function Documentation
- bool Matching::isMatched (Vertex * v) const [inline]
- returns true iff the vertex v is 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::isExposed (Vertex * v) const [inline]
- returns true iff the vertex v is exposed (not matched) in 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. - 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 [inline]
- does this matching include the edge e ?
- Returns:
true iff the edge e is element of this matching
- bool Matching::includesEdge (const Edge & e) const unsigned long Matching::getCardinality (void) const [inline]
- get the cardinality (the number of matched edges)
- const std::list<Vertex*>& Matching::getExposedVertices (void) const
- [inline]
- 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
- float Matching::getAvgEdgeWeight (void) const
- get the average weight of all edges that are in this matching
- 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. - 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,
- void Matching::addEdge (Edge * e) [inline] 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
- const std::list<Edge*>& Matching::getEdges (void) const [inline]
- get the list of all edges in this matching
- 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.
- Matching & Matching::augment (const std::vector< Edge * > & path) void Matching::printVerboseInfo (void) const void Matching::setCardinality (unsigned long c) [private]
- set the cardinality (thereby updating PrOut)
- bool Matching::check (void) const bool Matching::check_MatchingEdges_vs_VertexInformation (void) const bool Matching::check_ExposedVertices_vs_VertexInformation (void) const bool Matching::check_VertexInformation_Integrity (void) const bool Matching::check_ValidAugPath (const std::vector< Edge * > & path)
- const
Member Data Documentation
std::vector<VertexInfo> Matching::VertexInformation [private] std::list<Vertex*> Matching::ExposedVertices [private] std::list<Edge*> Matching::MatchingEdges [private] unsigned long Matching::Cardinality [private] Graph* Matching::TheGraph [private] ProgressOutput* Matching::PrOut [private]
Author
- Generated automatically by Doxygen for steghide from the source code.