00001 /* 00002 * steghide 0.5.1 - a steganography program 00003 * Copyright (C) 1999-2003 Stefan Hetzl <shetzl@chello.at> 00004 * 00005 * This program is free software; you can redistribute it and/or 00006 * modify it under the terms of the GNU General Public License 00007 * as published by the Free Software Foundation; either version 2 00008 * of the License, or (at your option) any later version. 00009 * 00010 * This program is distributed in the hope that it will be useful, 00011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 * GNU General Public License for more details. 00014 * 00015 * You should have received a copy of the GNU General Public License 00016 * along with this program; if not, write to the Free Software 00017 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 00018 * 00019 */ 00020 00021 #ifndef SH_MATCHING_H 00022 #define SH_MATCHING_H 00023 00024 #include <list> 00025 #include <vector> 00026 00027 #include "Vertex.h" 00028 #include "common.h" 00029 00030 class Edge ; 00031 class ProgressOutput ; 00032 00041 class Matching { 00042 public: 00048 Matching (Graph* g, ProgressOutput* po = NULL) ; 00049 00050 ~Matching (void) ; 00051 00055 bool isMatched (Vertex *v) const 00056 { return VertexInformation[v->getLabel()].isMatched() ; } ; 00057 00061 bool isMatched (VertexLabel vlbl) const 00062 { return VertexInformation[vlbl].isMatched() ; } ; 00063 00067 bool isExposed (Vertex *v) const 00068 { return VertexInformation[v->getLabel()].isExposed() ; } ; 00069 00073 bool isExposed (VertexLabel vlbl) const 00074 { return VertexInformation[vlbl].isExposed() ; } ; 00075 00080 const Edge* getMatchingEdge (Vertex *v) const 00081 { return VertexInformation[v->getLabel()].getMatchingEdge() ; } ; 00082 00087 bool includesEdge (const Edge* e) const { return includesEdge(*e) ; } ; 00088 bool includesEdge (const Edge& e) const ; 00089 00093 unsigned long getCardinality (void) const 00094 { return Cardinality ; } ; 00095 00096 const std::list<Vertex*>& getExposedVertices (void) const 00097 { return ExposedVertices ; } ; 00098 00103 float getMatchedRate (void) const ; 00104 00108 float getAvgEdgeWeight (void) const ; 00109 00118 const std::list<Vertex*> *getExposedVerticesLink (void) const 00119 { return &ExposedVertices ; } ; 00120 00128 void addEdge (const Edge& e) ; 00129 void addEdge (Edge* e) { addEdge(*e) ; } ; 00130 00137 void removeEdge (const Edge& e) ; 00138 00142 const std::list<Edge*>& getEdges (void) const 00143 { return MatchingEdges ; } ; 00144 00154 Matching& augment (const Edge** path, unsigned long len) ; 00155 00156 Matching& augment (const std::vector<Edge*>& path) ; 00157 00158 void printVerboseInfo (void) const ; 00159 00160 private: 00165 class VertexInfo { 00166 public: 00167 VertexInfo (std::list<Edge*>::iterator mit) 00168 { setMatched (mit) ; } ; 00169 00170 VertexInfo (std::list<Vertex*>::iterator eit) 00171 { setExposed (eit) ; } ; 00172 00173 bool isExposed (void) const 00174 { return !Matched ; } ; 00175 00176 bool isMatched (void) const 00177 { return Matched ; } ; 00178 00179 Edge *getMatchingEdge (void) const 00180 { return *MatchedIterator ; } ; 00181 00182 std::list<Edge*>::iterator getMatchedIterator (void) const 00183 { return MatchedIterator ; } ; 00184 00185 std::list<Vertex*>::iterator getExposedIterator (void) const 00186 { return ExposedIterator ; } ; 00187 00188 void setMatched (std::list<Edge*>::iterator mit) 00189 { Matched = true ; MatchedIterator = mit ; } ; 00190 00191 void setExposed (std::list<Vertex*>::iterator eit) 00192 { Matched = false ; ExposedIterator = eit ; } ; 00193 00194 private: 00195 bool Matched ; 00197 std::list<Edge*>::iterator MatchedIterator ; 00199 std::list<Vertex*>::iterator ExposedIterator ; 00200 } ; 00201 00203 std::vector<VertexInfo> VertexInformation ; 00204 00206 std::list<Vertex*> ExposedVertices ; 00207 00209 std::list<Edge*> MatchingEdges ; 00210 00212 unsigned long Cardinality ; 00213 00215 Graph* TheGraph ; 00216 00218 ProgressOutput* PrOut ; 00219 00223 void setCardinality (unsigned long c) ; 00224 00225 public: 00226 bool check (void) const ; 00227 bool check_MatchingEdges_vs_VertexInformation (void) const ; 00228 bool check_ExposedVertices_vs_VertexInformation (void) const ; 00229 bool check_VertexInformation_Integrity (void) const ; 00230 00231 bool check_ValidAugPath (const std::vector<Edge*>& path) const ; 00232 } ; 00233 00234 #endif // ndef SH_MATCHING_H