/*
* $Revision: 2583 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
***************************************************************/
/** \file
* \brief Declaration of graph copy classes.
*
* \author Carsten Gutwenger
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#ifdef _MSC_VER
#pragma once
#endif
#ifndef OGDF_GRAPH_COPY_H
#define OGDF_GRAPH_COPY_H
#include "NodeArray.h"
#include "EdgeArray.h"
#include "SList.h"
#include "CombinatorialEmbedding.h"
namespace ogdf {
class FaceSetPure;
//---------------------------------------------------------
// GraphCopySimple
// simple graph copies (no support for edge splitting)
//---------------------------------------------------------
/**
* \brief Copies of graphs with mapping between nodes and edges
*
* The class GraphCopySimple 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.
* This class does not support splitting of edges in such a way
* that both edges resulting from the split are mapped to the same
* original edge; this feature is provided by GraphCopy.
*/
class OGDF_EXPORT GraphCopySimple : public Graph
{
const Graph *m_pGraph; //!< The original graph.
NodeArray m_vOrig; //!< The corresponding node in the original graph.
NodeArray m_vCopy; //!< The corresponding node in the graph copy.
EdgeArray m_eOrig; //!< The corresponding edge in the original graph.
EdgeArray m_eCopy; //!< The corresponding edge in the graph copy.
public:
// construction
//! Constructs a copy of graph \a G.
GraphCopySimple(const Graph &G);
//! Copy constructor.
GraphCopySimple(const GraphCopySimple &GC);
virtual ~GraphCopySimple() { }
//! Returns a reference to the original graph.
const Graph &original() const { return *m_pGraph; }
/**
* \brief Returns the node in the original graph corresponding to \a v.
* @param v is a node in the graph copy.
* \return the corresponding node in the original graph, or 0 if no
* such node exists.
*/
node original(node v) const { return m_vOrig[v]; }
/**
* \brief Returns the edge in the original graph corresponding to \a e.
* @param e is an edge in the graph copy.
* \return the corresponding edge in the original graph, or 0 if no
* such edge exists.
*/
edge original(edge e) const { return m_eOrig[e]; }
/**
* \brief Returns the node in the graph copy corresponding to \a v.
* @param v is a node in the original graph.
* \return the corresponding node in the graph copy.
*/
node copy(node v) const { return m_vCopy[v]; }
/**
* \brief Returns the edge in the graph copy corresponding to \a e.
* @param e is an edge in the original graph.
* \return the corresponding edge in the graph copy.
*/
edge copy(edge e) const { return m_eCopy[e]; }
/**
* \brief Returns true iff \a v has no corresponding node in the original graph.
* @param v is a node in the graph copy.
*/
bool isDummy(node v) const { return (m_vOrig[v] == 0); }
/**
* \brief Returns true iff \a e has no corresponding edge in the original graph.
* @param e is an edge in the graph copy.
*/
bool isDummy(edge e) const { return (m_eOrig[e] == 0); }
//! Assignment operator.
GraphCopySimple &operator=(const GraphCopySimple &GC);
//! Creates a new node in the graph copy.
node newNode() {
return Graph::newNode();
}
/**
* \brief Creates a new node in the graph copy with original node \a vOrig.
* \warning You have to make sure that the original node makes sense, in
* particular that \a vOrig is not the original node of another node in the copy.
*/
node newNode(node vOrig) {
OGDF_ASSERT(vOrig != 0 && vOrig->graphOf() == m_pGraph);
node v = Graph::newNode();
m_vCopy[m_vOrig[v] = vOrig] = v;
return v;
}
//! Creates a new edge from \a v to \a w in the graph copy.
edge newEdge(node v, node w) {
return Graph::newEdge(v,w);
}
/**
* \brief Creates a new edge in the graph copy with original edge \a eOrig.
* \warning You have to make sure that the original edge makes sense, in
* particular that \a eOrig is not the original edge of another edge in the copy.
*/
edge newEdge(edge eOrig) {
OGDF_ASSERT(eOrig != 0 && eOrig->graphOf() == m_pGraph);
edge e = Graph::newEdge(m_vCopy[eOrig->source()], m_vCopy[eOrig->target()]);
m_eCopy[m_eOrig[e] = eOrig] = e;
return e;
}
private:
void initGC(const GraphCopySimple &GC, NodeArray &vCopy,
EdgeArray &eCopy);
}; // class GraphCopySimple
//---------------------------------------------------------
// GraphCopy
// graph copies (support for edge splitting)
//---------------------------------------------------------
/**
* \brief Copies of graphs supporting edge splitting
*
* 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.
*
* Do's and Dont's
* Here is a short summary, what can be done with GraphCopy, and what should not
* be done. The following operations are safely supported:
* - Splitting of edges such that an original edge is represented by a path
* in the copy (split(), unsplit()).
* - Reversing edges in the copy (Graph::reverseEdge(), Graph::reverseAllEdges()).
* - Reinsertion of original edges such that they are represented by a path
* in the copy (insertEdgePath(), insertEdgePathEmbedded(), removeEdgePath(),
* removeEdgePathEmbedded()).
* - Inserting and removing dummy edges in the copy which are not associated
* with edges in the original graph.
*
* The following operations are not supported and are thus dangerous:
* - Any modifications on the original graph, since the copy will not be
* notified.
* - Moving the source or target node of an edge in the copy to a different node.
* - Removing edges in the graph copy that belong to a path representing an
* original edge.
* - ... (better think first!)
*/
class OGDF_EXPORT GraphCopy : public Graph {
protected:
const Graph *m_pGraph; //!< The original graph.
NodeArray m_vOrig; //!< The corresponding node in the original graph.
EdgeArray m_eOrig; //!< The corresponding edge in the original graph.
EdgeArray > m_eIterator; //!< The position of copy edge in the list.
NodeArray m_vCopy; //!< The corresponding node in the graph copy.
EdgeArray > m_eCopy; //!< The corresponding list of edges in the graph copy.
public:
//! Creates a graph copy of \a G.
/**
* The constructor assures that the adjacency lists of nodes in the
* constructed copy are in the same order as the adjacency lists in \a G.
* This is in particular important when dealing with embedded graphs.
*/
GraphCopy(const Graph &G);
//! Default constructor (does nothing!).
GraphCopy() : Graph() { }
//! Copy constructor.
/**
* Creates a graph copy that is a copy of \a GC and represents a graph
* copy of the original graph of \a GC.
*/
GraphCopy(const GraphCopy &GC);
virtual ~GraphCopy() { }
/**
* @name Mapping between original graph and copy
*/
//@{
//! Returns a reference to the original graph.
const Graph &original() const { return *m_pGraph; }
/**
* \brief Returns the node in the original graph corresponding to \a v.
* @param v is a node in the graph copy.
* \return the corresponding node in the original graph, or 0 if no
* such node exists.
*/
node original(node v) const { return m_vOrig[v]; }
/**
* \brief Returns the edge in the original graph corresponding to \a e.
* @param e is an edge in the graph copy.
* \return the corresponding edge in the original graph, or 0 if no
* such edge exists.
*/
edge original(edge e) const { return m_eOrig[e]; }
/**
* \brief Returns the node in the graph copy corresponding to \a v.
* @param v is a node in the original graph.
* \return the corresponding node in the graph copy.
*/
node copy(node v) const { return m_vCopy[v]; }
/**
* \brief Returns the list of edges coresponding to edge \a e.
* \param e is an edge in the original graph.
* \return the corresponding list of edges in the graph copy.
*/
const List &chain(edge e) const { return m_eCopy[e]; }
// returns first edge in chain(e)
/**
* \brief Returns the first edge in the list of edges coresponding to edge \a e.
* @param e is an edge in the original graph.
* \return the first edge in the corresponding list of edges in
* the graph copy.
*/
edge copy(edge e) const { return m_eCopy[e].front(); }
/**
* \brief Returns true iff \a v has no corresponding node in the original graph.
* @param v is a node in the graph copy.
*/
bool isDummy(node v) const { return (m_vOrig[v] == 0); }
/**
* \brief Returns true iff \a e has no corresponding edge in the original graph.
* @param e is an edge in the graph copy.
*/
bool isDummy(edge e) const { return (m_eOrig[e] == 0); }
/**
* \brief Returns true iff edge \a e has been reversed.
* @param e is an edge in the original graph.
*/
bool isReversed (edge e) const {
return e->source() != original(copy(e)->source());
}
/**
* @name Creation and deletion of nodes and edges
*/
//@{
//! Creates a new node in the graph copy.
node newNode() {
return Graph::newNode();
}
/**
* \brief Creates a new node in the graph copy with original node \a vOrig.
* \warning You have to make sure that the original node makes sense, in
* particular that \a vOrig is not the original node of another node in the copy.
*/
node newNode(node vOrig) {
OGDF_ASSERT(vOrig != 0 && vOrig->graphOf() == m_pGraph);
node v = Graph::newNode();
m_vCopy[m_vOrig[v] = vOrig] = v;
return v;
}
/**
* \brief Removes node \a v and all its adjacent edges cleaning-up their corresponding lists of original edges.
*
* \pre The corresponding lists oforiginal edges contain each only one edge.
* \param v is a node in the graph copy.
*/
void delCopy(node v);
/**
* \brief Removes edge e and clears the list of edges corresponding to \a e's original edge.
*
* \pre The list of edges corresponding to \a e's original edge contains only \a e.
* \param e is an edge in the graph copy.
*/
void delCopy(edge e);
/**
* \brief Splits edge \a e.
* @param e is an edge in the graph copy.
*/
virtual edge split(edge e);
/**
* \brief Undoes a previous split operation.
* The two edges \a eIn and \a eOut are merged to a single edge \a eIn.
* \pre The vertex \a u that was created by the previous split operation has
* exactly one incoming edge \a eIn and one outgoing edge \a eOut.
* @param eIn is an edge (*,\a u) in the graph copy.
* @param eOut is an edge (\a u,*) in the graph copy.
*/
void unsplit(edge eIn, edge eOut);
//! Creates a new edge (\a v,\a w) with original edge \a eOrig.
edge newEdge(edge eOrig);
//! Creates a new edge with original edge \a eOrig at predefined positions in the adjacency lists.
/**
* Let \a v be the node whose adjacency list contains \a adjSrc. Then,
* the created edge is (\a v,\a w).
* @param eOrig is the original edge.
* @param adjSrc is the adjacency entry after which the new edge is inserted
* in the adjacency list of \a v.
* @param w is the source node of the new edge; the edge is added at the end
* of the adjacency list of \a w.
* @return the created edge.
*/
edge newEdge(edge eOrig, adjEntry adjSrc, node w);
//! Creates a new edge with original edge \a eOrig at predefined positions in the adjacency lists.
/**
* Let \a w be the node whose adjacency list contains \a adjTgt. Then,
* the created edge is (\a v,\a w).
* @param eOrig is the original edge.
* @param v is the source node of the new edge; the edge is added at the end
* of the adjacency list of \a v.
* @param adjTgt is the adjacency entry after which the new edge is inserted
* in the adjacency list of \a w.
* @return the created edge.
*/
edge newEdge(edge eOrig, node v, adjEntry adjTgt);
edge newEdge(node v, node w) { return Graph::newEdge(v, w); }
edge newEdge(adjEntry adjSrc, adjEntry adjTgt) { return Graph::newEdge(adjSrc, adjTgt); }
edge newEdge(node v, adjEntry adjTgt) { return Graph::newEdge(v, adjTgt); }
edge newEdge(adjEntry adjSrc, node w) { return Graph::newEdge(adjSrc, w); }
//! sets eOrig to be the corresponding original edge of eCopy and vice versa
/**
* @param eOrig is the original edge
* @param eCopy is the edge copy
*/
void setEdge(edge eOrig, edge eCopy);
//! Re-inserts edge \a eOrig by "crossing" the edges in \a crossedEdges.
/**
* Let \a v and \a w be the copies of the source and target nodes of \a eOrig.
* Each edge in \a crossedEdges is split creating a sequence
* \f$u_1,\ldots,u_k\f$ of new nodes, and additional edges are inserted creating
* a path \f$v,u_1,\ldots,u_k,w\f$.
* @param eOrig is an edge in the original graph and becomes the original edge of
* all edges in the path \f$v,u_1,\ldots,u_k,w\f$.
* @param crossedEdges are edges in the graph copy.
*/
void insertEdgePath(edge eOrig, const SList &crossedEdges);
//for FixedEmbeddingUpwardEdgeInserter only
void insertEdgePath(node srcOrig, node tgtOrig, const SList &crossedEdges);
//! Removes the complete edge path for edge \a eOrig.
/**
* \@param eOrig is an edge in the original graph.
*/
void removeEdgePath(edge eOrig);
//! Inserts crossings between two copy edges.
/**
* This method is used in TopologyModule.
*
* Let \a crossingEdge = (\a a, \a b) and \a crossedEdge = (\a v, \a w).
* Then \a crossedEdge is split creating two edges \a crossedEdge = (\a v, \a u)
* and (\a u, \a w), \a crossingEdge is removed and replaced by two new edges
* \a e1 = (\a a, \a u) and \a e1 = (\a u, \a b).
* Finally it sets \a crossingEdge to \a e2 and returns (\a u, \a w).
*
* @param crossingEdge is the edge that gets split.
* @param crossedEdge is the edge that is replaced by two new edges.
* @param topDown is used as follows: If set to true, \a crossingEdge will cross
* \a crossedEdge from right to left, otherwise from left to right.
*/
edge insertCrossing(
edge& crossingEdge,
edge crossedEdge,
bool topDown);
/**
* @name Combinatorial Embeddings
*/
//@{
//! Creates a new edge with original edge \a eOrig in an embedding \a E.
/**
* Let \a w be the node whose adjacency list contains \a adjTgt. The original
* edge \a eOrig must connect the original nodes of \a v and \a w. If \a eOrig =
* (original(\a v),original(\a w)), then the created edge is (\a v,\a w), otherwise
* it is (\a w,\a v). The new edge \a e must split a face in \a E, such that \a e
* comes after \a adj in the adjacency list of \a v and at the end of the adjacency
* list of \a v.
*
* @param v is a node in the graph copy.
* @param adj is an adjacency entry in the graph copy.
* @param eOrig is an edge in the original graph.
* @param E is an embedding of the graph copy.
* @return the created edge.
*/
edge newEdge(node v, adjEntry adj, edge eOrig, CombinatorialEmbedding &E);
/**
* \brief Sets the embedding of the graph copy to the embedding of the original graph.
* \pre The graph copy has not been changed after construction, i.e., no new nodes
* or edges have been added and no edges have been split.
*/
void setOriginalEmbedding();
//! Re-inserts edge \a eOrig by "crossing" the edges in \a crossedEdges in embedding \a E.
/**
* Let \a v and \a w be the copies of the source and target nodes of \a eOrig,
* and let \f$e_0,e_1,\ldots,e_k,e_{k+1}\f$ be the sequence of edges corresponding
* to the adjacency entries in \a crossedEdges. The first edge needs to be incident
* to \a v and the last to \a w; the edges \f$e_1,\ldots,e_k\f$ are each split
* creating a sequence \f$u_1,\ldots,u_k\f$ of new nodes, and additional edges
* are inserted creating a path \f$v,u_1,\ldots,u_k,w\f$.
*
* The following figure illustrates, which adjacency entries need to be in the list
* \a crossedEdges. It inserts an edge connecting \a v and \a w by passing through
* the faces \f$f_0,f_1,f_2\f$; in this case, the list \a crossedEdges must contain
* the adjacency entries \f$adj_0,\ldots,adj_3\f$ (in this order).
* \image html insertEdgePathEmbedded.png
*
* @param eOrig is an edge in the original graph and becomes the original edge of
* all edges in the path \f$v,u_1,\ldots,u_k,w\f$.
* @param E is an embedding of the graph copy.
* @param crossedEdges are a list of adjacency entries in the graph copy.
*/
void insertEdgePathEmbedded(
edge eOrig,
CombinatorialEmbedding &E,
const SList &crossedEdges);
/**
* Removes the complete edge path for edge \a eOrig while preserving the embedding.
* @param E is an embedding of the graph copy.
* @param eOrig is an edge in the original graph.
* @param newFaces is assigned the set of new faces resulting from joining faces
* when removing edges.
*/
void removeEdgePathEmbedded(
CombinatorialEmbedding &E,
edge eOrig,
FaceSetPure &newFaces);
//@}
/**
* @name Miscellaneous
*/
//@{
//! Checks the consistency of the data structure (for debugging only).
bool consistencyCheck() const;
//! Associates the graph copy with \a 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 \a G using this method, and then is initialized
* using either initByNodes() or initByActiveNodes().
*
* The following code snippet shows a typical application of this functionality:
* \code
* GraphCopy GC;
* GC.createEmpty(G);
*
* // compute connected components of G
* NodeArray component(G);
* int numCC = connectedComponents(G,component);
*
* // intialize the array of lists of nodes contained in a CC
* Array > nodesInCC(numCC);
*
* node v;
* forall_nodes(v,G)
* nodesInCC[component[v]].pushBack(v);
*
* EdgeArray auxCopy(G);
* Array boundingBox(numCC);
*
* for(int i = 0; i < numCC; ++i) {
* GC.initByNodes(nodesInCC[i],auxCopy);
* ...
* }
* \endcode
* @param G is the graph of which this graph copy shall be a copy.
*/
void createEmpty(const Graph &G);
//! Initializes the graph copy for the nodes in a component.
/**
* Creates copies of all nodes in \a nodes and their incident edges.
* Any nodes and edges allocated before are removed.
*
* The order of entries in the adjacency lists is preserved, i.e., if
* the original graph is embedded, its embedding induces the embedding
* of the created copy.
*
* It is important that \a 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().
* \see createEmpty() for an example.
* @param nodes is the list of nodes in the original graph for which
* copies are created in the graph copy.
* @param eCopy is assigned the copy of each original edge.
*/
void initByNodes(const List &nodes, EdgeArray &eCopy);
//! Initializes the graph copy for the nodes in \a nodes.
/**
* Creates copies of all nodes in \a nodes and edges between two nodes
* which are both contained in \a nodes.
* Any nodes and edges allocated before are destroyed.
*
* \see createEmpty()
* @param nodes is the list of nodes in the original graph for which
* copies are created in the graph copy.
* @param activeNodes must be true for every node in \a nodes, false
* otherwise.
* @param eCopy is assigned the copy of each original edge.
*/
void initByActiveNodes(const List &nodes,
const NodeArray &activeNodes, EdgeArray &eCopy);
//@}
/**
* @name Operators
*/
//@{
//! Assignment operator.
/**
* Creates a graph copy that is a copy of \a GC and represents a graph
* copy of the original graph of \a GC.
*
* The constructor assures that the adjacency lists of nodes in the
* constructed graph are in the same order as the adjacency lists in \a G.
* This is in particular important when dealing with embedded graphs.
*/
GraphCopy &operator=(const GraphCopy &GC);
//@}
private:
void initGC(const GraphCopy &GC,
NodeArray &vCopy, EdgeArray &eCopy);
}; // class GraphCopy
} // end namespace ogdf
#endif