WKSConstructionHeuristic Class Reference

a heuristic algorithm for constructing a matching More...

`#include <WKSConstructionHeuristic.h>`

Inheritance diagram for WKSConstructionHeuristic:

## 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)
Public Member Functions inherited from MatchingAlgorithm
| MatchingAlgorithm (Graph *g, Matching *m, float goal)
virtual | ~MatchingAlgorithm (void)
Matching * | getMatching (void) const
void | setGoal (float goal)

## 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

## Additional Inherited Members

Protected Attributes inherited from MatchingAlgorithm
Graph * | TheGraph
Matching * | TheMatching
unsigned long | CardinalityGoal

## 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::WKSConstructionHeuristic | ( | Graph * | g,
|  | Matching * | m,
|  | float | goal = 100.0 )

Parameters

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

## ~WKSConstructionHeuristic()

virtual WKSConstructionHeuristic::~WKSConstructionHeuristic | ( | void |  | ) |

inline virtual

## Member Function Documentation

## checkNeighboursDeg1()

void WKSConstructionHeuristic::checkNeighboursDeg1 | ( | Vertex * | v | ) |

private

copy all Neighbours of v that have degree 1 to VerticesDeg1

## findVertexDeg1()

Vertex * WKSConstructionHeuristic::findVertexDeg1 | ( | void |  | ) |

private

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

## findVertexDegG()

Vertex * WKSConstructionHeuristic::findVertexDegG | ( | void |  | ) |

private

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

## getName()

const char * WKSConstructionHeuristic::getName | ( | void |  | ) | const

inline virtual

Implements MatchingAlgorithm.

## run()

void WKSConstructionHeuristic::run | ( | void |  | ) |

virtual

Implements MatchingAlgorithm.

## Member Data Documentation

## VerticesDeg1

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

private

## VerticesDegG

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

private

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

- WKSConstructionHeuristic.h
- WKSConstructionHeuristic.cc