1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
*
* Copyright (C) 2011-2015 Monash University
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
* See the file LICENSE.LGPL distributed with the library.
*
* Licensees holding a valid commercial license may use this file in
* accordance with the commercial license agreement provided with the
* library.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* Author(s): Michael Wybrow
*/
//! @file hyperedge.h
//! @brief Contains the interface for the HyperedgeRerouter class.
#ifndef AVOID_HYPEREDGE_H
#define AVOID_HYPEREDGE_H
#include <cstdio>
#include <list>
#include <vector>
#include <set>
#include "libavoid/dllexport.h"
namespace Avoid {
class ConnRef;
class JunctionRef;
class Router;
class ConnEnd;
class VertInf;
//! @brief A list of ConnEnd objects.
typedef std::list<ConnEnd> ConnEndList;
//! @brief A list of ConnRef objects.
typedef std::list<ConnRef *> ConnRefList;
//! @brief A list of JunctionRef objects.
typedef std::list<JunctionRef *> JunctionRefList;
typedef std::list<VertInf *> VertexList;
typedef std::set<ConnRef *> ConnRefSet;
typedef std::set<VertInf *> VertexSet;
typedef std::vector<JunctionRef *> JunctionRefVector;
typedef std::vector<ConnEndList> ConnEndListVector;
typedef std::vector<ConnRefList> ConnRefListVector;
typedef std::vector<JunctionRefList> JunctionRefListVector;
typedef std::vector<VertexSet> VertexSetVector;
//! @brief The HyperedgeNewAndDeletedObjectLists class stores lists of
//! objects created and deleted during hyperedge improvement.
//!
//! After hyperedge improvement, this information can be produced by calling
//! the Router::newAndDeletedObjectListsFromHyperedgeImprovement() method.
//!
//! After hyperedge rerouting, this information can be produced by calling
//! the HyperedgeRerouter::newAndDeletedObjectLists() method for each
//! hyperedge being fully rerouted.
//!
//! The HyperedgeNewAndDeletedObjectLists::changedConnectorList attribute
//! will only be used for hyperedge improvement and will always be empty
//! for hyperedge rerouting.
//!
struct HyperedgeNewAndDeletedObjectLists
{
//! A list of newly created junctions.
JunctionRefList newJunctionList;
//! A list of newly created connectors.
ConnRefList newConnectorList;
//! A list of deleted junctions.
JunctionRefList deletedJunctionList;
//! A list of deleted connectors.
ConnRefList deletedConnectorList;
//! A list of changed connectors.
ConnRefList changedConnectorList;
};
//! @brief The HyperedgeRerouter class is a convenience object that can be
//! used to register hyperedges to be rerouted, improving the
//! placement of their junctions and connector paths.
//!
//! To work with this class, you should get a copy from the router instance
//! via a call to Router::hyperedgeRerouter().
//!
//! If you would like a particular hyperedge to be completely rerouted with
//! new junction positions then you should register it with this class via a
//! call to registerHyperedgeForRerouting. A hyperedge can either be
//! specified as a set of terminal vertices, or as a single JunctionRef.
//! Passing a JunctionRef will cause HyperedgeRerouter to follow the attached
//! connectors and junctions to determine the hyperedge. When you register
//! a hyperedge you get an index number that can be used to later find
//! information about it.
//!
//! The rerouting will actually occur the next time the Router processes a
//! transaction, see Router::processTransaction(). The rerouting will
//! effectively create new junctions (JunctionRefs) and connectors (ConnRefs)
//! for the hyperedge.
//!
//! Since hyperedges are composed of multiple connections and junction objects,
//! rerouting a hyperedge can cause creation of new or deletion of existing
//! connectors and/or junctions. Thus once the transaction has been completed
//! you should call the newAndDeletedObjectLists() to get an object containing
//! the lists of created and deleted junctions and connectors. After the
//! transaction You should not use references to these deleted objects any
//! more from your own code (since the router will free their memory at its
//! convenience) and you should refer only to the unaffected objects and the
//! new connectors and junctions.
//!
class AVOID_EXPORT HyperedgeRerouter
{
public:
//! @brief Constructor for hyperedge rerouter object.
//!
//! @note You shouldn't create this object yourself. The Router
//! instance has one that you can request a reference to
//! via Router::hyperedgeRerouter().
//!
HyperedgeRerouter();
//! @brief Registers a hyperedge to be fully rerouted the next time
//! the router processes a transaction.
//!
//! @param[in] terminals The ConnEnds that form the endpoints of the
//! hyperedge.
//! @return An index that can be used to request information on the
//! resulting routing of the hyperedge.
//!
size_t registerHyperedgeForRerouting(ConnEndList terminals);
//! @brief Registers a hyperedge to be fully rerouted the next time
//! the router processes a transaction.
//!
//! In this case the connectors and junctions attached to the given
//! junction will be traversed to determine the endpoints of the
//! hyperedge. These endpoints will then be used for the rerouting.
//! The junctions and connectors forming the old route will be
//! deleted.
//!
//! @param[in] junction One of the junctions that forms the
//! hyperedge.
//! @return An index that can be used to request information on the
//! resulting routing of the hyperedge.
//!
size_t registerHyperedgeForRerouting(JunctionRef *junction);
//! @brief Returns a HyperedgeNewAndDeletedObjectLists detailing the
//! lists of junctions and connectors created and deleted
//! during hyperedge improvement.
//!
//! This method will only return information once the router has
//! processed the transaction. You should read this information
//! before processTransaction() is called again.
//!
//! After calling this you should no longer refer to any of the
//! objects in the "deleted" lists --- the router will delete these
//! and free their memory at its convenience.
//!
//! @param index The index of the hyperedge to return junctions for.
//! @return A HyperedgeNewAndDeletedObjectLists containing lists of
//! junctions and connectors created and deleted.
//!
HyperedgeNewAndDeletedObjectLists newAndDeletedObjectLists(
size_t index) const;
// @brief The number of hyperedges that are being or have been
// rerouted.
// @return The number of rerouted hyperedges.
//
size_t count(void) const;
private:
friend class Router;
// @brief Sets the router instance that this object operates on.
//
// @param[in] router The router instance to operate on.
//
void setRouter(Router *router);
ConnRefSet calcHyperedgeConnectors(void);
// Called by Router during processTransaction().
void performRerouting(void);
void outputInstanceToSVG(FILE *fp);
bool findAttachedObjects(size_t index, ConnRef *connector,
JunctionRef *ignore, ConnRefSet& hyperedgeConns);
bool findAttachedObjects(size_t index, JunctionRef *junction,
ConnRef *ignore, ConnRefSet& hyperedgeConns);
Router *m_router;
ConnEndListVector m_terminals_vector;
JunctionRefVector m_root_junction_vector;
JunctionRefListVector m_new_junctions_vector;
JunctionRefListVector m_deleted_junctions_vector;
ConnRefListVector m_new_connectors_vector;
ConnRefListVector m_deleted_connectors_vector;
VertexSetVector m_terminal_vertices_vector;
VertexList m_added_vertices;
};
}
#endif
|
