Matching.h
Go to the documentation of this file.
/*
* steghide 0.5.1 - a steganography program
* Copyright (C) 1999-2003 Stefan Hetzl <shetzl@chello.at>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
*/
#ifndef SH_MATCHING_H
#define SH_MATCHING_H
#include <list>
#include <vector>
#include "Vertex.h"
#include "common.h"
class Edge ;
class ProgressOutput ;
class Matching {
public:
Matching (Graph* g, ProgressOutput* po = NULL) ;
~Matching (void) ;
bool isMatched (Vertex *v) const
{ return VertexInformation[v->getLabel()].isMatched() ; } ;
bool isMatched (VertexLabel vlbl) const
{ return VertexInformation[vlbl].isMatched() ; } ;
bool isExposed (Vertex *v) const
{ return VertexInformation[v->getLabel()].isExposed() ; } ;
bool isExposed (VertexLabel vlbl) const
{ return VertexInformation[vlbl].isExposed() ; } ;
const Edge* getMatchingEdge (Vertex *v) const
{ return VertexInformation[v->getLabel()].getMatchingEdge() ; } ;
bool includesEdge (const Edge* e) const { return includesEdge(*e) ; } ;
bool includesEdge (const Edge& e) const ;
unsigned long getCardinality (void) const
{ return Cardinality ; } ;
const std::list<Vertex*>& getExposedVertices (void) const
{ return ExposedVertices ; } ;
float getMatchedRate (void) const ;
float getAvgEdgeWeight (void) const ;
const std::list<Vertex*> *getExposedVerticesLink (void) const
{ return &ExposedVertices ; } ;
void addEdge (const Edge& e) ;
void addEdge (Edge* e) { addEdge(*e) ; } ;
void removeEdge (const Edge& e) ;
const std::list<Edge*>& getEdges (void) const
{ return MatchingEdges ; } ;
Matching& augment (const Edge** path, unsigned long len) ;
Matching& augment (const std::vector<Edge*>& path) ;
void printVerboseInfo (void) const ;
private:
class VertexInfo {
public:
VertexInfo (std::list<Edge*>::iterator mit)
{ setMatched (mit) ; } ;
VertexInfo (std::list<Vertex*>::iterator eit)
{ setExposed (eit) ; } ;
bool isExposed (void) const
{ return !Matched ; } ;
bool isMatched (void) const
{ return Matched ; } ;
Edge *getMatchingEdge (void) const
{ return *MatchedIterator ; } ;
std::list<Edge*>::iterator getMatchedIterator (void) const
{ return MatchedIterator ; } ;
std::list<Vertex*>::iterator getExposedIterator (void) const
{ return ExposedIterator ; } ;
void setMatched (std::list<Edge*>::iterator mit)
{ Matched = true ; MatchedIterator = mit ; } ;
void setExposed (std::list<Vertex*>::iterator eit)
{ Matched = false ; ExposedIterator = eit ; } ;
private:
bool Matched ;
std::list<Edge*>::iterator MatchedIterator ;
std::list<Vertex*>::iterator ExposedIterator ;
} ;
std::vector<VertexInfo> VertexInformation ;
std::list<Vertex*> ExposedVertices ;
std::list<Edge*> MatchingEdges ;
unsigned long Cardinality ;
Graph* TheGraph ;
ProgressOutput* PrOut ;
void setCardinality (unsigned long c) ;
public:
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 ;
} ;
#endif // ndef SH_MATCHING_H
Matching::Matching
Matching(Graph *g, ProgressOutput *po=NULL)
Definition: Matching.cc:28
Matching::setCardinality
void setCardinality(unsigned long c)
Definition: Matching.cc:220
Matching::TheGraph
Graph * TheGraph
the graph underlying this Matching
Definition: Matching.h:215
Matching::VertexInfo::getMatchedIterator
std::list< Edge * >::iterator getMatchedIterator(void) const
Definition: Matching.h:182
Matching::VertexInfo::MatchedIterator
std::list< Edge * >::iterator MatchedIterator
an iterator into the list of matched edges (only valid if this vertex is matched) ...
Definition: Matching.h:197
Graph
a graph constructed from a cover file and a message to be embedded
Definition: Graph.h:51
Matching::Cardinality
unsigned long Cardinality
the number of edges in the matching
Definition: Matching.h:212
Matching::getMatchingEdge
const Edge * getMatchingEdge(Vertex *v) const
Definition: Matching.h:80
Matching::getMatchedRate
float getMatchedRate(void) const
Definition: Matching.cc:206
Edge
Definition: Edge.h:28
Matching::VertexInfo
contains information about a vertex that is possibly in a matching
Definition: Matching.h:165
Matching::MatchingEdges
std::list< Edge * > MatchingEdges
the std::list of all edges in the matching
Definition: Matching.h:209
Matching::getAvgEdgeWeight
float getAvgEdgeWeight(void) const
Definition: Matching.cc:211
Matching::isExposed
bool isExposed(Vertex *v) const
Definition: Matching.h:67
ProgressOutput
prints the progress to stdout
Definition: ProgressOutput.h:32
Matching::VertexInfo::getMatchingEdge
Edge * getMatchingEdge(void) const
Definition: Matching.h:179
Matching::check
bool check(void) const
Definition: Matching.cc:228
Matching::check_VertexInformation_Integrity
bool check_VertexInformation_Integrity(void) const
Definition: Matching.cc:276
Matching::PrOut
ProgressOutput * PrOut
the ProgressOutput object that will print the number of matched vertices (as percentage) ...
Definition: Matching.h:218
Matching::removeEdge
void removeEdge(const Edge &e)
Definition: Matching.cc:87
Matching::VertexInfo::Matched
bool Matched
Definition: Matching.h:192
Matching::check_ExposedVertices_vs_VertexInformation
bool check_ExposedVertices_vs_VertexInformation(void) const
Definition: Matching.cc:257
Matching::getCardinality
unsigned long getCardinality(void) const
Definition: Matching.h:93
Matching::isMatched
bool isMatched(VertexLabel vlbl) const
Definition: Matching.h:61
VertexLabel
UWORD32 VertexLabel
Definition: common.h:68
Matching::VertexInfo::setExposed
void setExposed(std::list< Vertex *>::iterator eit)
Definition: Matching.h:191
Matching
represent a matching on a graph
Definition: Matching.h:41
Matching::isMatched
bool isMatched(Vertex *v) const
Definition: Matching.h:55
Vertex.h
Matching::VertexInfo::setMatched
void setMatched(std::list< Edge *>::iterator mit)
Definition: Matching.h:188
Matching::isExposed
bool isExposed(VertexLabel vlbl) const
Definition: Matching.h:73
Matching::augment
Matching & augment(const Edge **path, unsigned long len)
Definition: Matching.cc:114
Matching::VertexInfo::VertexInfo
VertexInfo(std::list< Edge *>::iterator mit)
Definition: Matching.h:167
Matching::VertexInfo::VertexInfo
VertexInfo(std::list< Vertex *>::iterator eit)
Definition: Matching.h:170
Matching::addEdge
void addEdge(const Edge &e)
Definition: Matching.cc:70
Matching::VertexInfo::isMatched
bool isMatched(void) const
Definition: Matching.h:176
Matching::addEdge
void addEdge(Edge *e)
Definition: Matching.h:129
Matching::VertexInfo::isExposed
bool isExposed(void) const
Definition: Matching.h:173
Matching::getEdges
const std::list< Edge * > & getEdges(void) const
Definition: Matching.h:142
Matching::VertexInfo::getExposedIterator
std::list< Vertex * >::iterator getExposedIterator(void) const
Definition: Matching.h:185
Vertex::getLabel
VertexLabel getLabel(void) const
Definition: Vertex.h:98
Matching::~Matching
~Matching(void)
Definition: Matching.cc:44
common.h
Matching::getExposedVertices
const std::list< Vertex * > & getExposedVertices(void) const
Definition: Matching.h:96
Matching::check_ValidAugPath
bool check_ValidAugPath(const std::vector< Edge *> &path) const
Definition: Matching.cc:298
Matching::getExposedVerticesLink
const std::list< Vertex * > * getExposedVerticesLink(void) const
Definition: Matching.h:118
Matching::includesEdge
bool includesEdge(const Edge *e) const
Definition: Matching.h:87
Matching::check_MatchingEdges_vs_VertexInformation
bool check_MatchingEdges_vs_VertexInformation(void) const
Definition: Matching.cc:237
Matching::printVerboseInfo
void printVerboseInfo(void) const
Definition: Matching.cc:189
Vertex
a vertex in a graph
Definition: Vertex.h:43
Matching::VertexInformation
std::vector< VertexInfo > VertexInformation
contains a VertexInfo object for every vertex
Definition: Matching.h:203
Matching::ExposedVertices
std::list< Vertex * > ExposedVertices
the std::list of all exposed vertices
Definition: Matching.h:206
Matching::VertexInfo::ExposedIterator
std::list< Vertex * >::iterator ExposedIterator
an iterator into the list of exposed vertices (only valid if this vertex is exposed) ...
Definition: Matching.h:199