src/libavoid/graph.h

   1 /*
   2  * vim: ts=4 sw=4 et tw=0 wm=0
   3  *
   4  * libavoid - Fast, Incremental, Object-avoiding Line Router
   5  * Copyright (C) 2004-2005  Michael Wybrow <mjwybrow@users.sourceforge.net>
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  *
  21 */
  22
  23 #ifndef AVOID_GRAPH_H
  24 #define AVOID_GRAPH_H
  25
  26
  27 #include <cassert>
  28 #include <list>
  29 #include <utility>
  30 using std::pair;
  31
  32 #include "libavoid/vertices.h"
  33
  34
  35 namespace Avoid {
  36
  37
  38 extern bool UseAStarSearch;
  39 extern bool IgnoreRegions;
  40 extern bool SelectiveReroute;
  41 extern bool IncludeEndpoints;
  42 extern bool UseLeesAlgorithm;
  43 extern bool InvisibilityGrph;
  44 extern bool PartialFeedback;
  45
  46
  47 typedef std::list<int> ShapeList;
  48 typedef std::list<bool *> FlagList;
  49
  50
  51 class EdgeInf
  52 {
  53     public:
  54         EdgeInf(VertInf *v1, VertInf *v2);
  55         ~EdgeInf();
  56         double getDist(void);
  57         void setDist(double dist);
  58         void alertConns(void);
  59         void addConn(bool *flag);
  60         void addCycleBlocker(void);
  61         void addBlocker(int b);
  62         bool hasBlocker(int b);
  63         pair<VertID, VertID> ids(void);
  64         pair<Point, Point> points(void);
  65         void db_print(void);
  66         void checkVis(void);
  67         VertInf *otherVert(VertInf *vert);
  68         static EdgeInf *checkEdgeVisibility(VertInf *i, VertInf *j,
  69                 bool knownNew = false);
  70         static EdgeInf *existingEdge(VertInf *i, VertInf *j);
  71
  72         EdgeInf *lstPrev;
  73         EdgeInf *lstNext;
  74     private:
  75         bool _added;
  76         bool _visible;
  77         VertInf *_v1;
  78         VertInf *_v2;
  79         EdgeInfList::iterator _pos1;
  80         EdgeInfList::iterator _pos2;
  81         ShapeList _blockers;
  82         FlagList  _conns;
  83         double  _dist;
  84
  85         void makeActive(void);
  86         void makeInactive(void);
  87         int firstBlocker(void);
  88         bool isBetween(VertInf *i, VertInf *j);
  89 };
  90
  91
  92 class EdgeList
  93 {
  94     public:
  95         EdgeList();
  96         void addEdge(EdgeInf *edge);
  97         void removeEdge(EdgeInf *edge);
  98         EdgeInf *begin(void);
  99         EdgeInf *end(void);
 100     private:
 101         EdgeInf *_firstEdge;
 102         EdgeInf *_lastEdge;
 103         unsigned int _count;
 104 };
 105
 106
 107 extern EdgeList visGraph;
 108 extern EdgeList invisGraph;
 109
 110 class ShapeRef;
 111
 112 extern void newBlockingShape(Polygn *poly, int pid);
 113 extern void checkAllBlockedEdges(int pid);
 114 extern void checkAllMissingEdges(void);
 115 extern void generateContains(VertInf *pt);
 116 extern void adjustContainsWithAdd(const Polygn& poly, const int p_shape);
 117 extern void adjustContainsWithDel(const int p_shape);
 118 extern void markConnectors(ShapeRef *shape);
 119 extern void printInfo(void);
 120
 121
 122 }
 123
 124
 125 #endif
 126
 127