Main Page | Class Hierarchy | Compound List | File List | Compound Members | File Members

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)


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

void Matching::addEdge Edge e  )  [inline]
 

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,

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:
e the edge to remove
The edge e _must_ be in this matching

void Matching::setCardinality unsigned long  c  )  [private]
 

set the cardinality (thereby updating PrOut)


Member Data Documentation

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]
 


The documentation for this class was generated from the following files:
Generated on Thu Nov 13 23:44:24 2003 for steghide by doxygen 1.3.3