steghide  0.5.1
Public Member Functions | Private Member Functions | Private Attributes | List of all members
DFSAPHeuristic Class Reference

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

#include <DFSAPHeuristic.h>

Inheritance diagram for DFSAPHeuristic:
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)
 
- 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

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
 

Additional Inherited Members

- Protected Attributes inherited from MatchingAlgorithm
GraphTheGraph
 
MatchingTheMatching
 
unsigned long CardinalityGoal
 

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
gthe graph on which this heuristic should run
mthe matching to start with
goalthe percentage of matched vertices that should be reached
mnethe maximum number of edges that should be considered for every vertex
mothe mode for edge iteration
DFSAPHeuristic::~DFSAPHeuristic ( void  )
virtual

Member Function Documentation

const char* DFSAPHeuristic::getName ( void  ) const
inlinevirtual

Implements MatchingAlgorithm.

const Edge * DFSAPHeuristic::getNextEdge ( Vertex v)
private
bool DFSAPHeuristic::isVisited ( Vertex v) const
inlineprivate

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
inlineprivate
void DFSAPHeuristic::markVisited ( Vertex v)
inlineprivate
void DFSAPHeuristic::reset ( UWORD32  mne = UWORD32_MAX,
EdgeIterator::ITERATIONMODE  mo = EdgeIterator::SAMPLEOCCURENCE 
)

reset the state of this DFSAPHeuristic, esp. the EdgeIterators

Parameters
mnethe 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
v0an exposed vertex
pathan array of Edge pointers where the path will be put
Returns
the length of the path (the number of valid edges in path)

Member Data Documentation

EdgeIterator* DFSAPHeuristic::EdgeIterators
private
UWORD32 DFSAPHeuristic::TimeCounter
private
UWORD32* DFSAPHeuristic::TimeCounters
private
bool* DFSAPHeuristic::VertexOnPath
private

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