00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
#ifndef SH_WKSCONSTRUCTIONHEURISTIC_H
00022
#define SH_WKSCONSTRUCTIONHEURISTIC_H
00023
00024
#include <functional>
00025
#include <queue>
00026
#include <vector>
00027
00028
class Edge ;
00029
class Graph ;
00030
class Matching ;
00031
#include "MatchingAlgorithm.h"
00032
class ProgressOutput ;
00033
class Vertex ;
00034
#include "common.h"
00035
00048 class WKSConstructionHeuristic :
public MatchingAlgorithm {
00049
public:
00054
WKSConstructionHeuristic (
Graph* g,
Matching* m,
float goal = 100.0) ;
00055
00056 virtual ~WKSConstructionHeuristic (
void) {} ;
00057
00058 const char*
getName (
void)
const
00059
{
return "Weighted Karp&Sipser Construction Heuristic" ; } ;
00060
00061
void run (
void) ;
00062
00073 class LongerShortestEdge :
public std::binary_function<Vertex*,Vertex*,bool> {
00074
public:
00075
bool operator() (
const Vertex *v1,
const Vertex *v2) ;
00076 } ;
00077
00078
#ifdef DEBUG
00079
void print (
unsigned short spc = 0) ;
00080
void printPQ (std::priority_queue<
Vertex*, std::vector<Vertex*>,
LongerShortestEdge>& pq) ;
00081
#endif
00082
00083
private:
00087
Vertex *
findVertexDeg1 (
void) ;
00088
00092
Vertex *
findVertexDegG (
void) ;
00093
00097
void checkNeighboursDeg1 (
Vertex *v) ;
00098
00100 std::priority_queue<Vertex*, std::vector<Vertex*>,
LongerShortestEdge>
VerticesDeg1 ;
00102 std::priority_queue<Vertex*, std::vector<Vertex*>,
LongerShortestEdge>
VerticesDegG ;
00103 } ;
00104
00105
#endif // ndef SH_WKSCONSTRUCTIONHEURISTIC_H