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

inline virtual

Implements MatchingAlgorithm.

## getNextEdge()

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

private

## isVisited() [1/2]

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

## isVisited() [2/2]

bool DFSAPHeuristic::isVisited | ( | VertexLabel | vlbl | ) | const

inline private

## markVisited()

void DFSAPHeuristic::markVisited | ( | Vertex * | v | ) |

inline private

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