wksconstructionheuristic(3)

NAME

WKSConstructionHeuristic - a heuristic algorithm for constructing a
matching

SYNOPSIS

#include <WKSConstructionHeuristic.h>
Inherits MatchingAlgorithm.
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
Vertex * findVertexDeg1 (void)
Vertex * findVertexDegG (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

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]

Author

Generated automatically by Doxygen for steghide from the source code.

Version 0.5.1 17 Mar 2008 WKSConstructionHeuristic(3)