/*
 * $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)<br>
 * 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 <b>does not</b> 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<node> m_vOrig; //!< The corresponding node in the original graph.
	NodeArray<node> m_vCopy; //!< The corresponding node in the graph copy.
	EdgeArray<edge> m_eOrig; //!< The corresponding edge in the original graph.
	EdgeArray<edge> 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<node> &vCopy,
		EdgeArray<edge> &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.
 *
 * <h3>Do's and Dont's</h3>
 * 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 <b>not supported</b> 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<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.

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<edge> &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<adjEntry> &crossedEdges);

	//for FixedEmbeddingUpwardEdgeInserter only
	void insertEdgePath(node srcOrig, node tgtOrig, const SList<adjEntry> &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<adjEntry> &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<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);
	 *     ...
	 *   }
	 * \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<node> &nodes, EdgeArray<edge> &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<node> &nodes,
		const NodeArray<bool> &activeNodes, EdgeArray<edge> &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<node> &vCopy, EdgeArray<edge> &eCopy);

}; // class GraphCopy


} // end namespace ogdf

#endif