steghide  0.5.1
Classes | Public Member Functions | Private Member Functions | Private Attributes | List of all members
Matching Class Reference

represent a matching on a graph More...

#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 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 More...
 
std::list< Vertex * > ExposedVertices
 the std::list of all exposed vertices More...
 
std::list< Edge * > MatchingEdges
 the std::list of all edges in the matching More...
 
unsigned long Cardinality
 the number of edges in the matching More...
 
GraphTheGraph
 the graph underlying this Matching More...
 
ProgressOutputPrOut
 the ProgressOutput object that will print the number of matched vertices (as percentage) 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::Matching ( Graph g,
ProgressOutput po = NULL 
)

create an empty matching that is ready for adding and augmenting

Parameters
gthe underlying graph
poa ProgressOutput object that will print the number of matched vertices (in percent)

§ ~Matching()

Matching::~Matching ( void  )

Member Function Documentation

§ addEdge() [1/2]

void Matching::addEdge ( const Edge e)

add an edge to the matching

Parameters
ethe 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,

§ 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
pathan augmenting path
lenthe 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
inline

does this matching include the edge e ?

Returns
true iff the edge e is element of this matching

§ includesEdge() [2/2]

bool Matching::includesEdge ( const Edge e) const

§ 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]

bool Matching::isExposed ( VertexLabel  vlbl) const
inline

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]

bool Matching::isMatched ( VertexLabel  vlbl) const
inline

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
ethe edge to remove

The edge e must be in this matching

§ setCardinality()

void Matching::setCardinality ( unsigned long  c)
private

set the cardinality (thereby updating PrOut)

Member Data Documentation

§ Cardinality

unsigned long Matching::Cardinality
private

§ ExposedVertices

std::list<Vertex*> Matching::ExposedVertices
private

§ MatchingEdges

std::list<Edge*> Matching::MatchingEdges
private

§ PrOut

ProgressOutput* Matching::PrOut
private

§ TheGraph

Graph* Matching::TheGraph
private

§ VertexInformation

std::vector<VertexInfo> Matching::VertexInformation
private

The documentation for this class was generated from the following files: