#include <ogdf/planarity/PlanarizerMixedInsertion.h>
Public Types | |
enum | NodeSelectionMethod { NodeSelectionMethod::Random, NodeSelectionMethod::HigherDegree, NodeSelectionMethod::LowerDegree, NodeSelectionMethod::HigherNonPlanarDegree, NodeSelectionMethod::LowerNonPlanarDegree, NodeSelectionMethod::BothEndpoints } |
Determines the node(s) of each deleted edge e which will be reinserted if neither of them is a cut vertex. More... | |
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 Member Functions | |
PlanarizerMixedInsertion () | |
Creates a PlanarizerMixedInsertion with default settings. More... | |
PlanarizerMixedInsertion (const PlanarizerMixedInsertion &planarizer) | |
Creates a PlanarizerMixedInsertion with the same settings as planarizer . More... | |
virtual CrossingMinimizationModule * | clone () const override |
Returns a new PlanarizerMixedInsertion with the same option settings. More... | |
NodeSelectionMethod | nodeSelectionMethod () |
Returns the used method of selecting nodes to reinsert. More... | |
void | nodeSelectionMethod (NodeSelectionMethod method) |
Sets the used method of selecting nodes to reinsert. More... | |
PlanarizerMixedInsertion & | operator= (const PlanarizerMixedInsertion &planarizer) |
Assignment operator, copies option settings only. More... | |
void | setSubgraph (PlanarSubgraphModule< int > *pSubgraph) |
Sets the module option for the computation of the planar subgraph. More... | |
Public Member Functions inherited from ogdf::CrossingMinimizationModule | |
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... | |
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... | |
Protected Member Functions | |
virtual ReturnType | doCall (PlanRep &pr, int cc, const EdgeArray< int > *pCostOrig, const EdgeArray< bool > *pForbiddenOrig, const EdgeArray< uint32_t > *pEdgeSubGraphs, int &crossingNumber) override |
Implements the algorithm call. More... | |
Private Attributes | |
NodeSelectionMethod | m_nodeSelectionMethod |
std::unique_ptr< PlanarSubgraphModule< int > > | m_subgraph |
< The planar subgraph algorithm. More... | |
Additional Inherited Members | |
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 Protected Member Functions inherited from ogdf::CrossingMinimizationModule | |
static int | computeCrossingNumber (GraphCopy &graphCopy, const EdgeArray< int > *pCost, const EdgeArray< uint32_t > *pEdgeSubGraphs) |
Computes the (weighted) crossing number of the planarization graphCopy . More... | |
Protected Attributes inherited from ogdf::Timeouter | |
double | m_timeLimit |
Time limit for module calls (< 0 means no limit). More... | |
Computes a planar subgraph of the graph and then re-inserts each original node that is incident to at least one edge not in the subgraph via the StarInserter. Whether all nodes incident to these edges are re-inserted or just some of them, can be configured. If an edge is not in the planar subgraph but both of its endpoints are cut vertices in the planar subgraph, the edge is reinserted via an EdgeInsertionModule. See:
M. Chimani, M. Ilsen, T. Wiedera: Star-Struck by Fixed Embeddings: Modern Crossing Number Heuristics. In: Purchase H.C., Rutter I. (eds) GD 2021. LNCS, vol. 12868, pp. 41–56. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92931-2_3
Option | Type | Default | Description |
---|---|---|---|
subgraph | PlanarSubgraphModule | PlanarSubgraphFast<int> | The module for the computation of the planar subgraph. |
nodeSelectionMethod | NodeSelectionMethod | HigherDegree | Determines which nodes are reinserted. |
Definition at line 69 of file PlanarizerMixedInsertion.h.
Determines the node(s) of each deleted edge e which will be reinserted if neither of them is a cut vertex.
Definition at line 84 of file PlanarizerMixedInsertion.h.
ogdf::PlanarizerMixedInsertion::PlanarizerMixedInsertion | ( | ) |
Creates a PlanarizerMixedInsertion with default settings.
ogdf::PlanarizerMixedInsertion::PlanarizerMixedInsertion | ( | const PlanarizerMixedInsertion & | planarizer | ) |
Creates a PlanarizerMixedInsertion with the same settings as planarizer
.
|
overridevirtual |
Returns a new PlanarizerMixedInsertion with the same option settings.
Implements ogdf::CrossingMinimizationModule.
|
overrideprotectedvirtual |
Implements the algorithm call.
pr
must be simple. Implements ogdf::CrossingMinimizationModule.
|
inline |
Returns the used method of selecting nodes to reinsert.
Definition at line 111 of file PlanarizerMixedInsertion.h.
|
inline |
Sets the used method of selecting nodes to reinsert.
Definition at line 114 of file PlanarizerMixedInsertion.h.
PlanarizerMixedInsertion& ogdf::PlanarizerMixedInsertion::operator= | ( | const PlanarizerMixedInsertion & | planarizer | ) |
Assignment operator, copies option settings only.
|
inline |
Sets the module option for the computation of the planar subgraph.
Definition at line 108 of file PlanarizerMixedInsertion.h.
|
private |
Definition at line 121 of file PlanarizerMixedInsertion.h.
|
private |
< The planar subgraph algorithm.
How to select the nodes which are reinserted.
Definition at line 118 of file PlanarizerMixedInsertion.h.