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