steghide
0.5.1
|
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 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 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... | |
Graph * | TheGraph |
the graph underlying this Matching More... | |
ProgressOutput * | PrOut |
the ProgressOutput object that will print the number of matched vertices (as percentage) More... | |
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.
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 | ( | const Edge & | e | ) |
add an edge to the matching
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,
|
inline |
augment this matching along the given augmenting path
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
|
inline |
get the cardinality (the number of matched edges)
|
inline |
get the list of all edges in this matching
|
inline |
|
inline |
get access to the std::list of exposed vertices
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
get the edge that is in the matching and adjacent to v
|
inline |
does this matching include the edge e ?
bool Matching::includesEdge | ( | const Edge & | e | ) | const |
|
inline |
returns true iff the vertex v is exposed (not matched) in this matching.
|
inline |
returns true iff the vertex with the label vlbl is exposed (not matched) in this matching.
|
inline |
returns true iff the vertex v is matched in this matching.
|
inline |
returns true iff the vertex with the label vlbl 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 |
The edge e must be in this matching
|
private |
set the cardinality (thereby updating PrOut)
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |