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::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::~DFSAPHeuristic ( void )
virtual

Member Function Documentation

◆ getName()

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

Implements MatchingAlgorithm.

◆ getNextEdge()

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

◆ isVisited() [1/2]

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

◆ isVisited() [2/2]

bool DFSAPHeuristic::isVisited ( VertexLabel vlbl) const
inlineprivate

◆ markVisited()

void DFSAPHeuristic::markVisited ( Vertex * v)
inlineprivate

◆ reset()

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

◆ run()

void DFSAPHeuristic::run ( void )
virtual

Implements MatchingAlgorithm.

◆ searchAugmentingPath()

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

◆ EdgeIterators

EdgeIterator* DFSAPHeuristic::EdgeIterators
private

◆ TimeCounter

UWORD32 DFSAPHeuristic::TimeCounter
private

◆ TimeCounters

UWORD32* DFSAPHeuristic::TimeCounters
private

◆ VertexOnPath

bool* DFSAPHeuristic::VertexOnPath
private

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