Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::MatchingModule< TWeight > Class Template Referenceabstract

#include <ogdf/graphalg/MatchingModule.h>

+ Inheritance diagram for ogdf::MatchingModule< TWeight >:

Public Member Functions

virtual ~MatchingModule ()
 
TWeight matchingWeight (const std::unordered_set< edge > &matching, const EdgeArray< TWeight > &weights)
 Calculate the weight of the matching with the weights given in weights. More...
 
TWeight matchingWeight (const std::unordered_set< edge > &matching, const GraphAttributes &GA)
 Calculate the weight of the matching with the weights given in GA. More...
 
TWeight maximumWeightMatching (const Graph &G, const EdgeArray< TWeight > &weights)
 Computes a maximum weight matching in G. More...
 
void maximumWeightMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)
 Computes a maximum weight matching in G. More...
 
TWeight maximumWeightMatching (const GraphAttributes &GA)
 Computes a maximum weight matching in G. More...
 
void maximumWeightMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching)
 Computes a maximum weight matching in GA. More...
 
std::tuple< bool, TWeight > maximumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights)
 Computes a maximum weight perfect matching in G. More...
 
bool maximumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)
 Computes a maximum weight perfect matching in G. More...
 
std::tuple< bool, TWeight > maximumWeightPerfectMatching (const GraphAttributes &GA)
 Computes a maximum weight perfect matching in G. More...
 
bool maximumWeightPerfectMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching)
 Computes a maximum weight perfect matching in GA. More...
 
std::tuple< bool, TWeight > minimumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights)
 Computes a minimum weight perfect matching in G. More...
 
bool minimumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)
 Computes a minimum weight perfect matching in G. More...
 
std::tuple< bool, TWeight > minimumWeightPerfectMatching (const GraphAttributes &GA)
 Computes a minimum weight perfect matching in G. More...
 
bool minimumWeightPerfectMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching)
 Computes a minimum weight perfect matching in GA. More...
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 
- Public Member Functions inherited from ogdf::Logger
 Logger ()
 creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel More...
 
 Logger (Level level)
 creates a new Logger-object with LogMode::Log and given local log-level More...
 
 Logger (LogMode m)
 creates a new Logger-object with given log-mode and local log-level equal globalLogLevel More...
 
 Logger (LogMode m, Level level)
 creates a new Logger-object with given log-mode and given local log-level More...
 
bool is_lout (Level level=Level::Default) const
 returns true if such an lout command will result in text being printed More...
 
std::ostream & lout (Level level=Level::Default, bool indent=true) const
 stream for logging-output (local) More...
 
std::ostream & sout () const
 stream for statistic-output (local) More...
 
std::ostream & fout () const
 stream for forced output (local) More...
 
Level localLogLevel () const
 gives the local log-level More...
 
void localLogLevel (Level level)
 sets the local log-level More...
 
LogMode localLogMode () const
 gives the local log-mode More...
 
void localLogMode (LogMode m)
 sets the local log-mode More...
 
void indent (int by=1)
 
void dedent (int by=1)
 
int getIndent () const
 
void setIndent (int indent)
 
Level effectiveLogLevel () const
 obtain the effective log-level for the Logger-object (i.e., resolve the dependencies on the global settings) More...
 
bool effectiveStatisticMode () const
 returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings) More...
 

Protected Member Functions

virtual bool doCall (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching)=0
 Main call function for the algorithm with an EdgeArray as weight container. More...
 
virtual bool doCall (const GraphAttributes &GA, std::unordered_set< edge > &matching)=0
 Main call function for the algorithm with GraphAttrubtes as weight container. More...
 

Private Member Functions

template<class WeightContainer >
void copyWeights (const Graph &G, const WeightContainer &weights, EdgeArray< TWeight > &copy, bool invert=false)
 
template<class WeightContainer >
void doMaximumWeightMatching (const Graph &G, const WeightContainer &weights, std::unordered_set< edge > &matching)
 
template<class WeightContainer >
TWeight getMatchingWeight (const std::unordered_set< edge > &matching, const WeightContainer &weights)
 

Additional Inherited Members

- Public Types inherited from ogdf::Module
enum  ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::Error }
 The return type of a module. More...
 
- Public Types inherited from ogdf::Logger
enum  Level { Level::Minor, Level::Medium, Level::Default, Level::High, Level::Alarm, Level::Force }
 supported log-levels from lowest to highest importance More...
 
enum  LogMode { LogMode::Global, LogMode::GlobalLog, LogMode::Log, LogMode::Statistic }
 Local log-modes. More...
 
- Static Public Member Functions inherited from ogdf::Module
static bool isSolution (ReturnType ret)
 Returns true iff ret indicates that the module returned a feasible solution. More...
 
- Static Public Member Functions inherited from ogdf::Logger
static bool is_slout (Level level=Level::Default)
 returns true if such an slout command will result in text being printed More...
 
static std::ostream & slout (Level level=Level::Default)
 stream for logging-output (global) More...
 
static std::ostream & ssout ()
 stream for statistic-output (global) More...
 
static std::ostream & sfout ()
 stream for forced output (global) More...
 
static bool is_ilout (Level level=Level::Default)
 stream for logging-output (global; used by internal libraries, e.g. Abacus) returns true if such an ilout command will result in text being printed More...
 
static std::ostream & ilout (Level level=Level::Default)
 
static std::ostream & ifout ()
 stream for forced output (global; used by internal libraries, e.g. Abacus) More...
 
static Level globalLogLevel ()
 gives the global log-level More...
 
static void globalLogLevel (Level level)
 sets the global log-level More...
 
static Level globalInternalLibraryLogLevel ()
 gives the internal-library log-level More...
 
static void globalInternalLibraryLogLevel (Level level)
 sets the internal-library log-level More...
 
static Level globalMinimumLogLevel ()
 gives the globally minimally required log-level More...
 
static void globalMinimumLogLevel (Level level)
 sets the globally minimally required log-level More...
 
static bool globalStatisticMode ()
 returns true if we are globally in statistic mode More...
 
static void globalStatisticMode (bool s)
 sets whether we are globally in statistic mode More...
 
static void setWorldStream (std::ostream &o)
 change the stream to which allowed output is written (by default: std::cout) More...
 

Detailed Description

template<typename TWeight>
class ogdf::MatchingModule< TWeight >

Definition at line 51 of file MatchingModule.h.

Constructor & Destructor Documentation

◆ ~MatchingModule()

template<typename TWeight >
virtual ogdf::MatchingModule< TWeight >::~MatchingModule ( )
inlinevirtual

Definition at line 53 of file MatchingModule.h.

Member Function Documentation

◆ copyWeights()

template<typename TWeight >
template<class WeightContainer >
void ogdf::MatchingModule< TWeight >::copyWeights ( const Graph G,
const WeightContainer &  weights,
EdgeArray< TWeight > &  copy,
bool  invert = false 
)
inlineprivate

Definition at line 236 of file MatchingModule.h.

◆ doCall() [1/2]

template<typename TWeight >
virtual bool ogdf::MatchingModule< TWeight >::doCall ( const Graph G,
const EdgeArray< TWeight > &  weights,
std::unordered_set< edge > &  matching 
)
protectedpure virtual

Main call function for the algorithm with an EdgeArray as weight container.

Implemented in ogdf::MatchingBlossomV< TWeight >, and ogdf::MatchingBlossom< TWeight >.

◆ doCall() [2/2]

template<typename TWeight >
virtual bool ogdf::MatchingModule< TWeight >::doCall ( const GraphAttributes GA,
std::unordered_set< edge > &  matching 
)
protectedpure virtual

Main call function for the algorithm with GraphAttrubtes as weight container.

Implemented in ogdf::MatchingBlossomV< TWeight >, and ogdf::MatchingBlossom< TWeight >.

◆ doMaximumWeightMatching()

template<typename TWeight >
template<class WeightContainer >
void ogdf::MatchingModule< TWeight >::doMaximumWeightMatching ( const Graph G,
const WeightContainer &  weights,
std::unordered_set< edge > &  matching 
)
inlineprivate

Definition at line 254 of file MatchingModule.h.

◆ getMatchingWeight()

template<typename TWeight >
template<class WeightContainer >
TWeight ogdf::MatchingModule< TWeight >::getMatchingWeight ( const std::unordered_set< edge > &  matching,
const WeightContainer &  weights 
)
inlineprivate

Definition at line 244 of file MatchingModule.h.

◆ matchingWeight() [1/2]

template<typename TWeight >
TWeight ogdf::MatchingModule< TWeight >::matchingWeight ( const std::unordered_set< edge > &  matching,
const EdgeArray< TWeight > &  weights 
)
inline

Calculate the weight of the matching with the weights given in weights.

Definition at line 216 of file MatchingModule.h.

◆ matchingWeight() [2/2]

template<typename TWeight >
TWeight ogdf::MatchingModule< TWeight >::matchingWeight ( const std::unordered_set< edge > &  matching,
const GraphAttributes GA 
)
inline

Calculate the weight of the matching with the weights given in GA.

Definition at line 222 of file MatchingModule.h.

◆ maximumWeightMatching() [1/4]

template<typename TWeight >
TWeight ogdf::MatchingModule< TWeight >::maximumWeightMatching ( const Graph G,
const EdgeArray< TWeight > &  weights 
)
inline

Computes a maximum weight matching in G.

Parameters
Gthe graph to compute the matching in
weightsthe weights of the edges of G
Returns
the weight of the maximum matching

Definition at line 197 of file MatchingModule.h.

◆ maximumWeightMatching() [2/4]

template<typename TWeight >
void ogdf::MatchingModule< TWeight >::maximumWeightMatching ( const Graph G,
const EdgeArray< TWeight > &  weights,
std::unordered_set< edge > &  matching 
)
inline

Computes a maximum weight matching in G.

Parameters
Gthe graph to compute the matching in
weightsthe weights of the edges of G
matchingoutput parameter to store the matching in

Definition at line 175 of file MatchingModule.h.

◆ maximumWeightMatching() [3/4]

template<typename TWeight >
TWeight ogdf::MatchingModule< TWeight >::maximumWeightMatching ( const GraphAttributes GA)
inline

Computes a maximum weight matching in G.

Parameters
GAThe graph to compute the matching in, together with its edge weights
Returns
the weight of the maximum matching

Definition at line 209 of file MatchingModule.h.

◆ maximumWeightMatching() [4/4]

template<typename TWeight >
void ogdf::MatchingModule< TWeight >::maximumWeightMatching ( const GraphAttributes GA,
std::unordered_set< edge > &  matching 
)
inline

Computes a maximum weight matching in GA.

Parameters
GAThe graph to compute the matching in, together with its edge weights
matchingoutput parameter to store the matching in

Definition at line 186 of file MatchingModule.h.

◆ maximumWeightPerfectMatching() [1/4]

template<typename TWeight >
std::tuple<bool, TWeight> ogdf::MatchingModule< TWeight >::maximumWeightPerfectMatching ( const Graph G,
const EdgeArray< TWeight > &  weights 
)
inline

Computes a maximum weight perfect matching in G.

Parameters
Gthe graph to compute the matching in
weightsthe weights of the edges of G
Returns
a tuple consisting of a boolean indicating whether or not a perfect matching was found and the weight of the matching, if one was found

Definition at line 146 of file MatchingModule.h.

◆ maximumWeightPerfectMatching() [2/4]

template<typename TWeight >
bool ogdf::MatchingModule< TWeight >::maximumWeightPerfectMatching ( const Graph G,
const EdgeArray< TWeight > &  weights,
std::unordered_set< edge > &  matching 
)
inline

Computes a maximum weight perfect matching in G.

Parameters
Gthe graph to compute the matching in
weightsthe weights of the edges of G
matchingoutput parameter to store the matching in
Returns
whether or not a perfect matching was found

Definition at line 117 of file MatchingModule.h.

◆ maximumWeightPerfectMatching() [3/4]

template<typename TWeight >
std::tuple<bool, TWeight> ogdf::MatchingModule< TWeight >::maximumWeightPerfectMatching ( const GraphAttributes GA)
inline

Computes a maximum weight perfect matching in G.

Parameters
GAThe graph to compute the matching in, together with its edge weights
Returns
a tuple consisting of a boolean indicating whether or not a perfect matching was found and the weight of the matching, if one was found

Definition at line 161 of file MatchingModule.h.

◆ maximumWeightPerfectMatching() [4/4]

template<typename TWeight >
bool ogdf::MatchingModule< TWeight >::maximumWeightPerfectMatching ( const GraphAttributes GA,
std::unordered_set< edge > &  matching 
)
inline

Computes a maximum weight perfect matching in GA.

Parameters
GAThe graph to compute the matching in, together with its edge weights
matchingoutput parameter to store the matching in
Returns
whether or not a perfect matching was found

Definition at line 131 of file MatchingModule.h.

◆ minimumWeightPerfectMatching() [1/4]

template<typename TWeight >
std::tuple<bool, TWeight> ogdf::MatchingModule< TWeight >::minimumWeightPerfectMatching ( const Graph G,
const EdgeArray< TWeight > &  weights 
)
inline

Computes a minimum weight perfect matching in G.

Parameters
Gthe graph to compute the matching in
weightsthe weights of the edges of G
Returns
a tuple consisting of a boolean indicating whether or not a perfect matching was found and the weight of the matching, if one was found

Definition at line 87 of file MatchingModule.h.

◆ minimumWeightPerfectMatching() [2/4]

template<typename TWeight >
bool ogdf::MatchingModule< TWeight >::minimumWeightPerfectMatching ( const Graph G,
const EdgeArray< TWeight > &  weights,
std::unordered_set< edge > &  matching 
)
inline

Computes a minimum weight perfect matching in G.

Parameters
Gthe graph to compute the matching in
weightsthe weights of the edges of G
matchingoutput parameter to store the matching in
Returns
whether or not a perfect matching was found

Definition at line 63 of file MatchingModule.h.

◆ minimumWeightPerfectMatching() [3/4]

template<typename TWeight >
std::tuple<bool, TWeight> ogdf::MatchingModule< TWeight >::minimumWeightPerfectMatching ( const GraphAttributes GA)
inline

Computes a minimum weight perfect matching in G.

Parameters
GAThe graph to compute the matching in, together with its edge weights
Returns
a tuple consisting of a boolean indicating whether or not a perfect matching was found and the weight of the matching, if one was found

Definition at line 102 of file MatchingModule.h.

◆ minimumWeightPerfectMatching() [4/4]

template<typename TWeight >
bool ogdf::MatchingModule< TWeight >::minimumWeightPerfectMatching ( const GraphAttributes GA,
std::unordered_set< edge > &  matching 
)
inline

Computes a minimum weight perfect matching in GA.

Parameters
GAThe graph to compute the matching in, together with its edge weights
matchingoutput parameter to store the matching in
Returns
whether or not a perfect matching was found

Definition at line 75 of file MatchingModule.h.


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