Open
Graph Drawing
Framework

 v.2010.10
 

PlanRepExpansion.h

Go to the documentation of this file.
00001 /*
00002  * $Revision: 2027 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
00007  ***************************************************************/
00008  
00054 #ifdef _MSC_VER
00055 #pragma once
00056 #endif
00057 
00058 #ifndef OGDF_PLAN_REP_EXPANSION_H
00059 #define OGDF_PLAN_REP_EXPANSION_H
00060 
00061 
00062 #include <ogdf/basic/Graph.h>
00063 #include <ogdf/basic/tuples.h>
00064 #include <ogdf/basic/SList.h>
00065 
00066 
00067 namespace ogdf {
00068 
00069 
00070 class OGDF_EXPORT CombinatorialEmbedding;
00071 class OGDF_EXPORT FaceSetPure;
00072 class OGDF_EXPORT NodeSetPure;
00073 
00074 
00081 class OGDF_EXPORT PlanRepExpansion : public Graph
00082 {
00083 public:
00084     struct Crossing {
00085         Crossing() { m_adj = 0; }
00086         Crossing(adjEntry adj) { m_adj = adj; }
00087 
00088         adjEntry m_adj;
00089         SList<adjEntry> m_partitionLeft;
00090         SList<adjEntry> m_partitionRight;
00091 
00092         friend ostream &operator<<(ostream &os, const Crossing &c) {
00093             os << "(" << c.m_adj << ")";
00094             return os;
00095         }
00096     };
00097 
00098 
00105     class NodeSplit
00106     {
00107     public:
00111         NodeSplit() { }
00112 
00116         NodeSplit(ListIterator<NodeSplit> it) : m_nsIterator(it) { }
00117 
00121         node source() const { return m_path.front()->source(); }
00122 
00126         node target() const { return m_path.back ()->target(); }
00127 
00128         List<edge> m_path; 
00129         ListIterator<NodeSplit> m_nsIterator; 
00130     };
00131 
00133     typedef PlanRepExpansion::NodeSplit *nodeSplit;
00134 
00135 
00141     PlanRepExpansion(const Graph& G);
00142 
00150     PlanRepExpansion(const Graph& G, const List<node> &splittableNodes);
00151 
00152     ~PlanRepExpansion() {}
00153 
00154 
00159 
00161     const Graph &original() const { return *m_pGraph; }
00162 
00164     node original(node v) const { return m_vOrig[v]; }
00165 
00167     const List<node> &expansion(node vOrig) const { return m_vCopy[vOrig]; }
00168 
00170     node copy(node vOrig) const { return m_vCopy[vOrig].front(); }
00171 
00173     edge originalEdge(edge e) const { return m_eOrig[e]; }
00174 
00176     const List<edge> &chain(edge eOrig) const { return m_eCopy[eOrig]; }
00177 
00179     edge copy(edge eOrig) const { return m_eCopy[eOrig].front(); }
00180 
00182     bool splittable(node v) const { return m_splittable[v]; }
00183 
00185     bool splittableOrig(node vOrig) const { return m_splittableOrig[vOrig]; }
00186 
00188     NodeSplit *nodeSplitOf(edge e) const { return m_eNodeSplit[e]; }
00189 
00191     int numberOfNodeSplits() const { return m_nodeSplits.size(); }
00192     int numberOfSplittedNodes() const;
00193 
00195     List<NodeSplit> &nodeSplits() { return m_nodeSplits; }
00196 
00206     List<edge> &setOrigs(edge e, edge &eOrig, nodeSplit &ns);
00207 
00208     ListConstIterator<edge> position(edge e) const { return m_eIterator[e]; }
00209 
00210     bool isPseudoCrossing(node v) const;
00211 
00213     int computeNumberOfCrossings() const;
00214 
00216 
00220 
00221 
00225     int numberOfCCs() const {
00226         return m_nodesInCC.size();
00227     }
00228 
00232     int currentCC() const {
00233         return m_currentCC;
00234     }
00235 
00241     const List<node> &nodesInCC(int i) const {
00242         return m_nodesInCC[i];
00243     }
00244 
00248     const List<node> &nodesInCC() const {
00249         return m_nodesInCC[m_currentCC];
00250     }
00251 
00260     void initCC(int i);
00261 
00262 
00264 
00268 
00269     edge split(edge e);
00270 
00271     void unsplit(edge eIn, edge eOut);
00272 
00274     void delCopy(edge e);
00275 
00277     bool embed();
00278 
00279     void insertEdgePath(
00280         edge eOrig,
00281         nodeSplit ns,
00282         node vStart,
00283         node vEnd,
00284         List<Crossing> &eip,
00285         edge eSrc,
00286         edge eTgt);
00287 
00300     void insertEdgePathEmbedded(
00301         edge eOrig,
00302         nodeSplit ns,
00303         CombinatorialEmbedding &E,
00304         const List<Tuple2<adjEntry,adjEntry> > &crossedEdges);
00305 
00319     void removeEdgePathEmbedded(
00320         CombinatorialEmbedding &E,
00321         edge eOrig,
00322         nodeSplit ns,
00323         FaceSetPure &newFaces,
00324         NodeSetPure &mergedNodes,
00325         node &oldSrc,
00326         node &oldTgt);
00327 
00337     void removeEdgePath(
00338         edge eOrig,
00339         nodeSplit ns,
00340         node &oldSrc,
00341         node &oldTgt);
00342 
00351     void contractSplit(nodeSplit ns, CombinatorialEmbedding &E);
00352 
00360     void contractSplit(nodeSplit ns);
00361 
00372     edge unsplitExpandNode(
00373         node u,
00374         edge eContract,
00375         edge eExpand,
00376         CombinatorialEmbedding &E);
00377 
00387     edge unsplitExpandNode(
00388         node u,
00389         edge eContract,
00390         edge eExpand);
00391 
00403     edge enlargeSplit(node v, edge e, CombinatorialEmbedding &E);
00404 
00415     edge enlargeSplit(node v, edge e);
00416 
00426     edge splitNodeSplit(edge e, CombinatorialEmbedding &E);
00427 
00436     edge splitNodeSplit(edge e);
00437 
00446     void removeSelfLoop(edge e, CombinatorialEmbedding &E);
00447 
00448     void removeSelfLoop(edge e);
00449 
00461     PlanRepExpansion::nodeSplit convertDummy(
00462         node u,
00463         node vOrig,
00464         PlanRepExpansion::nodeSplit ns);
00465 
00466     edge separateDummy(
00467         adjEntry adj_1,
00468         adjEntry adj_2, 
00469         node vStraight, 
00470         bool isSrc);
00471 
00472     void resolvePseudoCrossing(node v);
00473 
00475 
00479 
00483     bool consistencyCheck() const;
00484 
00486 
00487 private:
00488     void doInit(const Graph &G, const List<node> &splittableNodes);
00489     void prepareNodeSplit(
00490         const SList<adjEntry> &partitionLeft,
00491         adjEntry &adjLeft,
00492         adjEntry &adjRight);
00493 
00494     const Graph *m_pGraph;                      
00495     NodeArray<node> m_vOrig;                    
00496     EdgeArray<edge> m_eOrig;                    
00497     EdgeArray<ListIterator<edge> > m_eIterator; 
00498     EdgeArray<List<edge> > m_eCopy;             
00499     NodeArray<ListIterator<node> > m_vIterator; 
00500     NodeArray<List<node> > m_vCopy;             
00501 
00502     NodeArray<bool> m_splittable;
00503     NodeArray<bool> m_splittableOrig;
00504     EdgeArray<NodeSplit *> m_eNodeSplit;
00505     List<NodeSplit> m_nodeSplits;
00506 
00507     int m_currentCC; 
00508     int m_numCC;     
00509 
00510     Array<List<node> >  m_nodesInCC; 
00511     EdgeArray<edge>     m_eAuxCopy; // auxiliary
00512 };
00513 
00514 
00515 } // end namespace ogdf
00516 
00517 
00518 #endif