WKSConstructionHeuristic Class Reference

a heuristic algorithm for constructing a matching More...

#include <WKSConstructionHeuristic.h>

Inheritance diagram for WKSConstructionHeuristic:

MatchingAlgorithm

List of all members.

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

Classes

class  LongerShortestEdge
 a comparison operator More...


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

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

Implements MatchingAlgorithm.

void WKSConstructionHeuristic::run ( void   )  [virtual]

Implements MatchingAlgorithm.

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)

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

copy all Neighbours of v that have degree 1 to VerticesDeg1


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 Fri Aug 8 16:14:20 2008 for steghide by  doxygen 1.5.6