|
|||
|
|
|
|||
|
|
#include <VariableEmbeddingInserter.h>
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 |
| PlanRep * | m_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< node > | m_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 |
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 84 of file VariableEmbeddingInserter.h.
| ogdf::VariableEmbeddingInserter::VariableEmbeddingInserter | ( | ) |
Creates an instance of optimal edge inserter.
| ogdf::VariableEmbeddingInserter::~VariableEmbeddingInserter | ( | ) | [inline] |
Definition at line 90 of file VariableEmbeddingInserter.h.
| void ogdf::VariableEmbeddingInserter::removeReinsert | ( | RemoveReinsertType | rrOption | ) | [inline] |
Sets the remove-reinsert postprocessing method.
Definition at line 98 of file VariableEmbeddingInserter.h.
| RemoveReinsertType ogdf::VariableEmbeddingInserter::removeReinsert | ( | ) | const [inline] |
Returns the current setting of the remove-reinsert postprocessing method.
Definition at line 103 of file VariableEmbeddingInserter.h.
| 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 113 of file VariableEmbeddingInserter.h.
| double ogdf::VariableEmbeddingInserter::percentMostCrossed | ( | ) | const [inline] |
Returns the current setting of option percentMostCrossed.
Definition at line 118 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 128 of file VariableEmbeddingInserter.h.
| int ogdf::VariableEmbeddingInserter::costCrossed | ( | edge | eOrig | ) | const [private] |
| void ogdf::VariableEmbeddingInserter::blockInsert | ( | const BiconnectedComponent & | G, | |
| node | s, | |||
| node | t, | |||
| List< adjEntry > & | L | |||
| ) | [private] |
| bool ogdf::VariableEmbeddingInserter::dfsVertex | ( | node | v, | |
| int | parent | |||
| ) | [private] |
| bool ogdf::VariableEmbeddingInserter::pathSearch | ( | node | v, | |
| edge | parent, | |||
| List< edge > & | path | |||
| ) | [private] |
| void ogdf::VariableEmbeddingInserter::buildSubpath | ( | node | v, | |
| edge | eIn, | |||
| edge | eOut, | |||
| List< adjEntry > & | L, | |||
| ExpandedGraph & | Exp, | |||
| node | s, | |||
| node | t | |||
| ) | [private] |
| edge ogdf::VariableEmbeddingInserter::insertEdge | ( | node | v, | |
| node | w, | |||
| Graph & | Exp, | |||
| NodeArray< node > & | GtoExp, | |||
| List< node > & | nodesG | |||
| ) | [private] |
bool ogdf::VariableEmbeddingInserter::m_forbidCrossingGens [private] |
Definition at line 151 of file VariableEmbeddingInserter.h.
const EdgeArray<int>* ogdf::VariableEmbeddingInserter::m_costOrig [private] |
Definition at line 152 of file VariableEmbeddingInserter.h.
const EdgeArray<bool>* ogdf::VariableEmbeddingInserter::m_forbiddenEdgeOrig [private] |
Definition at line 153 of file VariableEmbeddingInserter.h.
const EdgeArray<unsigned int>* ogdf::VariableEmbeddingInserter::m_edgeSubgraph [private] |
Definition at line 154 of file VariableEmbeddingInserter.h.
Definition at line 155 of file VariableEmbeddingInserter.h.
PlanRep* ogdf::VariableEmbeddingInserter::m_pPG [private] |
Definition at line 166 of file VariableEmbeddingInserter.h.
node ogdf::VariableEmbeddingInserter::m_s [private] |
Definition at line 167 of file VariableEmbeddingInserter.h.
node ogdf::VariableEmbeddingInserter::m_t [private] |
Definition at line 167 of file VariableEmbeddingInserter.h.
edge ogdf::VariableEmbeddingInserter::m_st [private] |
Definition at line 168 of file VariableEmbeddingInserter.h.
SList<adjEntry>* ogdf::VariableEmbeddingInserter::m_pEip [private] |
Definition at line 169 of file VariableEmbeddingInserter.h.
int ogdf::VariableEmbeddingInserter::m_bigM [static, private] |
Definition at line 171 of file VariableEmbeddingInserter.h.
NodeArray<SList<int> > ogdf::VariableEmbeddingInserter::m_compV [private] |
Definition at line 173 of file VariableEmbeddingInserter.h.
Array<SList<node> > ogdf::VariableEmbeddingInserter::m_nodeB [private] |
Definition at line 174 of file VariableEmbeddingInserter.h.
Array<SList<edge> > ogdf::VariableEmbeddingInserter::m_edgeB [private] |
Definition at line 175 of file VariableEmbeddingInserter.h.
Definition at line 176 of file VariableEmbeddingInserter.h.
node ogdf::VariableEmbeddingInserter::m_v1 [private] |
Definition at line 189 of file VariableEmbeddingInserter.h.
node ogdf::VariableEmbeddingInserter::m_v2 [private] |
Definition at line 189 of file VariableEmbeddingInserter.h.
double ogdf::VariableEmbeddingInserter::m_percentMostCrossed [private] |
The portion of most crossed edges considered.
Definition at line 192 of file VariableEmbeddingInserter.h.
int ogdf::VariableEmbeddingInserter::m_runsPostprocessing [private] |
