ext/OGDF/ogdf/basic/TopologyModule.h

   1 /*
   2  * $Revision: 2564 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class TopologyModule.
  11  *
  12  * The TopologyModule transports the layout information from
  13  * GraphAttributes to PlanRep on that Graph, i.e., it computes a
  14  * combinatorial embedding for the input.
  15  *
  16  * \author Karsten Klein
  17  *
  18  * \par License:
  19  * This file is part of the Open Graph Drawing Framework (OGDF).
  20  *
  21  * \par
  22  * Copyright (C)<br>
  23  * See README.txt in the root directory of the OGDF installation for details.
  24  *
  25  * \par
  26  * This program is free software; you can redistribute it and/or
  27  * modify it under the terms of the GNU General Public License
  28  * Version 2 or 3 as published by the Free Software Foundation;
  29  * see the file LICENSE.txt included in the packaging of this file
  30  * for details.
  31  *
  32  * \par
  33  * This program is distributed in the hope that it will be useful,
  34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  36  * GNU General Public License for more details.
  37  *
  38  * \par
  39  * You should have received a copy of the GNU General Public
  40  * License along with this program; if not, write to the Free
  41  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  42  * Boston, MA 02110-1301, USA.
  43  *
  44  * \see  http://www.gnu.org/copyleft/gpl.html
  45  ***************************************************************/
  46
  47
  48 #ifdef _MSC_VER
  49 #pragma once
  50 #endif
  51
  52
  53 #ifndef OGDF_TOPOLOGYMODULE_H
  54 #define OGDF_TOPOLOGYMODULE_H
  55
  56
  57
  58 #include <ogdf/planarity/PlanRep.h>
  59 #include <ogdf/basic/GraphAttributes.h>
  60 #include <ogdf/basic/EdgeComparer.h>
  61
  62 namespace ogdf {
  63
  64 class EdgeLeg;
  65
  66 //===============================================
  67 //main function(s):
  68 //              setEmbeddingFromGraph(PlanRep&, GraphAttributes&)
  69 //          assumes that PG(AG) without bend nodes in PG
  70 //
  71 //              sortEdgesFromLayout(GraphAttributes &AG)
  72 //      sort the edges in AG, no crossing insertion
  73 //===============================================
  74
  75 class OGDF_EXPORT TopologyModule
  76 {
  77 public:
  78         TopologyModule() : m_options(opDegOneCrossings | opGenToAss |
  79                 opCrossFlip | opLoop | opFlipUML) {}
  80         virtual ~TopologyModule() {}
  81
  82         //the (pre/post)processing options
  83         //opCrossFlip increases running time by const*n,
  84         //opLoop increases running time by const*m
  85         enum Options {
  86                 opDegOneCrossings = 0x0001, //should degree one node's edge be crossed
  87                 opGenToAss        = 0x0002, //should generalizations be turned into associations
  88                 opCrossFlip       = 0x0004, //if there is a crossing (first ~) between two edges with
  89                                                                         //same start or end point, should there position
  90                                                                         //at the node be flipped and the crossing be skipped?
  91                                                                         //(postprocessing)
  92                 opFlipUML         = 0x0010, //only flip if same edge type
  93                 opLoop            = 0x0008  //should loops between crossings (consecutive on both
  94                                                                         //crossing edges) be deleted (we dont check for enclosed
  95                                                                         //CC's. Therefore it is safe to remove the crossing
  96         };
  97
  98         void setOptions(int i) {m_options = i;}
  99         void addOption(TopologyModule::Options o)  {m_options = (m_options | o);}
 100         //use AG layout to determine an embedding for PG.
 101         //non-constness of AG in the following methods is only
 102         //used when resolving problems, e.g. setting edge types
 103         //if two generalizations cross in the input layout
 104
 105         //Parameter setExternal: run over faces to compute external face
 106         //Parameter reuseAGEmbedding: If true, the call only
 107         //checks for a correct embedding of PG and tries to insert
 108         //crossings detected in the given layout otherwise.
 109         //this allows to assign already sorted UMLGraphs
 110         //NOTE: if the sorting of the edges does not correspond
 111         //to the layout given in AG, this cannot work correctly
 112         //returns false if planarization fails
 113         bool setEmbeddingFromGraph(
 114                 PlanRep &PG,
 115                 GraphAttributes &AG,
 116                 adjEntry &adjExternal,
 117                 bool setExternal = true,
 118                 bool reuseAGEmbedding = false);
 119
 120         //sorts the edges around all nodes of AG corresponding to the
 121         //layout given in AG
 122         //there is no check of the embedding afterwards because this
 123         //method could be used as a first step of a planarization
 124         void sortEdgesFromLayout(Graph &G, GraphAttributes &AG);
 125
 126         face getExternalFace(PlanRep &PG, const GraphAttributes &AG);
 127
 128         double faceSum(PlanRep &PG, const GraphAttributes &AG, face f);
 129
 130 protected:
 131         //compute a planarization, i.e. insert crossing vertices,
 132         //corresponding to the AG layout
 133         void planarizeFromLayout(PlanRep &PG,
 134                                                          GraphAttributes &AG);
 135         //compute crossing point and return if existing
 136         bool hasCrossing(EdgeLeg* legA, EdgeLeg* legB, DPoint& xp);
 137         //check if node v is a crossing of two edges with a common
 138         //endpoint adjacent to v, crossing is removed if flip is set
 139         bool checkFlipCrossing(PlanRep &PG,node v, bool flip = true);
 140
 141         void postProcess(PlanRep &PG);
 142         void handleImprecision(PlanRep &PG);
 143         bool skipable(EdgeLeg* legA, EdgeLeg* legB);
 144
 145 private:
 146         //compare vectors for sorting
 147         int compare_vectors(const double& x1, const double& y1,
 148                                                 const double& x2, const double& y2);
 149         //compute and return the angle defined by p-q,p-r
 150         double angle(DPoint p, DPoint q, DPoint r);
 151         //we have to save the position of the inserted crossing vertices
 152         //in order to compute the external face
 153         NodeArray<DPoint> m_crossPosition;
 154
 155         //we save a list of EdgeLegs for all original edges in
 156         //AG
 157         EdgeArray< List<EdgeLeg*> > m_eLegs;
 158
 159
 160         //option settings as bits
 161         int m_options;
 162
 163 };//TopologyModule
 164
 165
 166 //sorts EdgeLegs according to their xp distance to a reference point
 167 class PointComparer {
 168 public:
 169         PointComparer(DPoint refPoint) : m_refPoint(refPoint) {}
 170         //compares the crossing points stored in the EdgeLeg
 171         int compare(const ListIterator<EdgeLeg*> &ep1,
 172                 const ListIterator<EdgeLeg*> &ep2) const;
 173         OGDF_AUGMENT_COMPARER(ListIterator<EdgeLeg*>)
 174
 175         // undefined methods to avoid automatic creation
 176         PointComparer &operator=(const PointComparer &);
 177
 178 private:
 179         const DPoint m_refPoint;
 180 };//PointComparer
 181
 182 //helper class for the computation of crossings
 183 //represents a part of the edge between two consecutive
 184 //bends (in the layout, there are no bends allowed in
 185 //the representation) or crossings
 186 //there can be multiple EdgeLegs associated to one copy
 187 //edge in the PlanRep because of bends
 188 class EdgeLeg
 189 {
 190 public:
 191         EdgeLeg() : m_topDown(false)
 192                 {m_copyEdge = 0; m_xp = DPoint(0.0, 0.0);}
 193         EdgeLeg(edge e, int number, DPoint p1, DPoint p2) :
 194                 m_xp(DPoint(0.0,0.0)), m_topDown(false),
 195                 m_copyEdge(e), m_p1(p1), m_p2(p2), m_number(number)
 196                 {}
 197
 198         DPoint& start() {return m_p1;}
 199         DPoint& end()   {return m_p2;}
 200         int& number()    {return m_number;}
 201         edge& copyEdge() { return m_copyEdge;}
 202
 203         //to avoid sorting both edgelegs and crossing points,
 204         //do not store a pair of them, but allow the xp to be
 205         //stored in the edgeleg
 206         DPoint m_xp;
 207         //we store the direction of the crossed EdgeLeg, too
 208         //if crossingEdgeLeg is horizontally left to right
 209         bool m_topDown;
 210
 211         //each edgeLeg holds an entry with a ListIterator pointing to
 212         //its entry in a <edgeLeg*> List for an original edge
 213         ListIterator< EdgeLeg* > m_eIterator;
 214
 215 private:
 216         edge m_copyEdge; //the edge in the PlanRep copy corresponding to the EdgeLeg
 217         DPoint m_p1, m_p2;  //"Starting" and "End" point of the EdgeLeg
 218         int    m_number;    //the order nuumber on the edge, starting at 0
 219
 220 };//edgeleg
 221
 222
 223 /*
 224 EdgeArray<ListIterator<edge> > m_eIterator; // position of copy edge in chain
 225
 226         NodeArray<node> m_vCopy; // corresponding node in graph copy
 227         EdgeArray<List<edge> > m_eCopy; // corresponding chain of edges in graph copy
 228
 229 */
 230 } // end namespace ogdf
 231
 232 #endif