a heuristic algorithm for constructing a matching More...
#include <WKSConstructionHeuristic.h>
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 | |
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 |
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.
g | the underlying graph | |
m | the inital matching (should be empty) |
virtual WKSConstructionHeuristic::~WKSConstructionHeuristic | ( | void | ) | [inline, virtual] |
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.
std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge> WKSConstructionHeuristic::VerticesDeg1 [private] |
std::priority_queue<Vertex*, std::vector<Vertex*>, LongerShortestEdge> WKSConstructionHeuristic::VerticesDegG [private] |