#include <GraphCopy.h>

Public Member Functions | |
| GraphCopy (const Graph &G) | |
| Creates a graph copy of G. | |
| GraphCopy () | |
| Default constructor (does nothing!). | |
| GraphCopy (const GraphCopy &GC) | |
| Copy constructor. | |
| virtual | ~GraphCopy () |
Mapping between original graph and copy | |
| const Graph & | original () const |
| Returns a reference to the original graph. | |
| node | original (node v) const |
| Returns the node in the original graph corresponding to v. | |
| edge | original (edge e) const |
| Returns the edge in the original graph corresponding to e. | |
| node | copy (node v) const |
| Returns the node in the graph copy corresponding to v. | |
| const List< edge > & | chain (edge e) const |
| Returns the list of edges coresponding to edge e. | |
| edge | copy (edge e) const |
| Returns the first edge in the list of edges coresponding to edge e. | |
| bool | isDummy (node v) const |
| Returns true iff v has no corresponding node in the original graph. | |
| bool | isDummy (edge e) const |
| Returns true iff e has no corresponding edge in the original graph. | |
| bool | isReversed (edge e) const |
| Returns true iff edge e has been reversed. | |
Creation and deletion of nodes and edges | |
| node | newNode () |
| Creates a new node in the graph copy. | |
| node | newNode (node vOrig) |
| Creates a new node in the graph copy with original node vOrig. | |
| void | delCopy (node v) |
| Removes node v and all its adjacent edges cleaning-up their corresponding lists of original edges. | |
| void | delCopy (edge e) |
| Removes edge e and clears the list of edges corresponding to e's original edge. | |
| virtual edge | split (edge e) |
| Splits edge e. | |
| void | unsplit (edge eIn, edge eOut) |
| Undoes a previous split operation. The two edges eIn and eOut are merged to a single edge eIn. | |
| edge | newEdge (edge eOrig) |
| Creates a new edge (v,w) with original edge eOrig. | |
| edge | newEdge (edge eOrig, adjEntry adjSrc, node w) |
| Creates a new edge with original edge eOrig at predefined positions in the adjacency lists. | |
| edge | newEdge (edge eOrig, node v, adjEntry adjTgt) |
| Creates a new edge with original edge eOrig at predefined positions in the adjacency lists. | |
| edge | newEdge (node v, node w) |
| Creates a new edge (v,w) and returns it. | |
| edge | newEdge (adjEntry adjSrc, adjEntry adjTgt) |
| edge | newEdge (node v, adjEntry adjTgt) |
| Creates a new edge at predefined positions in the adjacency lists. | |
| edge | newEdge (adjEntry adjSrc, node w) |
| Creates a new edge at predefined positions in the adjacency lists. | |
| void | setEdge (edge eOrig, edge eCopy) |
| sets eOrig to be the corresponding original edge of eCopy and vice versa | |
| void | insertEdgePath (edge eOrig, const SList< adjEntry > &crossedEdges) |
| Re-inserts edge eOrig by "crossing" the edges in crossedEdges. | |
| void | removeEdgePath (edge eOrig) |
| Removes the complete edge path for edge eOrig. | |
| edge | insertCrossing (edge &crossingEdge, edge crossedEdge, bool topDown) |
| Inserts crossings between already existing edges (used in TopologyModule). | |
Combinatorial Embeddings | |
| edge | newEdge (node v, adjEntry adj, edge eOrig, CombinatorialEmbedding &E) |
| Creates a new edge with original edge eOrig in an embedding E. | |
| void | setOriginalEmbedding () |
| Sets the embedding of the graph copy to the embedding of the original graph. | |
| void | insertEdgePathEmbedded (edge eOrig, CombinatorialEmbedding &E, const SList< adjEntry > &crossedEdges) |
| Re-inserts edge eOrig by "crossing" the edges in crossedEdges in embedding E. | |
| void | removeEdgePathEmbedded (CombinatorialEmbedding &E, edge eOrig, FaceSetPure &newFaces) |
Miscellaneous | |
| bool | consistencyCheck () const |
| Checks the consistency of the data structure (for debugging only). | |
| void | createEmpty (const Graph &G) |
| Associates the graph copy with G, but does not create any nodes or edges. | |
| void | initByNodes (const List< node > &nodes, EdgeArray< edge > &eCopy) |
| Initializes the graph copy for the nodes in a component. | |
| void | initByActiveNodes (const List< node > &nodes, const NodeArray< bool > &activeNodes, EdgeArray< edge > &eCopy) |
| Initializes the graph copy for the nodes in nodes. | |
Operators | |
| GraphCopy & | operator= (const GraphCopy &GC) |
| Assignment operator. | |
Protected 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. | |
| NodeArray< node > | m_vCopy |
| The corresponding node in the graph copy. | |
| EdgeArray< List< edge > > | m_eCopy |
| The corresponding list of edges in the graph copy. | |
Private Member Functions | |
| void | initGC (const GraphCopy &GC, NodeArray< node > &vCopy, EdgeArray< edge > &eCopy) |
The class GraphCopy represents a copy of a graph and maintains a mapping between the nodes and edges of the original graph to the copy and vice versa.
New nodes and edges can be added to the copy; the counterpart of those nodes and edges is 0 indicating that there is no counterpart. GraphCopy also support splitting of edges in such a way that both edges resulting from the split are mapped to the same original edge, and each edge of the original graph is mapped to a list of edges. Furthermore, it is allowed to reverse edges in the graph copy.
Here is a short summary, what can be done with GraphCopy, and what should not be done. The following operations are safely supported:
The following operations are not supported and are thus dangerous:
Definition at line 233 of file GraphCopy.h.
| ogdf::GraphCopy::GraphCopy | ( | const Graph & | G | ) |
Creates a graph copy of G.
The constructor assures that the adjacency lists of nodes in the constructed copy are in the same order as the adjacency lists in G. This is in particular important when dealing with embedded graphs.
| ogdf::GraphCopy::GraphCopy | ( | ) | [inline] |
| ogdf::GraphCopy::GraphCopy | ( | const GraphCopy & | GC | ) |
Copy constructor.
Creates a graph copy that is a copy of GC and represents a graph copy of the original graph of GC.
| virtual ogdf::GraphCopy::~GraphCopy | ( | ) | [inline, virtual] |
Definition at line 263 of file GraphCopy.h.
| const Graph& ogdf::GraphCopy::original | ( | ) | const [inline] |
Returns the node in the original graph corresponding to v.
| v | is a node in the graph copy. |
Definition at line 280 of file GraphCopy.h.
Returns the edge in the original graph corresponding to e.
| e | is an edge in the graph copy. |
Definition at line 288 of file GraphCopy.h.
Returns the node in the graph copy corresponding to v.
| v | is a node in the original graph. |
Definition at line 295 of file GraphCopy.h.
Returns the list of edges coresponding to edge e.
| e | is an edge in the original graph. |
Definition at line 302 of file GraphCopy.h.
Returns the first edge in the list of edges coresponding to edge e.
| e | is an edge in the original graph. |
Definition at line 311 of file GraphCopy.h.
| bool ogdf::GraphCopy::isDummy | ( | node | v | ) | const [inline] |
Returns true iff v has no corresponding node in the original graph.
| v | is a node in the graph copy. |
Definition at line 317 of file GraphCopy.h.
| bool ogdf::GraphCopy::isDummy | ( | edge | e | ) | const [inline] |
Returns true iff e has no corresponding edge in the original graph.
| e | is an edge in the graph copy. |
Definition at line 323 of file GraphCopy.h.
| bool ogdf::GraphCopy::isReversed | ( | edge | e | ) | const [inline] |
Returns true iff edge e has been reversed.
| e | is an edge in the graph copy. |
Definition at line 329 of file GraphCopy.h.
| node ogdf::GraphCopy::newNode | ( | ) | [inline] |
Creates a new node in the graph copy.
Reimplemented from ogdf::Graph.
Definition at line 340 of file GraphCopy.h.
Creates a new node in the graph copy with original node vOrig.
Definition at line 349 of file GraphCopy.h.
| void ogdf::GraphCopy::delCopy | ( | node | v | ) |
Removes node v and all its adjacent edges cleaning-up their corresponding lists of original edges.
| v | is a node in the graph copy. |
| void ogdf::GraphCopy::delCopy | ( | edge | e | ) |
Removes edge e and clears the list of edges corresponding to e's original edge.
| e | is an edge in the graph copy. |
Splits edge e.
| e | is an edge in the graph copy. |
Reimplemented from ogdf::Graph.
Reimplemented in ogdf::ClusterPlanRep, ogdf::PlanRep, ogdf::PlanRepInc, and ogdf::PlanRepUML.
Undoes a previous split operation. The two edges eIn and eOut are merged to a single edge eIn.
| eIn | is an edge (*,u) in the graph copy. | |
| eOut | is an edge (u,*) in the graph copy. |
Reimplemented from ogdf::Graph.
Creates a new edge with original edge eOrig at predefined positions in the adjacency lists.
Let v be the node whose adjacency list contains adjSrc. Then, the created edge is (v,w).
| adjSrc | is the adjacency entry after which the new edge is inserted in the adjacency list of v. | |
| w | is the source node of the new edge; the edge is added at the end of the adjacency list of w. |
Creates a new edge with original edge eOrig at predefined positions in the adjacency lists.
Let w be the node whose adjacency list contains adjTgt. Then, the created edge is (v,w).
| v | is the source node of the new edge; the edge is added at the end of the adjacency list of v. | |
| adjTgt | is the adjacency entry after which the new edge is inserted in the adjacency list of w. |
Creates a new edge (v,w) and returns it.
Reimplemented from ogdf::Graph.
Definition at line 417 of file GraphCopy.h.
Definition at line 418 of file GraphCopy.h.
Creates a new edge at predefined positions in the adjacency lists.
Let w be the node whose adjacency list contains adjTgt. Then, the created edge is (v,w).
| v | is the source node of the new edge; the edge is added at the end of the adjacency list of v. | |
| adjTgt | is the adjacency entry after which the new edge is inserted in the adjacency list of w. |
Reimplemented from ogdf::Graph.
Definition at line 419 of file GraphCopy.h.
Creates a new edge at predefined positions in the adjacency lists.
Let v be the node whose adjacency list contains adjSrc. Then, the created edge is (v,w).
| adjSrc | is the adjacency entry after which the new edge is inserted in the adjacency list of v. | |
| w | is the source node of the new edge; the edge is added at the end of the adjacency list of w. |
Reimplemented from ogdf::Graph.
Definition at line 420 of file GraphCopy.h.
sets eOrig to be the corresponding original edge of eCopy and vice versa
| eOrig | is the original edge | |
| eCopy | is the edge copy |
Re-inserts edge eOrig by "crossing" the edges in crossedEdges.
Let v and w be the copies of the source and target nodes of eOrig. Each edge in crossedEdges is split creating a sequence
of new nodes, and additional edges are inserted creating a path
.
| eOrig | is an edge in the original graph and becomes the original edge of all edges in the path . | |
| crossedEdges | are edges in the graph copy. |
Reimplemented in ogdf::PlanRep.
| void ogdf::GraphCopy::removeEdgePath | ( | edge | eOrig | ) |
Removes the complete edge path for edge eOrig.
@param eOrig is an edge in the original graph.
Inserts crossings between already existing edges (used in TopologyModule).
Replaces crossingEdge by first crossingEdge part and returns second.
| topDown | describes the following: if the crossingEdge is running horizontally from left to right, is the crossedEdge direction top->down? |
Reimplemented in ogdf::PlanRep.
| edge ogdf::GraphCopy::newEdge | ( | node | v, | |
| adjEntry | adj, | |||
| edge | eOrig, | |||
| CombinatorialEmbedding & | E | |||
| ) |
Creates a new edge with original edge eOrig in an embedding E.
Let w be the node whose adjacency list contains adjTgt. The original edge eOrig must connect the original nodes of v and w. If eOrig = (original(v),original(w)), then the created edge is (v,w), otherwise it is (w,v). The new edge e must split a face in E, such that e comes after adj in the adjacency list of v and at the end of the adjacency list of v.
| v | is a node in the graph copy. | |
| adj | is an adjacency entry in the graph copy. | |
| eOrig | is an edge in the original graph. | |
| E | is an embedding of the graph copy. |
| void ogdf::GraphCopy::setOriginalEmbedding | ( | ) |
Sets the embedding of the graph copy to the embedding of the original graph.
| void ogdf::GraphCopy::insertEdgePathEmbedded | ( | edge | eOrig, | |
| CombinatorialEmbedding & | E, | |||
| const SList< adjEntry > & | crossedEdges | |||
| ) |
Re-inserts edge eOrig by "crossing" the edges in crossedEdges in embedding E.
Let v and w be the copies of the source and target nodes of eOrig, and let
be the sequence of edges corresponding to the adjacency entries in crossedEdges. The first edge needs to be incident to v and the last to w; the edges
are each split creating a sequence
of new nodes, and additional edges are inserted creating a path
.
The following figure illustrates, which adjacency entries need to be in the list crossedEdges. It inserts an edge connecting v and w by passing through the faces
; in this case, the list crossedEdges must contain the adjacency entries
(in this order).
| eOrig | is an edge in the original graph and becomes the original edge of all edges in the path . | |
| E | is an embedding of the graph copy. | |
| crossedEdges | are a list of adjacency entries in the graph copy. |
Reimplemented in ogdf::ClusterPlanRep, and ogdf::PlanRep.
| void ogdf::GraphCopy::removeEdgePathEmbedded | ( | CombinatorialEmbedding & | E, | |
| edge | eOrig, | |||
| FaceSetPure & | newFaces | |||
| ) |
Removes the complete edge path for edge eOrig while preserving the embedding.
| E | is an embedding of the graph copy. | |
| eOrig | is an edge in the original graph. | |
| newFaces | is assigned the set of new faces resulting from joining faces when removing edges. |
Reimplemented in ogdf::PlanRep.
| bool ogdf::GraphCopy::consistencyCheck | ( | ) | const |
| void ogdf::GraphCopy::createEmpty | ( | const Graph & | G | ) |
Associates the graph copy with G, but does not create any nodes or edges.
This method is used for a special creation of the graph copy. The graph copy needs to be constructed with the default constructor, gets associated with G using this method, and then is initialized using either initByNodes() or initByActiveNodes().
The following code snippet shows a typical application of this functionality:
GraphCopy GC; GC.createEmpty(G); // compute connected components of G NodeArray<int> component(G); int numCC = connectedComponents(G,component); // intialize the array of lists of nodes contained in a CC Array<List<node> > nodesInCC(numCC); node v; forall_nodes(v,G) nodesInCC[component[v]].pushBack(v); EdgeArray<edge> auxCopy(G); Array<DPoint> boundingBox(numCC); for(int i = 0; i < numCC; ++i) { GC.initByNodes(nodesInCC[i],auxCopy); ... }
| G | is the graph of which this graph copy shall be a copy. |
Initializes the graph copy for the nodes in a component.
Creates copies of all nodes in nodes and their incident edges. Any nodes and edges allocated before are removed.
The order of entries in the adjecency lists is preserved, i.e., if the original graph is embedded, its embedding induces the embedding of the created copy.
It is important that nodes is the complete list of nodes in a connected component. If you wish to initialize the graph copy for an arbitrary set of nodes, use the method initByActiveNodes().
| nodes | is the list of nodes in the original graph for which copies are created in the graph copy. | |
| eCopy | is assigned the copy of each original edge. |
| void ogdf::GraphCopy::initByActiveNodes | ( | const List< node > & | nodes, | |
| const NodeArray< bool > & | activeNodes, | |||
| EdgeArray< edge > & | eCopy | |||
| ) |
Initializes the graph copy for the nodes in nodes.
Creates copies of all nodes in nodes and edges between two nodes which are both contained in nodes. Any nodes and edges allocated before are destroyed.
| nodes | is the list of nodes in the original graph for which copies are created in the graph copy. | |
| activeNodes | must be true for every node in nodes, false otherwise. | |
| eCopy | is assigned the copy of each original edge. |
Assignment operator.
Creates a graph copy that is a copy of GC and represents a graph copy of the original graph of GC.
The constructor assures that the adjacency lists of nodes in the constructed graph are in the same order as the adjacency lists in G. This is in particular important when dealing with embedded graphs.
| void ogdf::GraphCopy::initGC | ( | const GraphCopy & | GC, | |
| NodeArray< node > & | vCopy, | |||
| EdgeArray< edge > & | eCopy | |||
| ) | [private] |
const Graph* ogdf::GraphCopy::m_pGraph [protected] |
NodeArray<node> ogdf::GraphCopy::m_vOrig [protected] |
EdgeArray<edge> ogdf::GraphCopy::m_eOrig [protected] |
EdgeArray<ListIterator<edge> > ogdf::GraphCopy::m_eIterator [protected] |
NodeArray<node> ogdf::GraphCopy::m_vCopy [protected] |
EdgeArray<List<edge> > ogdf::GraphCopy::m_eCopy [protected] |