steghide  0.5.1
WKSConstructionHeuristic.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_WKSCONSTRUCTIONHEURISTIC_H
22 #define SH_WKSCONSTRUCTIONHEURISTIC_H
23 
24 #include <functional>
25 #include <queue>
26 #include <vector>
27 
28 class Edge ;
29 class Graph ;
30 class Matching ;
31 #include "MatchingAlgorithm.h"
32 class ProgressOutput ;
33 class Vertex ;
34 #include "common.h"
35 
49  public:
54  WKSConstructionHeuristic (Graph* g, Matching* m, float goal = 100.0) ;
55 
56  virtual ~WKSConstructionHeuristic (void) {} ;
57 
58  const char* getName (void) const
59  { return "Weighted Karp&Sipser Construction Heuristic" ; } ;
60 
61  void run (void) ;
62 
73  class LongerShortestEdge : public std::binary_function<Vertex*,Vertex*,bool> {
74  public:
75  bool operator() (const Vertex *v1, const Vertex *v2) ;
76  } ;
77 
78 #ifdef DEBUG
79  void print (unsigned short spc = 0) ;
80  void printPQ (std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge>& pq) ;
81 #endif
82 
83  private:
87  Vertex *findVertexDeg1 (void) ;
88 
92  Vertex *findVertexDegG (void) ;
93 
97  void checkNeighboursDeg1 (Vertex *v) ;
98 
100  std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge> VerticesDeg1 ;
102  std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge> VerticesDegG ;
103 } ;
104 
105 #endif // ndef SH_WKSCONSTRUCTIONHEURISTIC_H
virtual ~WKSConstructionHeuristic(void)
Definition: WKSConstructionHeuristic.h:56
a graph constructed from a cover file and a message to be embedded
Definition: Graph.h:51
a comparison operator
Definition: WKSConstructionHeuristic.h:73
Definition: Edge.h:28
void checkNeighboursDeg1(Vertex *v)
Definition: WKSConstructionHeuristic.cc:98
prints the progress to stdout
Definition: ProgressOutput.h:32
const char * getName(void) const
Definition: WKSConstructionHeuristic.h:58
WKSConstructionHeuristic(Graph *g, Matching *m, float goal=100.0)
Definition: WKSConstructionHeuristic.cc:27
void run(void)
Definition: WKSConstructionHeuristic.cc:52
std::priority_queue< Vertex *, std::vector< Vertex * >, LongerShortestEdge > VerticesDegG
contains all vertices with degree greater than 1
Definition: WKSConstructionHeuristic.h:102
std::priority_queue< Vertex *, std::vector< Vertex * >, LongerShortestEdge > VerticesDeg1
contains all vertices of degree 1 - every vertex in this queue has a correct shortest edge if it stil...
Definition: WKSConstructionHeuristic.h:100
a heuristic algorithm for constructing a matching
Definition: WKSConstructionHeuristic.h:48
Vertex * findVertexDeg1(void)
Definition: WKSConstructionHeuristic.cc:153
represent a matching on a graph
Definition: Matching.h:41
Vertex * findVertexDegG(void)
Definition: WKSConstructionHeuristic.cc:124
Definition: MatchingAlgorithm.h:27
bool operator()(const Vertex *v1, const Vertex *v2)
Definition: WKSConstructionHeuristic.cc:172
a vertex in a graph
Definition: Vertex.h:43