DFSAPHeuristic Class Reference

a matching algorithm implementing a heuristic search for augmenting paths More...

#include <DFSAPHeuristic.h>

Inheritance diagram for DFSAPHeuristic:

MatchingAlgorithm

List of all members.

Public Member Functions

 DFSAPHeuristic (Graph *g, Matching *m, float goal=100.0, UWORD32 mne=UWORD32_MAX, EdgeIterator::ITERATIONMODE mo=EdgeIterator::SAMPLEOCCURENCE)
virtual ~DFSAPHeuristic (void)
const char * getName (void) const
void reset (UWORD32 mne=UWORD32_MAX, EdgeIterator::ITERATIONMODE mo=EdgeIterator::SAMPLEOCCURENCE)
void run (void)

Private Member Functions

unsigned long searchAugmentingPath (Vertex *v0, const Edge **path)
const EdgegetNextEdge (Vertex *v)
void markVisited (Vertex *v)
bool isVisited (Vertex *v) const
bool isVisited (VertexLabel vlbl) const

Private Attributes

UWORD32 TimeCounter
UWORD32TimeCounters
bool * VertexOnPath
EdgeIteratorEdgeIterators


Detailed Description

This class implements the heuristic augmenting path search presented by Rolf H. Moehring and Matthias Mueller-Hannemann in their paper: "Cardinality Matching: Heuristic Search for Augmenting Paths".

Constructor & Destructor Documentation

DFSAPHeuristic::DFSAPHeuristic ( Graph g,
Matching m,
float  goal = 100.0,
UWORD32  mne = UWORD32_MAX,
EdgeIterator::ITERATIONMODE  mo = EdgeIterator::SAMPLEOCCURENCE 
)

construct an DFSAPHeuristic object

Parameters:
g the graph on which this heuristic should run
m the matching to start with
goal the percentage of matched vertices that should be reached
mne the maximum number of edges that should be considered for every vertex
mo the mode for edge iteration

DFSAPHeuristic::~DFSAPHeuristic ( void   )  [virtual]


Member Function Documentation

const char* DFSAPHeuristic::getName ( void   )  const [inline, virtual]

Implements MatchingAlgorithm.

void DFSAPHeuristic::reset ( UWORD32  mne = UWORD32_MAX,
EdgeIterator::ITERATIONMODE  mo = EdgeIterator::SAMPLEOCCURENCE 
)

reset the state of this DFSAPHeuristic, esp. the EdgeIterators

Parameters:
mne the maximum number of edges that should be considered for every vertex for now on

void DFSAPHeuristic::run ( void   )  [virtual]

Implements MatchingAlgorithm.

unsigned long DFSAPHeuristic::searchAugmentingPath ( Vertex v0,
const Edge **  path 
) [private]

Parameters:
v0 an exposed vertex
path an array of Edge pointers where the path will be put
Returns:
the length of the path (the number of valid edges in path)

const Edge * DFSAPHeuristic::getNextEdge ( Vertex v  )  [private]

void DFSAPHeuristic::markVisited ( Vertex v  )  [inline, private]

bool DFSAPHeuristic::isVisited ( Vertex v  )  const [inline, private]

returns true iff v has already been visited in this iteration, i.e. in the current call of searchAugmentingPath

bool DFSAPHeuristic::isVisited ( VertexLabel  vlbl  )  const [inline, private]


Member Data Documentation


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

Generated on Fri Aug 8 16:14:19 2008 for steghide by  doxygen 1.5.6