ext/OGDF/ogdf/orthogonal/EdgeRouter.h

   1 /*
   2  * $Revision: 2573 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-10 18:48:33 +0200 (Di, 10. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of EdgeRouter...
  11  *
  12  * ... which places node boxes in replacement areas of an orthogonal
  13  * drawing step and routes edges to minimize bends.
  14  *
  15  * \author Karsten Klein
  16  *
  17  * \par License:
  18  * This file is part of the Open Graph Drawing Framework (OGDF).
  19  *
  20  * \par
  21  * Copyright (C)<br>
  22  * See README.txt in the root directory of the OGDF installation for details.
  23  *
  24  * \par
  25  * This program is free software; you can redistribute it and/or
  26  * modify it under the terms of the GNU General Public License
  27  * Version 2 or 3 as published by the Free Software Foundation;
  28  * see the file LICENSE.txt included in the packaging of this file
  29  * for details.
  30  *
  31  * \par
  32  * This program is distributed in the hope that it will be useful,
  33  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35  * GNU General Public License for more details.
  36  *
  37  * \par
  38  * You should have received a copy of the GNU General Public
  39  * License along with this program; if not, write to the Free
  40  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  41  * Boston, MA 02110-1301, USA.
  42  *
  43  * \see  http://www.gnu.org/copyleft/gpl.html
  44  ***************************************************************/
  45
  46 #ifdef _MSC_VER
  47 #pragma once
  48 #endif
  49
  50 #ifndef OGDF_EDGE_ROUTER_H
  51 #define OGDF_EDGE_ROUTER_H
  52
  53
  54
  55 #include <ogdf/internal/orthogonal/RoutingChannel.h>
  56 #include <ogdf/orthogonal/MinimumEdgeDistances.h>
  57 #include <ogdf/orthogonal/OrthoLayout.h>
  58 #include <ogdf/basic/Layout.h>
  59 #include <ogdf/basic/GridLayout.h>
  60 #include <ogdf/basic/GridLayoutMapped.h>
  61 #include <ogdf/planarity/PlanRep.h>
  62 #include <ogdf/orthogonal/OrthoRep.h>
  63 #include <ogdf/internal/orthogonal/NodeInfo.h>
  64
  65 namespace ogdf {
  66
  67 //! edge types, defined by necessary bends
  68 enum bend_type {
  69         bend_free,
  70         bend_1left,
  71         bend_1right,
  72         bend_2left,
  73         bend_2right, //results
  74         prob_bf,
  75         prob_b1l,
  76         prob_b1r,
  77         prob_b2l,
  78         prob_b2r
  79 }; //and preliminary
  80
  81
  82 // unprocessed, processed in degree1 preprocessing, used by degree1
  83 enum process_type {
  84         unprocessed,
  85         processed,
  86         used
  87 };
  88
  89
  90 /**
  91  * Places node boxes in replacement areas of orthogonal
  92  * drawing step and route edges to minimize bends
  93  */
  94 class OGDF_EXPORT EdgeRouter
  95 {
  96 public:
  97         //constructor
  98         EdgeRouter() { }
  99
 100         EdgeRouter(
 101                 PlanRep& pru,
 102                 OrthoRep& H,
 103                 GridLayoutMapped& L,
 104                 CombinatorialEmbedding& E,
 105                 RoutingChannel<int>& rou,
 106                 MinimumEdgeDistances<int>& med,
 107                 NodeArray<int>& nodewidth,
 108                 NodeArray<int>& nodeheight);
 109
 110         virtual ~EdgeRouter() { }
 111
 112         void init(
 113                 PlanRep& pru,
 114                 RoutingChannel<int>& rou,
 115                 bool align = false);
 116
 117         //! sets the computed distances in structure MinimumEdgeDistance m_med
 118         void setDistances();
 119
 120         //! places nodes in cages and routes incident edges
 121         void call();
 122
 123         //! places nodes in cages and routes incident edges
 124         void call(
 125                 PlanRep& pru,
 126                 OrthoRep& H,
 127                 GridLayoutMapped& L,
 128                 CombinatorialEmbedding& E,
 129                 RoutingChannel<int>& rou,
 130                 MinimumEdgeDistances<int>& med,
 131                 NodeArray<int>& nodewidth,
 132                 NodeArray<int>& nodeheight,
 133                 bool align = false);
 134
 135         //! applies precomputed placement
 136         void place(node v/*, int l_sep, int l_overh*/);
 137
 138         //! computes placement
 139         void compute_place(node v, NodeInfo& inf/*, int sep = 10.0, int overh = 2*/);
 140
 141         //! computes routing after compute_place
 142         void compute_routing(node v);
 143
 144         //! compute glue points positions
 145         void compute_glue_points_y(node v);
 146
 147         //! compute glue points positions
 148         void compute_gen_glue_points_y(node v);
 149
 150         //! compute glue points positions
 151         void compute_glue_points_x(node& v);
 152
 153         //! compute glue points positions
 154         void compute_gen_glue_points_x(node v);
 155
 156         //! sets values derivable from input
 157         void initialize_node_info(node v, int sep);
 158
 159         // returns assigned connection point and glue point coordinates for each edge
 160         int cp_x(adjEntry ae) { return m_acp_x[ae]; } //!< connection point (cage border) coord of source
 161         int cp_y(adjEntry ae) { return m_acp_y[ae]; } //!< connection point (cage border) coord of source
 162         int gp_x(adjEntry ae) { return m_agp_x[ae]; } //!< glue point (node border)
 163         int gp_y(adjEntry ae) { return m_agp_y[ae]; } //!< glue point (node border)
 164
 165         bend_type abendType(adjEntry ae) { return m_abends[ae]; }
 166
 167         void addbends(BendString& bs, const char* s2);
 168
 169         edge addRightBend(edge e);
 170
 171         edge addLeftBend(edge e);
 172
 173         //! adjEntries for edges in inLists
 174         adjEntry outEntry(NodeInfo& inf, OrthoDir d, int pos) {
 175                 if (inf.is_in_edge(d, pos))
 176                         return (*inf.inList(d).get(pos))->adjTarget();
 177                 else
 178                         return (*inf.inList(d).get(pos))->adjSource();//we only bend on outentries
 179         }
 180
 181         //! adjEntries for edges in inLists
 182         adjEntry inEntry(NodeInfo& inf, OrthoDir d, int pos) {
 183                 if (inf.is_in_edge(d, pos))
 184                         return (*inf.inList(d).get(pos))->adjSource();
 185                 else
 186                         return (*inf.inList(d).get(pos))->adjTarget();
 187         }
 188
 189         //! sets position for node v in layout to value x,y, invoked to have central control over change
 190         void set_position(node v, int x = 0, int y = 0);
 191
 192         //! same as set but updates m_fixed, coordinates cant be changed afterwards
 193         void fix_position(node v, int x = 0, int y = 0);
 194
 195         //! for all multiple edges, set the delta value on both sides to minimum if not m_minDelta
 196         /**
 197         * postprocessing function, hmm maybe preprocessing
 198         */
 199         void multiDelta();
 200
 201         //! set alignment option: place nodes in cage at outgoing generalization
 202         /**
 203         * postprocessing function, hmm maybe preprocessing
 204         */
 205         void align(bool b) { m_align = b; }
 206
 207         //test fuer skalierende Kompaktierung
 208         //void setOrSep(int sep)
 209         //{m_hasOrSep = true; m_orSep = sep;}
 210
 211
 212 private:
 213         PlanRep* m_prup;
 214         GridLayoutMapped* m_layoutp;
 215         OrthoRep* m_orp;
 216         CombinatorialEmbedding* m_comb;
 217         RoutingChannel<int>* m_rc;
 218         MinimumEdgeDistances<int>* m_med;
 219         NodeArray<int>* m_nodewidth;
 220         NodeArray<int>* m_nodeheight;
 221
 222         NodeArray<NodeInfo> infos; //!< holds the cage and placement information
 223
 224         int    m_sep;   //!< minimum separation
 225         int    m_overh; //!< minimum overhang
 226         double Cconst;  //!< relative sep to overhang / delta to eps
 227
 228         void unsplit(edge e1, edge e2);
 229
 230         //! set coordinates of cage corners after placement
 231         void set_corners(node v);
 232
 233         //! computes the alpha value described in the paper
 234         int alpha_move(OrthoDir s_to, OrthoDir s_from, node v);
 235
 236         //! set minimum delta values for flip decision and adjust distances correspondingly
 237         bool m_minDelta;
 238
 239         //! helper for oppositeExpander
 240         node oppositeNode(adjEntry ae) { return ae->twinNode(); }
 241
 242         //! check if the target node of the outgoing adjEntry still is a expander
 243         bool oppositeExpander(adjEntry ae) {
 244                 Graph::NodeType nt;
 245                 nt = m_prup->typeOf(oppositeNode(ae));
 246                 return ((nt == Graph::highDegreeExpander) || (nt == Graph::lowDegreeExpander));
 247         }
 248         //if yes, set its m_oppositeBendType value according to the newly introduced bend
 249
 250         //! computes the beta value described in the paper
 251         /**
 252          * number of additional bend free edges on side s_from
 253          * if move_num edges are moved from side s_from to s_to
 254          */
 255         int beta_move(OrthoDir s_from, OrthoDir s_to, int move_num, node v);
 256
 257         //! compute the maximum number of moveable edges
 258         /**
 259          * dependant on space on available edges, return number of saved bends
 260          */
 261         int compute_move(OrthoDir s_from, OrthoDir s_to, int& kflip, node v);
 262
 263         NodeArray<int> m_newx, m_newy; //!< new placement position for original node
 264         //!< node array saves info about changed position, no further change is allowed
 265         NodeArray<bool> m_fixed;
 266         EdgeArray<int>  lowe, uppe, lefte, righte; //!< max box borders for bendfree edges
 267         AdjEntryArray<int>  alowe, auppe, alefte, arighte;
 268         AdjEntryArray<int>  m_agp_x, m_agp_y; //!< because edges can connect two replacement cages
 269         AdjEntryArray<node> m_cage_point; //!< newly introduced bends destroy edge to point connection
 270         AdjEntryArray<int>  m_acp_x, m_acp_y;//!< edge connection point coordinates before treatment
 271
 272         //! bends
 273         /**
 274          * 0 = bendfree, 1 = single bend from left to node,
 275          * 2 = single from right, 3 = int from left,
 276          * 4 = int from right,...
 277          */
 278         AdjEntryArray<bend_type> m_abends;
 279
 280         //! keep the information about the type of bend inserted at one end of an (originally unbend) edge, so that we can check possible bendsaving
 281         NodeArray<bend_type> m_oppositeBendType;
 282
 283         //! keep information about already processed Nodes
 284         NodeArray<process_type> m_processStatus;
 285
 286         //alignment test
 287         NodeArray<bool> m_mergerSon; //!< is part of merger son cage
 288         NodeArray<OrthoDir> m_mergeDir; //!< direction of adjacent (to) merger edges
 289         bool m_align;
 290 };
 291
 292 } //end namespace
 293
 294 #endif