ext/OGDF/ogdf/labeling/EdgeLabel.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 EdgeLabelPositioner classes used in EdgeLabel placement.
  11  *
  12  * \author Karsten Klein
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #ifdef _MSC_VER
  44 #pragma once
  45 #endif
  46
  47 #ifndef OGDF_EDGE_LABEL_H
  48 #define OGDF_EDGE_LABEL_H
  49
  50
  51 #include <ogdf/basic/geometry.h>
  52 #include <ogdf/basic/List.h>
  53 #include <ogdf/basic/BinaryHeap2.h>
  54 #include <ogdf/basic/Graph.h>
  55 #include <ogdf/basic/GraphCopy.h>
  56 #include <ogdf/planarity/PlanRepUML.h>
  57 #include <ogdf/basic/GridLayoutMapped.h>
  58 #include <ogdf/orthogonal/OrthoRep.h>
  59
  60 #include <ogdf/labeling/ELabelInterface.h>
  61
  62
  63 //debug
  64 //#define foutput
  65
  66 namespace ogdf {
  67
  68 //*******************************************************
  69 //all label types are declared in ELabelInterface
  70
  71 //every edge has a number of labels associated with it
  72 //current status:
  73
  74 //two end labels
  75 //two end multiplicities
  76 //a name
  77
  78 //each label has two coordinates and its input size
  79 //*******************************************************
  80
  81
  82 //*******************************************************
  83 //there are some discrete phases:
  84 // *compute(UML)Candidates:
  85 //  assign candidate positions to all input labels
  86 // *test(UML)FeatureIntersect:
  87 //      test intersection of graph features by position candidates
  88 //      currently, only nodes are considered
  89 // *test(UML)AllIntersect:
  90 //  test label position intersection against each other
  91 //  and save the resulting information
  92 // *Assignment of "good" candidates
  93 //  different heuristics can be applied
  94 //*******************************************************
  95
  96
  97 //parameter values for write(UML)GML - output function
  98 enum OutputParameter {opStandard, opOmitIntersect, opOmitFIntersect, opResult};
  99
 100 //the candidate status values have the following meaning
 101 //csActive: candidate can be assigned
 102 //csAssigned: another candidate was assigned for that label
 103 //csFIntersect: label would intersect Graph node
 104 //csUsed: this candidate was used for the label
 105
 106 //csActive and csUsed are both counted as active candidates
 107 //in PosInfo structure, cause they can have influence on the number
 108 //of necessary intersections
 109 enum candStatus {csAssigned, csFIntersect, csActive, csUsed};
 110
 111
 112
 113 //class ELabelPos is responsible for computation of edge label positions
 114
 115 //this should NOT be a template class
 116 //UG call is for double only, PRU call for int, PRU call maybe be considered obsolete
 117 //and is no longer maintained (but works)
 118 template <class coordType>
 119 class ELabelPos {
 120
 121 public:
 122         //construction and destruction
 123         ELabelPos();
 124
 125         ~ELabelPos() {}
 126
 127         //we can call the positioner on a given PlanRepUML (grid)drawing or
 128         //just with given (double)positions for all graph features and label sizes
 129         virtual void call(PlanRepUML& pru, GridLayoutMapped& L, ELabelInterface<coordType>& eli); //int
 130
 131         virtual void call(GraphAttributes& ug, ELabelInterface<coordType>& eli); //double
 132
 133         //set the edge-label distance
 134         void setDefaultDistance(coordType dist) { m_defaultDistance = dist; }
 135
 136         void setDistance(edge e, eLabelType elt, coordType dist) { (m_distance[elt])[e] = dist; }
 137
 138         //switch if all label types should be distributed evenly on the edge length
 139         void setEndLabelPlacement(bool b) { m_endLabelPlacement = b; }
 140
 141         void writeGML(const char *filename="labelgraph.gml", OutputParameter sectOmit = opStandard);
 142         void writeUMLGML(const char *filename="labelgraphUML.gml", OutputParameter sectOmit = opStandard);
 143
 144 protected:
 145
 146         //**********************************************************
 147         //needed structures
 148
 149         struct SegmentInfo {
 150                 //SegmentInfo() {length = 0; number = 0; direction = odNorth;}
 151
 152                 coordType length;
 153                 int number;
 154                 coordType min_x, max_x, min_y, max_y;
 155                 OrthoDir direction;
 156         };//Segmentinfo
 157
 158
 159         struct FeatureInfo {
 160                 coordType min_x, max_x, min_y, max_y, size_x, size_y;
 161         };//FeatureInfo
 162
 163         //Candidate positions have the following properties:
 164         //*active/passive (if intersection)
 165         //*pointer list, pointers to all intersecting candidates
 166         //*Number of intersections with status active (=> if number == 0, this
 167         //candidate can be assigned,fuer andere Kandidaten deren Ueberlappungspartner --Anzahl
 168         //sowie die aktiven Ueberlappungen vorlaeufig sperren
 169         struct PosInfo {
 170                 GenericPoint<coordType> m_coord; //position of middle
 171                 List< PosInfo* >  m_intersect;
 172                 int m_numActive; //active label intersections
 173                 int m_numFeatures; //number of intersected features
 174                 int m_posIndex; //holds the relative position of candidates
 175
 176                 edge m_edge;
 177                 eLabelType m_typ;
 178                 candStatus m_active; //csAssigned assigned, csFIntersect  node, csActive
 179
 180                 double m_cost; //costs for intersections, placement
 181
 182                 PosInfo() {m_edge = 0; m_active = csActive; m_posIndex = 0; m_numActive = 0;
 183                 m_typ = elName;
 184                 m_cost = 0.0;
 185                 }
 186                 PosInfo(edge e, eLabelType elt, GenericPoint<coordType> gp, int posIndex = -1)
 187                 {
 188                         m_edge = e;
 189                         m_typ = elt;
 190                         m_coord = gp;
 191                         m_numActive = 0;
 192                         m_numFeatures = 0;
 193                         m_posIndex = posIndex;
 194                         m_active = csActive;
 195                         m_cost = 0.0;
 196                 }
 197                 PosInfo(edge e, eLabelType elt)
 198                 {
 199                         m_edge = e;
 200                         m_typ = elt;
 201                         m_numActive = 0;
 202                         m_numFeatures = 0;
 203                         m_posIndex = 0;
 204                         m_active = csActive;
 205                         m_cost = 0.0;
 206                 }
 207
 208                 bool active() {return (m_active == csActive) || (m_active == csUsed);}
 209                 //deactivate candidate
 210                 void deactivate() {}
 211
 212         };//PosInfo
 213
 214
 215         //used for sorting and intersection graph buildup
 216         struct FeatureLink {
 217                 FeatureInfo m_fi;
 218                 edge m_edge;
 219                 eLabelType m_elt;
 220                 int m_index; //index of label position entry in list
 221                 node m_node; //representant in intersection graph
 222                 PosInfo* m_posInfo;
 223
 224                 FeatureLink() {m_edge = 0; m_elt = (eLabelType)0; m_index = 0; m_node = 0; m_posInfo = 0;}
 225                 FeatureLink(edge e, eLabelType elt, node v, FeatureInfo& fi, int index)
 226                 {
 227                         m_edge = e;
 228                         m_elt = elt;
 229                         m_node = v;
 230                         m_fi = fi;
 231                         m_index = index;
 232                         m_posInfo = 0;
 233                 }
 234                 FeatureLink(edge e, eLabelType elt, node v, FeatureInfo& fi, int index, PosInfo& pi)
 235                 {
 236                         m_edge = e;
 237                         m_elt = elt;
 238                         m_node = v;
 239                         m_fi = fi;
 240                         m_index = index;
 241                         m_posInfo = &pi;
 242                 }
 243         };//FeatureLink
 244
 245         struct LabelInfo {
 246                 edge m_e;
 247                 int m_labelTyp;
 248
 249                 int m_index; //index in der PosListe
 250
 251                 LabelInfo() {m_e = 0; m_labelTyp = m_index = 0;}
 252                 LabelInfo(edge e, int l, int i) {m_e = e; m_labelTyp = l; m_index = i;}
 253         };//LabelInfo
 254
 255
 256         //**********************************************************
 257         //modification
 258
 259         //********
 260         //settings
 261         //cost for feature (node?) intersection
 262         double costFI()  {return m_posNum*5.0;}
 263         //cost for label intersection
 264         double costLI()  {return 0.9;}//2.0;}
 265         //cost for edge intersection
 266         double costEI()  {return 0.7;}
 267         //cost for distance from standard position,
 268         double costPos() {return 0.6;} //e.g. edge start for start label
 269         //cost for non-symmetry at start/end label pairs
 270         double costSym() {return 1.3;}
 271
 272         coordType segmentMargin() {return m_segMargin;} //defining the size of the rectangle
 273         //around a segment for intersection testing
 274
 275         bool usePosCost() {return m_posCost;}
 276         bool useSymCost() {return m_symCost;}
 277
 278         //**********************************************************
 279         //main parts of the algorithm
 280         //check edges for segment structure
 281         void initSegments();
 282         void initUMLSegments();
 283
 284         //build rectangle structures for all graph features
 285         void initFeatureRectangles();
 286         void initUMLFeatureRectangles();
 287
 288         //computes the candidate positions, fills the lists
 289         void computeCandidates();
 290         void computeUMLCandidates();
 291
 292         //build up data structure to decide feasible solutions
 293         //only needed if labeltree not already build
 294         void initStructure();
 295
 296         //check label candidates for feature intersection, delete from list
 297         void testFeatureIntersect();
 298         void testUMLFeatureIntersect();
 299
 300         //assign special candidate to avoid empty list after featuretest
 301         void saveRecovery(EdgeArray< GenericPoint<coordType> > (&saveCandidate)[elNumLabels]);
 302         void saveUMLRecovery(EdgeArray< GenericPoint<coordType> > (&saveCandidate)[elNumLabels]);
 303
 304         //check label candidates for label intersection
 305         void testAllIntersect();
 306         void testUMLAllIntersect();
 307
 308
 309         //return the list of all label position candidates (PlanRepUML)
 310         List< GenericPoint<coordType> >& posList(edge e, int lnum) {return (m_candPosList[lnum])[e];}
 311         //return the list of all label position candidates
 312         List< PosInfo >& candList(edge e, int lnum) {return (m_candList[lnum])[e];}
 313
 314
 315         //****************************
 316         //information about the segments
 317         //return number of segments for original edge e
 318         int segNumber(edge e) {return m_poly[e].size() - 1;}
 319         //return direction (?ver/hor?) of edge segments, dynamic version
 320         //of SegInfo.dir
 321         OrthoDir segDir(edge e, int segNum)
 322         {
 323                 OrthoDir od;
 324                 if (segNum > segNumber(e)) OGDF_THROW(Exception);
 325
 326                 IPoint ip1 = (*m_poly[e].get(segNum - 1));
 327                 IPoint ip2 = (*m_poly[e].get(segNum));
 328                 bool isHor = (ip1.m_y == ip2.m_y); //may still be same place
 329                 if (isHor)
 330                 {
 331                         if (ip1.m_x > ip2.m_x) od = odWest;
 332                         else od = odEast;
 333                 }//if isHor
 334                 else
 335                 {
 336                         //check m_x == m_x
 337                         if (ip1.m_y < ip2.m_y) od = odNorth;
 338                         else od = odSouth;
 339                 }//else
 340
 341                 return od;
 342         }//segDir
 343
 344
 345 private:
 346
 347         //settings
 348         int m_numAssignment; //number of necessary assignments
 349
 350         int m_candStyle; //defines the style how pos cands are computed
 351         int m_placeHeuristic; //defines how candidates are chosen
 352         bool m_endInsertion; //should candidates nearest to endnode be chosen
 353
 354         bool m_endLabelPlacement; //are endlabels candidates computed near the nodes
 355
 356         bool m_posCost; //should end label distance to end give a cost for candidates
 357         bool m_symCost; //should non-symmetric assignment for end label pairs -"-
 358
 359         //number of candidates for every label
 360         //end pos. candidates get double the number , cause a position
 361         //on both sides of the edge is possible for these values
 362         int m_posNum; //number of pos. cand. for candstyle 1, like ppinch
 363
 364         //only internally used option: dont stop after first feature intersection,
 365         //allows weighting over number of feature intersections
 366         bool m_countFeatureIntersect;
 367
 368         coordType m_segMargin;
 369
 370         //pointers to the PlanRepUML input instances
 371         PlanRepUML* m_prup;
 372         GridLayoutMapped* m_gl; //the existing drawing
 373
 374         //pointers to the AttributedGraph input instances
 375         GraphAttributes* m_ug;
 376
 377         //pointers to the generic input instances
 378         ELabelInterface<coordType>* m_eli;//the input/output interface
 379
 380         //maybe this should be a parameter, reference
 381         //forall label types the cand. pos.
 382         EdgeArray< List<GenericPoint<coordType> > > m_candPosList[elNumLabels];
 383         //wird ersetzt durch: Liste von PosInfos
 384         EdgeArray< List < PosInfo > > m_candList[elNumLabels];
 385         //structure holding all intersection free labels
 386         List< PosInfo* > m_freeLabels;
 387         //structure holding all intersecting labels (should be PQ)
 388         List< PosInfo* > m_sectLabels;
 389         //structure holding candidates sorted by associated costs
 390         BinaryHeap2<double, PosInfo*> m_candidateHeap;
 391
 392         //the bends and crossings, in the UML call use AttributedGraph::bends
 393         EdgeArray< List<GenericPoint<coordType> > > m_poly;
 394
 395         //list of segment info
 396         EdgeArray< List<SegmentInfo> > m_segInfo;
 397         EdgeArray<coordType> m_edgeLength;
 398
 399         //list of graph feature(nodes,...) info
 400         NodeArray<FeatureInfo> m_featureInfo; //on prup-original
 401
 402         //save the intersections
 403         EdgeArray< List< List<LabelInfo> > > m_intersect[elNumLabels];
 404
 405         EdgeArray<bool> m_assigned[elNumLabels]; //edges with already assigned labels?
 406
 407         //allow specific edge to label distance, there is a default value
 408         EdgeArray<coordType> m_distance[elNumLabels];
 409         coordType m_defaultDistance;
 410
 411         Graph m_intersectGraph;
 412
 413         void init(PlanRepUML& pru, GridLayoutMapped& L, ELabelInterface<coordType>& eli); //int
 414
 415         void initUML(GraphAttributes& ug, ELabelInterface<coordType>& eli); //double
 416
 417         //intersection test section
 418         //we have to sort the features and therefore define a special method
 419         class FeatureComparer;
 420         friend class FeatureComparer;
 421         class FeatureComparer
 422         {
 423         public:
 424                 //we sort from lower (bottom side) to upper and from left to right side
 425                 static int compare(const FeatureLink &f1, const FeatureLink &f2) {
 426                         coordType d1 = f1.m_fi.min_y;
 427                         coordType d2 = f2.m_fi.min_y;
 428
 429                         if (DIsLess(d1, d2)) return -1;
 430                         else if (DIsGreater(d1, d2)) return 1;
 431                         else
 432                         {
 433                                 if (DIsLess(f1.m_fi.min_x, f2.m_fi.min_x)) return -1;
 434                                 else if (DIsGreater(f1.m_fi.min_x, f2.m_fi.min_x)) return 1;
 435
 436                                 return 0;
 437                         }
 438                 }
 439                 OGDF_AUGMENT_STATICCOMPARER(FeatureLink)
 440         };
 441
 442
 443 };//ELabelPos
 444
 445 }//namespace
 446
 447 //#if defined(_MSC_VER) || defined(__BORLANDC__)
 448 #include <src/orthogonal/EdgeLabel-impl.h>
 449 //#endif
 450
 451 #endif