steghide
0.5.1
|
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) |
![]() | |
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 | |
![]() | |
Graph * | TheGraph |
Matching * | TheMatching |
unsigned long | CardinalityGoal |
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) |
|
inlinevirtual |
|
private |
copy all Neighbours of v that have degree 1 to VerticesDeg1
|
private |
get the Vertex from VerticesDeg1 that is nearest to top (with updated degrees and shortest edges)
|
private |
get the Vertex from VerticesDegG that is nearest to top (with updated degrees and shortest edges)
|
inlinevirtual |
Implements MatchingAlgorithm.
|
virtual |
Implements MatchingAlgorithm.
|
private |
|
private |