DFSAPHeuristic Class Reference
a matching algorithm implementing a heuristic search for augmenting paths
More...
#include <DFSAPHeuristic.h>
List of all members.
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
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] |
const Edge * DFSAPHeuristic::getNextEdge |
( |
Vertex * |
v |
) |
[private] |
bool DFSAPHeuristic::isVisited |
( |
VertexLabel |
vlbl |
) |
const [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
void DFSAPHeuristic::markVisited |
( |
Vertex * |
v |
) |
[inline, private] |
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] |
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
The documentation for this class was generated from the following files: