Multi edge inserter with approximation guarantee. More...
#include <ogdf/planarity/MultiEdgeApproxInserter.h>
Classes | |
struct | VertexBlock |
Public Member Functions | |
MultiEdgeApproxInserter () | |
Creates an instance of multi-edge approx inserter with default option settings. | |
MultiEdgeApproxInserter (const MultiEdgeApproxInserter &inserter) | |
Creates an instance of multi-edge approx inserter with the same settings as inserter . | |
~MultiEdgeApproxInserter () | |
Destructor. | |
virtual EdgeInsertionModule * | clone () const override |
Returns a new instance of the multi-edge approx inserter with the same option settings. | |
MultiEdgeApproxInserter & | operator= (const MultiEdgeApproxInserter &inserter) |
Assignment operator. Copies option settings only. | |
double | percentMostCrossedFix () const |
Returns the current setting of option percentMostCrossed. | |
void | percentMostCrossedFix (double percent) |
Sets the option percentMostCrossed to percent . | |
double | percentMostCrossedVar () const |
Returns the current setting of option percentMostCrossed (variable embedding). | |
void | percentMostCrossedVar (double percent) |
Sets the option percentMostCrossedVar to percent . | |
RemoveReinsertType | removeReinsertFix () const |
Returns the current setting of the remove-reinsert postprocessing method. | |
void | removeReinsertFix (RemoveReinsertType rrOption) |
Sets the remove-reinsert postprocessing method. | |
RemoveReinsertType | removeReinsertVar () const |
Returns the current setting of the remove-reinsert postprocessing method. | |
void | removeReinsertVar (RemoveReinsertType rrOption) |
Sets the remove-reinsert postprocessing method. | |
bool | statistics () const |
void | statistics (bool b) |
int | sumFEInsertionCosts () const |
int | sumInsertionCosts () const |
![]() | |
EdgeInsertionModule () | |
Initializes an edge insertion module (default constructor). | |
EdgeInsertionModule (const EdgeInsertionModule &eim) | |
Initializes an edge insertion module (copy constructor). | |
virtual | ~EdgeInsertionModule () |
Destructor. | |
ReturnType | call (PlanRepLight &pr, const Array< edge > &origEdges) |
Inserts all edges in origEdges into pr . | |
ReturnType | call (PlanRepLight &pr, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges) |
Inserts all edges in origEdges with given forbidden edges into pr . | |
ReturnType | call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const Array< edge > &origEdges) |
Inserts all edges in origEdges with given costs into pr . | |
ReturnType | call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const Array< edge > &origEdges, const EdgeArray< uint32_t > &edgeSubGraphs) |
Inserts all edges in origEdges with given costs and subgraphs (for simultaneous drawing) into pr . | |
ReturnType | call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges) |
Inserts all edges in origEdges with given costs and forbidden edges into pr . | |
ReturnType | call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges, const EdgeArray< uint32_t > &edgeSubGraphs) |
Inserts all edges in origEdges with given costs, forbidden edges, and subgraphs (for simultaneous drawing) into pr . | |
ReturnType | callEx (PlanRepLight &pr, const Array< edge > &origEdges, const EdgeArray< int > *pCostOrig=nullptr, const EdgeArray< bool > *pForbiddenOrig=nullptr, const EdgeArray< uint32_t > *pEdgeSubGraphs=nullptr) |
Inserts all edges in origEdges into pr , optionally costs, forbidden edges, and subgraphs (for simultaneous drawing) may be given. | |
![]() | |
Module () | |
Initializes a module. | |
virtual | ~Module () |
![]() | |
Timeouter () | |
timeout is turned of by default | |
Timeouter (bool t) | |
timeout is turned off (false) or on (true) (with 0 second) | |
Timeouter (const Timeouter &t) | |
Timeouter (double t) | |
timeout is set to the given value (seconds) | |
~Timeouter () | |
bool | isTimeLimit () const |
returns whether any time limit is set or not | |
Timeouter & | operator= (const Timeouter &t) |
double | timeLimit () const |
returns the current time limit for the call | |
void | timeLimit (bool t) |
shorthand to turn timelimit off or on (with 0 seconds) | |
void | timeLimit (double t) |
sets the time limit for the call (in seconds); <0 means no limit. | |
Private Types | |
enum class | PathDir { Left , Right , None } |
Private Member Functions | |
void | cleanup () |
void | computePathBC (int k) |
int | computePathSPQR (int b, node v, node w, int k) |
MultiEdgeApproxInserter::Block * | constructBlock (int i) |
void | constructDual (const PlanRepLight &pr) |
node | copy (node vOrig, int b) |
bool | dfsPathBlock (int b, node parent, int k, node t) |
bool | dfsPathVertex (node v, int parent, int k, node t) |
ReturnType | doCall (PlanRepLight &pr, const Array< edge > &origEdges, const EdgeArray< int > *costOrig, const EdgeArray< bool > *forbiddenEdge, const EdgeArray< uint32_t > *edgeSubGraphs) override |
Implements the algorithm call. | |
void | embedBlock (int b, int m) |
int | findShortestPath (node s, node t) |
void | recFlipPref (adjEntry adjP, NodeArray< EmbeddingPreference > &pi_pick, const NodeArray< bool > &visited, StaticPlanarSPQRTree &spqr) |
Static Private Member Functions | |
static bool | dfsPathSPQR (node v, node v2, edge eParent, List< edge > &path) |
static PathDir | oppDir (PathDir dir) |
Returns the opposite direction of dir . | |
Private Attributes | |
Array< Block * > | m_block |
NodeArray< SList< int > > | m_compV |
NodeArray< SList< VertexBlock > > | m_copyInBlocks |
const EdgeArray< int > * | m_costOrig |
Graph | m_dual |
ConstCombinatorialEmbedding | m_E |
const Array< edge > * | m_edge |
Array< SList< edge > > | m_edgesB |
FaceArray< node > | m_faceNode |
NodeArray< node > | m_GtoBC |
Array< int > | m_insertionCosts |
Array< List< VertexBlock > > | m_pathBCs |
double | m_percentMostCrossedFix |
The portion of most crossed edges considered (fixed embedding). | |
double | m_percentMostCrossedVar |
The portion of most crossed edges considered (variable embedding). | |
PlanRepLight * | m_pPG |
AdjEntryArray< adjEntry > | m_primalAdj |
RemoveReinsertType | m_rrOptionFix |
The remove-reinsert method for fixed embedding. | |
RemoveReinsertType | m_rrOptionVar |
The remove-reinsert method for variable embedding. | |
bool | m_statistics |
int | m_sumFEInsertionCosts |
int | m_sumInsertionCosts |
Array< SList< node > > | m_verticesB |
node | m_vS |
node | m_vT |
Additional Inherited Members | |
![]() | |
enum class | ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , Error } |
The return type of a module. More... | |
![]() | |
static bool | isSolution (ReturnType ret) |
Returns true iff ret indicates that the module returned a feasible solution. | |
![]() | |
double | m_timeLimit |
Time limit for module calls (< 0 means no limit). | |
Multi edge inserter with approximation guarantee.
The implementation is based on the following publication:
Markus Chimani and Carsten Gutwenger: Advances in the Planarization Method: Effective Multiple Edge Insertions. Journal of Graph Algorithms and Applications (JGAA), 16(3), pp. 729-757, 2012.
Definition at line 50 of file MultiEdgeApproxInserter.h.
|
strongprivate |
Enumerator | |
---|---|
Left | |
Right | |
None |
Definition at line 108 of file MultiEdgeApproxInserter.h.
ogdf::MultiEdgeApproxInserter::MultiEdgeApproxInserter | ( | ) |
Creates an instance of multi-edge approx inserter with default option settings.
ogdf::MultiEdgeApproxInserter::MultiEdgeApproxInserter | ( | const MultiEdgeApproxInserter & | inserter | ) |
Creates an instance of multi-edge approx inserter with the same settings as inserter
.
|
inline |
Destructor.
Definition at line 59 of file MultiEdgeApproxInserter.h.
|
private |
|
overridevirtual |
Returns a new instance of the multi-edge approx inserter with the same option settings.
Implements ogdf::EdgeInsertionModule.
|
private |
|
private |
|
staticprivate |
|
overrideprivatevirtual |
Implements the algorithm call.
Implements ogdf::EdgeInsertionModule.
MultiEdgeApproxInserter & ogdf::MultiEdgeApproxInserter::operator= | ( | const MultiEdgeApproxInserter & | inserter | ) |
Assignment operator. Copies option settings only.
Returns the opposite direction of dir
.
Definition at line 111 of file MultiEdgeApproxInserter.h.
|
inline |
Returns the current setting of option percentMostCrossed.
Definition at line 87 of file MultiEdgeApproxInserter.h.
Sets the option percentMostCrossed to percent
.
This option determines the portion of most crossed edges used if the remove-reinsert method is set to RemoveReinsertType::MostCrossed. This portion is number of edges * percentMostCrossed() / 100.
Definition at line 84 of file MultiEdgeApproxInserter.h.
|
inline |
Returns the current setting of option percentMostCrossed (variable embedding).
Definition at line 97 of file MultiEdgeApproxInserter.h.
Sets the option percentMostCrossedVar to percent
.
This option determines the portion of most crossed edges used if the remove-reinsert method (variable embedding) is set to RemoveReinsertType::MostCrossed. This portion is number of edges * percentMostCrossed() / 100.
Definition at line 94 of file MultiEdgeApproxInserter.h.
|
private |
|
inline |
Returns the current setting of the remove-reinsert postprocessing method.
Definition at line 71 of file MultiEdgeApproxInserter.h.
|
inline |
Sets the remove-reinsert postprocessing method.
Definition at line 68 of file MultiEdgeApproxInserter.h.
|
inline |
Returns the current setting of the remove-reinsert postprocessing method.
Definition at line 77 of file MultiEdgeApproxInserter.h.
|
inline |
Sets the remove-reinsert postprocessing method.
Definition at line 74 of file MultiEdgeApproxInserter.h.
|
inline |
Definition at line 101 of file MultiEdgeApproxInserter.h.
Definition at line 99 of file MultiEdgeApproxInserter.h.
|
inline |
Definition at line 105 of file MultiEdgeApproxInserter.h.
|
inline |
Definition at line 103 of file MultiEdgeApproxInserter.h.
Definition at line 173 of file MultiEdgeApproxInserter.h.
Definition at line 164 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 168 of file MultiEdgeApproxInserter.h.
Definition at line 162 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 184 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 183 of file MultiEdgeApproxInserter.h.
Definition at line 170 of file MultiEdgeApproxInserter.h.
Definition at line 166 of file MultiEdgeApproxInserter.h.
Definition at line 185 of file MultiEdgeApproxInserter.h.
Definition at line 167 of file MultiEdgeApproxInserter.h.
Definition at line 172 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 171 of file MultiEdgeApproxInserter.h.
|
private |
The portion of most crossed edges considered (fixed embedding).
Definition at line 157 of file MultiEdgeApproxInserter.h.
|
private |
The portion of most crossed edges considered (variable embedding).
Definition at line 158 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 161 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 186 of file MultiEdgeApproxInserter.h.
|
private |
The remove-reinsert method for fixed embedding.
Definition at line 155 of file MultiEdgeApproxInserter.h.
|
private |
The remove-reinsert method for variable embedding.
Definition at line 156 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 159 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 177 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 176 of file MultiEdgeApproxInserter.h.
Definition at line 165 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 187 of file MultiEdgeApproxInserter.h.
|
private |
Definition at line 187 of file MultiEdgeApproxInserter.h.