Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MultiEdgeApproxInserter Class Reference

Multi edge inserter with approximation guarantee. More...

#include <ogdf/planarity/MultiEdgeApproxInserter.h>

+ Inheritance diagram for ogdf::MultiEdgeApproxInserter:

Classes

struct  VertexBlock
 

Public Member Functions

 MultiEdgeApproxInserter ()
 Creates an instance of multi-edge approx inserter with default option settings. More...
 
 MultiEdgeApproxInserter (const MultiEdgeApproxInserter &inserter)
 Creates an instance of multi-edge approx inserter with the same settings as inserter. More...
 
 ~MultiEdgeApproxInserter ()
 Destructor. More...
 
virtual EdgeInsertionModuleclone () const override
 Returns a new instance of the multi-edge approx inserter with the same option settings. More...
 
MultiEdgeApproxInserteroperator= (const MultiEdgeApproxInserter &inserter)
 Assignment operator. Copies option settings only. More...
 
double percentMostCrossedFix () const
 Returns the current setting of option percentMostCrossed. More...
 
void percentMostCrossedFix (double percent)
 Sets the option percentMostCrossed to percent. More...
 
double percentMostCrossedVar () const
 Returns the current setting of option percentMostCrossed (variable embedding). More...
 
void percentMostCrossedVar (double percent)
 Sets the option percentMostCrossedVar to percent. More...
 
RemoveReinsertType removeReinsertFix () const
 Returns the current setting of the remove-reinsert postprocessing method. More...
 
void removeReinsertFix (RemoveReinsertType rrOption)
 Sets the remove-reinsert postprocessing method. More...
 
RemoveReinsertType removeReinsertVar () const
 Returns the current setting of the remove-reinsert postprocessing method. More...
 
void removeReinsertVar (RemoveReinsertType rrOption)
 Sets the remove-reinsert postprocessing method. More...
 
bool statistics () const
 
void statistics (bool b)
 
int sumFEInsertionCosts () const
 
int sumInsertionCosts () const
 
- Public Member Functions inherited from ogdf::EdgeInsertionModule
 EdgeInsertionModule ()
 Initializes an edge insertion module (default constructor). More...
 
 EdgeInsertionModule (const EdgeInsertionModule &eim)
 Initializes an edge insertion module (copy constructor). More...
 
virtual ~EdgeInsertionModule ()
 Destructor. More...
 
ReturnType call (PlanRepLight &pr, const Array< edge > &origEdges)
 Inserts all edges in origEdges into pr. More...
 
ReturnType call (PlanRepLight &pr, const EdgeArray< bool > &forbiddenOrig, const Array< edge > &origEdges)
 Inserts all edges in origEdges with given forbidden edges into pr. More...
 
ReturnType call (PlanRepLight &pr, const EdgeArray< int > &costOrig, const Array< edge > &origEdges)
 Inserts all edges in origEdges with given costs into pr. More...
 
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. More...
 
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. More...
 
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. More...
 
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. 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...
 
Timeouteroperator= (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...
 

Private Types

enum  PathDir { PathDir::Left, PathDir::Right, PathDir::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. More...
 
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. More...
 

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< nodem_faceNode
 
NodeArray< nodem_GtoBC
 
Array< int > m_insertionCosts
 
Array< List< VertexBlock > > m_pathBCs
 
double m_percentMostCrossedFix
 The portion of most crossed edges considered (fixed embedding). More...
 
double m_percentMostCrossedVar
 The portion of most crossed edges considered (variable embedding). More...
 
PlanRepLightm_pPG
 
AdjEntryArray< adjEntrym_primalAdj
 
RemoveReinsertType m_rrOptionFix
 The remove-reinsert method for fixed embedding. More...
 
RemoveReinsertType m_rrOptionVar
 The remove-reinsert method for variable embedding. More...
 
bool m_statistics
 
int m_sumFEInsertionCosts
 
int m_sumInsertionCosts
 
Array< SList< node > > m_verticesB
 
node m_vS
 
node m_vT
 

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...
 
- 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...
 
- Protected Attributes inherited from ogdf::Timeouter
double m_timeLimit
 Time limit for module calls (< 0 means no limit). More...
 

Detailed Description

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.

Member Enumeration Documentation

◆ PathDir

Enumerator
Left 
Right 
None 

Definition at line 128 of file MultiEdgeApproxInserter.h.

Constructor & Destructor Documentation

◆ MultiEdgeApproxInserter() [1/2]

ogdf::MultiEdgeApproxInserter::MultiEdgeApproxInserter ( )

Creates an instance of multi-edge approx inserter with default option settings.

◆ MultiEdgeApproxInserter() [2/2]

ogdf::MultiEdgeApproxInserter::MultiEdgeApproxInserter ( const MultiEdgeApproxInserter inserter)

Creates an instance of multi-edge approx inserter with the same settings as inserter.

◆ ~MultiEdgeApproxInserter()

ogdf::MultiEdgeApproxInserter::~MultiEdgeApproxInserter ( )
inline

Destructor.

Definition at line 60 of file MultiEdgeApproxInserter.h.

Member Function Documentation

◆ cleanup()

void ogdf::MultiEdgeApproxInserter::cleanup ( )
private

◆ clone()

virtual EdgeInsertionModule* ogdf::MultiEdgeApproxInserter::clone ( ) const
overridevirtual

Returns a new instance of the multi-edge approx inserter with the same option settings.

Implements ogdf::EdgeInsertionModule.

◆ computePathBC()

void ogdf::MultiEdgeApproxInserter::computePathBC ( int  k)
private

◆ computePathSPQR()

int ogdf::MultiEdgeApproxInserter::computePathSPQR ( int  b,
node  v,
node  w,
int  k 
)
private

◆ constructBlock()

MultiEdgeApproxInserter::Block* ogdf::MultiEdgeApproxInserter::constructBlock ( int  i)
private

◆ constructDual()

void ogdf::MultiEdgeApproxInserter::constructDual ( const PlanRepLight pr)
private

◆ copy()

node ogdf::MultiEdgeApproxInserter::copy ( node  vOrig,
int  b 
)
private

◆ dfsPathBlock()

bool ogdf::MultiEdgeApproxInserter::dfsPathBlock ( int  b,
node  parent,
int  k,
node  t 
)
private

◆ dfsPathSPQR()

static bool ogdf::MultiEdgeApproxInserter::dfsPathSPQR ( node  v,
node  v2,
edge  eParent,
List< edge > &  path 
)
staticprivate

◆ dfsPathVertex()

bool ogdf::MultiEdgeApproxInserter::dfsPathVertex ( node  v,
int  parent,
int  k,
node  t 
)
private

◆ doCall()

ReturnType ogdf::MultiEdgeApproxInserter::doCall ( PlanRepLight pr,
const Array< edge > &  origEdges,
const EdgeArray< int > *  costOrig,
const EdgeArray< bool > *  forbiddenEdge,
const EdgeArray< uint32_t > *  edgeSubGraphs 
)
overrideprivatevirtual

Implements the algorithm call.

Implements ogdf::EdgeInsertionModule.

◆ embedBlock()

void ogdf::MultiEdgeApproxInserter::embedBlock ( int  b,
int  m 
)
private

◆ findShortestPath()

int ogdf::MultiEdgeApproxInserter::findShortestPath ( node  s,
node  t 
)
private

◆ operator=()

MultiEdgeApproxInserter& ogdf::MultiEdgeApproxInserter::operator= ( const MultiEdgeApproxInserter inserter)

Assignment operator. Copies option settings only.

◆ oppDir()

static PathDir ogdf::MultiEdgeApproxInserter::oppDir ( PathDir  dir)
inlinestaticprivate

Returns the opposite direction of dir.

Definition at line 131 of file MultiEdgeApproxInserter.h.

◆ percentMostCrossedFix() [1/2]

double ogdf::MultiEdgeApproxInserter::percentMostCrossedFix ( ) const
inline

Returns the current setting of option percentMostCrossed.

Definition at line 98 of file MultiEdgeApproxInserter.h.

◆ percentMostCrossedFix() [2/2]

void ogdf::MultiEdgeApproxInserter::percentMostCrossedFix ( double  percent)
inline

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 93 of file MultiEdgeApproxInserter.h.

◆ percentMostCrossedVar() [1/2]

double ogdf::MultiEdgeApproxInserter::percentMostCrossedVar ( ) const
inline

Returns the current setting of option percentMostCrossed (variable embedding).

Definition at line 112 of file MultiEdgeApproxInserter.h.

◆ percentMostCrossedVar() [2/2]

void ogdf::MultiEdgeApproxInserter::percentMostCrossedVar ( double  percent)
inline

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 107 of file MultiEdgeApproxInserter.h.

◆ recFlipPref()

void ogdf::MultiEdgeApproxInserter::recFlipPref ( adjEntry  adjP,
NodeArray< EmbeddingPreference > &  pi_pick,
const NodeArray< bool > &  visited,
StaticPlanarSPQRTree spqr 
)
private

◆ removeReinsertFix() [1/2]

RemoveReinsertType ogdf::MultiEdgeApproxInserter::removeReinsertFix ( ) const
inline

Returns the current setting of the remove-reinsert postprocessing method.

Definition at line 74 of file MultiEdgeApproxInserter.h.

◆ removeReinsertFix() [2/2]

void ogdf::MultiEdgeApproxInserter::removeReinsertFix ( RemoveReinsertType  rrOption)
inline

Sets the remove-reinsert postprocessing method.

Definition at line 69 of file MultiEdgeApproxInserter.h.

◆ removeReinsertVar() [1/2]

RemoveReinsertType ogdf::MultiEdgeApproxInserter::removeReinsertVar ( ) const
inline

Returns the current setting of the remove-reinsert postprocessing method.

Definition at line 84 of file MultiEdgeApproxInserter.h.

◆ removeReinsertVar() [2/2]

void ogdf::MultiEdgeApproxInserter::removeReinsertVar ( RemoveReinsertType  rrOption)
inline

Sets the remove-reinsert postprocessing method.

Definition at line 79 of file MultiEdgeApproxInserter.h.

◆ statistics() [1/2]

bool ogdf::MultiEdgeApproxInserter::statistics ( ) const
inline

Definition at line 120 of file MultiEdgeApproxInserter.h.

◆ statistics() [2/2]

void ogdf::MultiEdgeApproxInserter::statistics ( bool  b)
inline

Definition at line 116 of file MultiEdgeApproxInserter.h.

◆ sumFEInsertionCosts()

int ogdf::MultiEdgeApproxInserter::sumFEInsertionCosts ( ) const
inline

Definition at line 125 of file MultiEdgeApproxInserter.h.

◆ sumInsertionCosts()

int ogdf::MultiEdgeApproxInserter::sumInsertionCosts ( ) const
inline

Definition at line 124 of file MultiEdgeApproxInserter.h.

Member Data Documentation

◆ m_block

Array<Block*> ogdf::MultiEdgeApproxInserter::m_block
private

Definition at line 196 of file MultiEdgeApproxInserter.h.

◆ m_compV

NodeArray<SList<int> > ogdf::MultiEdgeApproxInserter::m_compV
private

Definition at line 187 of file MultiEdgeApproxInserter.h.

◆ m_copyInBlocks

NodeArray<SList<VertexBlock> > ogdf::MultiEdgeApproxInserter::m_copyInBlocks
private

Definition at line 191 of file MultiEdgeApproxInserter.h.

◆ m_costOrig

const EdgeArray<int>* ogdf::MultiEdgeApproxInserter::m_costOrig
private

Definition at line 185 of file MultiEdgeApproxInserter.h.

◆ m_dual

Graph ogdf::MultiEdgeApproxInserter::m_dual
private

Definition at line 207 of file MultiEdgeApproxInserter.h.

◆ m_E

ConstCombinatorialEmbedding ogdf::MultiEdgeApproxInserter::m_E
private

Definition at line 206 of file MultiEdgeApproxInserter.h.

◆ m_edge

const Array<edge>* ogdf::MultiEdgeApproxInserter::m_edge
private

Definition at line 193 of file MultiEdgeApproxInserter.h.

◆ m_edgesB

Array<SList<edge> > ogdf::MultiEdgeApproxInserter::m_edgesB
private

Definition at line 189 of file MultiEdgeApproxInserter.h.

◆ m_faceNode

FaceArray<node> ogdf::MultiEdgeApproxInserter::m_faceNode
private

Definition at line 208 of file MultiEdgeApproxInserter.h.

◆ m_GtoBC

NodeArray<node> ogdf::MultiEdgeApproxInserter::m_GtoBC
private

Definition at line 190 of file MultiEdgeApproxInserter.h.

◆ m_insertionCosts

Array<int> ogdf::MultiEdgeApproxInserter::m_insertionCosts
private

Definition at line 195 of file MultiEdgeApproxInserter.h.

◆ m_pathBCs

Array<List<VertexBlock> > ogdf::MultiEdgeApproxInserter::m_pathBCs
private

Definition at line 194 of file MultiEdgeApproxInserter.h.

◆ m_percentMostCrossedFix

double ogdf::MultiEdgeApproxInserter::m_percentMostCrossedFix
private

The portion of most crossed edges considered (fixed embedding).

Definition at line 180 of file MultiEdgeApproxInserter.h.

◆ m_percentMostCrossedVar

double ogdf::MultiEdgeApproxInserter::m_percentMostCrossedVar
private

The portion of most crossed edges considered (variable embedding).

Definition at line 181 of file MultiEdgeApproxInserter.h.

◆ m_pPG

PlanRepLight* ogdf::MultiEdgeApproxInserter::m_pPG
private

Definition at line 184 of file MultiEdgeApproxInserter.h.

◆ m_primalAdj

AdjEntryArray<adjEntry> ogdf::MultiEdgeApproxInserter::m_primalAdj
private

Definition at line 209 of file MultiEdgeApproxInserter.h.

◆ m_rrOptionFix

RemoveReinsertType ogdf::MultiEdgeApproxInserter::m_rrOptionFix
private

The remove-reinsert method for fixed embedding.

Definition at line 178 of file MultiEdgeApproxInserter.h.

◆ m_rrOptionVar

RemoveReinsertType ogdf::MultiEdgeApproxInserter::m_rrOptionVar
private

The remove-reinsert method for variable embedding.

Definition at line 179 of file MultiEdgeApproxInserter.h.

◆ m_statistics

bool ogdf::MultiEdgeApproxInserter::m_statistics
private

Definition at line 182 of file MultiEdgeApproxInserter.h.

◆ m_sumFEInsertionCosts

int ogdf::MultiEdgeApproxInserter::m_sumFEInsertionCosts
private

Definition at line 200 of file MultiEdgeApproxInserter.h.

◆ m_sumInsertionCosts

int ogdf::MultiEdgeApproxInserter::m_sumInsertionCosts
private

Definition at line 199 of file MultiEdgeApproxInserter.h.

◆ m_verticesB

Array<SList<node> > ogdf::MultiEdgeApproxInserter::m_verticesB
private

Definition at line 188 of file MultiEdgeApproxInserter.h.

◆ m_vS

node ogdf::MultiEdgeApproxInserter::m_vS
private

Definition at line 210 of file MultiEdgeApproxInserter.h.

◆ m_vT

node ogdf::MultiEdgeApproxInserter::m_vT
private

Definition at line 210 of file MultiEdgeApproxInserter.h.


The documentation for this class was generated from the following file: