All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
NetworKit::PathGrowingMatcher Class Reference

Path growing matching algorithm as described by Hougardy and Drake, http://dx.doi.org/10.1016/S0020-0190(02)00393-9 Computes an approximate maximum weight matching with guarantee 1/2. More...

#include <PathGrowingMatcher.h>

Public Member Functions

 PathGrowingMatcher (const Graph &G)
 
 PathGrowingMatcher (const Graph &G, const std::vector< double > &edgeScores)
 
virtual void run ()
 Runs path growing algorithm to compute approximate maximum weight matching for graph G. More...
 
- Public Member Functions inherited from NetworKit::Matcher
 Matcher (const Graph &G)
 Constructor. More...
 
 Matcher (const Graph &G, const std::vector< double > &edgeScores)
 Constructor. More...
 
virtual ~Matcher ()=default
 Default destructor. More...
 
Matching getMatching () const
 
- Public Member Functions inherited from NetworKit::Algorithm
 Algorithm ()
 Constructor to the algorithm base class. More...
 
virtual ~Algorithm ()=default
 Virtual default destructor. More...
 
bool hasFinished () const
 Indicates whether an algorithm has completed computation or not. More...
 
void assureFinished () const
 Assure that the algorithm has been run, throws a std::runtime_error otherwise. More...
 
virtual std::string toString () const
 Returns a string with the algorithm's name and its parameters, if there are any. More...
 
virtual bool isParallel () const
 

Additional Inherited Members

- Protected Attributes inherited from NetworKit::Matcher
const GraphG
 
Matching M
 
bool edgeScoresAsWeights
 
const std::vector< double > edgeScores
 
- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Detailed Description

Path growing matching algorithm as described by Hougardy and Drake, http://dx.doi.org/10.1016/S0020-0190(02)00393-9 Computes an approximate maximum weight matching with guarantee 1/2.

(Note that better algorithms in terms of approximation quality exist.)

Constructor & Destructor Documentation

NetworKit::PathGrowingMatcher::PathGrowingMatcher ( const Graph G)
Parameters
[in]GGraph for which matching is computed.
NetworKit::PathGrowingMatcher::PathGrowingMatcher ( const Graph G,
const std::vector< double > &  edgeScores 
)
Parameters
[in]GGraph for which matching is computed.

Member Function Documentation

void NetworKit::PathGrowingMatcher::run ( )
virtual

Runs path growing algorithm to compute approximate maximum weight matching for graph G.

Returns
Matching (at least half as heavy as maximum weight matching).

Implements NetworKit::Matcher.


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