|
|||
|
|
|
|||
|
|
Helper class for the blossom matching algorithms. More...
#include <ogdf/graphalg/matching_blossom/BlossomHelper.h>
Inheritance diagram for ogdf::matching_blossom::BlossomHelper< TWeight >:Public Member Functions | |
| BlossomHelper (bool greedyInit) | |
| Construct a new Blossom V Helper object. More... | |
| ~BlossomHelper () | |
| void | addPseudonode (Pseudonode *pseudonode) |
| Adds a pseudonode to the current representation structure. More... | |
| void | addToMatching (edge e) |
Adds the edge e to the matching. More... | |
| TWeight & | c (edge e) |
Returns the base edge weight of e. More... | |
| void | expandRepr (Pseudonode *pseudonode) |
| Expands a pseudonode in the current representation structure. More... | |
| node | getBaseNode (edge e, node v) |
Returns the original end point of e which is currently represented by v. More... | |
| std::pair< node, node > | getBaseNodes (edge e, node v=nullptr) |
Return both original end points of e where the first end point is currently represented by v. More... | |
| node | getOppositeBaseNode (edge e, node v) |
Returns the original end point of e where the other end point is currently represented by v. More... | |
| void | getOriginalMatching (std::unordered_set< edge > &matching) |
Fills matching with the original edges which correspond to the edges in m_matching after expanding it with the correct edges currently contracted in blossoms. More... | |
| virtual TWeight | getRealReducedWeight (edge e) |
| Returns the real reduced weight. Can be overridden by subclasses to consider additional factors. More... | |
| TWeight | getReducedWeight (edge e) |
Returns the reduced weight of e, taking into account the y values of the endpoints. More... | |
| GraphCopySimple & | graph () |
| template<class WeightContainer > | |
| bool | init (const Graph &graph, const WeightContainer &weights) |
| Reinitialize the helper class with a new graph and edge weights. Resets all helper members. Returns false if the graph cannot have a perfect matching. More... | |
| virtual bool | isEqualityEdge (edge e) |
Checks whether e is an equality edge, i.e. the reduced weight is 0. More... | |
| bool | isPseudonode (node v) |
Checks whether v is a pseudonode. More... | |
| bool | isZero (TWeight x) |
| Helper function to determine whether a floating point value is 0. More... | |
| bool | isZeroCostNode (node v) |
Checks whether v is a zero-cost node, i.e. the y value is 0. More... | |
| NodeArray< edge > & | matching () |
| edge & | matching (node v) |
Returns the matching edge of v, or nullptr if v is not matched. More... | |
| Pseudonode * | pseudonode (node v) |
Returns the pseudonode corresponding to v, or nullptr if v is not a pseudonode. More... | |
| std::unordered_map< node, Pseudonode * > & | pseudonodes () |
| void | removePseudonode (Pseudonode *pseudonode) |
| Removes a pseudonode from the current representation structure. More... | |
| node | repr (node v) |
Returns the representative of v in the tree induced by the pseudonodes. More... | |
| node | reprChild (node v) |
Returns the child of the representative of v in the tree induced by the pseudonodes. More... | |
| TWeight & | y (node v) |
Returns the base y value of v. More... | |
Protected Member Functions | |
| void | deletePseudonodes () |
| Deletes all pseudonodes. More... | |
| node | findParentInRepr (node v, node child=nullptr) |
Finds the parent of v in the tree induced by the pseudonodes. More... | |
| bool | initDualSolution (NodeArray< TWeight > &minY) |
| Initializes the dual solution with the given y values. More... | |
Protected Attributes | |
| EdgeArray< TWeight > | m_c |
| LP-induced data used by the algorithm. More... | |
| EpsilonTest | m_eps |
| The epsilon test used for floating point comparisons. More... | |
| GraphCopySimple | m_graph |
| A copy of the graph to work on. More... | |
| bool | m_greedyInit |
| Whether or not to use the greedy initialization. More... | |
| NodeArray< edge > | m_matching |
| The current matching, mapping both endpoints to the corresponding matching edge. More... | |
| std::unordered_map< node, Pseudonode * > | m_pseudonodes |
| A mapping of all pseudonodes in the graph. More... | |
| std::vector< node > | m_repr |
| The tree induced by the pseudonodes, mapping each node index to its parent. More... | |
| std::vector< node > | m_shortcuts |
| A shortcut array for the tree, mapping each node index to the penultimate node. More... | |
| NodeArray< TWeight > | m_y |
Static Protected Attributes | |
| static const int | WEIGHT_FACTOR = std::numeric_limits<TWeight>::is_integer ? 4 : 1 |
Additional Inherited Members | |
| Private 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... | |
| Private 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... | |
| Static Private 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... | |
Helper class for the blossom matching algorithms.
Definition at line 55 of file BlossomHelper.h.
|
inline |
Construct a new Blossom V Helper object.
| greedyInit | whether or not to use the greedy initialization |
Definition at line 185 of file BlossomHelper.h.
|
inline |
Definition at line 187 of file BlossomHelper.h.
|
inline |
Adds a pseudonode to the current representation structure.
Definition at line 280 of file BlossomHelper.h.
|
inline |
Adds the edge e to the matching.
Definition at line 394 of file BlossomHelper.h.
|
inline |
Returns the base edge weight of e.
Definition at line 231 of file BlossomHelper.h.
|
inlineprotected |
Deletes all pseudonodes.
Definition at line 154 of file BlossomHelper.h.
|
inline |
Expands a pseudonode in the current representation structure.
Definition at line 303 of file BlossomHelper.h.
|
inlineprotected |
Finds the parent of v in the tree induced by the pseudonodes.
Definition at line 141 of file BlossomHelper.h.
|
inline |
Returns the original end point of e which is currently represented by v.
Definition at line 311 of file BlossomHelper.h.
|
inline |
Return both original end points of e where the first end point is currently represented by v.
Definition at line 317 of file BlossomHelper.h.
|
inline |
Returns the original end point of e where the other end point is currently represented by v.
Definition at line 314 of file BlossomHelper.h.
|
inline |
Fills matching with the original edges which correspond to the edges in m_matching after expanding it with the correct edges currently contracted in blossoms.
Definition at line 346 of file BlossomHelper.h.
|
inlinevirtual |
Returns the real reduced weight. Can be overridden by subclasses to consider additional factors.
Definition at line 336 of file BlossomHelper.h.
|
inline |
Returns the reduced weight of e, taking into account the y values of the endpoints.
Definition at line 333 of file BlossomHelper.h.
|
inline |
Definition at line 228 of file BlossomHelper.h.
|
inline |
Reinitialize the helper class with a new graph and edge weights. Resets all helper members. Returns false if the graph cannot have a perfect matching.
Definition at line 192 of file BlossomHelper.h.
|
inlineprotected |
Initializes the dual solution with the given y values.
Definition at line 86 of file BlossomHelper.h.
|
inlinevirtual |
Checks whether e is an equality edge, i.e. the reduced weight is 0.
Definition at line 339 of file BlossomHelper.h.
|
inline |
Checks whether v is a pseudonode.
Definition at line 247 of file BlossomHelper.h.
|
inline |
Helper function to determine whether a floating point value is 0.
Definition at line 330 of file BlossomHelper.h.
|
inline |
Checks whether v is a zero-cost node, i.e. the y value is 0.
Definition at line 342 of file BlossomHelper.h.
|
inline |
Definition at line 236 of file BlossomHelper.h.
|
inline |
Returns the matching edge of v, or nullptr if v is not matched.
Definition at line 239 of file BlossomHelper.h.
|
inline |
Returns the pseudonode corresponding to v, or nullptr if v is not a pseudonode.
Definition at line 244 of file BlossomHelper.h.
|
inline |
Definition at line 241 of file BlossomHelper.h.
|
inline |
Removes a pseudonode from the current representation structure.
Definition at line 291 of file BlossomHelper.h.
|
inline |
Returns the representative of v in the tree induced by the pseudonodes.
Definition at line 252 of file BlossomHelper.h.
|
inline |
Returns the child of the representative of v in the tree induced by the pseudonodes.
Definition at line 267 of file BlossomHelper.h.
|
inline |
Returns the base y value of v.
Definition at line 234 of file BlossomHelper.h.
|
protected |
LP-induced data used by the algorithm.
Definition at line 64 of file BlossomHelper.h.
|
protected |
The epsilon test used for floating point comparisons.
Definition at line 80 of file BlossomHelper.h.
|
protected |
A copy of the graph to work on.
Definition at line 61 of file BlossomHelper.h.
|
protected |
Whether or not to use the greedy initialization.
Definition at line 58 of file BlossomHelper.h.
|
protected |
The current matching, mapping both endpoints to the corresponding matching edge.
Definition at line 68 of file BlossomHelper.h.
|
protected |
A mapping of all pseudonodes in the graph.
Definition at line 71 of file BlossomHelper.h.
|
protected |
The tree induced by the pseudonodes, mapping each node index to its parent.
Definition at line 74 of file BlossomHelper.h.
|
protected |
A shortcut array for the tree, mapping each node index to the penultimate node.
Definition at line 77 of file BlossomHelper.h.
|
protected |
Definition at line 65 of file BlossomHelper.h.
|
staticprotected |
Definition at line 83 of file BlossomHelper.h.
