steghide  0.5.1
Graph.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_GRAPH_H
22 #define SH_GRAPH_H
23 
24 #include <iostream>
25 #include <list>
26 #include <map>
27 #include <queue>
28 #include <vector>
29 
30 #include "EdgeIterator.h"
32 #include "common.h"
33 #include "wrapper_hash_set.h"
34 
35 class BitString ;
36 class SampleOccurence ;
37 class Selector ;
38 class Vertex ;
39 class VertexContent ;
40 struct VertexContentsEqual ;
41 
51 class Graph {
52  public:
58  Graph (CvrStgFile* cvr, const BitString& emb, Selector& sel) ;
59 
63  ~Graph (void) ;
64 
68  unsigned long getNumVertices (void) const
69  { return Vertices.size() ; } ;
70 
77  { return Vertices[l] ; } ;
78 
79  void unmarkDeletedAllVertices (void) ;
80 
84  float getAvgVertexDegree (void) const ;
85 
86  void printVerboseInfo (void) ;
87 
92  bool check (bool verbose = false) const ;
97  bool check_Vertices (bool verbose = false) const ;
102  bool check_SampleValues (bool verbose = false) const ;
108  bool check_SampleOccurences (bool verbose = false) const ;
113  bool check_SVALists (bool verbose = false) const ;
114 
115 #ifdef DEBUG
116 
121  void print (void) const ;
122 
123  void print_gml (std::ostream& out) const ;
124  void printVertex_gml (std::ostream& out, Vertex* v, unsigned int recdepth, std::vector<bool>& nodeprinted, std::vector<bool>& edgesprinted, bool start = true) const ;
125  void printPrologue_gml (std::ostream& out) const ;
126  void printEpilogue_gml (std::ostream& out) const ;
127 
128  void print_Vertices (unsigned short spc = 0) const ;
129 #endif
130 
131  private:
132  //
133  // friend-declarations
134  //
136  friend class EdgeIterator ;
138  friend class Vertex ;
139 
141  std::vector<Vertex*> Vertices ;
142 
144  std::vector<SampleValue*> SampleValues ;
145 
147  std::vector<SampleValueAdjacencyList*> SVALists ;
148 
150  std::vector<std::list<SampleOccurence> > SampleOccurences ;
151 
155  std::vector<UWORD32*> NumSampleOccurences ;
156 
158  std::vector<std::list<SampleOccurence> > DeletedSampleOccurences ;
159  std::vector<UWORD32*> NumDeletedSampleOccurences ;
160 
161  std::list<SampleOccurence>::iterator markDeletedSampleOccurence (std::list<SampleOccurence>::iterator it) ;
162  std::list<SampleOccurence>::iterator unmarkDeletedSampleOccurence (std::list<SampleOccurence>::iterator it) ;
163 
164  //
165  // end of friend-declarations
166  // Note: private members of Graph that are declared beyond this point should
167  // not be used by friends.
168  //
169 
176  void constructSamples (const std::vector<SamplePos*> &sposs, std::vector<SampleValue**>& svalues) ;
177 
184  void constructVertices (std::vector<SamplePos*>& sposs, std::vector<SampleValue**>& svalues, const std::vector<EmbValue>& tvalues) ;
185 
192  void constructEdges (void) ;
193 
196  unsigned short SamplesPerVertex ;
197 
198  bool check_SampleOccurences_size (bool verbose = false) const ;
199  bool check_SampleOccurences_correctness (bool verbose = false) const ;
200  bool check_SampleOccurences_completeness (bool verbose = false) const ;
201 
202  bool check_SVALists_size (bool verbose = false) const ;
203  bool check_SVALists_soundness (bool verbose = false) const ;
204  bool check_SVALists_sorted (bool verbose = false) const ;
205  bool check_SVALists_uniqueness (bool verbose = false) const ;
206  bool check_SVALists_completeness (bool verbose = false) const ;
207 } ;
208 
209 #endif // ndef SH_GRAPH_H
bool check_SVALists_completeness(bool verbose=false) const
Definition: Graph.cc:499
std::list< SampleOccurence >::iterator unmarkDeletedSampleOccurence(std::list< SampleOccurence >::iterator it)
Definition: Graph.cc:204
Graph(CvrStgFile *cvr, const BitString &emb, Selector &sel)
Definition: Graph.cc:38
a graph constructed from a cover file and a message to be embedded
Definition: Graph.h:51
a cover-/stego-file
Definition: CvrStgFile.h:46
std::vector< Vertex * > Vertices
contains the vertices in this graph - Vertices[l] is the vertex with label l
Definition: Graph.h:141
void unmarkDeletedAllVertices(void)
Definition: Graph.cc:186
std::vector< UWORD32 * > NumDeletedSampleOccurences
Definition: Graph.h:159
bool check(bool verbose=false) const
Definition: Graph.cc:261
bool check_SVALists_uniqueness(bool verbose=false) const
Definition: Graph.cc:474
std::vector< SampleValueAdjacencyList * > SVALists
contains the sample value adjacency lists (SVALists[v] contains only sample values with embedded valu...
Definition: Graph.h:147
bool check_SampleOccurences_size(bool verbose=false) const
Definition: Graph.cc:336
float getAvgVertexDegree(void) const
Definition: Graph.cc:215
bool check_SampleValues(bool verbose=false) const
Definition: Graph.cc:290
bool check_SVALists_soundness(bool verbose=false) const
Definition: Graph.cc:404
unsigned short SamplesPerVertex
Definition: Graph.h:196
std::vector< UWORD32 * > NumSampleOccurences
Definition: Graph.h:155
CvrStgFile * File
Definition: Graph.h:194
EmbValue EmbValueModulus
Definition: Graph.h:195
Vertex * getVertex(VertexLabel l) const
Definition: Graph.h:76
std::vector< SampleValue * > SampleValues
contains the list of (unique) sample values - SampleValues[l] is the sample value with label l ...
Definition: Graph.h:144
bool check_SVALists_size(bool verbose=false) const
Definition: Graph.cc:389
UWORD32 VertexLabel
Definition: common.h:68
void constructVertices(std::vector< SamplePos *> &sposs, std::vector< SampleValue **> &svalues, const std::vector< EmbValue > &tvalues)
Definition: Graph.cc:113
an adjacency list-like data structur for sample values
Definition: SampleValueAdjacencyList.h:33
a heuristic algorithm for constructing a matching
Definition: WKSConstructionHeuristic.h:48
a random permutation of a random combination
Definition: Selector.h:36
void constructSamples(const std::vector< SamplePos *> &sposs, std::vector< SampleValue **> &svalues)
Definition: Graph.cc:80
void constructEdges(void)
Definition: Graph.cc:122
bool check_SampleOccurences_correctness(bool verbose=false) const
Definition: Graph.cc:348
allows an iteration trough all edges of a vertex
Definition: EdgeIterator.h:51
Definition: SampleOccurence.h:26
void printVerboseInfo(void)
Definition: Graph.cc:224
unsigned long getNumVertices(void) const
Definition: Graph.h:68
a string of bits
Definition: BitString.h:42
std::vector< std::list< SampleOccurence > > DeletedSampleOccurences
contains those sample occurences that have been marked as deleted from SampleOccurences ...
Definition: Graph.h:158
bool check_SampleOccurences(bool verbose=false) const
Definition: Graph.cc:327
BYTE EmbValue
Definition: common.h:66
std::vector< std::list< SampleOccurence > > SampleOccurences
SampleOccurences[l] contains all occurences of the sample value with label l.
Definition: Graph.h:150
bool check_SVALists_sorted(bool verbose=false) const
Definition: Graph.cc:439
std::list< SampleOccurence >::iterator markDeletedSampleOccurence(std::list< SampleOccurence >::iterator it)
Definition: Graph.cc:193
bool check_SVALists(bool verbose=false) const
Definition: Graph.cc:378
bool check_SampleOccurences_completeness(bool verbose=false) const
Definition: Graph.cc:363
bool check_Vertices(bool verbose=false) const
Definition: Graph.cc:271
a vertex in a graph
Definition: Vertex.h:43
~Graph(void)
Definition: Graph.cc:166