|
|||
|
|
|
|||
|
|
The planarization approach for crossing minimization. More...
#include <ogdf/planarity/SubgraphPlanarizer.h>
Classes | |
| class | CrossingStructure |
Public Member Functions | |
| SubgraphPlanarizer () | |
| Creates an instance of subgraph planarizer. | |
| void | setSubgraph (PlanarSubgraphModule *pSubgraph) |
| Sets the module option for the computation of the planar subgraph. | |
| void | setInserter (EdgeInsertionModule *pInserter) |
| Sets the module option for the edge insertion module. | |
| int | permutations () |
| Returns the number of permutations. | |
| void | permutations (int p) |
| Sets the number of permutations to p. | |
| bool | setTimeout () |
| Returns the current setting of options setTimeout. | |
| void | setTimeout (bool b) |
| Sets the option setTimeout to b. | |
Protected Member Functions | |
| virtual ReturnType | doCall (PlanRep &PG, int cc, const EdgeArray< int > &cost, const EdgeArray< bool > &forbid, const EdgeArray< unsigned int > &subgraphs, int &crossingNumber) |
| Implements the algorithm call. | |
Private Attributes | |
| ModuleOption < PlanarSubgraphModule > | m_subgraph |
| The planar subgraph algorithm. | |
| ModuleOption< EdgeInsertionModule > | m_inserter |
| The edge insertion module. | |
| int | m_permutations |
| The number of permutations. | |
| bool | m_setTimeout |
| The option for setting timeouts in submodules. | |
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.
| 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. |
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 113 of file SubgraphPlanarizer.h.
| ogdf::SubgraphPlanarizer::SubgraphPlanarizer | ( | ) |
Creates an instance of subgraph planarizer.
| virtual ReturnType ogdf::SubgraphPlanarizer::doCall | ( | PlanRep & | PG, | |
| int | cc, | |||
| const EdgeArray< int > & | cost, | |||
| const EdgeArray< bool > & | forbid, | |||
| const EdgeArray< unsigned int > & | subgraphs, | |||
| int & | crossingNumber | |||
| ) | [protected, virtual] |
Implements the algorithm call.
| int ogdf::SubgraphPlanarizer::permutations | ( | ) | [inline] |
Returns the number of permutations.
Definition at line 99 of file SubgraphPlanarizer.h.
| void ogdf::SubgraphPlanarizer::permutations | ( | int | p | ) | [inline] |
Sets the number of permutations to p.
Definition at line 102 of file SubgraphPlanarizer.h.
| void ogdf::SubgraphPlanarizer::setInserter | ( | EdgeInsertionModule * | pInserter | ) | [inline] |
Sets the module option for the edge insertion module.
Definition at line 94 of file SubgraphPlanarizer.h.
| void ogdf::SubgraphPlanarizer::setSubgraph | ( | PlanarSubgraphModule * | pSubgraph | ) | [inline] |
Sets the module option for the computation of the planar subgraph.
Definition at line 89 of file SubgraphPlanarizer.h.
| void ogdf::SubgraphPlanarizer::setTimeout | ( | bool | b | ) | [inline] |
Sets the option setTimeout to b.
Definition at line 108 of file SubgraphPlanarizer.h.
| bool ogdf::SubgraphPlanarizer::setTimeout | ( | ) | [inline] |
Returns the current setting of options setTimeout.
Definition at line 105 of file SubgraphPlanarizer.h.
The edge insertion module.
Definition at line 112 of file SubgraphPlanarizer.h.
int ogdf::SubgraphPlanarizer::m_permutations [private] |
The number of permutations.
Definition at line 114 of file SubgraphPlanarizer.h.
bool ogdf::SubgraphPlanarizer::m_setTimeout [private] |
The option for setting timeouts in submodules.
Definition at line 115 of file SubgraphPlanarizer.h.
The planar subgraph algorithm.
Definition at line 111 of file SubgraphPlanarizer.h.
