steghide  0.5.1
Matching.h
Go to the documentation of this file.
1 /*
2  * steghide 0.5.1 - a steganography program
3  * Copyright (C) 1999-2003 Stefan Hetzl <shetzl@chello.at>
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18  *
19  */
20 
21 #ifndef SH_MATCHING_H
22 #define SH_MATCHING_H
23 
24 #include <list>
25 #include <vector>
26 
27 #include "Vertex.h"
28 #include "common.h"
29 
30 class Edge ;
31 class ProgressOutput ;
32 
41 class Matching {
42  public:
48  Matching (Graph* g, ProgressOutput* po = NULL) ;
49 
50  ~Matching (void) ;
51 
55  bool isMatched (Vertex *v) const
56  { return VertexInformation[v->getLabel()].isMatched() ; } ;
57 
61  bool isMatched (VertexLabel vlbl) const
62  { return VertexInformation[vlbl].isMatched() ; } ;
63 
67  bool isExposed (Vertex *v) const
68  { return VertexInformation[v->getLabel()].isExposed() ; } ;
69 
73  bool isExposed (VertexLabel vlbl) const
74  { return VertexInformation[vlbl].isExposed() ; } ;
75 
80  const Edge* getMatchingEdge (Vertex *v) const
81  { return VertexInformation[v->getLabel()].getMatchingEdge() ; } ;
82 
87  bool includesEdge (const Edge* e) const { return includesEdge(*e) ; } ;
88  bool includesEdge (const Edge& e) const ;
89 
93  unsigned long getCardinality (void) const
94  { return Cardinality ; } ;
95 
96  const std::list<Vertex*>& getExposedVertices (void) const
97  { return ExposedVertices ; } ;
98 
103  float getMatchedRate (void) const ;
104 
108  float getAvgEdgeWeight (void) const ;
109 
118  const std::list<Vertex*> *getExposedVerticesLink (void) const
119  { return &ExposedVertices ; } ;
120 
128  void addEdge (const Edge& e) ;
129  void addEdge (Edge* e) { addEdge(*e) ; } ;
130 
137  void removeEdge (const Edge& e) ;
138 
142  const std::list<Edge*>& getEdges (void) const
143  { return MatchingEdges ; } ;
144 
154  Matching& augment (const Edge** path, unsigned long len) ;
155 
156  Matching& augment (const std::vector<Edge*>& path) ;
157 
158  void printVerboseInfo (void) const ;
159 
160  private:
165  class VertexInfo {
166  public:
167  VertexInfo (std::list<Edge*>::iterator mit)
168  { setMatched (mit) ; } ;
169 
170  VertexInfo (std::list<Vertex*>::iterator eit)
171  { setExposed (eit) ; } ;
172 
173  bool isExposed (void) const
174  { return !Matched ; } ;
175 
176  bool isMatched (void) const
177  { return Matched ; } ;
178 
179  Edge *getMatchingEdge (void) const
180  { return *MatchedIterator ; } ;
181 
182  std::list<Edge*>::iterator getMatchedIterator (void) const
183  { return MatchedIterator ; } ;
184 
185  std::list<Vertex*>::iterator getExposedIterator (void) const
186  { return ExposedIterator ; } ;
187 
188  void setMatched (std::list<Edge*>::iterator mit)
189  { Matched = true ; MatchedIterator = mit ; } ;
190 
191  void setExposed (std::list<Vertex*>::iterator eit)
192  { Matched = false ; ExposedIterator = eit ; } ;
193 
194  private:
195  bool Matched ;
197  std::list<Edge*>::iterator MatchedIterator ;
199  std::list<Vertex*>::iterator ExposedIterator ;
200  } ;
201 
203  std::vector<VertexInfo> VertexInformation ;
204 
206  std::list<Vertex*> ExposedVertices ;
207 
209  std::list<Edge*> MatchingEdges ;
210 
212  unsigned long Cardinality ;
213 
216 
219 
223  void setCardinality (unsigned long c) ;
224 
225  public:
226  bool check (void) const ;
227  bool check_MatchingEdges_vs_VertexInformation (void) const ;
229  bool check_VertexInformation_Integrity (void) const ;
230 
231  bool check_ValidAugPath (const std::vector<Edge*>& path) const ;
232 } ;
233 
234 #endif // ndef SH_MATCHING_H
Matching::includesEdge
bool includesEdge(const Edge *e) const
Definition: Matching.h:87
Matching::VertexInfo::VertexInfo
VertexInfo(std::list< Edge * >::iterator mit)
Definition: Matching.h:167
Matching::Matching
Matching(Graph *g, ProgressOutput *po=NULL)
Definition: Matching.cc:28
Matching::check_MatchingEdges_vs_VertexInformation
bool check_MatchingEdges_vs_VertexInformation(void) const
Definition: Matching.cc:237
Matching
represent a matching on a graph
Definition: Matching.h:41
Matching::VertexInformation
std::vector< VertexInfo > VertexInformation
contains a VertexInfo object for every vertex
Definition: Matching.h:203
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::TheGraph
Graph * TheGraph
the graph underlying this Matching
Definition: Matching.h:215
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::MatchingEdges
std::list< Edge * > MatchingEdges
the std::list of all edges in the matching
Definition: Matching.h:209
Matching::VertexInfo::VertexInfo
VertexInfo(std::list< Vertex * >::iterator eit)
Definition: Matching.h:170
Matching::VertexInfo::getMatchedIterator
std::list< Edge * >::iterator getMatchedIterator(void) const
Definition: Matching.h:182
Matching::check_ExposedVertices_vs_VertexInformation
bool check_ExposedVertices_vs_VertexInformation(void) const
Definition: Matching.cc:257
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
Matching::getMatchedRate
float getMatchedRate(void) const
Definition: Matching.cc:206
VertexLabel
UWORD32 VertexLabel
Definition: common.h:68
Matching::isMatched
bool isMatched(VertexLabel vlbl) const
Definition: Matching.h:61
Matching::VertexInfo::isExposed
bool isExposed(void) const
Definition: Matching.h:173
Matching::check_VertexInformation_Integrity
bool check_VertexInformation_Integrity(void) const
Definition: Matching.cc:276
Matching::getAvgEdgeWeight
float getAvgEdgeWeight(void) const
Definition: Matching.cc:211
Matching::isExposed
bool isExposed(Vertex *v) const
Definition: Matching.h:67
Vertex.h
Matching::VertexInfo::getExposedIterator
std::list< Vertex * >::iterator getExposedIterator(void) const
Definition: Matching.h:185
Matching::removeEdge
void removeEdge(const Edge &e)
Definition: Matching.cc:87
Matching::check
bool check(void) const
Definition: Matching.cc:228
Matching::PrOut
ProgressOutput * PrOut
the ProgressOutput object that will print the number of matched vertices (as percentage)
Definition: Matching.h:218
Matching::addEdge
void addEdge(Edge *e)
Definition: Matching.h:129
Matching::isMatched
bool isMatched(Vertex *v) const
Definition: Matching.h:55
Matching::addEdge
void addEdge(const Edge &e)
Definition: Matching.cc:70
Matching::VertexInfo
contains information about a vertex that is possibly in a matching
Definition: Matching.h:165
Matching::getCardinality
unsigned long getCardinality(void) const
Definition: Matching.h:93
Matching::VertexInfo::getMatchingEdge
Edge * getMatchingEdge(void) const
Definition: Matching.h:179
common.h
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
Matching::isExposed
bool isExposed(VertexLabel vlbl) const
Definition: Matching.h:73
Edge
Definition: Edge.h:28
Matching::augment
Matching & augment(const Edge **path, unsigned long len)
Definition: Matching.cc:114
Matching::~Matching
~Matching(void)
Definition: Matching.cc:44
ProgressOutput
prints the progress to stdout
Definition: ProgressOutput.h:32
Matching::getEdges
const std::list< Edge * > & getEdges(void) const
Definition: Matching.h:142
Graph
a graph constructed from a cover file and a message to be embedded
Definition: Graph.h:51
Vertex
a vertex in a graph
Definition: Vertex.h:43
Matching::getExposedVertices
const std::list< Vertex * > & getExposedVertices(void) const
Definition: Matching.h:96
Matching::VertexInfo::Matched
bool Matched
Definition: Matching.h:192
Matching::setCardinality
void setCardinality(unsigned long c)
Definition: Matching.cc:220
Matching::VertexInfo::setMatched
void setMatched(std::list< Edge * >::iterator mit)
Definition: Matching.h:188
Matching::ExposedVertices
std::list< Vertex * > ExposedVertices
the std::list of all exposed vertices
Definition: Matching.h:206
Matching::VertexInfo::isMatched
bool isMatched(void) const
Definition: Matching.h:176
Matching::printVerboseInfo
void printVerboseInfo(void) const
Definition: Matching.cc:189
Vertex::getLabel
VertexLabel getLabel(void) const
Definition: Vertex.h:98
Matching::VertexInfo::setExposed
void setExposed(std::list< Vertex * >::iterator eit)
Definition: Matching.h:191