WKSConstructionHeuristic.h
Go to the documentation of this file.
/*
* steghide 0.5.1 - a steganography program
* Copyright (C) 1999-2003 Stefan Hetzl <shetzl@chello.at>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*
*/
#ifndef SH_WKSCONSTRUCTIONHEURISTIC_H
#define SH_WKSCONSTRUCTIONHEURISTIC_H
#include <functional>
#include <queue>
#include <vector>
class Edge ;
class Graph ;
class Matching ;
#include "MatchingAlgorithm.h"
class ProgressOutput ;
class Vertex ;
#include "common.h"
class WKSConstructionHeuristic : public MatchingAlgorithm {
public:
WKSConstructionHeuristic (Graph* g, Matching* m, float goal = 100.0) ;
virtual ~WKSConstructionHeuristic (void) {} ;
const char* getName (void) const
{ return "Weighted Karp&Sipser Construction Heuristic" ; } ;
void run (void) ;
class LongerShortestEdge : public std::binary_function<Vertex*,Vertex*,bool> {
public:
bool operator() (const Vertex *v1, const Vertex *v2) ;
} ;
#ifdef DEBUG
void print (unsigned short spc = 0) ;
void printPQ (std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge>& pq) ;
#endif
private:
Vertex *findVertexDeg1 (void) ;
Vertex *findVertexDegG (void) ;
void checkNeighboursDeg1 (Vertex *v) ;
std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge> VerticesDeg1 ;
std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge> VerticesDegG ;
} ;
#endif // ndef SH_WKSCONSTRUCTIONHEURISTIC_H
MatchingAlgorithm.h
WKSConstructionHeuristic::~WKSConstructionHeuristic
virtual ~WKSConstructionHeuristic(void)
Definition: WKSConstructionHeuristic.h:56
Graph
a graph constructed from a cover file and a message to be embedded
Definition: Graph.h:51
WKSConstructionHeuristic::LongerShortestEdge
a comparison operator
Definition: WKSConstructionHeuristic.h:73
Edge
Definition: Edge.h:28
WKSConstructionHeuristic::checkNeighboursDeg1
void checkNeighboursDeg1(Vertex *v)
Definition: WKSConstructionHeuristic.cc:98
ProgressOutput
prints the progress to stdout
Definition: ProgressOutput.h:32
WKSConstructionHeuristic::getName
const char * getName(void) const
Definition: WKSConstructionHeuristic.h:58
WKSConstructionHeuristic::WKSConstructionHeuristic
WKSConstructionHeuristic(Graph *g, Matching *m, float goal=100.0)
Definition: WKSConstructionHeuristic.cc:27
WKSConstructionHeuristic::run
void run(void)
Definition: WKSConstructionHeuristic.cc:52
WKSConstructionHeuristic::VerticesDegG
std::priority_queue< Vertex *, std::vector< Vertex * >, LongerShortestEdge > VerticesDegG
contains all vertices with degree greater than 1
Definition: WKSConstructionHeuristic.h:102
WKSConstructionHeuristic::VerticesDeg1
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
WKSConstructionHeuristic
a heuristic algorithm for constructing a matching
Definition: WKSConstructionHeuristic.h:48
WKSConstructionHeuristic::findVertexDeg1
Vertex * findVertexDeg1(void)
Definition: WKSConstructionHeuristic.cc:153
Matching
represent a matching on a graph
Definition: Matching.h:41
WKSConstructionHeuristic::findVertexDegG
Vertex * findVertexDegG(void)
Definition: WKSConstructionHeuristic.cc:124
common.h
MatchingAlgorithm
Definition: MatchingAlgorithm.h:27
WKSConstructionHeuristic::LongerShortestEdge::operator()
bool operator()(const Vertex *v1, const Vertex *v2)
Definition: WKSConstructionHeuristic.cc:172
Vertex
a vertex in a graph
Definition: Vertex.h:43