graph.h
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 
25 
26 #ifndef AVOID_GRAPH_H
27 #define AVOID_GRAPH_H
28 
29 
30 #include <cassert>
31 #include <list>
32 #include <utility>
33 #include "libavoid/vertices.h"
34 
35 namespace Avoid {
36 
37 
38 class ConnRef;
39 class Router;
40 
41 
42 typedef std::list<int> ShapeList;
43 typedef std::list<bool *> FlagList;
44 
45 
46 class EdgeInf
47 {
48  public:
49  EdgeInf(VertInf *v1, VertInf *v2, const bool orthogonal = false);
50  ~EdgeInf();
51  inline double getDist(void)
52  {
53  return m_dist;
54  }
55  void setDist(double dist);
56  void alertConns(void);
57  void addConn(bool *flag);
58  void addCycleBlocker(void);
59  void addBlocker(int b);
60  bool added(void);
61  bool isOrthogonal(void) const;
62  bool isDummyConnection(void) const;
63  bool rotationLessThan(const VertInf* last, const EdgeInf *rhs) const;
64  std::pair<VertID, VertID> ids(void) const;
65  std::pair<Point, Point> points(void) const;
66  void db_print(void);
67  void checkVis(void);
68  VertInf *otherVert(const VertInf *vert) const;
69  static EdgeInf *checkEdgeVisibility(VertInf *i, VertInf *j,
70  bool knownNew = false);
71  static EdgeInf *existingEdge(VertInf *i, VertInf *j);
72  int blocker(void) const;
73 
74  EdgeInf *lstPrev;
75  EdgeInf *lstNext;
76  private:
77  void makeActive(void);
78  void makeInactive(void);
79  int firstBlocker(void);
80  bool isBetween(VertInf *i, VertInf *j);
81 
82  Router *m_router;
83  int m_blocker;
84  bool m_added;
85  bool m_visible;
86  bool m_orthogonal;
87  VertInf *m_vert1;
88  VertInf *m_vert2;
89  EdgeInfList::iterator m_pos1;
90  EdgeInfList::iterator m_pos2;
91  FlagList m_conns;
92  double m_dist;
93 };
94 
95 
96 class EdgeList
97 {
98  public:
99  friend class EdgeInf;
100  EdgeList(bool orthogonal = false);
101  ~EdgeList();
102  void clear(void);
103  EdgeInf *begin(void);
104  EdgeInf *end(void);
105  int size(void) const;
106  private:
107  void addEdge(EdgeInf *edge);
108  void removeEdge(EdgeInf *edge);
109 
110  bool m_orthogonal;
111  EdgeInf *m_first_edge;
112  EdgeInf *m_last_edge;
113  unsigned int m_count;
114 };
115 
116 
117 }
118 
119 
120 #endif
121 
122