steghide 0.5.1
WKSConstructionHeuristic Class Reference

a heuristic algorithm for constructing a matching More...

#include <WKSConstructionHeuristic.h>

Inheritance diagram for WKSConstructionHeuristic:
MatchingAlgorithm

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)
 
MatchinggetMatching (void) const
 
void setGoal (float goal)
 

Private Member Functions

VertexfindVertexDeg1 (void)
 
VertexfindVertexDegG (void)
 
void checkNeighboursDeg1 (Vertex *v)
 

Private Attributes

std::priority_queue< Vertex *, std::vector< Vertex * >, LongerShortestEdgeVerticesDeg1
 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 * >, LongerShortestEdgeVerticesDegG
 contains all vertices with degree greater than 1
 

Additional Inherited Members

- Protected Attributes inherited from MatchingAlgorithm
GraphTheGraph
 
MatchingTheMatching
 
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
gthe underlying graph
mthe inital matching (should be empty)

◆ ~WKSConstructionHeuristic()

virtual WKSConstructionHeuristic::~WKSConstructionHeuristic ( void )
inlinevirtual

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
inlinevirtual

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: