Implementation of the Blossom-I algorithm by Edmonds (1965) for Minimum Weight Perfect Matching.
More...
|
| | MatchingBlossom (bool greedyInit=true) |
| | Construct a MatchingBlossom instance.
|
| |
| 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.
|
| |
| TWeight | matchingWeight (const std::unordered_set< edge > &matching, const GraphAttributes &GA) |
| | Calculate the weight of the matching with the weights given in GA.
|
| |
| TWeight | maximumWeightMatching (const Graph &G, const EdgeArray< TWeight > &weights) |
| | Computes a maximum weight matching in G.
|
| |
| void | maximumWeightMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching) |
| | Computes a maximum weight matching in G.
|
| |
| TWeight | maximumWeightMatching (const GraphAttributes &GA) |
| | Computes a maximum weight matching in G.
|
| |
| void | maximumWeightMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching) |
| | Computes a maximum weight matching in GA.
|
| |
| std::tuple< bool, TWeight > | maximumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights) |
| | Computes a maximum weight perfect matching in G.
|
| |
| bool | maximumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching) |
| | Computes a maximum weight perfect matching in G.
|
| |
| std::tuple< bool, TWeight > | maximumWeightPerfectMatching (const GraphAttributes &GA) |
| | Computes a maximum weight perfect matching in G.
|
| |
| bool | maximumWeightPerfectMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching) |
| | Computes a maximum weight perfect matching in GA.
|
| |
| std::tuple< bool, TWeight > | minimumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights) |
| | Computes a minimum weight perfect matching in G.
|
| |
| bool | minimumWeightPerfectMatching (const Graph &G, const EdgeArray< TWeight > &weights, std::unordered_set< edge > &matching) |
| | Computes a minimum weight perfect matching in G.
|
| |
| std::tuple< bool, TWeight > | minimumWeightPerfectMatching (const GraphAttributes &GA) |
| | Computes a minimum weight perfect matching in G.
|
| |
| bool | minimumWeightPerfectMatching (const GraphAttributes &GA, std::unordered_set< edge > &matching) |
| | Computes a minimum weight perfect matching in GA.
|
| |
| | Module () |
| | Initializes a module.
|
| |
| virtual | ~Module () |
| |
| | Logger () |
| | creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel
|
| |
| | Logger (Level level) |
| | creates a new Logger-object with LogMode::Log and given local log-level
|
| |
| | Logger (LogMode m) |
| | creates a new Logger-object with given log-mode and local log-level equal globalLogLevel
|
| |
| | Logger (LogMode m, Level level) |
| | creates a new Logger-object with given log-mode and given local log-level
|
| |
| bool | is_lout (Level level=Level::Default) const |
| | returns true if such an lout command will result in text being printed
|
| |
| std::ostream & | lout (Level level=Level::Default, bool indent=true) const |
| | stream for logging-output (local)
|
| |
| std::ostream & | sout () const |
| | stream for statistic-output (local)
|
| |
| std::ostream & | fout () const |
| | stream for forced output (local)
|
| |
| Level | localLogLevel () const |
| | gives the local log-level
|
| |
| void | localLogLevel (Level level) |
| | sets the local log-level
|
| |
| LogMode | localLogMode () const |
| | gives the local log-mode
|
| |
| void | localLogMode (LogMode m) |
| | sets the local log-mode
|
| |
| 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)
|
| |
| bool | effectiveStatisticMode () const |
| | returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings)
|
| |
|
| 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.
|
| |
| 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.
|
| |
| bool | doCall (const GraphAttributes &GA, std::unordered_set< edge > &matching) |
| | Main call function for the algorithm with GraphAttrubtes as weight container.
|
| |
| bool | dualChange () |
| | Executes a dual change step.
|
| |
| void | expand (Pseudonode *pseudonode) |
| | Expand the pseudonode pseudonode.
|
| |
| bool | findExpandablePseudonode () |
| | Finds and expands an odd pseudonode, if possible.
|
| |
| bool | findMatching (std::unordered_set< edge > &matching) |
| | Main function of the algorithm.
|
| |
| bool | findMatchingAugmentation () |
| | Finds and executes a matching augmentation, if possible.
|
| |
| bool | findShrinkableCycle () |
| | Finds and shrinks an odd cycle, if possible.
|
| |
| bool | findTreeAugmentation () |
| | Finds and executes a tree augmentation, if possible.
|
| |
| node | getNewRoot () |
| | Helper function to get a new root for the tree.
|
| |
| void | hideNonEqualityEdges () |
| | Helper function to hide all non-equality edges.
|
| |
| std::ostream & | lout (Level level=Level::Default, bool indent=true) const |
| | stream for logging-output (local)
|
| |
| bool | primalChange () |
| | Executes a primal change step.
|
| |
| void | restoreNonEqualityEdges () |
| | Helper function to restore all non-equality edges.
|
| |
| void | shrink (edge cycleEdge) |
| | Shrink the odd cycle induced by the current tree together with cycleEdge.
|
| |
|
| enum class | ReturnType { Feasible
, Optimal
, NoFeasibleSolution
, TimeoutFeasible
, TimeoutInfeasible
, Error
} |
| | The return type of a module. More...
|
| |
| enum class | Level { Minor
, Medium
, Default
, High
, Alarm
, Force
} |
| | supported log-levels from lowest to highest importance More...
|
| |
| enum class | LogMode { Global
, GlobalLog
, Log
, Statistic
} |
| | Local log-modes. More...
|
| |
| static bool | isSolution (ReturnType ret) |
| | Returns true iff ret indicates that the module returned a feasible solution.
|
| |
| static bool | is_slout (Level level=Level::Default) |
| | returns true if such an slout command will result in text being printed
|
| |
| static std::ostream & | slout (Level level=Level::Default) |
| | stream for logging-output (global)
|
| |
| static std::ostream & | ssout () |
| | stream for statistic-output (global)
|
| |
| static std::ostream & | sfout () |
| | stream for forced output (global)
|
| |
| 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
|
| |
| static std::ostream & | ilout (Level level=Level::Default) |
| |
| static std::ostream & | ifout () |
| | stream for forced output (global; used by internal libraries, e.g. Abacus)
|
| |
| static Level | globalLogLevel () |
| | gives the global log-level
|
| |
| static void | globalLogLevel (Level level) |
| | sets the global log-level
|
| |
| static Level | globalInternalLibraryLogLevel () |
| | gives the internal-library log-level
|
| |
| static void | globalInternalLibraryLogLevel (Level level) |
| | sets the internal-library log-level
|
| |
| static Level | globalMinimumLogLevel () |
| | gives the globally minimally required log-level
|
| |
| static void | globalMinimumLogLevel (Level level) |
| | sets the globally minimally required log-level
|
| |
| static bool | globalStatisticMode () |
| | returns true if we are globally in statistic mode
|
| |
| static void | globalStatisticMode (bool s) |
| | sets whether we are globally in statistic mode
|
| |
| static void | setWorldStream (std::ostream &o) |
| | change the stream to which allowed output is written (by default: std::cout)
|
| |
template<typename TWeight>
class ogdf::MatchingBlossom< TWeight >
Implementation of the Blossom-I algorithm by Edmonds (1965) for Minimum Weight Perfect Matching.
Use MatchingBlossomV for a more sophisticated and faster version of this algorithm.
Definition at line 63 of file MatchingBlossom.h.
Inheritance diagram for ogdf::MatchingBlossom< TWeight >:
