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