WKSConstructionHeuristic Class Reference

a heuristic algorithm for constructing a matching More...

#include <WKSConstructionHeuristic.h>

Inheritance diagram for WKSConstructionHeuristic:

MatchingAlgorithm

List of all members.

Classes

class  LongerShortestEdge
 a comparison operator More...

Public Member Functions

 WKSConstructionHeuristic (Graph *g, Matching *m, float goal=100.0)
virtual ~WKSConstructionHeuristic (void)
const char * getName (void) const
void run (void)

Private Member Functions

VertexfindVertexDeg1 (void)
VertexfindVertexDegG (void)
void checkNeighboursDeg1 (Vertex *v)

Private Attributes

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 still has degree 1
std::priority_queue< Vertex
*, std::vector< Vertex * >
, LongerShortestEdge
VerticesDegG
 contains all vertices with degree greater than 1


Detailed Description

This class implements a construction heuristic for the maximum matching problem. The idea for the algorithm is taken from Michael Sipser, Richard M. Karp: "Maximum matchings in sparse random graphs", in 22nd Annual Symposium on Foundations of Computer Science. The modification consists of the priority queues, resp. of the fact that the vertices in the priority queues are ordered by the length of their shortest edge, thus creating a weighted version of this heuristic by biasing the algorithm to choose shorter edges on average.

Constructor & Destructor Documentation

WKSConstructionHeuristic::WKSConstructionHeuristic ( Graph g,
Matching m,
float  goal = 100.0 
)

Parameters:
g the underlying graph
m the inital matching (should be empty)

virtual WKSConstructionHeuristic::~WKSConstructionHeuristic ( void   )  [inline, virtual]


Member Function Documentation

void WKSConstructionHeuristic::checkNeighboursDeg1 ( Vertex v  )  [private]

copy all Neighbours of v that have degree 1 to VerticesDeg1

Vertex * WKSConstructionHeuristic::findVertexDeg1 ( void   )  [private]

get the Vertex from VerticesDeg1 that is nearest to top (with updated degrees and shortest edges)

Vertex * WKSConstructionHeuristic::findVertexDegG ( void   )  [private]

get the Vertex from VerticesDegG that is nearest to top (with updated degrees and shortest edges)

const char* WKSConstructionHeuristic::getName ( void   )  const [inline, virtual]

Implements MatchingAlgorithm.

void WKSConstructionHeuristic::run ( void   )  [virtual]

Implements MatchingAlgorithm.


Member Data Documentation

std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge> WKSConstructionHeuristic::VerticesDeg1 [private]

std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge> WKSConstructionHeuristic::VerticesDegG [private]


The documentation for this class was generated from the following files:

Generated on Mon Aug 17 10:58:33 2009 for steghide by  doxygen 1.5.9