|
|||
|
|
|
|||
|
|
#include <PlanRepExpansion.h>
Public Types | |
| typedef PlanRepExpansion::NodeSplit * | nodeSplit |
| Pointer to a node split. | |
Public Member Functions | |
| PlanRepExpansion (const Graph &G) | |
| Creates a planarized expansion of graph G. | |
| PlanRepExpansion (const Graph &G, const List< node > &splittableNodes) | |
| Creates a planarized expansion of graph G with given splittable nodes. | |
| ~PlanRepExpansion () | |
Acess methods | |
| const Graph & | original () const |
| Returns a reference to the original graph. | |
| node | original (node v) const |
| Returns the original node of v, or 0 if v is a dummy. | |
| const List< node > & | expansion (node vOrig) const |
| Returns the list of copy nodes of vOrig. | |
| node | copy (node vOrig) const |
| Returns the first copy node of vOrig. | |
| edge | originalEdge (edge e) const |
| Returns the original edge of \ e, or 0 if e has none (e.g., e belongs to a node split). | |
| const List< edge > & | chain (edge eOrig) const |
| Returns the insertion path of edge eOrig. | |
| edge | copy (edge eOrig) const |
| Returns the first edge in eOrig's insertion path. | |
| bool | splittable (node v) const |
| Returns true iff v is splittable. | |
| bool | splittableOrig (node vOrig) const |
| Returns true iff vOrig is splittable. | |
| NodeSplit * | nodeSplitOf (edge e) const |
| Returns the node split associated with e, or 0 if none (e.g., e belongs to an original edge). | |
| int | numberOfNodeSplits () const |
| Returns the number of node splits. | |
| int | numberOfSplittedNodes () const |
| List< NodeSplit > & | nodeSplits () |
| Returns the list of node splits. | |
| List< edge > & | setOrigs (edge e, edge &eOrig, nodeSplit &ns) |
| Sets the original edge and corresponding node split of e and returns the corresponding insertion path. | |
| ListConstIterator< edge > | position (edge e) const |
| bool | isPseudoCrossing (node v) const |
| int | computeNumberOfCrossings () const |
| Computes the number of crossings. | |
Processing connected components | |
| int | numberOfCCs () const |
| Returns the number of connected components in the original graph. | |
| int | currentCC () const |
| Returns the index of the current connected component (-1 if not yet initialized). | |
| const List< node > & | nodesInCC (int i) const |
| Returns the list of (original) nodes in connected component i. | |
| const List< node > & | nodesInCC () const |
| Returns the list of (original) nodes in the current connected component. | |
| void | initCC (int i) |
| Initializes the planarized representation for connected component i. | |
Update operations | |
| edge | split (edge e) |
| Splits edge e into two edges introducing a new node. | |
| void | unsplit (edge eIn, edge eOut) |
| Undoes a split operation. | |
| void | delCopy (edge e) |
| Removes edge e from the planarized expansion. | |
| bool | embed () |
| Embeds the planarized expansion; returns true iff it is planar. | |
| void | insertEdgePath (edge eOrig, nodeSplit ns, node vStart, node vEnd, List< Crossing > &eip, edge eSrc, edge eTgt) |
| void | insertEdgePathEmbedded (edge eOrig, nodeSplit ns, CombinatorialEmbedding &E, const List< Tuple2< adjEntry, adjEntry > > &crossedEdges) |
| Inserts an edge or a node split according to insertion path crossedEdges. | |
| void | removeEdgePathEmbedded (CombinatorialEmbedding &E, edge eOrig, nodeSplit ns, FaceSetPure &newFaces, NodeSetPure &mergedNodes, node &oldSrc, node &oldTgt) |
| Removes the insertion path of eOrig or ns. | |
| void | removeEdgePath (edge eOrig, nodeSplit ns, node &oldSrc, node &oldTgt) |
| Removes the insertion path of eOrig or ns. | |
| void | contractSplit (nodeSplit ns, CombinatorialEmbedding &E) |
| Removes an (unneccessary) node split consisting of a single edge. | |
| void | contractSplit (nodeSplit ns) |
| Removes an (unneccessary) node split consisting of a single edge. | |
| edge | unsplitExpandNode (node u, edge eContract, edge eExpand, CombinatorialEmbedding &E) |
| Unsplits a superfluous expansion node of degree 2. | |
| edge | unsplitExpandNode (node u, edge eContract, edge eExpand) |
| Unsplits a superfluous expansion node of degree 2. | |
| edge | enlargeSplit (node v, edge e, CombinatorialEmbedding &E) |
| Splits edge e and introduces a new node split starting at v. | |
| edge | enlargeSplit (node v, edge e) |
| Splits edge e and introduces a new node split starting at v. | |
| edge | splitNodeSplit (edge e, CombinatorialEmbedding &E) |
| Introduces a new node split by splitting an exisiting node split. | |
| edge | splitNodeSplit (edge e) |
| Introduces a new node split by splitting an exisiting node split. | |
| void | removeSelfLoop (edge e, CombinatorialEmbedding &E) |
| Removes a self-loop e = (u,u). | |
| void | removeSelfLoop (edge e) |
| PlanRepExpansion::nodeSplit | convertDummy (node u, node vOrig, PlanRepExpansion::nodeSplit ns) |
| Converts a dummy node u to a copy of an original node vOrig. | |
| edge | separateDummy (adjEntry adj_1, adjEntry adj_2, node vStraight, bool isSrc) |
| void | resolvePseudoCrossing (node v) |
Miscelleaneous | |
| bool | consistencyCheck () const |
| Performs various consistency checks on the data structure. | |
Private Member Functions | |
| void | doInit (const Graph &G, const List< node > &splittableNodes) |
| void | prepareNodeSplit (const SList< adjEntry > &partitionLeft, adjEntry &adjLeft, adjEntry &adjRight) |
Private Attributes | |
| const Graph * | m_pGraph |
| The original graph. | |
| NodeArray< node > | m_vOrig |
| The corresponding node in the original graph. | |
| EdgeArray< edge > | m_eOrig |
| The corresponding edge in the original graph. | |
| EdgeArray< ListIterator< edge > > | m_eIterator |
| The position of copy edge in the list. | |
| EdgeArray< List< edge > > | m_eCopy |
| The corresponding list of edges in the graph copy. | |
| NodeArray< ListIterator< node > > | m_vIterator |
| The position of copy node in the list. | |
| NodeArray< List< node > > | m_vCopy |
| The corresponding list of nodes in the graph copy. | |
| NodeArray< bool > | m_splittable |
| NodeArray< bool > | m_splittableOrig |
| EdgeArray< NodeSplit * > | m_eNodeSplit |
| List< NodeSplit > | m_nodeSplits |
| int | m_currentCC |
| The index of the current component. | |
| int | m_numCC |
| The number of components in the original graph. | |
| Array< List< node > > | m_nodesInCC |
| The list of original nodes in each component. | |
| EdgeArray< edge > | m_eAuxCopy |
Classes | |
| struct | Crossing |
| class | NodeSplit |
| Representation of a node split in a planarized expansion. More... | |
Maintains types of edges (generalization, association) and nodes, and the connected components of the graph.
Definition at line 79 of file PlanRepExpansion.h.
| ogdf::PlanRepExpansion::PlanRepExpansion | ( | const Graph & | G | ) |
Creates a planarized expansion of graph G.
All nodes are allowed to be split.
Creates a planarized expansion of graph G with given splittable nodes.
Only the node in splittableNodes are allowed to be split.
| G | is the original graph of this planarized expansion. | |
| splittableNodes | contains all the nodes in G that are splittable. |
| ogdf::PlanRepExpansion::~PlanRepExpansion | ( | ) | [inline] |
Definition at line 145 of file PlanRepExpansion.h.
| const Graph& ogdf::PlanRepExpansion::original | ( | ) | const [inline] |
Returns the original node of v, or 0 if v is a dummy.
Definition at line 157 of file PlanRepExpansion.h.
Returns the original edge of \ e, or 0 if e has none (e.g., e belongs to a node split).
Definition at line 166 of file PlanRepExpansion.h.
Returns the first edge in eOrig's insertion path.
Definition at line 172 of file PlanRepExpansion.h.
| bool ogdf::PlanRepExpansion::splittable | ( | node | v | ) | const [inline] |
| bool ogdf::PlanRepExpansion::splittableOrig | ( | node | vOrig | ) | const [inline] |
Returns the node split associated with e, or 0 if none (e.g., e belongs to an original edge).
Definition at line 181 of file PlanRepExpansion.h.
| int ogdf::PlanRepExpansion::numberOfNodeSplits | ( | ) | const [inline] |
| int ogdf::PlanRepExpansion::numberOfSplittedNodes | ( | ) | const |
Sets the original edge and corresponding node split of e and returns the corresponding insertion path.
| e | is an edge in the planarized expansion. | |
| eOrig | is assigned the original edge of e (or 0 if none). | |
| ns | is assigned the node split corresponding to e (or 0 if none). |
| ListConstIterator<edge> ogdf::PlanRepExpansion::position | ( | edge | e | ) | const [inline] |
Definition at line 201 of file PlanRepExpansion.h.
| bool ogdf::PlanRepExpansion::isPseudoCrossing | ( | node | v | ) | const |
| int ogdf::PlanRepExpansion::computeNumberOfCrossings | ( | ) | const |
Computes the number of crossings.
| int ogdf::PlanRepExpansion::numberOfCCs | ( | ) | const [inline] |
Returns the number of connected components in the original graph.
Definition at line 218 of file PlanRepExpansion.h.
| int ogdf::PlanRepExpansion::currentCC | ( | ) | const [inline] |
Returns the index of the current connected component (-1 if not yet initialized).
Definition at line 225 of file PlanRepExpansion.h.
Returns the list of (original) nodes in connected component i.
Note that connected components are numbered 0,1,...
Definition at line 234 of file PlanRepExpansion.h.
Returns the list of (original) nodes in the current connected component.
Definition at line 241 of file PlanRepExpansion.h.
| void ogdf::PlanRepExpansion::initCC | ( | int | i | ) |
Initializes the planarized representation for connected component i.
This initialization is always required. After performing this initialization, the planarized representation represents a copy of the i-th connected component of the original graph, where connected components are numbered 0,1,2,...
Splits edge e into two edges introducing a new node.
Let e=(v,w). Then, the resulting two edges are e=(v,u) and e'=(u,w), where u is a new node.
Reimplemented from ogdf::Graph.
Undoes a split operation.
For two edges eIn = (x,u) and eOut = (u,y), removes node u by joining eIn and eOut. Edge eOut is removed and eIn is reused.
Reimplemented from ogdf::Graph.
| void ogdf::PlanRepExpansion::delCopy | ( | edge | e | ) |
Removes edge e from the planarized expansion.
| bool ogdf::PlanRepExpansion::embed | ( | ) |
Embeds the planarized expansion; returns true iff it is planar.
| void ogdf::PlanRepExpansion::insertEdgePath | ( | edge | eOrig, | |
| nodeSplit | ns, | |||
| node | vStart, | |||
| node | vEnd, | |||
| List< Crossing > & | eip, | |||
| edge | eSrc, | |||
| edge | eTgt | |||
| ) |
| void ogdf::PlanRepExpansion::insertEdgePathEmbedded | ( | edge | eOrig, | |
| nodeSplit | ns, | |||
| CombinatorialEmbedding & | E, | |||
| const List< Tuple2< adjEntry, adjEntry > > & | crossedEdges | |||
| ) |
Inserts an edge or a node split according to insertion path crossedEdges.
If eOrig is not 0, a new insertion path for eOrig is inserted; otherwise, a new insertion path for node split ns is inserted.
| eOrig | is an original edge in the graph (or 0). | |
| ns | is a node split in the planarized expansion. | |
| E | is an embedding of the planarized expansion. | |
| crossedEdges | defines the insertion path. |
| void ogdf::PlanRepExpansion::removeEdgePathEmbedded | ( | CombinatorialEmbedding & | E, | |
| edge | eOrig, | |||
| nodeSplit | ns, | |||
| FaceSetPure & | newFaces, | |||
| NodeSetPure & | mergedNodes, | |||
| node & | oldSrc, | |||
| node & | oldTgt | |||
| ) |
Removes the insertion path of eOrig or ns.
| E | is an embedding of the planarized expansion. | |
| eOrig | is an original edge in the graph (or 0). | |
| ns | is a node split in the planarized expansion. | |
| newFaces | is assigned the set of new faces resulting from joining faces when removing edges. | |
| mergedNodes | is assigned the set of nodes in the planarized expansion that resulted from merging (splittable) nodes. | |
| oldSrc | is assigned the source node of the removed insertion path. | |
| oldTgt | is assigned the target node of the removed insertion path. |
| void ogdf::PlanRepExpansion::removeEdgePath | ( | edge | eOrig, | |
| nodeSplit | ns, | |||
| node & | oldSrc, | |||
| node & | oldTgt | |||
| ) |
Removes the insertion path of eOrig or ns.
| eOrig | is an original edge in the graph (or 0). | |
| ns | is a node split in the planarized expansion. | |
| oldSrc | is assigned the source node of the removed insertion path. | |
| oldTgt | is assigned the target node of the removed insertion path. |
| void ogdf::PlanRepExpansion::contractSplit | ( | nodeSplit | ns, | |
| CombinatorialEmbedding & | E | |||
| ) |
Removes an (unneccessary) node split consisting of a single edge.
Nodes splits consisting of a single edge are superfluous and canbe removed by contracting the respective edge.
| ns | is the node split to be removed. | |
| E | is an embedding of the planarized expansion. |
| void ogdf::PlanRepExpansion::contractSplit | ( | nodeSplit | ns | ) |
Removes an (unneccessary) node split consisting of a single edge.
Nodes splits consisting of a single edge are superfluous and canbe removed by contracting the respective edge.
| ns | is the node split to be removed. |
| edge ogdf::PlanRepExpansion::unsplitExpandNode | ( | node | u, | |
| edge | eContract, | |||
| edge | eExpand, | |||
| CombinatorialEmbedding & | E | |||
| ) |
Unsplits a superfluous expansion node of degree 2.
| u | is a node in the planarized expansion which has degree 2 and is part of the expansion of an original node. | |
| eContract | is the edge incident to u which is part of a node split; this edge gets contracted. | |
| eExpand | is the edge incident to u which belongs to the insertion path that gets enlarged. | |
| E | is an embedding of the planarized expansion. |
Unsplits a superfluous expansion node of degree 2.
| u | is a node in the planarized expansion which has degree 2 and is part of the expansion of an original node. | |
| eContract | is the edge incident to u which is part of a node split; this edge gets contracted. | |
| eExpand | is the edge incident to u which belongs to the insertion path that gets enlarged. |
| edge ogdf::PlanRepExpansion::enlargeSplit | ( | node | v, | |
| edge | e, | |||
| CombinatorialEmbedding & | E | |||
| ) |
Splits edge e and introduces a new node split starting at v.
| v | is a node in the planarized expansion; the expansion of v's original node is enlarged. | |
| e | is the edge to be split; the insertion path of e's original edge must start or end at v. | |
| E | is an embedding of the planarized expansion. |
Splits edge e and introduces a new node split starting at v.
| v | is a node in the planarized expansion; the expansion of v's original node is enlarged. | |
| e | is the edge to be split; the insertion path of e's original edge must start or end at v. |
| edge ogdf::PlanRepExpansion::splitNodeSplit | ( | edge | e, | |
| CombinatorialEmbedding & | E | |||
| ) |
Introduces a new node split by splitting an exisiting node split.
| e | is the edge to be split; the node split corresponding to e is split into two node splits. | |
| E | is an embedding of the planarized expansion. |
Introduces a new node split by splitting an exisiting node split.
| e | is the edge to be split; the node split corresponding to e is split into two node splits. |
| void ogdf::PlanRepExpansion::removeSelfLoop | ( | edge | e, | |
| CombinatorialEmbedding & | E | |||
| ) |
Removes a self-loop e = (u,u).
u must be a dummy node; hence, u has degree 2 node after removing \ e, and u is unsplit afterwards.
| e | must be a self loop in the planarized expansion. | |
| E | is an embedding of the planarized expansion. |
| void ogdf::PlanRepExpansion::removeSelfLoop | ( | edge | e | ) |
| PlanRepExpansion::nodeSplit ogdf::PlanRepExpansion::convertDummy | ( | node | u, | |
| node | vOrig, | |||
| PlanRepExpansion::nodeSplit | ns | |||
| ) |
Converts a dummy node u to a copy of an original node vOrig.
This method is used if two copy nodes x and y of the same original node vOrig can be connected by converting a dummy node u into a copy node of vOrig, since an insertion path starting (or ending) at x crosses an insertion path starting (or ending) at y.
| u | is a dummy node in the planarized expansion. | |
| vOrig | is an original node. | |
| ns | is a node split that can be reused for connecting x with u. |
| edge ogdf::PlanRepExpansion::separateDummy | ( | adjEntry | adj_1, | |
| adjEntry | adj_2, | |||
| node | vStraight, | |||
| bool | isSrc | |||
| ) |
| void ogdf::PlanRepExpansion::resolvePseudoCrossing | ( | node | v | ) |
| bool ogdf::PlanRepExpansion::consistencyCheck | ( | ) | const |
| void ogdf::PlanRepExpansion::doInit | ( | const Graph & | G, | |
| const List< node > & | splittableNodes | |||
| ) | [private] |
| void ogdf::PlanRepExpansion::prepareNodeSplit | ( | const SList< adjEntry > & | partitionLeft, | |
| adjEntry & | adjLeft, | |||
| adjEntry & | adjRight | |||
| ) | [private] |
const Graph* ogdf::PlanRepExpansion::m_pGraph [private] |
NodeArray<node> ogdf::PlanRepExpansion::m_vOrig [private] |
EdgeArray<edge> ogdf::PlanRepExpansion::m_eOrig [private] |
EdgeArray<ListIterator<edge> > ogdf::PlanRepExpansion::m_eIterator [private] |
EdgeArray<List<edge> > ogdf::PlanRepExpansion::m_eCopy [private] |
The corresponding list of edges in the graph copy.
Definition at line 491 of file PlanRepExpansion.h.
NodeArray<ListIterator<node> > ogdf::PlanRepExpansion::m_vIterator [private] |
NodeArray<List<node> > ogdf::PlanRepExpansion::m_vCopy [private] |
The corresponding list of nodes in the graph copy.
Definition at line 493 of file PlanRepExpansion.h.
NodeArray<bool> ogdf::PlanRepExpansion::m_splittable [private] |
Definition at line 495 of file PlanRepExpansion.h.
NodeArray<bool> ogdf::PlanRepExpansion::m_splittableOrig [private] |
Definition at line 496 of file PlanRepExpansion.h.
EdgeArray<NodeSplit *> ogdf::PlanRepExpansion::m_eNodeSplit [private] |
Definition at line 497 of file PlanRepExpansion.h.
List<NodeSplit> ogdf::PlanRepExpansion::m_nodeSplits [private] |
Definition at line 498 of file PlanRepExpansion.h.
int ogdf::PlanRepExpansion::m_currentCC [private] |
int ogdf::PlanRepExpansion::m_numCC [private] |
Array<List<node> > ogdf::PlanRepExpansion::m_nodesInCC [private] |
EdgeArray<edge> ogdf::PlanRepExpansion::m_eAuxCopy [private] |
Definition at line 504 of file PlanRepExpansion.h.
