router.h
Go to the documentation of this file.
1 /*
2  * vim: ts=4 sw=4 et tw=0 wm=0
3  *
4  * libavoid - Fast, Incremental, Object-avoiding Line Router
5  *
6  * Copyright (C) 2004-2009 Monash University
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  * See the file LICENSE.LGPL distributed with the library.
13  *
14  * Licensees holding a valid commercial license may use this file in
15  * accordance with the commercial license agreement provided with the
16  * library.
17  *
18  * This library is distributed in the hope that it will be useful,
19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
21  *
22  * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net>
23 */
24 
27 
28 
29 #ifndef AVOID_ROUTER_H
30 #define AVOID_ROUTER_H
31 
32 #include <list>
33 #include <utility>
34 #include <string>
35 
36 #include "libavoid/connector.h"
37 #include "libavoid/vertices.h"
38 #include "libavoid/graph.h"
39 #include "libavoid/timer.h"
40 
41 #if defined(LINEDEBUG) || defined(ASTAR_DEBUG) || defined(LIBAVOID_SDL)
42  #include <SDL.h>
43  #ifndef LIBAVOID_SDL
44  #define LIBAVOID_SDL
45  #endif
46 #endif
47 
48 
49 namespace Avoid {
50 
51 typedef std::list<unsigned int> IntList;
52 
53 class ActionInfo;
54 typedef std::list<ActionInfo> ActionInfoList;
55 class ShapeRef;
56 class JunctionRef;
57 class ClusterRef;
58 typedef std::list<ClusterRef *> ClusterRefList;
59 class Obstacle;
60 typedef std::list<Obstacle *> ObstacleList;
61 
65 {
72 };
73 
74 
75 static const unsigned int runningTo = 1;
76 static const unsigned int runningFrom = 2;
77 static const unsigned int runningToAndFrom = runningTo | runningFrom;
78 
82 {
122  // Used for determining the size of the penalty array.
123  // This should always we the last value in the enum.
124  lastPenaltyMarker
125 };
126 
127 
128 static const double noPenalty = 0;
129 static const double chooseSensiblePenalty = -1;
130 
131 
136 //
137 class Router {
138  public:
143  Router(const unsigned int flags);
144 
150  ~Router();
151 
152  ObstacleList m_obstacles;
153  ConnRefList connRefs;
154  ClusterRefList clusterRefs;
155  EdgeList visGraph;
156  EdgeList invisGraph;
157  EdgeList visOrthogGraph;
158  ContainsMap contains;
159  VertInfList vertices;
160  ContainsMap enclosingClusters;
161 
162  bool PartialTime;
163  bool SimpleRouting;
164  bool ClusteredRouting;
165 
166  // Poly-line routing options:
167  bool IgnoreRegions;
168  bool UseLeesAlgorithm;
169  bool InvisibilityGrph;
170 
171  // General routing options:
172  bool SelectiveReroute;
173 
174  bool PartialFeedback;
175  bool RubberBandRouting;
176 
177 
178  // Instrumentation:
179  Timer timers;
180  int st_checked_edges;
181 #ifdef LIBAVOID_SDL
182  SDL_Surface *avoid_screen;
183 #endif
184 
205  void setTransactionUse(const bool transactions);
206 
214  bool transactionUse(void) const;
215 
231  bool processTransaction(void);
232 
245  void addShape(ShapeRef *shape);
246 
258  void removeShape(ShapeRef *shape);
259 
278  void moveShape(ShapeRef *shape, const Polygon& newPoly,
279  const bool first_move = false);
280 
298  void moveShape(ShapeRef *shape, const double xDiff, const double yDiff);
299 
308  void addJunction(JunctionRef *junction);
309 
319  void removeJunction(JunctionRef *junction);
320 
334  void moveJunction(JunctionRef *junction, const Point& newPosition);
335 
353  void moveJunction(JunctionRef *junction, const double xDiff,
354  const double yDiff);
355 
366  void setOrthogonalNudgeDistance(const double dist);
367 
373  double orthogonalNudgeDistance(void) const;
374 
393  void setRoutingPenalty(const PenaltyType penType,
394  const double penVal = chooseSensiblePenalty);
395 
402  double routingPenalty(const PenaltyType penType) const;
403 
404  void addCluster(ClusterRef *cluster);
405  void delCluster(ClusterRef *cluster);
406 
407 #if 0
408  // XXX: attachedShapes and attachedConns both need to be rewritten
409  // for constant time lookup of attached objects once this info
410  // is stored better within libavoid. Also they shouldn't need to
411  // be friends of ConnRef.
412  void attachedShapes(IntList &shapes, const unsigned int shapeId,
413  const unsigned int type);
414  void attachedConns(IntList &conns, const unsigned int shapeId,
415  const unsigned int type);
416 #endif
417 
418  void markConnectors(Obstacle *obstacle);
419  void generateContains(VertInf *pt);
420  void printInfo(void);
421  void outputInstanceToSVG(std::string filename = std::string());
422  unsigned int assignId(const unsigned int suggestedId);
423  void regenerateStaticBuiltGraph(void);
424  void destroyOrthogonalVisGraph(void);
425  void setStaticGraphInvalidated(const bool invalidated);
426  ConnType validConnType(const ConnType select = ConnType_None) const;
427  bool objectIsInQueuedActionList(void *object) const;
428  double& penaltyRef(const PenaltyType penType);
429  bool existsOrthogonalPathOverlap(void);
430  bool existsOrthogonalTouchingPaths(void);
431  int existsOrthogonalCrossings(void);
432 
433  private:
434  friend class ShapeRef;
435  friend class ConnRef;
436  friend class JunctionRef;
437  friend class Obstacle;
438 
439  void modifyConnector(ConnRef *conn);
440  void modifyConnector(ConnRef *conn, unsigned int type,
441  const ConnEnd &connEnd);
442  void modifyConnectionPin(ShapeConnectionPin *pin);
443  void removeQueuedConnectorActions(ConnRef *conn);
444  void newBlockingShape(const Polygon& poly, int pid);
445  void checkAllBlockedEdges(int pid);
446  void checkAllMissingEdges(void);
447  void adjustContainsWithAdd(const Polygon& poly, const int p_shape);
448  void adjustContainsWithDel(const int p_shape);
449  void adjustClustersWithAdd(const PolygonInterface& poly,
450  const int p_cluster);
451  void adjustClustersWithDel(const int p_cluster);
452  void rerouteAndCallbackConnectors(void);
453  bool idIsUnique(const unsigned int id) const;
454  void improveCrossings(void);
455 
456  ActionInfoList actionList;
457  unsigned int _largestAssignedId;
458  bool _consolidateActions;
459  double _orthogonalNudgeDistance;
460  double _routingPenalties[lastPenaltyMarker];
461 
462  public:
463  // Overall modes:
464  bool _polyLineRouting;
465  bool _orthogonalRouting;
466 
467  bool _staticGraphInvalidated;
468  bool _inCrossingPenaltyReroutingStage;
469 };
470 
471 }
472 
473 
474 
475 #endif