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 33 /** 34 * \class Matching 35 * \brief represent a matching on a graph 36 * 37 * A Matching object will copy all Edges that are passed to it and will take care of them, i.e. 38 * delete them if they are no longer used. Edges do only "leave" a Matching object as const 39 * pointers. 40 **/ 41 class Matching { 42 public: 43 /** 44 * create an empty matching that is ready for adding and augmenting 45 * \param g the underlying graph 46 * \param po a ProgressOutput object that will print the number of matched vertices (in percent) 47 **/ 48 Matching (Graph* g, ProgressOutput* po = NULL) ; 49 50 ~Matching (void) ; 51 52 /** 53 * returns true iff the vertex v is matched in this matching. 54 **/ isMatched(Vertex * v)55 bool isMatched (Vertex *v) const 56 { return VertexInformation[v->getLabel()].isMatched() ; } ; 57 58 /** 59 * returns true iff the vertex with the label vlbl is matched in this matching. 60 **/ isMatched(VertexLabel vlbl)61 bool isMatched (VertexLabel vlbl) const 62 { return VertexInformation[vlbl].isMatched() ; } ; 63 64 /** 65 * returns true iff the vertex v is exposed (not matched) in this matching. 66 **/ isExposed(Vertex * v)67 bool isExposed (Vertex *v) const 68 { return VertexInformation[v->getLabel()].isExposed() ; } ; 69 70 /** 71 * returns true iff the vertex with the label vlbl is exposed (not matched) in this matching. 72 **/ isExposed(VertexLabel vlbl)73 bool isExposed (VertexLabel vlbl) const 74 { return VertexInformation[vlbl].isExposed() ; } ; 75 76 /** 77 * get the edge that is in the matching and adjacent to v 78 * \return the matched edge or NULL if v is exposed 79 **/ getMatchingEdge(Vertex * v)80 const Edge* getMatchingEdge (Vertex *v) const 81 { return VertexInformation[v->getLabel()].getMatchingEdge() ; } ; 82 83 /** 84 * does this matching include the edge e ? 85 * \return true iff the edge e is element of this matching 86 **/ includesEdge(const Edge * e)87 bool includesEdge (const Edge* e) const { return includesEdge(*e) ; } ; 88 bool includesEdge (const Edge& e) const ; 89 90 /** 91 * get the cardinality (the number of matched edges) 92 **/ getCardinality(void)93 unsigned long getCardinality (void) const 94 { return Cardinality ; } ; 95 getExposedVertices(void)96 const std::list<Vertex*>& getExposedVertices (void) const 97 { return ExposedVertices ; } ; 98 99 /** 100 * get the rate of vertices of the underlying graph that are currently matched in this matching 101 * \return a value between 0 and 1 102 **/ 103 float getMatchedRate (void) const ; 104 105 /** 106 * get the average weight of all edges that are in this matching 107 **/ 108 float getAvgEdgeWeight (void) const ; 109 110 /** 111 * get access to the std::list of exposed vertices 112 * \return a pointer to the std::list of exposed vertices in this matching. 113 * 114 * The std::list that is pointed to by return value contains the exposed vertices 115 * even after augment has been called (it is the ExposedVertices member) an 116 * arbitrary number of times. 117 **/ getExposedVerticesLink(void)118 const std::list<Vertex*> *getExposedVerticesLink (void) const 119 { return &ExposedVertices ; } ; 120 121 /** 122 * add an edge to the matching 123 * \param e the edge to add. 124 * 125 * For e=(v1,v2): neither v1 nor v2 are allowed to be adjacent 126 * to an edge that is already in the matching, 127 **/ 128 void addEdge (const Edge& e) ; addEdge(Edge * e)129 void addEdge (Edge* e) { addEdge(*e) ; } ; 130 131 /** 132 * remove an edge from the matching 133 * \param e the edge to remove 134 * 135 * The edge e _must_ be in this matching 136 **/ 137 void removeEdge (const Edge& e) ; 138 139 /** 140 * get the list of all edges in this matching 141 **/ getEdges(void)142 const std::list<Edge*>& getEdges (void) const 143 { return MatchingEdges ; } ; 144 145 /** 146 * augment this matching along the given augmenting path 147 * \param path an augmenting path 148 * \param len the length (number of edges) of the augmenting path 149 * 150 * An augementing path is a path where edges with odd indices (the first, third,...) are not 151 * in the matching and edges with even indices are and the path has 152 * an odd length. 153 **/ 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: 161 /** 162 * \class VertexInfo 163 * \brief contains information about a vertex that is possibly in a matching 164 **/ 165 class VertexInfo { 166 public: VertexInfo(std::list<Edge * >::iterator mit)167 VertexInfo (std::list<Edge*>::iterator mit) 168 { setMatched (mit) ; } ; 169 VertexInfo(std::list<Vertex * >::iterator eit)170 VertexInfo (std::list<Vertex*>::iterator eit) 171 { setExposed (eit) ; } ; 172 isExposed(void)173 bool isExposed (void) const 174 { return !Matched ; } ; 175 isMatched(void)176 bool isMatched (void) const 177 { return Matched ; } ; 178 getMatchingEdge(void)179 Edge *getMatchingEdge (void) const 180 { return *MatchedIterator ; } ; 181 getMatchedIterator(void)182 std::list<Edge*>::iterator getMatchedIterator (void) const 183 { return MatchedIterator ; } ; 184 getExposedIterator(void)185 std::list<Vertex*>::iterator getExposedIterator (void) const 186 { return ExposedIterator ; } ; 187 setMatched(std::list<Edge * >::iterator mit)188 void setMatched (std::list<Edge*>::iterator mit) 189 { Matched = true ; MatchedIterator = mit ; } ; 190 setExposed(std::list<Vertex * >::iterator eit)191 void setExposed (std::list<Vertex*>::iterator eit) 192 { Matched = false ; ExposedIterator = eit ; } ; 193 194 private: 195 bool Matched ; 196 /// an iterator into the list of matched edges (only valid if this vertex is matched) 197 std::list<Edge*>::iterator MatchedIterator ; 198 /// an iterator into the list of exposed vertices (only valid if this vertex is exposed) 199 std::list<Vertex*>::iterator ExposedIterator ; 200 } ; 201 202 /// contains a VertexInfo object for every vertex 203 std::vector<VertexInfo> VertexInformation ; 204 205 /// the std::list of all exposed vertices 206 std::list<Vertex*> ExposedVertices ; 207 208 /// the std::list of all edges in the matching 209 std::list<Edge*> MatchingEdges ; 210 211 /// the number of edges in the matching 212 unsigned long Cardinality ; 213 214 /// the graph underlying this Matching 215 Graph* TheGraph ; 216 217 /// the ProgressOutput object that will print the number of matched vertices (as percentage) 218 ProgressOutput* PrOut ; 219 220 /** 221 * set the cardinality (thereby updating PrOut) 222 **/ 223 void setCardinality (unsigned long c) ; 224 225 public: 226 bool check (void) const ; 227 bool check_MatchingEdges_vs_VertexInformation (void) const ; 228 bool check_ExposedVertices_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 235