dfsapheuristic(3)
NAME
DFSAPHeuristic - a matching algorithm implementing a heuristic search
for augmenting paths
SYNOPSIS
#include <DFSAPHeuristic.h> Inherits MatchingAlgorithm. 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 Edge * getNextEdge (Vertex *v) void markVisited (Vertex *v) bool isVisited (Vertex *v) const bool isVisited (VertexLabel vlbl) const Private Attributes UWORD32 TimeCounter UWORD32 * TimeCounters bool * VertexOnPath EdgeIterator * EdgeIterators
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
UWORD32 DFSAPHeuristic::TimeCounter [private] UWORD32* DFSAPHeuristic::TimeCounters [private] bool* DFSAPHeuristic::VertexOnPath [private] EdgeIterator* DFSAPHeuristic::EdgeIterators [private]
Author
- Generated automatically by Doxygen for steghide from the source code.