DFSAPHeuristic Class Reference

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

#include <DFSAPHeuristic.h>

Inheritance diagram for DFSAPHeuristic:

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)
Matching *	getMatching (void) const
void	setGoal (float goal)

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

Additional Inherited Members
Protected Attributes inherited from MatchingAlgorithm
Graph *	TheGraph
Matching *	TheMatching
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

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

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

run()

void DFSAPHeuristic::run ( void  )

virtual

Implements MatchingAlgorithm.

searchAugmentingPath()

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)

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:

• DFSAPHeuristic.h
• DFSAPHeuristic.cc