Planarized representations (of a connected component) of a graph. More...
#include <ogdf/planarity/PlanRepExpansion.h>
Classes | |
struct | Crossing |
class | NodeSplit |
Representation of a node split in a planarized expansion. More... | |
Public Types | |
using | nodeSplit = PlanRepExpansion::NodeSplit * |
Pointer to a node split. More... | |
Public Types inherited from ogdf::Graph | |
enum | EdgeType { EdgeType::association = 0, EdgeType::generalization = 1, EdgeType::dependency = 2 } |
The type of edges (only used in derived classes). More... | |
enum | NodeType { NodeType::vertex = 0, NodeType::dummy = 1, NodeType::generalizationMerger = 2, NodeType::generalizationExpander = 3, NodeType::highDegreeExpander = 4, NodeType::lowDegreeExpander = 5, NodeType::associationClass = 6 } |
The type of nodes. More... | |
using | node_iterator = internal::GraphIterator< node > |
Provides a bidirectional iterator to a node in a graph. More... | |
using | edge_iterator = internal::GraphIterator< edge > |
Provides a bidirectional iterator to an edge in a graph. More... | |
using | adjEntry_iterator = internal::GraphIterator< adjEntry > |
Provides a bidirectional iterator to an entry in an adjacency list. More... | |
Public Member Functions | |
PlanRepExpansion (const Graph &G) | |
Creates a planarized expansion of graph G . More... | |
PlanRepExpansion (const Graph &G, const List< node > &splittableNodes) | |
Creates a planarized expansion of graph G with given splittable nodes. More... | |
~PlanRepExpansion () | |
Acess methods | |
const Graph & | original () const |
Returns a reference to the original graph. More... | |
node | original (node v) const |
Returns the original node of v , or 0 if v is a dummy. More... | |
const List< node > & | expansion (node vOrig) const |
Returns the list of copy nodes of vOrig . More... | |
node | copy (node vOrig) const |
Returns the first copy node of vOrig . More... | |
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). More... | |
const List< edge > & | chain (edge eOrig) const |
Returns the insertion path of edge eOrig . More... | |
edge | copy (edge eOrig) const |
Returns the first edge in eOrig's insertion path. More... | |
bool | splittable (node v) const |
Returns true iff v is splittable. More... | |
bool | splittableOrig (node vOrig) const |
Returns true iff vOrig is splittable. More... | |
NodeSplit * | nodeSplitOf (edge e) const |
Returns the node split associated with e , or 0 if none (e.g., e belongs to an original edge). More... | |
int | numberOfNodeSplits () const |
Returns the number of node splits. More... | |
int | numberOfSplittedNodes () const |
List< NodeSplit > & | nodeSplits () |
Returns the list of node splits. More... | |
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. More... | |
ListConstIterator< edge > | position (edge e) const |
bool | isPseudoCrossing (node v) const |
int | computeNumberOfCrossings () const |
Computes the number of crossings. More... | |
Processing connected components | |
int | numberOfCCs () const |
Returns the number of connected components in the original graph. More... | |
int | currentCC () const |
Returns the index of the current connected component (-1 if not yet initialized). More... | |
const List< node > & | nodesInCC (int i) const |
Returns the list of (original) nodes in connected component i . More... | |
const List< node > & | nodesInCC () const |
Returns the list of (original) nodes in the current connected component. More... | |
void | initCC (int i) |
Initializes the planarized representation for connected component i . More... | |
Update operations | |
edge | split (edge e) override |
Splits edge e into two edges introducing a new node. More... | |
void | unsplit (edge eIn, edge eOut) override |
Undoes a split operation. More... | |
virtual void | delEdge (edge e) override |
Removes edge e from the planarized expansion. More... | |
bool | embed () |
Embeds the planarized expansion; returns true iff it is planar. More... | |
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 . More... | |
void | removeEdgePathEmbedded (CombinatorialEmbedding &E, edge eOrig, nodeSplit ns, FaceSet< false > &newFaces, NodeSet< false > &mergedNodes, node &oldSrc, node &oldTgt) |
Removes the insertion path of eOrig or ns . More... | |
void | removeEdgePath (edge eOrig, nodeSplit ns, node &oldSrc, node &oldTgt) |
Removes the insertion path of eOrig or ns . More... | |
void | contractSplit (nodeSplit ns, CombinatorialEmbedding &E) |
Removes an (unneccessary) node split consisting of a single edge. More... | |
void | contractSplit (nodeSplit ns) |
Removes an (unneccessary) node split consisting of a single edge. More... | |
edge | unsplitExpandNode (node u, edge eContract, edge eExpand, CombinatorialEmbedding &E) |
Unsplits a superfluous expansion node of degree 2. More... | |
edge | unsplitExpandNode (node u, edge eContract, edge eExpand) |
Unsplits a superfluous expansion node of degree 2. More... | |
edge | enlargeSplit (node v, edge e, CombinatorialEmbedding &E) |
Splits edge e and introduces a new node split starting at v . More... | |
edge | enlargeSplit (node v, edge e) |
Splits edge e and introduces a new node split starting at v . More... | |
edge | splitNodeSplit (edge e, CombinatorialEmbedding &E) |
Introduces a new node split by splitting an exisiting node split. More... | |
edge | splitNodeSplit (edge e) |
Introduces a new node split by splitting an exisiting node split. More... | |
void | removeSelfLoop (edge e, CombinatorialEmbedding &E) |
Removes a self-loop e = (u,u). More... | |
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 . More... | |
edge | separateDummy (adjEntry adj_1, adjEntry adj_2, node vStraight, bool isSrc) |
void | resolvePseudoCrossing (node v) |
Miscelleaneous | |
void | consistencyCheck () const |
Public Member Functions inherited from ogdf::Graph | |
Graph () | |
Constructs an empty graph. More... | |
Graph (const Graph ©) | |
Constructs a graph that is a copy of G . More... | |
Graph (Graph &&move)=delete | |
virtual | ~Graph () |
Destructor. More... | |
Graph & | operator= (const Graph ©) |
Overwrites this graph to be a copy of G . More... | |
Graph & | operator= (Graph &&move)=delete |
bool | empty () const |
Returns true iff the graph is empty, i.e., contains no nodes. More... | |
int | numberOfNodes () const |
Returns the number of nodes in the graph. More... | |
int | numberOfEdges () const |
Returns the number of edges in the graph. More... | |
int | maxNodeIndex () const |
Returns the largest used node index. More... | |
int | maxEdgeIndex () const |
Returns the largest used edge index. More... | |
int | maxAdjEntryIndex () const |
Returns the largest used adjEntry index. More... | |
node | firstNode () const |
Returns the first node in the list of all nodes. More... | |
node | lastNode () const |
Returns the last node in the list of all nodes. More... | |
edge | firstEdge () const |
Returns the first edge in the list of all edges. More... | |
edge | lastEdge () const |
Returns the last edge in the list of all edges. More... | |
node | chooseNode (std::function< bool(node)> includeNode=[](node) { return true;}, bool isFastTest=true) const |
Returns a random node. More... | |
edge | chooseEdge (std::function< bool(edge)> includeEdge=[](edge) { return true;}, bool isFastTest=true) const |
Returns a random edge. More... | |
template<class CONTAINER > | |
void | allNodes (CONTAINER &nodeContainer) const |
Returns a container with all nodes of the graph. More... | |
template<class CONTAINER > | |
void | allEdges (CONTAINER &edgeContainer) const |
Returns a container with all edges of the graph. More... | |
node | newNode (int index=-1) |
Creates a new node and returns it. More... | |
edge | newEdge (node v, node w, int index=-1) |
Creates a new edge (v ,w ) and returns it. More... | |
edge | newEdge (node v, adjEntry adjTgt, int index=-1) |
Creates a new edge at predefined positions in the adjacency lists. More... | |
edge | newEdge (adjEntry adjSrc, node w, int index=-1) |
Creates a new edge at predefined positions in the adjacency lists. More... | |
edge | newEdge (adjEntry adjSrc, adjEntry adjTgt, Direction dir=Direction::after, int index=-1) |
Creates a new edge at predefined positions in the adjacency lists. More... | |
template<typename S , typename T > | |
edge | newEdge (S src, Direction dirSrc, T tgt, Direction dirTgt, int index=-1) |
Creates a new edge at predefined positions in the adjacency lists. More... | |
virtual void | delNode (node v) |
Removes node v and all incident edges from the graph. More... | |
virtual void | clear () |
Removes all nodes and all edges from the graph. More... | |
void | restoreAllEdges () |
Restore all hidden edges and invalidate all HiddenEdgeSets. More... | |
void | unsplit (node u) |
Undoes a split operation. More... | |
node | splitNode (adjEntry adjStartLeft, adjEntry adjStartRight) |
Splits a node while preserving the order of adjacency entries. More... | |
node | contract (edge e, bool keepSelfLoops=false) |
Contracts edge e while preserving the order of adjacency entries. More... | |
void | move (edge e, adjEntry adjSrc, Direction dirSrc, adjEntry adjTgt, Direction dirTgt) |
Moves edge e to a different adjacency list. More... | |
void | moveTarget (edge e, node w) |
Moves the target node of edge e to node w . More... | |
void | moveTarget (edge e, adjEntry adjTgt, Direction dir) |
Moves the target node of edge e to a specific position in an adjacency list. More... | |
void | moveSource (edge e, node w) |
Moves the source node of edge e to node w . More... | |
void | moveSource (edge e, adjEntry adjSrc, Direction dir) |
Moves the source node of edge e to a specific position in an adjacency list. More... | |
edge | searchEdge (node v, node w, bool directed=false) const |
Searches and returns an edge connecting nodes v and w in time O( min(deg(v ), deg(w ))). More... | |
void | reverseEdge (edge e) |
Reverses the edge e , i.e., exchanges source and target node. More... | |
void | reverseAllEdges () |
Reverses all edges in the graph. More... | |
template<class NODELIST > | |
void | collapse (NODELIST &nodesToCollapse) |
Collapses all nodes in the list nodesToCollapse to the first node in the list. More... | |
template<class ADJ_ENTRY_LIST > | |
void | sort (node v, const ADJ_ENTRY_LIST &newOrder) |
Sorts the adjacency list of node v according to newOrder . More... | |
template<class IT > | |
void | sort (node v, IT begin, IT end) |
Sorts the adjacency list of node v according to the range denoted by two iterators. More... | |
void | reverseAdjEdges (node v) |
Reverses the adjacency list of v . More... | |
void | moveAdj (adjEntry adjMove, Direction dir, adjEntry adjPos) |
Moves adjacency entry adjMove before or after adjPos . More... | |
void | moveAdjAfter (adjEntry adjMove, adjEntry adjAfter) |
Moves adjacency entry adjMove after adjAfter . More... | |
void | moveAdjBefore (adjEntry adjMove, adjEntry adjBefore) |
Moves adjacency entry adjMove before adjBefore . More... | |
void | reverseAdjEdges () |
Reverses all adjacency lists. More... | |
void | swapAdjEdges (adjEntry adj1, adjEntry adj2) |
Exchanges two entries in an adjacency list. More... | |
int | genus () const |
Returns the genus of the graph's embedding. More... | |
bool | representsCombEmbedding () const |
Returns true iff the graph represents a combinatorial embedding. More... | |
void | consistencyCheck () const |
Asserts that this graph is consistent. More... | |
internal::GraphNodeRegistry & | nodeRegistry () |
Returns a reference to the registry of node arrays associated with this graph. More... | |
const internal::GraphNodeRegistry & | nodeRegistry () const |
Returns a const reference to the registry of node arrays associated with this graph. More... | |
operator const internal::GraphNodeRegistry & () const | |
internal::GraphEdgeRegistry & | edgeRegistry () |
Returns a reference to the registry of edge arrays associated with this graph. More... | |
const internal::GraphEdgeRegistry & | edgeRegistry () const |
Returns a const reference to the registry of edge arrays associated with this graph. More... | |
operator const internal::GraphEdgeRegistry & () const | |
internal::GraphAdjRegistry & | adjEntryRegistry () |
Returns a reference to the registry of adjEntry arrays associated with this graph. More... | |
const internal::GraphAdjRegistry & | adjEntryRegistry () const |
Returns a const reference to the registry of adjEntry arrays associated with this graph. More... | |
operator const internal::GraphAdjRegistry & () const | |
void | resetEdgeIdCount (int maxId) |
Resets the edge id count to maxId . More... | |
void | resetNodeIdCount (int maxId) |
template<OGDF_NODE_ITER NI, OGDF_EDGE_ITER EI, bool copyEmbedding = true, bool copyIDs = false, bool notifyObservers = true> | |
std::pair< int, int > | insert (const NI &nodesBegin, const NI &nodesEnd, const EI &edgesBegin, const EI &edgesEnd, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap) |
Inserts a copy of a given subgraph into this graph. More... | |
template<OGDF_NODE_ITER NI, OGDF_EDGE_FILTER EF, bool copyIDs = false, bool notifyObservers = true> | |
std::pair< int, int > | insert (const NI &nodesBegin, const NI &nodesEnd, const EF &edgeFilter, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap) |
Inserts a copy of a given subgraph into this graph. More... | |
template<OGDF_NODE_LIST NL> | |
std::pair< int, int > | insert (const NL &nodeList, const EdgeSet< true > &edgeSet, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap) |
Inserts a copy of a given subgraph into this graph. More... | |
template<OGDF_NODE_LIST NL> | |
std::pair< int, int > | insert (const NL &nodeList, const EdgeSet< false > &edgeSet, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap) |
Inserts a copy of a given subgraph into this graph. More... | |
template<OGDF_NODE_LIST NL, OGDF_EDGE_LIST EL> | |
std::pair< int, int > | insert (const NL &nodeList, const EL &edgeList, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap) |
Inserts a copy of a given subgraph into this graph. More... | |
std::pair< int, int > | insert (const CCsInfo &info, int cc, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap) |
Inserts a copy of a given connected component cc into this graph. More... | |
std::pair< int, int > | insert (const Graph &G, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap) |
Inserts a copy of a given Graph G into this graph. More... | |
std::pair< int, int > | insert (const Graph &G) |
Inserts a copy of a given Graph G into this graph. More... | |
Public Member Functions inherited from ogdf::Observable< GraphObserver, Graph > | |
Observable ()=default | |
Observable (const Observable ©)=delete | |
If you want to copy a subclass of Observable, call the default Observable() constructor. More... | |
Observable (Observable &&move)=delete | |
If you want to move a subclass of Observable, call the default Observable() constructor. More... | |
virtual | ~Observable () |
Observable & | operator= (const Observable ©)=delete |
Observable & | operator= (Observable &&move)=delete |
Private Member Functions | |
void | doInit (const Graph &G, const List< node > &splittableNodes) |
void | prepareNodeSplit (const SList< adjEntry > &partitionLeft, adjEntry &adjLeft, adjEntry &adjRight) |
Private Attributes | |
int | m_currentCC |
The index of the current component. More... | |
EdgeArray< edge > | m_eAuxCopy |
EdgeArray< List< edge > > | m_eCopy |
The corresponding list of edges in the graph copy. More... | |
EdgeArray< ListIterator< edge > > | m_eIterator |
The position of copy edge in the list. More... | |
EdgeArray< NodeSplit * > | m_eNodeSplit |
EdgeArray< edge > | m_eOrig |
The corresponding edge in the original graph. More... | |
Array< List< node > > | m_nodesInCC |
The list of original nodes in each component. More... | |
List< NodeSplit > | m_nodeSplits |
int | m_numCC |
The number of components in the original graph. More... | |
const Graph * | m_pGraph |
The original graph. More... | |
NodeArray< bool > | m_splittable |
NodeArray< bool > | m_splittableOrig |
NodeArray< List< node > > | m_vCopy |
The corresponding list of nodes in the graph copy. More... | |
NodeArray< ListIterator< node > > | m_vIterator |
The position of copy node in the list. More... | |
NodeArray< node > | m_vOrig |
The corresponding node in the original graph. More... | |
Additional Inherited Members | |
Public Attributes inherited from ogdf::Graph | |
internal::GraphObjectContainer< NodeElement > | nodes |
The container containing all node objects. More... | |
internal::GraphObjectContainer< EdgeElement > | edges |
The container containing all edge objects. More... | |
Protected Member Functions inherited from ogdf::Graph | |
virtual void * | preInsert (bool copyEmbedding, bool copyIDs, bool notifyObservers, bool edgeFilter, NodeArray< node > &nodeMap, EdgeArray< edge > &edgeMap, int *newNodes, int *newEdges) |
Callback notifying subclasses that some graph is about to be insert() -ed. More... | |
virtual void | nodeInserted (void *userData, node original, node copy) |
Callback notifying subclasses that insert() copied a node. More... | |
virtual void | edgeInserted (void *userData, edge original, edge copy) |
Callback notifying subclasses that insert() copied an edge. More... | |
virtual void | postInsert (void *userData, int newNodes, int newEdges) |
Callback notifying subclasses that an insert() call has finished. More... | |
Protected Member Functions inherited from ogdf::Observable< GraphObserver, Graph > | |
void | clearObservers () |
const ListPure< GraphObserver * > & | getObservers () const |
Planarized representations (of a connected component) of a graph.
Maintains types of edges (generalization, association) and nodes, and the connected components of the graph.
Definition at line 52 of file PlanRepExpansion.h.
Pointer to a node split.
Definition at line 102 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. |
|
inline |
Definition at line 121 of file PlanRepExpansion.h.
Returns the insertion path of edge eOrig
.
Definition at line 144 of file PlanRepExpansion.h.
int ogdf::PlanRepExpansion::computeNumberOfCrossings | ( | ) | const |
Computes the number of crossings.
void ogdf::PlanRepExpansion::consistencyCheck | ( | ) | const |
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. |
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. |
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 . |
Returns the first edge in eOrig's
insertion path.
Definition at line 147 of file PlanRepExpansion.h.
Returns the first copy node of vOrig
.
Definition at line 138 of file PlanRepExpansion.h.
|
inline |
Returns the index of the current connected component (-1 if not yet initialized).
Definition at line 199 of file PlanRepExpansion.h.
|
overridevirtual |
Removes edge e
from the planarized expansion.
Reimplemented from ogdf::Graph.
|
private |
bool ogdf::PlanRepExpansion::embed | ( | ) |
Embeds the planarized expansion; returns true iff it is planar.
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 the target node of this edge. 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. |
e
is the target node of this edge. Returns the list of copy nodes of vOrig
.
Definition at line 135 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,...
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. |
eOrig
and ns
may be 0. crossedEdges
. bool ogdf::PlanRepExpansion::isPseudoCrossing | ( | node | v | ) | const |
Returns the list of (original) nodes in the current connected component.
Definition at line 211 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 206 of file PlanRepExpansion.h.
Returns the node split associated with e
, or 0 if none (e.g., e
belongs to an original edge).
Definition at line 156 of file PlanRepExpansion.h.
Returns the list of node splits.
Definition at line 164 of file PlanRepExpansion.h.
|
inline |
Returns the number of connected components in the original graph.
Definition at line 194 of file PlanRepExpansion.h.
|
inline |
Returns the number of node splits.
Definition at line 159 of file PlanRepExpansion.h.
int ogdf::PlanRepExpansion::numberOfSplittedNodes | ( | ) | const |
|
inline |
Returns a reference to the original graph.
Definition at line 129 of file PlanRepExpansion.h.
Returns the original node of v
, or 0 if v
is a dummy.
Definition at line 132 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 141 of file PlanRepExpansion.h.
|
inline |
Definition at line 177 of file PlanRepExpansion.h.
|
private |
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. |
eOrig
and ns
may be 0. void ogdf::PlanRepExpansion::removeEdgePathEmbedded | ( | CombinatorialEmbedding & | E, |
edge | eOrig, | ||
nodeSplit | ns, | ||
FaceSet< false > & | newFaces, | ||
NodeSet< false > & | 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. |
eOrig
and ns
may be 0. void ogdf::PlanRepExpansion::removeSelfLoop | ( | edge | e | ) |
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::resolvePseudoCrossing | ( | node | v | ) |
edge ogdf::PlanRepExpansion::separateDummy | ( | adjEntry | adj_1, |
adjEntry | adj_2, | ||
node | vStraight, | ||
bool | isSrc | ||
) |
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). |
e
; this is either the insertion path of eOrig
(if this is not 0), or of ns
. 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.
e
is modified by this operation.e | is the edge to be split. |
Reimplemented from ogdf::Graph.
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 the target node of this edge. 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. |
e
is the target node of this edge.
|
inline |
Returns true iff v
is splittable.
Definition at line 150 of file PlanRepExpansion.h.
|
inline |
Returns true iff vOrig
is splittable.
Definition at line 153 of file PlanRepExpansion.h.
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.
eIn
and eOut
are the only edges incident with u and none of them is a self-loop.eIn | is the (only) incoming edge of u. |
eOut | is the (only) outgoing edge of u. |
Reimplemented from ogdf::Graph.
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::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. |
|
private |
The index of the current component.
Definition at line 432 of file PlanRepExpansion.h.
Definition at line 436 of file PlanRepExpansion.h.
The corresponding list of edges in the graph copy.
Definition at line 423 of file PlanRepExpansion.h.
|
private |
The position of copy edge in the list.
Definition at line 422 of file PlanRepExpansion.h.
Definition at line 429 of file PlanRepExpansion.h.
The corresponding edge in the original graph.
Definition at line 421 of file PlanRepExpansion.h.
The list of original nodes in each component.
Definition at line 435 of file PlanRepExpansion.h.
Definition at line 430 of file PlanRepExpansion.h.
|
private |
The number of components in the original graph.
Definition at line 433 of file PlanRepExpansion.h.
|
private |
The original graph.
Definition at line 419 of file PlanRepExpansion.h.
|
private |
Definition at line 427 of file PlanRepExpansion.h.
|
private |
Definition at line 428 of file PlanRepExpansion.h.
The corresponding list of nodes in the graph copy.
Definition at line 425 of file PlanRepExpansion.h.
|
private |
The position of copy node in the list.
Definition at line 424 of file PlanRepExpansion.h.
The corresponding node in the original graph.
Definition at line 420 of file PlanRepExpansion.h.