Open
Graph Drawing
Framework

 v.2010.10
 

Public Member Functions | Private Member Functions | Private Attributes | Static Private Attributes

ogdf::VariableEmbeddingInserter Class Reference

Optimal edge insertion module. More...

#include <ogdf/planarity/VariableEmbeddingInserter.h>

Inheritance diagram for ogdf::VariableEmbeddingInserter:
ogdf::EdgeInsertionModule ogdf::Module ogdf::Timeouter

List of all members.

Public Member Functions

 VariableEmbeddingInserter ()
 Creates an instance of optimal edge inserter.
 ~VariableEmbeddingInserter ()
Optional parameters

void removeReinsert (RemoveReinsertType rrOption)
 Sets the remove-reinsert postprocessing method.
RemoveReinsertType removeReinsert () const
 Returns the current setting of the remove-reinsert postprocessing method.
void percentMostCrossed (double percent)
 Sets the option percentMostCrossed to percent.
double percentMostCrossed () const
 Returns the current setting of option percentMostCrossed.
Further information

int runsPostprocessing () const
 Returns the number of runs performed by the remove-reinsert method after the algorithm has been called.

Private Member Functions

ReturnType doCall (PlanRep &PG, const List< edge > &origEdges, bool forbidCrossingGens, const EdgeArray< int > *costOrig, const EdgeArray< bool > *forbiddenEdgeOrig, const EdgeArray< unsigned int > *edgeSubGraph)
 Implements the algorithm call.
edge crossedEdge (adjEntry adj) const
int costCrossed (edge eOrig) const
void insert (node s, node t, SList< adjEntry > &eip)
void blockInsert (const BiconnectedComponent &G, node s, node t, List< adjEntry > &L)
bool dfsVertex (node v, int parent)
bool dfsComp (int i, node parent, node &repT)
bool pathSearch (node v, edge parent, List< edge > &path)
void buildSubpath (node v, edge eIn, edge eOut, List< adjEntry > &L, ExpandedGraph &Exp, node s, node t)
edge insertEdge (node v, node w, Graph &Exp, NodeArray< node > &GtoExp, List< node > &nodesG)

Private Attributes

bool m_forbidCrossingGens
const EdgeArray< int > * m_costOrig
const EdgeArray< bool > * m_forbiddenEdgeOrig
const EdgeArray< unsigned int > * m_edgeSubgraph
Graph::EdgeType m_typeOfCurrentEdge
PlanRepm_pPG
node m_s
node m_t
edge m_st
SList< adjEntry > * m_pEip
NodeArray< SList< int > > m_compV
Array< SList< node > > m_nodeB
Array< SList< edge > > m_edgeB
NodeArray< nodem_GtoBC
node m_v1
node m_v2
RemoveReinsertType m_rrOption
 The remove-reinsert method.
double m_percentMostCrossed
 The portion of most crossed edges considered.
int m_runsPostprocessing
 Runs of remove-reinsert method.

Static Private Attributes

static int m_bigM

Detailed Description

Optimal edge insertion module.

The class VariableEmbeddingInserter represents the optimal edge insertion algorithm, which inserts a single edge with a minum number of crossings into a planar graph.

The implementation is based on the following publication:

Carsten Gutwenger, Petra Mutzel, Rene Weiskircher: Inserting an Edge into a Planar Graph. Algorithmica 41(4), pp. 289-308, 2005.

Definition at line 86 of file VariableEmbeddingInserter.h.


Constructor & Destructor Documentation

ogdf::VariableEmbeddingInserter::VariableEmbeddingInserter (  ) 

Creates an instance of optimal edge inserter.

ogdf::VariableEmbeddingInserter::~VariableEmbeddingInserter (  )  [inline]

Definition at line 92 of file VariableEmbeddingInserter.h.


Member Function Documentation

void ogdf::VariableEmbeddingInserter::blockInsert ( const BiconnectedComponent &  G,
node  s,
node  t,
List< adjEntry > &  L 
) [private]
void ogdf::VariableEmbeddingInserter::buildSubpath ( node  v,
edge  eIn,
edge  eOut,
List< adjEntry > &  L,
ExpandedGraph &  Exp,
node  s,
node  t 
) [private]
int ogdf::VariableEmbeddingInserter::costCrossed ( edge  eOrig  )  const [private]
edge ogdf::VariableEmbeddingInserter::crossedEdge ( adjEntry  adj  )  const [private]
bool ogdf::VariableEmbeddingInserter::dfsComp ( int  i,
node  parent,
node repT 
) [private]
bool ogdf::VariableEmbeddingInserter::dfsVertex ( node  v,
int  parent 
) [private]
ReturnType ogdf::VariableEmbeddingInserter::doCall ( PlanRep PG,
const List< edge > &  origEdges,
bool  forbidCrossingGens,
const EdgeArray< int > *  costOrig,
const EdgeArray< bool > *  forbiddenEdgeOrig,
const EdgeArray< unsigned int > *  edgeSubGraph 
) [private, virtual]

Implements the algorithm call.

Implements ogdf::EdgeInsertionModule.

void ogdf::VariableEmbeddingInserter::insert ( node  s,
node  t,
SList< adjEntry > &  eip 
) [private]
edge ogdf::VariableEmbeddingInserter::insertEdge ( node  v,
node  w,
Graph Exp,
NodeArray< node > &  GtoExp,
List< node > &  nodesG 
) [private]
bool ogdf::VariableEmbeddingInserter::pathSearch ( node  v,
edge  parent,
List< edge > &  path 
) [private]
void ogdf::VariableEmbeddingInserter::percentMostCrossed ( 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 rrMostCrossed. This portion is number of edges * percentMostCrossed() / 100.

Definition at line 115 of file VariableEmbeddingInserter.h.

double ogdf::VariableEmbeddingInserter::percentMostCrossed (  )  const [inline]

Returns the current setting of option percentMostCrossed.

Definition at line 120 of file VariableEmbeddingInserter.h.

void ogdf::VariableEmbeddingInserter::removeReinsert ( RemoveReinsertType  rrOption  )  [inline]

Sets the remove-reinsert postprocessing method.

Definition at line 100 of file VariableEmbeddingInserter.h.

RemoveReinsertType ogdf::VariableEmbeddingInserter::removeReinsert (  )  const [inline]

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

Definition at line 105 of file VariableEmbeddingInserter.h.

int ogdf::VariableEmbeddingInserter::runsPostprocessing (  )  const [inline, virtual]

Returns the number of runs performed by the remove-reinsert method after the algorithm has been called.

Reimplemented from ogdf::EdgeInsertionModule.

Definition at line 130 of file VariableEmbeddingInserter.h.


Member Data Documentation

Definition at line 173 of file VariableEmbeddingInserter.h.

Definition at line 154 of file VariableEmbeddingInserter.h.

Definition at line 156 of file VariableEmbeddingInserter.h.

The portion of most crossed edges considered.

Definition at line 194 of file VariableEmbeddingInserter.h.

The remove-reinsert method.

Definition at line 193 of file VariableEmbeddingInserter.h.

Runs of remove-reinsert method.

Definition at line 196 of file VariableEmbeddingInserter.h.


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