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
30class Edge ;
31class ProgressOutput ;
32
41class 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:
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 ;
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
Definition: Edge.h:28
a graph constructed from a cover file and a message to be embedded
Definition: Graph.h:51
contains information about a vertex that is possibly in a matching
Definition: Matching.h:165
bool isMatched(void) const
Definition: Matching.h:176
std::list< Vertex * >::iterator getExposedIterator(void) const
Definition: Matching.h:185
std::list< Edge * >::iterator MatchedIterator
an iterator into the list of matched edges (only valid if this vertex is matched)
Definition: Matching.h:197
Edge * getMatchingEdge(void) const
Definition: Matching.h:179
bool isExposed(void) const
Definition: Matching.h:173
void setExposed(std::list< Vertex * >::iterator eit)
Definition: Matching.h:191
void setMatched(std::list< Edge * >::iterator mit)
Definition: Matching.h:188
std::list< Vertex * >::iterator ExposedIterator
an iterator into the list of exposed vertices (only valid if this vertex is exposed)
Definition: Matching.h:199
VertexInfo(std::list< Edge * >::iterator mit)
Definition: Matching.h:167
bool Matched
Definition: Matching.h:195
VertexInfo(std::list< Vertex * >::iterator eit)
Definition: Matching.h:170
std::list< Edge * >::iterator getMatchedIterator(void) const
Definition: Matching.h:182
represent a matching on a graph
Definition: Matching.h:41
unsigned long Cardinality
the number of edges in the matching
Definition: Matching.h:212
void removeEdge(const Edge &e)
Definition: Matching.cc:87
std::vector< VertexInfo > VertexInformation
contains a VertexInfo object for every vertex
Definition: Matching.h:203
bool isMatched(Vertex *v) const
Definition: Matching.h:55
unsigned long getCardinality(void) const
Definition: Matching.h:93
std::list< Edge * > MatchingEdges
the std::list of all edges in the matching
Definition: Matching.h:209
Matching & augment(const Edge **path, unsigned long len)
Definition: Matching.cc:114
float getMatchedRate(void) const
Definition: Matching.cc:206
bool isExposed(Vertex *v) const
Definition: Matching.h:67
bool check(void) const
Definition: Matching.cc:228
bool check_MatchingEdges_vs_VertexInformation(void) const
Definition: Matching.cc:237
const Edge * getMatchingEdge(Vertex *v) const
Definition: Matching.h:80
ProgressOutput * PrOut
the ProgressOutput object that will print the number of matched vertices (as percentage)
Definition: Matching.h:218
bool includesEdge(const Edge *e) const
Definition: Matching.h:87
void printVerboseInfo(void) const
Definition: Matching.cc:189
bool check_ValidAugPath(const std::vector< Edge * > &path) const
Definition: Matching.cc:298
bool isExposed(VertexLabel vlbl) const
Definition: Matching.h:73
void addEdge(const Edge &e)
Definition: Matching.cc:70
const std::list< Vertex * > & getExposedVertices(void) const
Definition: Matching.h:96
void addEdge(Edge *e)
Definition: Matching.h:129
const std::list< Vertex * > * getExposedVerticesLink(void) const
Definition: Matching.h:118
float getAvgEdgeWeight(void) const
Definition: Matching.cc:211
bool check_VertexInformation_Integrity(void) const
Definition: Matching.cc:276
bool isMatched(VertexLabel vlbl) const
Definition: Matching.h:61
const std::list< Edge * > & getEdges(void) const
Definition: Matching.h:142
void setCardinality(unsigned long c)
Definition: Matching.cc:220
bool check_ExposedVertices_vs_VertexInformation(void) const
Definition: Matching.cc:257
std::list< Vertex * > ExposedVertices
the std::list of all exposed vertices
Definition: Matching.h:206
~Matching(void)
Definition: Matching.cc:44
Graph * TheGraph
the graph underlying this Matching
Definition: Matching.h:215
Matching(Graph *g, ProgressOutput *po=NULL)
Definition: Matching.cc:28
prints the progress to stdout
Definition: ProgressOutput.h:32
a vertex in a graph
Definition: Vertex.h:43
VertexLabel getLabel(void) const
Definition: Vertex.h:98
UWORD32 VertexLabel
Definition: common.h:68