diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libavoid/hyperedge.cpp')
-rw-r--r-- | src/3rdparty/adaptagrams/libavoid/hyperedge.cpp | 388 |
1 files changed, 388 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libavoid/hyperedge.cpp b/src/3rdparty/adaptagrams/libavoid/hyperedge.cpp new file mode 100644 index 0000000..d6f2a40 --- /dev/null +++ b/src/3rdparty/adaptagrams/libavoid/hyperedge.cpp @@ -0,0 +1,388 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * + * Copyright (C) 2011-2014 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 +*/ + +#include "libavoid/hyperedge.h" +#include "libavoid/hyperedgetree.h" +#include "libavoid/mtst.h" +#include "libavoid/junction.h" +#include "libavoid/connector.h" +#include "libavoid/vertices.h" +#include "libavoid/connend.h" +#include "libavoid/shape.h" +#include "libavoid/router.h" +#include "libavoid/assertions.h" +#include "libavoid/debughandler.h" +#include "libavoid/debug.h" + + +namespace Avoid { + +HyperedgeRerouter::HyperedgeRerouter() + : m_router(nullptr) +{ +} + +void HyperedgeRerouter::setRouter(Router *router) +{ + m_router = router; +} + +size_t HyperedgeRerouter::registerHyperedgeForRerouting( + ConnEndList terminals) +{ + m_terminals_vector.push_back(terminals); + m_root_junction_vector.push_back(nullptr); + + return m_terminals_vector.size() - 1; +} + +size_t HyperedgeRerouter::registerHyperedgeForRerouting( + JunctionRef *junction) +{ + m_terminals_vector.push_back(ConnEndList()); + m_root_junction_vector.push_back(junction); + + return m_terminals_vector.size() - 1; +} + +size_t HyperedgeRerouter::count(void) const +{ + return m_terminals_vector.size(); +} + +HyperedgeNewAndDeletedObjectLists HyperedgeRerouter::newAndDeletedObjectLists( + size_t index) const +{ + COLA_ASSERT(index <= count()); + + HyperedgeNewAndDeletedObjectLists result; + + result.newJunctionList = m_new_junctions_vector[index]; + result.deletedJunctionList = m_deleted_junctions_vector[index]; + result.newConnectorList = m_new_connectors_vector[index]; + result.deletedConnectorList = m_deleted_connectors_vector[index]; + + return result; +} + + +void HyperedgeRerouter::outputInstanceToSVG(FILE *fp) +{ + if (count() == 0) + { + return; + } + + fprintf(fp, " HyperedgeRerouter *hyperedgeRerouter = router->hyperedgeRerouter();\n"); + const size_t num_hyperedges = count(); + for (size_t i = 0; i < num_hyperedges; ++i) + { + if (m_root_junction_vector[i]) + { + fprintf(fp, " hyperedgeRerouter->registerHyperedgeForRerouting(junctionRef%u);\n", + m_root_junction_vector[i]->id()); + } + else + { + fprintf(fp, " ConnEndList heConnList%u;\n", (unsigned int) i); + for (ConnEndList::const_iterator it = m_terminals_vector[i].begin(); + it != m_terminals_vector[i].end(); ++it) + { + (*it).outputCode(fp, "heEnd"); + fprintf(fp, " heConnList%u.push_back(heEndPt);\n", + (unsigned int) i); + } + fprintf(fp, " hyperedgeRerouter->registerHyperedgeForRerouting(heConnList%u);\n", + (unsigned int) i); + + } + } + fprintf(fp, "\n"); +} + + +// Follow connected junctions and connectors from the given connector to +// determine the hyperedge topology, saving objects to the deleted-objects +// vectors as we go. +bool HyperedgeRerouter::findAttachedObjects(size_t index, + ConnRef *connector, JunctionRef *ignore, ConnRefSet& hyperedgeConns) +{ + bool validHyperedge = false; + + connector->assignConnectionPinVisibility(true); + + m_deleted_connectors_vector[index].push_back(connector); + hyperedgeConns.insert(connector); + + std::pair<Obstacle *, Obstacle *> anchors = connector->endpointAnchors(); + JunctionRef *jFirst = dynamic_cast<JunctionRef *> (anchors.first); + JunctionRef *jSecond = dynamic_cast<JunctionRef *> (anchors.second); + + if (jFirst) + { + // If attached to a junction and not one we've explored, then continue. + if (jFirst != ignore) + { + validHyperedge |= findAttachedObjects(index, jFirst, connector, hyperedgeConns); + } + } + else + { + // If its an endpoint, then record the vertex for this endpoint. + COLA_ASSERT(connector->m_src_vert); + m_terminal_vertices_vector[index].insert(connector->m_src_vert); + } + + if (jSecond) + { + // If attached to a junction and not one we've explored, then continue. + if (jSecond != ignore) + { + validHyperedge |= findAttachedObjects(index, jSecond, connector, hyperedgeConns); + } + } + else + { + // If its an endpoint, then record the vertex for this endpoint. + COLA_ASSERT(connector->m_dst_vert); + m_terminal_vertices_vector[index].insert(connector->m_dst_vert); + } + return validHyperedge; +} + + +// Follow connected junctions and connectors from the given junction to +// determine the hyperedge topology, saving objects to the deleted-objects +// vectors as we go. +bool HyperedgeRerouter::findAttachedObjects(size_t index, + JunctionRef *junction, ConnRef *ignore, ConnRefSet& hyperedgeConns) +{ + bool validHyperedge = false; + + m_deleted_junctions_vector[index].push_back(junction); + + ConnRefList connectors = junction->attachedConnectors(); + + if (connectors.size() > 2) + { + // A valid hyperedge must have at least one junction with three + // connectors attached, i.e., more than two endpoints. + validHyperedge |= true; + } + + for (ConnRefList::iterator curr = connectors.begin(); + curr != connectors.end(); ++curr) + { + if (*curr == ignore) + { + continue; + } + + COLA_ASSERT(*curr != nullptr); + validHyperedge |= findAttachedObjects(index, (*curr), junction, hyperedgeConns); + } + return validHyperedge; +} + + +// Populate the deleted-object vectors with all the connectors and junctions +// that form the registered hyperedges. Then return the set of all these +// connectors so they can be ignored for individual rerouting. +ConnRefSet HyperedgeRerouter::calcHyperedgeConnectors(void) +{ + COLA_ASSERT(m_router != nullptr); + + ConnRefSet allRegisteredHyperedgeConns; + + // Clear the deleted-object vectors. We populate them here if necessary. + m_deleted_junctions_vector.clear(); + m_deleted_junctions_vector.resize(count()); + m_deleted_connectors_vector.clear(); + m_deleted_connectors_vector.resize(count()); + + m_terminal_vertices_vector.clear(); + m_terminal_vertices_vector.resize(count()); + m_added_vertices.clear(); + + // Populate the deleted-object vectors. + const size_t num_hyperedges = count(); + for (size_t i = 0; i < num_hyperedges; ++i) + { + if (m_root_junction_vector[i]) + { + // Follow objects attached to junction to find the hyperedge. + bool valid = findAttachedObjects(i, m_root_junction_vector[i], nullptr, + allRegisteredHyperedgeConns); + if (!valid) + { + err_printf("Warning: Hyperedge %d registered with " + "HyperedgeRerouter is invalid and will be " + "ignored.\n", (int) i); + // Hyperedge is invalid. Clear the terminals and other info + // so it will be ignored, and rerouted as a normal set of + // connectors. + m_terminals_vector[i].clear(); + m_terminal_vertices_vector[i].clear(); + m_deleted_junctions_vector[i].clear(); + m_deleted_connectors_vector[i].clear(); + } + continue; + } + + // Alternatively, we have a set of ConnEnds, so store the + // corresponding terminals + std::pair<bool, VertInf *> maybeNewVertex; + for (ConnEndList::const_iterator it = m_terminals_vector[i].begin(); + it != m_terminals_vector[i].end(); ++it) + { + maybeNewVertex = it->getHyperedgeVertex(m_router); + COLA_ASSERT(maybeNewVertex.second != nullptr); + m_terminal_vertices_vector[i].insert(maybeNewVertex.second); + + if (maybeNewVertex.first) + { + // This is a newly created vertex. Remember it so we can + // free it and it's visibility edges later. + m_added_vertices.push_back(maybeNewVertex.second); + } + } + } + + // Return these connectors that don't require rerouting. + return allRegisteredHyperedgeConns; +} + + +void HyperedgeRerouter::performRerouting(void) +{ + COLA_ASSERT(m_router != nullptr); + + m_new_junctions_vector.clear(); + m_new_junctions_vector.resize(count()); + m_new_connectors_vector.clear(); + m_new_connectors_vector.resize(count()); + +#ifdef DEBUGHANDLER + if (m_router->debugHandler()) + { + std::vector<Box> obstacleBoxes; + ObstacleList::iterator obstacleIt = m_router->m_obstacles.begin(); + while (obstacleIt != m_router->m_obstacles.end()) + { + Obstacle *obstacle = *obstacleIt; + JunctionRef *junction = dynamic_cast<JunctionRef *> (obstacle); + if (junction && ! junction->positionFixed()) + { + // Junctions that are free to move are not treated as obstacles. + ++obstacleIt; + continue; + } + Box bbox = obstacle->routingBox(); + obstacleBoxes.push_back(bbox); + ++obstacleIt; + } + m_router->debugHandler()->updateObstacleBoxes(obstacleBoxes); + } +#endif + + // For each hyperedge... + const size_t num_hyperedges = count(); + for (size_t i = 0; i < num_hyperedges; ++i) + { + if (m_terminal_vertices_vector[i].empty()) + { + // Invalid hyperedge, ignore. + continue; + } + + // Execute the MTST method to find good junction positions and an + // initial path. A hyperedge tree will be built for the new route. + JunctionHyperedgeTreeNodeMap hyperedgeTreeJunctions; + MinimumTerminalSpanningTree mtst(m_router, + m_terminal_vertices_vector[i], &hyperedgeTreeJunctions); + + // The older MTST construction method (faster, worse results). + //mtst.constructSequential(); + + // The preferred MTST construction method. + // Slightly slower, better quality results. + mtst.constructInterleaved(); + + HyperedgeTreeNode *treeRoot = mtst.rootJunction(); + COLA_ASSERT(treeRoot); + + // Fill in connector information and join them to junctions of endpoints + // of original connectors. + treeRoot->addConns(nullptr, m_router, + m_deleted_connectors_vector[i], nullptr); + + // Output the list of new junctions and connectors from hyperedge tree. + treeRoot->listJunctionsAndConnectors(nullptr, m_new_junctions_vector[i], + m_new_connectors_vector[i]); + + // Write paths from the hyperedge tree back into individual + // connector routes. + for (size_t pass = 0; pass < 2; ++pass) + { + treeRoot->writeEdgesToConns(nullptr, pass); + } + + // Tell the router that we are deleting the objects used for the + // previous path for the hyperedge. + for (ConnRefList::iterator curr = + m_deleted_connectors_vector[i].begin(); + curr != m_deleted_connectors_vector[i].end(); ++curr) + { + // Clear visibility assigned for connection pins. + (*curr)->assignConnectionPinVisibility(false); + + m_router->deleteConnector(*curr); + } + for (JunctionRefList::iterator curr = + m_deleted_junctions_vector[i].begin(); + curr != m_deleted_junctions_vector[i].end(); ++curr) + { + m_router->deleteJunction(*curr); + } + } + + // Clear the input to this class, so that new objects can be registered + // for rerouting for the next time that transaction that is processed. + m_terminals_vector.clear(); + m_root_junction_vector.clear(); + + // Free temporarily added vertices. + for (VertexList::iterator curr = m_added_vertices.begin(); + curr != m_added_vertices.end(); ++curr) + { + (*curr)->removeFromGraph(); + m_router->vertices.removeVertex(*curr); + delete *curr; + } + m_added_vertices.clear(); +} + + +} + |