The planarization approach for UML crossing minimization. More...
#include <ogdf/uml/SubgraphPlanarizerUML.h>
Public Member Functions | |
SubgraphPlanarizerUML () | |
Creates an instance of subgraph planarizer with default settings. More... | |
SubgraphPlanarizerUML (const SubgraphPlanarizerUML &planarizer) | |
Creates an instance of subgraph planarizer with the same settings as planarizer . More... | |
virtual UMLCrossingMinimizationModule * | clone () const override |
Returns a new instance of subgraph planarizer with the same option settings. More... | |
unsigned int | maxThreads () const |
Returns the maximal number of used threads. More... | |
void | maxThreads (unsigned int n) |
Sets the maximal number of used threads to n . More... | |
SubgraphPlanarizerUML & | operator= (const SubgraphPlanarizerUML &planarizer) |
Assignment operator. Copies option settings only. More... | |
int | permutations () |
Returns the number of permutations. More... | |
void | permutations (int p) |
Sets the number of permutations to p . More... | |
void | setInserter (UMLEdgeInsertionModule *pInserter) |
Sets the module option for the edge insertion module. More... | |
void | setSubgraph (PlanarSubgraphModule< int > *pSubgraph) |
Sets the module option for the computation of the planar subgraph. More... | |
bool | setTimeout () |
Returns the current setting of options setTimeout. More... | |
void | setTimeout (bool b) |
Sets the option setTimeout to b . More... | |
Public Member Functions inherited from ogdf::UMLCrossingMinimizationModule | |
UMLCrossingMinimizationModule () | |
Initializes a UML crossing minimization module (default constructor). More... | |
UMLCrossingMinimizationModule (const UMLCrossingMinimizationModule &cmm) | |
Initializes a UML crossing minimization module (copy constructor). More... | |
virtual | ~UMLCrossingMinimizationModule () |
Destructor. More... | |
ReturnType | call (PlanRepUML &prUML, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr) |
Computes a planarized representation of the input graph. More... | |
ReturnType | operator() (PlanRepUML &prUML, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr) |
Computes a planarized representation of the input graph. More... | |
Public Member Functions inherited from ogdf::Module | |
Module () | |
Initializes a module. More... | |
virtual | ~Module () |
Public Member Functions inherited from ogdf::Timeouter | |
Timeouter () | |
timeout is turned of by default More... | |
Timeouter (bool t) | |
timeout is turned off (false) or on (true) (with 0 second) More... | |
Timeouter (const Timeouter &t) | |
Timeouter (double t) | |
timeout is set to the given value (seconds) More... | |
~Timeouter () | |
bool | isTimeLimit () const |
returns whether any time limit is set or not More... | |
Timeouter & | operator= (const Timeouter &t) |
double | timeLimit () const |
returns the current time limit for the call More... | |
void | timeLimit (bool t) |
shorthand to turn timelimit off or on (with 0 seconds) More... | |
void | timeLimit (double t) |
sets the time limit for the call (in seconds); <0 means no limit. More... | |
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 ReturnType | doCall (PlanRepUML &pr, int cc, const EdgeArray< int > *pCostOrig, int &crossingNumber) override |
Implements the algorithm call. More... | |
Static Private Member Functions | |
static bool | doSinglePermutation (PlanRepLight &prl, int cc, const EdgeArray< int > *pCost, Array< edge > &deletedEdges, UMLEdgeInsertionModule &inserter, std::minstd_rand &rng, int &crossingNumber) |
static void | doWorkHelper (ThreadMaster &master, UMLEdgeInsertionModule &inserter, std::minstd_rand &rng) |
Private Attributes | |
std::unique_ptr< UMLEdgeInsertionModule > | m_inserter |
The edge insertion module. More... | |
unsigned int | m_maxThreads |
The maximal number of used threads. More... | |
int | m_permutations |
The number of permutations. More... | |
bool | m_setTimeout |
The option for setting timeouts in submodules. More... | |
std::unique_ptr< PlanarSubgraphModule< int > > | m_subgraph |
The planar subgraph algorithm. More... | |
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::UMLCrossingMinimizationModule | |
static bool | checkCrossingGens (const PlanRepUML &prUML) |
Checks if the planarized represenation contains crossing generalizations. 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... | |
Protected Attributes inherited from ogdf::Timeouter | |
double | m_timeLimit |
Time limit for module calls (< 0 means no limit). More... | |
The planarization approach for UML crossing minimization.
This crossing minimization module represents a customizable implementation of the planarization approach. This approach consists of two phases. In the first phase, a planar subgraph is computed, and in the second phase, the remaining edges are re-inserted one-by-one, each time with as few crossings as possible; the crossings are then replaced by dummy nodes of degree four, resulting in a planarized representation of the graph.
Both steps, the computation of the planar subgraph and the re-insertion of a single edge, are implemented using module options. Additionaly, the second phase can be repeated several times, each time with a randomly permuted order of the edges to be re-inserted, and taking the solution with the least crossings. This can improve the quality of the solution significantly. More details on the planarization approach can be found in
C. Gutwenger, P. Mutzel: An Experimental Study of Crossing Minimization Heuristics. 11th International Symposium on Graph Drawing 2003, Perugia (GD '03), LNCS 2912, pp. 13-24, 2004.
Option | Type | Default | Description |
---|---|---|---|
permutations | int | 1 | The number of permutations the (complete) edge insertion phase is repeated. |
setTimeout | bool | true | If set to true, the time limit is also passed to submodules; otherwise, a timeout might be checked late when a submodule requires a lot of runtime. |
maxThreads | int | System::numberOfProcessors() | This is the maximal number of threads that will be used for parallelizing the algorithm. At the moment, each permutation is parallelized, hence the there will never be used more threads than permutations. To achieve sequential behaviour, set maxThreads to 1. |
The various phases of the algorithm can be exchanged by setting module options allowing flexible customization. The algorithm provides the following module options:
Option | Type | Default | Description |
---|---|---|---|
subgraph | PlanarSubgraphModule | FastPlanarSubgraph | The module for the computation of the planar subgraph. |
inserter | UMLEdgeInsertionModule | VariableEmbeddingInserterLight | The module used for edge insertion. The edges not contained in the planar subgraph are re-inserted one-by-one, each with as few crossings as possible. |
Definition at line 104 of file SubgraphPlanarizerUML.h.
ogdf::SubgraphPlanarizerUML::SubgraphPlanarizerUML | ( | ) |
Creates an instance of subgraph planarizer with default settings.
ogdf::SubgraphPlanarizerUML::SubgraphPlanarizerUML | ( | const SubgraphPlanarizerUML & | planarizer | ) |
Creates an instance of subgraph planarizer with the same settings as planarizer
.
|
overridevirtual |
Returns a new instance of subgraph planarizer with the same option settings.
Implements ogdf::UMLCrossingMinimizationModule.
|
overrideprotectedvirtual |
Implements the algorithm call.
Implements ogdf::UMLCrossingMinimizationModule.
|
staticprivate |
|
staticprivate |
|
inline |
Returns the maximal number of used threads.
Definition at line 145 of file SubgraphPlanarizerUML.h.
|
inline |
Sets the maximal number of used threads to n
.
Definition at line 148 of file SubgraphPlanarizerUML.h.
SubgraphPlanarizerUML& ogdf::SubgraphPlanarizerUML::operator= | ( | const SubgraphPlanarizerUML & | planarizer | ) |
Assignment operator. Copies option settings only.
|
inline |
Returns the number of permutations.
Definition at line 133 of file SubgraphPlanarizerUML.h.
|
inline |
Sets the number of permutations to p
.
Definition at line 136 of file SubgraphPlanarizerUML.h.
|
inline |
Sets the module option for the edge insertion module.
Definition at line 130 of file SubgraphPlanarizerUML.h.
|
inline |
Sets the module option for the computation of the planar subgraph.
Definition at line 127 of file SubgraphPlanarizerUML.h.
|
inline |
Returns the current setting of options setTimeout.
Definition at line 139 of file SubgraphPlanarizerUML.h.
|
inline |
Sets the option setTimeout to b
.
Definition at line 142 of file SubgraphPlanarizerUML.h.
|
private |
The edge insertion module.
Definition at line 163 of file SubgraphPlanarizerUML.h.
|
private |
The maximal number of used threads.
Definition at line 167 of file SubgraphPlanarizerUML.h.
|
private |
The number of permutations.
Definition at line 165 of file SubgraphPlanarizerUML.h.
|
private |
The option for setting timeouts in submodules.
Definition at line 166 of file SubgraphPlanarizerUML.h.
|
private |
The planar subgraph algorithm.
Definition at line 162 of file SubgraphPlanarizerUML.h.