Open
Graph Drawing
Framework

 v.2012.05
 

PlanRepExpansion.h
Go to the documentation of this file.
00001 /*
00002  * $Revision: 2299 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
00007  ***************************************************************/
00008  
00044 #ifdef _MSC_VER
00045 #pragma once
00046 #endif
00047 
00048 #ifndef OGDF_PLAN_REP_EXPANSION_H
00049 #define OGDF_PLAN_REP_EXPANSION_H
00050 
00051 
00052 #include <ogdf/basic/Graph.h>
00053 #include <ogdf/basic/tuples.h>
00054 #include <ogdf/basic/SList.h>
00055 
00056 
00057 namespace ogdf {
00058 
00059 
00060 class OGDF_EXPORT CombinatorialEmbedding;
00061 class OGDF_EXPORT FaceSetPure;
00062 class OGDF_EXPORT NodeSetPure;
00063 
00064 
00071 class OGDF_EXPORT PlanRepExpansion : public Graph
00072 {
00073 public:
00074     struct Crossing {
00075         Crossing() { m_adj = 0; }
00076         Crossing(adjEntry adj) { m_adj = adj; }
00077 
00078         adjEntry m_adj;
00079         SList<adjEntry> m_partitionLeft;
00080         SList<adjEntry> m_partitionRight;
00081 
00082         friend ostream &operator<<(ostream &os, const Crossing &c) {
00083             os << "(" << c.m_adj << ")";
00084             return os;
00085         }
00086     };
00087 
00088 
00095     class NodeSplit
00096     {
00097     public:
00101         NodeSplit() { }
00102 
00106         NodeSplit(ListIterator<NodeSplit> it) : m_nsIterator(it) { }
00107 
00111         node source() const { return m_path.front()->source(); }
00112 
00116         node target() const { return m_path.back ()->target(); }
00117 
00118         List<edge> m_path; 
00119         ListIterator<NodeSplit> m_nsIterator; 
00120     };
00121 
00123     typedef PlanRepExpansion::NodeSplit *nodeSplit;
00124 
00125 
00131     PlanRepExpansion(const Graph& G);
00132 
00140     PlanRepExpansion(const Graph& G, const List<node> &splittableNodes);
00141 
00142     ~PlanRepExpansion() {}
00143 
00144 
00149 
00151     const Graph &original() const { return *m_pGraph; }
00152 
00154     node original(node v) const { return m_vOrig[v]; }
00155 
00157     const List<node> &expansion(node vOrig) const { return m_vCopy[vOrig]; }
00158 
00160     node copy(node vOrig) const { return m_vCopy[vOrig].front(); }
00161 
00163     edge originalEdge(edge e) const { return m_eOrig[e]; }
00164 
00166     const List<edge> &chain(edge eOrig) const { return m_eCopy[eOrig]; }
00167 
00169     edge copy(edge eOrig) const { return m_eCopy[eOrig].front(); }
00170 
00172     bool splittable(node v) const { return m_splittable[v]; }
00173 
00175     bool splittableOrig(node vOrig) const { return m_splittableOrig[vOrig]; }
00176 
00178     NodeSplit *nodeSplitOf(edge e) const { return m_eNodeSplit[e]; }
00179 
00181     int numberOfNodeSplits() const { return m_nodeSplits.size(); }
00182     int numberOfSplittedNodes() const;
00183 
00185     List<NodeSplit> &nodeSplits() { return m_nodeSplits; }
00186 
00196     List<edge> &setOrigs(edge e, edge &eOrig, nodeSplit &ns);
00197 
00198     ListConstIterator<edge> position(edge e) const { return m_eIterator[e]; }
00199 
00200     bool isPseudoCrossing(node v) const;
00201 
00203     int computeNumberOfCrossings() const;
00204 
00206 
00210 
00211 
00215     int numberOfCCs() const {
00216         return m_nodesInCC.size();
00217     }
00218 
00222     int currentCC() const {
00223         return m_currentCC;
00224     }
00225 
00231     const List<node> &nodesInCC(int i) const {
00232         return m_nodesInCC[i];
00233     }
00234 
00238     const List<node> &nodesInCC() const {
00239         return m_nodesInCC[m_currentCC];
00240     }
00241 
00250     void initCC(int i);
00251 
00252 
00254 
00258 
00259     edge split(edge e);
00260 
00261     void unsplit(edge eIn, edge eOut);
00262 
00264     void delCopy(edge e);
00265 
00267     bool embed();
00268 
00269     void insertEdgePath(
00270         edge eOrig,
00271         nodeSplit ns,
00272         node vStart,
00273         node vEnd,
00274         List<Crossing> &eip,
00275         edge eSrc,
00276         edge eTgt);
00277 
00290     void insertEdgePathEmbedded(
00291         edge eOrig,
00292         nodeSplit ns,
00293         CombinatorialEmbedding &E,
00294         const List<Tuple2<adjEntry,adjEntry> > &crossedEdges);
00295 
00309     void removeEdgePathEmbedded(
00310         CombinatorialEmbedding &E,
00311         edge eOrig,
00312         nodeSplit ns,
00313         FaceSetPure &newFaces,
00314         NodeSetPure &mergedNodes,
00315         node &oldSrc,
00316         node &oldTgt);
00317 
00327     void removeEdgePath(
00328         edge eOrig,
00329         nodeSplit ns,
00330         node &oldSrc,
00331         node &oldTgt);
00332 
00341     void contractSplit(nodeSplit ns, CombinatorialEmbedding &E);
00342 
00350     void contractSplit(nodeSplit ns);
00351 
00362     edge unsplitExpandNode(
00363         node u,
00364         edge eContract,
00365         edge eExpand,
00366         CombinatorialEmbedding &E);
00367 
00377     edge unsplitExpandNode(
00378         node u,
00379         edge eContract,
00380         edge eExpand);
00381 
00393     edge enlargeSplit(node v, edge e, CombinatorialEmbedding &E);
00394 
00405     edge enlargeSplit(node v, edge e);
00406 
00416     edge splitNodeSplit(edge e, CombinatorialEmbedding &E);
00417 
00426     edge splitNodeSplit(edge e);
00427 
00436     void removeSelfLoop(edge e, CombinatorialEmbedding &E);
00437 
00438     void removeSelfLoop(edge e);
00439 
00451     PlanRepExpansion::nodeSplit convertDummy(
00452         node u,
00453         node vOrig,
00454         PlanRepExpansion::nodeSplit ns);
00455 
00456     edge separateDummy(
00457         adjEntry adj_1,
00458         adjEntry adj_2, 
00459         node vStraight, 
00460         bool isSrc);
00461 
00462     void resolvePseudoCrossing(node v);
00463 
00465 
00469 
00473     bool consistencyCheck() const;
00474 
00476 
00477 private:
00478     void doInit(const Graph &G, const List<node> &splittableNodes);
00479     void prepareNodeSplit(
00480         const SList<adjEntry> &partitionLeft,
00481         adjEntry &adjLeft,
00482         adjEntry &adjRight);
00483 
00484     const Graph *m_pGraph;                      
00485     NodeArray<node> m_vOrig;                    
00486     EdgeArray<edge> m_eOrig;                    
00487     EdgeArray<ListIterator<edge> > m_eIterator; 
00488     EdgeArray<List<edge> > m_eCopy;             
00489     NodeArray<ListIterator<node> > m_vIterator; 
00490     NodeArray<List<node> > m_vCopy;             
00491 
00492     NodeArray<bool> m_splittable;
00493     NodeArray<bool> m_splittableOrig;
00494     EdgeArray<NodeSplit *> m_eNodeSplit;
00495     List<NodeSplit> m_nodeSplits;
00496 
00497     int m_currentCC; 
00498     int m_numCC;     
00499 
00500     Array<List<node> >  m_nodesInCC; 
00501     EdgeArray<edge>     m_eAuxCopy; // auxiliary
00502 };
00503 
00504 
00505 } // end namespace ogdf
00506 
00507 
00508 #endif