DFSAPHeuristic Class Reference

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

#include <DFSAPHeuristic.h>

Inheritance diagram for DFSAPHeuristic:

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 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]

---

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

• DFSAPHeuristic.h
• DFSAPHeuristic.cc

---