|
| | SubgraphPlanarizer () |
| | Creates an instance of subgraph planarizer with default settings. More...
|
| |
| | SubgraphPlanarizer (const SubgraphPlanarizer &planarizer) |
| | Creates an instance of subgraph planarizer with the same settings as planarizer. More...
|
| |
| virtual CrossingMinimizationModule * | 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...
|
| |
| SubgraphPlanarizer & | operator= (const SubgraphPlanarizer &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 (EdgeInsertionModule *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...
|
| |
| | CrossingMinimizationModule () |
| | Initializes a crossing minimization module (default constructor). More...
|
| |
| | CrossingMinimizationModule (const CrossingMinimizationModule &cmm) |
| | Initializes an crossing minimization module (copy constructor). More...
|
| |
| virtual | ~CrossingMinimizationModule () |
| | Destructor. More...
|
| |
| ReturnType | call (PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr) |
| | Computes a planarized representation of the input graph. More...
|
| |
| ReturnType | operator() (PlanRep &pr, int cc, int &crossingNumber, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr) |
| | Computes a planarized representation of the input graph. More...
|
| |
| | Module () |
| | Initializes a module. More...
|
| |
| virtual | ~Module () |
| |
| | 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...
|
| |
| | 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...
|
| |
|
| 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...
|
| |
| static int | computeCrossingNumber (GraphCopy &graphCopy, const EdgeArray< int > *pCost, const EdgeArray< uint32_t > *pEdgeSubGraphs) |
| | Computes the (weighted) crossing number of the planarization graphCopy. More...
|
| |
| double | m_timeLimit |
| | Time limit for module calls (< 0 means no limit). More...
|
| |
The planarization approach for 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.
Optional parameters
| 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. |
Module options
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 | EdgeInsertionModule | VariableEmbeddingInserter | 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 112 of file SubgraphPlanarizer.h.
Inheritance diagram for ogdf::SubgraphPlanarizer:
