Implementation of the Blossom-V algorithm by Kolmogorov (2009) for Minimum Weight Perfect Matching.
More...
|
| MatchingBlossomV (bool greedyInit=true) |
| Construct a MatchingBlossomV instance. More...
|
|
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...
|
|
| Module () |
| Initializes a module. More...
|
|
virtual | ~Module () |
|
| 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...
|
|
|
template<class WeightContainer > |
bool | _doCall (const Graph &G, const WeightContainer &weights, std::unordered_set< edge > &matching) |
| Helper for the main call function since abstract functions cannot be templated. More...
|
|
void | advanceCurrentAuxNode () |
| Helper function to advance the current aux node to the next one. More...
|
|
void | augment (edge augmentationEdge) |
| Augment the matching with augmentationEdge . More...
|
|
bool | doCall (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching) |
| Main call function for the algorithm with an EdgeArray as weight container. More...
|
|
bool | doCall (const GraphAttributes &GA, std::unordered_set< edge > &matching) |
| Main call function for the algorithm with GraphAttrubtes as weight container. More...
|
|
bool | dualChange () |
| Executes a dual change step. More...
|
|
long long | end (std::chrono::high_resolution_clock::time_point start) |
| Get the time difference between start and now in nanoseconds. More...
|
|
void | expand (Pseudonode *pseudonode) |
| Expand the given pseudonode . More...
|
|
bool | findExpandablePseudonode (AuxNode< TWeight > *auxNode) |
| Finds and expands an odd pseudonode in auxNode , if possible. More...
|
|
bool | findMatching (std::unordered_set< edge > &matching) |
| Main function of the algorithm. More...
|
|
bool | findMatchingAugmentation (AuxNode< TWeight > *auxNode) |
| Finds and executes a matching augmentation in auxNode , if possible. More...
|
|
bool | findShrinkableCycle (AuxNode< TWeight > *auxNode) |
| Finds and shrinks an odd cycle in auxNode , if possible. More...
|
|
bool | findTreeAugmentation (AuxNode< TWeight > *auxNode) |
| Finds and executes a tree augmentation in auxNode , if possible. More...
|
|
void | grow (edge newEdge) |
| Augment the corresponding tree with augmentationEdge . More...
|
|
std::ostream & | lout (Level level=Level::Default, bool indent=true) const |
| stream for logging-output (local) More...
|
|
std::ostream & | louth () |
| Helper function to log with high priority. More...
|
|
std::chrono::high_resolution_clock::time_point | now () |
| Get the current time point. More...
|
|
bool | primalChange () |
| Executes a primal change step. More...
|
|
void | printParallelEdgesStats () |
| Print additional statistics about parallel edges. More...
|
|
void | printStatistics () |
| Print all statistics. More...
|
|
long long | processStatisticEntry (const std::string &key) |
| Print a single statistics entry. More...
|
|
void | shrink (edge cycleEdge) |
| Shrink the odd cycle induced by cycleEdge and the tree determined by its endpoints. More...
|
|
|
enum | ReturnType { ReturnType::Feasible,
ReturnType::Optimal,
ReturnType::NoFeasibleSolution,
ReturnType::TimeoutFeasible,
ReturnType::TimeoutInfeasible,
ReturnType::Error
} |
| The return type of a module. More...
|
|
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 bool | isSolution (ReturnType ret) |
| Returns true iff ret indicates that the module returned a feasible solution. More...
|
|
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...
|
|
template<typename TWeight>
class ogdf::MatchingBlossomV< TWeight >
Implementation of the Blossom-V algorithm by Kolmogorov (2009) for Minimum Weight Perfect Matching.
Definition at line 80 of file MatchingBlossomV.h.