Matching Class Reference

represent a matching on a graph More...

#include <Matching.h>

List of all members.

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 EdgegetMatchingEdge (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
Matchingaugment (const Edge **path, unsigned long len)
Matchingaugment (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< VertexInfoVertexInformation
 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
GraphTheGraph
 the graph underlying this Matching
ProgressOutputPrOut
 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 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 ( 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]


The documentation for this class was generated from the following files:
Generated on Thu Jan 3 18:39:33 2008 for steghide by  doxygen 1.5.4