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-2011  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
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();
getDist(void)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 isDisabled(void) const;
64         void setDisabled(const bool disabled);
65         bool rotationLessThan(const VertInf* last, const EdgeInf *rhs) const;
66         std::pair<VertID, VertID> ids(void) const;
67         std::pair<Point, Point> points(void) const;
68         void db_print(void);
69         void checkVis(void);
70         VertInf *otherVert(const VertInf *vert) const;
71         static EdgeInf *checkEdgeVisibility(VertInf *i, VertInf *j,
72                 bool knownNew = false);
73         static EdgeInf *existingEdge(VertInf *i, VertInf *j);
74         int blocker(void) const;
75 
76         bool isHyperedgeSegment(void) const;
77         void setHyperedgeSegment(const bool hyperedge);
78         double mtstDist(void) const;
79         void setMtstDist(const double joinCost);
80 
81         EdgeInf *lstPrev;
82         EdgeInf *lstNext;
83     private:
84         friend class MinimumTerminalSpanningTree;
85         friend class VertInf;
86 
87         void makeActive(void);
88         void makeInactive(void);
89         int firstBlocker(void);
90         bool isBetween(VertInf *i, VertInf *j);
91 
92         Router *m_router;
93         int m_blocker;
94         bool m_added;
95         bool m_visible;
96         bool m_orthogonal;
97         bool m_isHyperedgeSegment;
98         bool m_disabled;
99         VertInf *m_vert1;
100         VertInf *m_vert2;
101         EdgeInfList::iterator m_pos1;
102         EdgeInfList::iterator m_pos2;
103         FlagList  m_conns;
104         double  m_dist;
105         double  m_mtst_dist;
106 };
107 
108 
109 class EdgeList
110 {
111     public:
112         friend class EdgeInf;
113         EdgeList(bool orthogonal = false);
114         ~EdgeList();
115         void clear(void);
116         EdgeInf *begin(void);
117         EdgeInf *end(void);
118         int size(void) const;
119     private:
120         void addEdge(EdgeInf *edge);
121         void removeEdge(EdgeInf *edge);
122 
123         bool m_orthogonal;
124         EdgeInf *m_first_edge;
125         EdgeInf *m_last_edge;
126         unsigned int m_count;
127 };
128 
129 
130 }
131 
132 
133 #endif
134 
135 
136