Minor-monotone edge insertion with variable embedding. More...
#include <ogdf/planarity/MMVariableEmbeddingInserter.h>
Classes | |
| struct | AnchorNodeInfo |
| struct | Paths |
Public Member Functions | |
| MMVariableEmbeddingInserter () | |
| Creates a minor-monotone fixed embedding inserter. | |
| virtual | ~MMVariableEmbeddingInserter () |
| void | removeReinsert (RemoveReinsertType rrOption) |
| Sets the remove-reinsert option for postprocessing. | |
| RemoveReinsertType | removeReinsert () const |
| Returns the current setting of the remove-reinsert option. | |
| void | percentMostCrossed (double percent) |
| Sets the portion of most crossed edges used during postprocessing. | |
| double | percentMostCrossed () const |
| Returns the current setting of the option percentMostCrossed. | |
Private Types | |
| enum | PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 } |
| typedef PlanRepExpansion::Crossing | Crossing |
Private Member Functions | |
| ReturnType | doCall (PlanRepExpansion &PG, const List< edge > &origEdges, const EdgeArray< bool > *forbiddenEdgeOrig) |
| Implementation of algorithm call. | |
| void | collectAnchorNodes (node v, NodeSet &nodes, const PlanRepExpansion::NodeSplit *nsParent) const |
| Collects all anchor nodes (including dummies) of a node. | |
| void | findSourcesAndTargets (node src, node tgt, NodeSet &sources, NodeSet &targets) const |
| Finds the set of anchor nodes of src and tgt. | |
| void | anchorNodes (node vOrig, NodeSet &nodes) const |
| Returns all anchor nodes of vOrig in nnodes. | |
| void | insert (List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd) |
| Computes insertion path eip. | |
| node | prepareAnchorNode (const AnchorNodeInfo &anchor, node vOrig, bool isSrc, edge &eExtra) |
| void | preprocessInsertionPath (const AnchorNodeInfo &srcInfo, const AnchorNodeInfo &tgtInfo, node srcOrig, node tgtOrig, node &src, node &tgt, edge &eSrc, edge &eTgt) |
| node | preparePath (node vAnchor, adjEntry adjPath, bool bOrigEdge, node vOrig) |
| void | findPseudos (node vDummy, adjEntry adjSrc, AnchorNodeInfo &infoSrc, SListPure< node > &pseudos) |
| void | insertWithCommonDummy (edge eOrig, node vDummy, node &src, node &tgt) |
| bool | dfsVertex (node v, int parent, List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd) |
| Implements vertex case of recursive path search in BC-tree. | |
| bool | dfsBlock (int i, node parent, node &repS, List< Crossing > &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd) |
| Implements block case of recursive path search in BC-tree. | |
| bool | pathSearch (node v, edge parent, const Block &BC, List< edge > &path) |
| void | blockInsert (Block &BC, List< Crossing > &L, AnchorNodeInfo &srcInfo, AnchorNodeInfo &tgtInfo) |
| Computes optimal insertion path in block BC. | |
| void | buildSubpath (node v, edge eIn, edge eOut, Paths &paths, bool &bPathToEdge, bool &bPathToSrc, bool &bPathToTgt, ExpandedSkeleton &Exp) |
| void | contractSplitIfReq (node u) |
| void | convertDummy (node u, node vOrig, PlanRepExpansion::nodeSplit ns_0) |
| void | writeEip (const List< Crossing > &eip) |
Static Private Member Functions | |
| static node | commonDummy (NodeSet &sources, NodeSet &targets) |
Private Attributes | |
| RemoveReinsertType | m_rrOption |
| The remove-reinsert option. | |
| double | m_percentMostCrossed |
| The percentMostCrossed option. | |
| PlanRepExpansion * | m_pPG |
| Pointer to the planarized expansion. | |
| NodeSet * | m_pSources |
| The set of possible start nodes of an insertion path. | |
| NodeSet * | m_pTargets |
| The set of possible end nodes of an insertion path. | |
| NodeArray< SList< int > > | m_compV |
| The list of blocks containing a node v. | |
| Array< SList< node > > | m_nodeB |
| The list of nodes in block i. | |
| Array< SList< edge > > | m_edgeB |
| The list of edges in block i. | |
| NodeArray< node > | m_GtoBC |
| Maps a node in the planarized expansion to the corresponding node in block. | |
| bool | m_conFinished |
| Stores if a possible target node in a block has already been found. | |
| const EdgeArray< bool > * | m_forbiddenEdgeOrig |
Minor-monotone edge insertion with variable embedding.
Definition at line 65 of file MMVariableEmbeddingInserter.h.
typedef PlanRepExpansion::Crossing ogdf::MMVariableEmbeddingInserter::Crossing [private] |
Definition at line 104 of file MMVariableEmbeddingInserter.h.
enum ogdf::MMVariableEmbeddingInserter::PathType [private] |
Definition at line 123 of file MMVariableEmbeddingInserter.h.
Creates a minor-monotone fixed embedding inserter.
| virtual ogdf::MMVariableEmbeddingInserter::~MMVariableEmbeddingInserter | ( | ) | [inline, virtual] |
Definition at line 72 of file MMVariableEmbeddingInserter.h.
| void ogdf::MMVariableEmbeddingInserter::anchorNodes | ( | node | vOrig, |
| NodeSet & | nodes | ||
| ) | const [private] |
Returns all anchor nodes of vOrig in nnodes.
| vOrig | is a node in the original graph. |
| nodes | ia assigned the set of anchor nodes. |
| void ogdf::MMVariableEmbeddingInserter::blockInsert | ( | Block & | BC, |
| List< Crossing > & | L, | ||
| AnchorNodeInfo & | srcInfo, | ||
| AnchorNodeInfo & | tgtInfo | ||
| ) | [private] |
Computes optimal insertion path in block BC.
| BC | is the block. |
| s | is a node in BC representing a source node. |
| t | is a node in BC representing a target node. |
| L | is assigned the insertion path (the crossed edges). |
| void ogdf::MMVariableEmbeddingInserter::buildSubpath | ( | node | v, |
| edge | eIn, | ||
| edge | eOut, | ||
| Paths & | paths, | ||
| bool & | bPathToEdge, | ||
| bool & | bPathToSrc, | ||
| bool & | bPathToTgt, | ||
| ExpandedSkeleton & | Exp | ||
| ) | [private] |
| void ogdf::MMVariableEmbeddingInserter::collectAnchorNodes | ( | node | v, |
| NodeSet & | nodes, | ||
| const PlanRepExpansion::NodeSplit * | nsParent | ||
| ) | const [private] |
Collects all anchor nodes (including dummies) of a node.
| v | is the current node when traversing all copy nodes of an original node that are connected in a tree-wise manner. |
| nodes | is assigned the set of anchor nodes. |
| nsParent | is the parent node split. |
| static node ogdf::MMVariableEmbeddingInserter::commonDummy | ( | NodeSet & | sources, |
| NodeSet & | targets | ||
| ) | [static, private] |
| void ogdf::MMVariableEmbeddingInserter::contractSplitIfReq | ( | node | u | ) | [private] |
| void ogdf::MMVariableEmbeddingInserter::convertDummy | ( | node | u, |
| node | vOrig, | ||
| PlanRepExpansion::nodeSplit | ns_0 | ||
| ) | [private] |
| bool ogdf::MMVariableEmbeddingInserter::dfsBlock | ( | int | i, |
| node | parent, | ||
| node & | repS, | ||
| List< Crossing > & | eip, | ||
| AnchorNodeInfo & | vStart, | ||
| AnchorNodeInfo & | vEnd | ||
| ) | [private] |
Implements block case of recursive path search in BC-tree.
| i | is the block in the graph currently visited during BC-tree traversal. |
| parent | is the parent node in DFS-traversal. |
| repS | is assigned the representative (nodein the graph) of a source node. |
| eip | is (step-by-step) assigned the insertion path (crossed edges). |
| bool ogdf::MMVariableEmbeddingInserter::dfsVertex | ( | node | v, |
| int | parent, | ||
| List< Crossing > & | eip, | ||
| AnchorNodeInfo & | vStart, | ||
| AnchorNodeInfo & | vEnd | ||
| ) | [private] |
Implements vertex case of recursive path search in BC-tree.
| v | is the node in the graph currently visited during BC-tree traversal. |
| parent | is the parent block in DFS-traversal. |
| eip | is (step-by-step) assigned the insertion path (crossed edges). |
| ReturnType ogdf::MMVariableEmbeddingInserter::doCall | ( | PlanRepExpansion & | PG, |
| const List< edge > & | origEdges, | ||
| const EdgeArray< bool > * | forbiddenEdgeOrig | ||
| ) | [private, virtual] |
Implementation of algorithm call.
| PG | is the input planarized expansion and will also receive the result. |
| origEdges | is the list of original edges (edges in the original graph of PG) that have to be inserted. |
| forbiddenEdgeOrig | points to an edge array indicating if an original edge is forbidden to be crossed. |
Implements ogdf::MMEdgeInsertionModule.
| void ogdf::MMVariableEmbeddingInserter::findPseudos | ( | node | vDummy, |
| adjEntry | adjSrc, | ||
| AnchorNodeInfo & | infoSrc, | ||
| SListPure< node > & | pseudos | ||
| ) | [private] |
| void ogdf::MMVariableEmbeddingInserter::findSourcesAndTargets | ( | node | src, |
| node | tgt, | ||
| NodeSet & | sources, | ||
| NodeSet & | targets | ||
| ) | const [private] |
Finds the set of anchor nodes of src and tgt.
| src | is a node in PG representing an original node. |
| tgt | is a node in PG representing an original node. |
| sources | ia assigned the set of anchor nodes of src's original node. |
| targets | ia assigned the set of anchor nodes of tgt's original node. |
| void ogdf::MMVariableEmbeddingInserter::insert | ( | List< Crossing > & | eip, |
| AnchorNodeInfo & | vStart, | ||
| AnchorNodeInfo & | vEnd | ||
| ) | [private] |
Computes insertion path eip.
The possible start and end nodes of the insertion path have to be stored in m_pSources and m_pTargets.
| eip | is assigned the insertion path (the crossed edges). |
| void ogdf::MMVariableEmbeddingInserter::insertWithCommonDummy | ( | edge | eOrig, |
| node | vDummy, | ||
| node & | src, | ||
| node & | tgt | ||
| ) | [private] |
| bool ogdf::MMVariableEmbeddingInserter::pathSearch | ( | node | v, |
| edge | parent, | ||
| const Block & | BC, | ||
| List< edge > & | path | ||
| ) | [private] |
| void ogdf::MMVariableEmbeddingInserter::percentMostCrossed | ( | double | percent | ) | [inline] |
Sets the portion of most crossed edges used during postprocessing.
The value is only used if the remove-reinsert option is set to rrMostCrossed. The number of edges used in postprocessing is then number of edges * percentMostCrossed() / 100.
Definition at line 92 of file MMVariableEmbeddingInserter.h.
| double ogdf::MMVariableEmbeddingInserter::percentMostCrossed | ( | ) | const [inline] |
Returns the current setting of the option percentMostCrossed.
Definition at line 97 of file MMVariableEmbeddingInserter.h.
| node ogdf::MMVariableEmbeddingInserter::prepareAnchorNode | ( | const AnchorNodeInfo & | anchor, |
| node | vOrig, | ||
| bool | isSrc, | ||
| edge & | eExtra | ||
| ) | [private] |
| node ogdf::MMVariableEmbeddingInserter::preparePath | ( | node | vAnchor, |
| adjEntry | adjPath, | ||
| bool | bOrigEdge, | ||
| node | vOrig | ||
| ) | [private] |
| void ogdf::MMVariableEmbeddingInserter::preprocessInsertionPath | ( | const AnchorNodeInfo & | srcInfo, |
| const AnchorNodeInfo & | tgtInfo, | ||
| node | srcOrig, | ||
| node | tgtOrig, | ||
| node & | src, | ||
| node & | tgt, | ||
| edge & | eSrc, | ||
| edge & | eTgt | ||
| ) | [private] |
| void ogdf::MMVariableEmbeddingInserter::removeReinsert | ( | RemoveReinsertType | rrOption | ) | [inline] |
Sets the remove-reinsert option for postprocessing.
Definition at line 76 of file MMVariableEmbeddingInserter.h.
| RemoveReinsertType ogdf::MMVariableEmbeddingInserter::removeReinsert | ( | ) | const [inline] |
Returns the current setting of the remove-reinsert option.
Definition at line 81 of file MMVariableEmbeddingInserter.h.
| void ogdf::MMVariableEmbeddingInserter::writeEip | ( | const List< Crossing > & | eip | ) | [private] |
NodeArray<SList<int> > ogdf::MMVariableEmbeddingInserter::m_compV [private] |
The list of blocks containing a node v.
Definition at line 308 of file MMVariableEmbeddingInserter.h.
bool ogdf::MMVariableEmbeddingInserter::m_conFinished [private] |
Stores if a possible target node in a block has already been found.
Definition at line 313 of file MMVariableEmbeddingInserter.h.
Array<SList<edge> > ogdf::MMVariableEmbeddingInserter::m_edgeB [private] |
The list of edges in block i.
Definition at line 310 of file MMVariableEmbeddingInserter.h.
const EdgeArray<bool>* ogdf::MMVariableEmbeddingInserter::m_forbiddenEdgeOrig [private] |
Definition at line 314 of file MMVariableEmbeddingInserter.h.
Maps a node in the planarized expansion to the corresponding node in block.
Definition at line 311 of file MMVariableEmbeddingInserter.h.
Array<SList<node> > ogdf::MMVariableEmbeddingInserter::m_nodeB [private] |
The list of nodes in block i.
Definition at line 309 of file MMVariableEmbeddingInserter.h.
double ogdf::MMVariableEmbeddingInserter::m_percentMostCrossed [private] |
The percentMostCrossed option.
Definition at line 301 of file MMVariableEmbeddingInserter.h.
Pointer to the planarized expansion.
Definition at line 303 of file MMVariableEmbeddingInserter.h.
The set of possible start nodes of an insertion path.
Definition at line 305 of file MMVariableEmbeddingInserter.h.
The set of possible end nodes of an insertion path.
Definition at line 306 of file MMVariableEmbeddingInserter.h.
The remove-reinsert option.
Definition at line 300 of file MMVariableEmbeddingInserter.h.