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