diff options
Diffstat (limited to 'src/libavoid/hyperedgetree.cpp')
| -rw-r--r-- | src/libavoid/hyperedgetree.cpp | 821 |
1 files changed, 0 insertions, 821 deletions
diff --git a/src/libavoid/hyperedgetree.cpp b/src/libavoid/hyperedgetree.cpp deleted file mode 100644 index d795be801..000000000 --- a/src/libavoid/hyperedgetree.cpp +++ /dev/null @@ -1,821 +0,0 @@ -/* - * 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 <algorithm> - -#include "libavoid/hyperedgetree.h" -#include "libavoid/geometry.h" -#include "libavoid/connector.h" -#include "libavoid/router.h" -#include "libavoid/connend.h" -#include "libavoid/assertions.h" -#include "libavoid/junction.h" -#include "libavoid/debughandler.h" - -namespace Avoid { - - -// Constructs a new hyperedge tree node. -// -HyperedgeTreeNode::HyperedgeTreeNode() - : junction(NULL), - shiftSegmentNodeSet(NULL), - finalVertex(NULL), - isConnectorSource(false), - isPinDummyEndpoint(false), - visited(false) -{ -} - -HyperedgeTreeNode::~HyperedgeTreeNode() -{ - if (shiftSegmentNodeSet) - { - shiftSegmentNodeSet->erase(this); - shiftSegmentNodeSet = NULL; - } -} - - -// This method traverses the hyperedge tree and outputs each of the edges -// and junction positions as SVG objects to the file fp. -// -void HyperedgeTreeNode::outputEdgesExcept(FILE *fp, HyperedgeTreeEdge *ignored) -{ - if (junction) - { - fprintf(fp, "<circle cx=\"%g\" cy=\"%g\" r=\"6\" " - "style=\"fill: green; stroke: none;\" />\n", point.x, point.y); - } - for (std::list<HyperedgeTreeEdge *>::iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - if (*curr != ignored) - { - (*curr)->outputNodesExcept(fp, this); - } - } -} - - -// This method traverses the hyperedge tree and removes from treeRoots any -// junction nodes (other than this one). - -bool HyperedgeTreeNode::removeOtherJunctionsFrom(HyperedgeTreeEdge *ignored, - JunctionSet& treeRoots) -{ - bool containsCycle = false; - if (visited) - { - // We've encountered this node before, so there must be cycles in - // the hyperedge. Don't recurse any further. - containsCycle = true; - return containsCycle; - } - - if (junction && (ignored != NULL)) - { - // Remove junctions other than the first (when ignored == NULL). - treeRoots.erase(junction); - } - visited = true; - for (std::list<HyperedgeTreeEdge *>::iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - if (*curr != ignored) - { - containsCycle |= (*curr)->removeOtherJunctionsFrom(this, treeRoots); - } - } - return containsCycle; -} - - -// This method traverses the hyperedge tree and writes each of the paths -// back to the individual connectors as routes. -// -void HyperedgeTreeNode::writeEdgesToConns(HyperedgeTreeEdge *ignored, - size_t pass) -{ - for (std::list<HyperedgeTreeEdge *>::iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - if (*curr != ignored) - { - (*curr)->writeEdgesToConns(this, pass); - } - } -} - -// This method traverses the hyperedge tree and creates connectors for each -// segment bridging junction and/or terminals. It also sets the -// appropriate ConnEnds for each connector. -// -void HyperedgeTreeNode::addConns(HyperedgeTreeEdge *ignored, Router *router, - ConnRefList& oldConns, ConnRef *conn) -{ - // If no connector is set, then we must be starting off at a junction. - COLA_ASSERT(conn || junction); - - for (std::list<HyperedgeTreeEdge *>::iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - if (*curr != ignored) - { - // If we're not at a junction, then use the connector value being - // passed in to the method. - - if (junction) - { - // If we're at a junction, then we are effectively starting - // our traversal along a connector, so create this new connector - // and set it's start ConnEnd to be this junction. - conn = new ConnRef(router); - router->removeObjectFromQueuedActions(conn); - conn->makeActive(); - conn->m_initialised = true; - ConnEnd connend(junction); - conn->updateEndPoint(VertID::src, connend); - } - - // Set the connector for this edge. - (*curr)->conn = conn; - - // Continue recursive traversal. - (*curr)->addConns(this, router, oldConns); - } - } -} - -static bool travellingForwardOnConnector(ConnRef *conn, JunctionRef *junction) -{ - std::pair<ConnEnd, ConnEnd> connEnds = conn->endpointConnEnds(); - - if (connEnds.first.junction() == junction) - { - return true; - } - if (connEnds.second.junction() == junction) - { - return false; - } - if (connEnds.first.type() != ConnEndJunction && - connEnds.first.type() != ConnEndEmpty) - { - return false; - } - if (connEnds.second.type() != ConnEndJunction && - connEnds.second.type() != ConnEndEmpty) - { - return true; - } - return true; -} - -// This method traverses the hyperedge tree and rewrites connector ends -// that may have changed junctions due to major hyperedge improvement. -// -void HyperedgeTreeNode::updateConnEnds(HyperedgeTreeEdge *ignored, - bool forward, ConnRefList& changedConns) -{ - for (std::list<HyperedgeTreeEdge *>::iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - HyperedgeTreeEdge *edge = *curr; - if (edge != ignored) - { - if (junction) - { - // If we're at a junction, then we are effectively starting - // our traversal along a connector, so create this new connector - // and set it's start ConnEnd to be this junction. - forward = travellingForwardOnConnector(edge->conn, junction); - - std::pair<ConnEnd, ConnEnd> existingEnds = - edge->conn->endpointConnEnds(); - ConnEnd existingEnd = (forward) ? - existingEnds.first : existingEnds.second; - if (existingEnd.junction() != junction) - { -#ifdef MAJOR_HYPEREDGE_IMPROVEMENT_DEBUG - fprintf(stderr, "HyperedgeImprover: changed %s of " - "connector %u (from junction %u to %u)\n", - (forward) ? "src" : "tar", edge->conn->id(), - existingEnd.junction()->id(), junction->id()); -#endif - unsigned short end = (forward) ? VertID::src : VertID::tar; - ConnEnd connend(junction); - edge->conn->updateEndPoint(end, connend); - changedConns.push_back(edge->conn); - } - } - - // Continue recursive traversal. - edge->updateConnEnds(this, forward, changedConns); - } - } -} - - -// This method traverses the hyperedge tree and returns a list of the junctions -// and connectors that make up the hyperedge. -// -void HyperedgeTreeNode::listJunctionsAndConnectors(HyperedgeTreeEdge *ignored, - JunctionRefList& junctions, ConnRefList& connectors) -{ - if (junction) - { - junctions.push_back(junction); - } - - for (std::list<HyperedgeTreeEdge *>::iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - if (*curr != ignored) - { - (*curr)->listJunctionsAndConnectors(this, junctions, connectors); - } - } -} - - -void HyperedgeTreeNode::validateHyperedge(const HyperedgeTreeEdge *ignored, - const size_t dist) const -{ - size_t newDist = dist; -#ifdef MAJOR_HYPEREDGE_IMPROVEMENT_DEBUG - if (junction) - { - if (newDist == 0) - { - fprintf(stderr,"\nHyperedge topology:\n"); - } - else - { - ++newDist; - } - for (size_t d = 0; d < newDist; ++d) - { - fprintf(stderr," "); - } - fprintf(stderr, "j(%d)\n", junction->id()); - ++newDist; - } - else if (edges.size() == 1) - { - ++newDist; - for (size_t d = 0; d < newDist; ++d) - { - fprintf(stderr, " "); - } - fprintf(stderr, "t()\n"); - ++newDist; - } -#endif - for (std::list<HyperedgeTreeEdge *>::const_iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - HyperedgeTreeEdge *edge = *curr; - std::pair<ConnEnd, ConnEnd> connEnds = edge->conn->endpointConnEnds(); - - if (junction) - { - COLA_ASSERT((connEnds.first.junction() == junction) || - (connEnds.second.junction() == junction)); - COLA_ASSERT(connEnds.first.junction() != connEnds.second.junction()); - } - else if (edges.size() == 1) - { - COLA_ASSERT(!connEnds.first.junction() || - !connEnds.second.junction()); - } - - if (edge != ignored) - { - edge->validateHyperedge(this, newDist); - } - } -} - - -// This method traverses the hyperedge tree, clearing up the objects and -// memory used to store the tree. -// -void HyperedgeTreeNode::deleteEdgesExcept(HyperedgeTreeEdge *ignored) -{ - for (std::list<HyperedgeTreeEdge *>::iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - if (*curr != ignored) - { - (*curr)->deleteNodesExcept(this); - delete *curr; - } - } - edges.clear(); -} - - -// This method disconnects a specific hyperedge tree edge from the given node. -// -void HyperedgeTreeNode::disconnectEdge(HyperedgeTreeEdge *edge) -{ - for (std::list<HyperedgeTreeEdge *>::iterator curr = edges.begin(); - curr != edges.end(); ) - { - if (*curr == edge) - { - curr = edges.erase(curr); - } - else - { - ++curr; - } - } - -} - - -// This method moves all edges attached to oldNode to instead be attached to -// the given hyperedge tree node. -// -void HyperedgeTreeNode::spliceEdgesFrom(HyperedgeTreeNode *oldNode) -{ - COLA_ASSERT(oldNode != this); - for (std::list<HyperedgeTreeEdge *>::iterator curr = oldNode->edges.begin(); - curr != oldNode->edges.end(); curr = oldNode->edges.begin()) - { - (*curr)->replaceNode(oldNode, this); - } -} - - -bool HyperedgeTreeNode::isImmovable(void) const -{ - if ((edges.size() == 1) || (junction && junction->positionFixed())) - { - return true; - } - for (std::list<HyperedgeTreeEdge *>::const_iterator curr = edges.begin(); - curr != edges.end(); ++curr) - { - if ((*curr)->hasFixedRoute) - { - return true; - } - } - return false; -} - -// Constructs a new hyperedge tree edge, given two endpoint nodes. -// -HyperedgeTreeEdge::HyperedgeTreeEdge(HyperedgeTreeNode *node1, - HyperedgeTreeNode *node2, ConnRef *conn) - : conn(conn), - hasFixedRoute(false) -{ - if (conn) - { - hasFixedRoute = conn->hasFixedRoute(); - } - ends = std::make_pair(node1, node2); - node1->edges.push_back(this); - node2->edges.push_back(this); -} - - -// Given one endpoint of the hyperedge tree edge, returns the other endpoint. -// -HyperedgeTreeNode *HyperedgeTreeEdge::followFrom(HyperedgeTreeNode *from) const -{ - return (ends.first == from) ? ends.second : ends.first; -} - - -// Returns true if the length of this edge is zero, i.e., the endpoints are -// located at the same position. -// -bool HyperedgeTreeEdge::zeroLength(void) const -{ - return (ends.first->point == ends.second->point); -} - - -// This method traverses the hyperedge tree and outputs each of the edges -// and junction positions as SVG objects to the file fp. -// -void HyperedgeTreeEdge::outputNodesExcept(FILE *fp, HyperedgeTreeNode *ignored) -{ - fprintf(fp, "<path d=\"M %g %g L %g %g\" " - "style=\"fill: none; stroke: %s; stroke-width: 2px; " - "stroke-opacity: 0.5;\" />\n", - ends.first->point.x, ends.first->point.y, - ends.second->point.x, ends.second->point.y, "purple"); - if (ends.first != ignored) - { - ends.first->outputEdgesExcept(fp, this); - } - - if (ends.second != ignored) - { - ends.second->outputEdgesExcept(fp, this); - } -} - - -// This method returns true if the edge is in the dimension given, i.e., -// either horizontal or vertical. -// -bool HyperedgeTreeEdge::hasOrientation(const size_t dimension) const -{ - return (ends.first->point[dimension] == ends.second->point[dimension]); -} - - -// This method updates any of the given hyperedge tree edge's endpoints that -// are attached to oldNode to instead be attached to newNode. -// -void HyperedgeTreeEdge::replaceNode(HyperedgeTreeNode *oldNode, - HyperedgeTreeNode *newNode) -{ - if (ends.first == oldNode) - { - oldNode->disconnectEdge(this); - newNode->edges.push_back(this); - ends.first = newNode; - } - else if (ends.second == oldNode) - { - oldNode->disconnectEdge(this); - newNode->edges.push_back(this); - ends.second = newNode; - } -} - - -// This method traverses the hyperedge tree and writes each of the paths -// back to the individual connectors as routes. -// -void HyperedgeTreeEdge::writeEdgesToConns(HyperedgeTreeNode *ignored, - size_t pass) -{ - COLA_ASSERT(ignored != NULL); - COLA_ASSERT(ends.first != NULL); - COLA_ASSERT(ends.second != NULL); - - HyperedgeTreeNode *prevNode = - (ignored == ends.first) ? ends.first : ends.second; - HyperedgeTreeNode *nextNode = - (ignored == ends.first) ? ends.second : ends.first; - - if (pass == 0) - { - conn->m_display_route.clear(); - } - else if (pass == 1) - { - if (conn->m_display_route.empty()) - { - //printf("[%u] - %g %g\n", conn->id(), prevNode->point.x, prevNode->point.y); - conn->m_display_route.ps.push_back(prevNode->point); - } - //printf("[%u] + %g %g\n", conn->id(), nextNode->point.x, nextNode->point.y); - conn->m_display_route.ps.push_back(nextNode->point); - - size_t nextNodeEdges = nextNode->edges.size(); - if (nextNodeEdges != 2) - { - // We have finished writing a connector. If the node has just - // two edges then it is an intermediate node on a connector. - bool shouldReverse = false; - if (nextNodeEdges == 1) - { - // This connector led to a terminal. - if (nextNode->isConnectorSource) - { - shouldReverse = true; - } - - if (nextNode->isPinDummyEndpoint) - { - // If may be that the hyperedge has an extra segment or - // two leading to the centre dummy pin used for connection - // pin routing. If so, remove these points from the - // resulting route. - conn->m_display_route.ps.pop_back(); - if (prevNode->point == nextNode->point) - { - // Duplicated dummy point. Remove second one. - conn->m_display_route.ps.pop_back(); - } - } - } - else // if (nextNodeEdges > 2) - { - // This connector was between two junctions. - COLA_ASSERT(conn->m_dst_connend); - JunctionRef *correctEndJunction = - conn->m_dst_connend->junction(); - if (nextNode->junction != correctEndJunction) - { - shouldReverse = true; - } - } - - if (shouldReverse == true) - { - // Reverse the written connector route. - std::reverse(conn->m_display_route.ps.begin(), - conn->m_display_route.ps.end()); - } - } - -#ifdef DEBUGHANDLER - if (conn->router()->debugHandler()) - { - conn->router()->debugHandler()->updateConnectorRoute( - conn, -1, -1); - } -#endif - } - - nextNode->writeEdgesToConns(this, pass); -} - -// This method traverses the hyperedge tree and creates connectors for each -// segment bridging junction and/or terminals. It also sets the -// appropriate ConnEnds for each connector. -// -void HyperedgeTreeEdge::addConns(HyperedgeTreeNode *ignored, Router *router, - ConnRefList& oldConns) -{ - COLA_ASSERT(conn != NULL); - HyperedgeTreeNode *endNode = NULL; - if (ends.first && (ends.first != ignored)) - { - endNode = ends.first; - ends.first->addConns(this, router, oldConns, conn); - } - - if (ends.second && (ends.second != ignored)) - { - endNode = ends.second; - ends.second->addConns(this, router, oldConns, conn); - } - - if (endNode->finalVertex) - { - // We have reached a terminal of the hyperedge, so set a ConnEnd for - // the original connector endpoint - ConnEnd connend; - bool result = false; - // Find the ConnEnd from the list of original connectors. - for (ConnRefList::iterator curr = oldConns.begin(); - curr != oldConns.end(); ++curr) - { - result |= (*curr)->getConnEndForEndpointVertex( - endNode->finalVertex, connend); - if (result) - { - break; - } - } - if (result) - { - // XXX: Create new conn here. - conn->updateEndPoint(VertID::tar, connend); - } - } - else if (endNode->junction) - { - // Or, set a ConnEnd connecting to the junction we have reached. - ConnEnd connend(endNode->junction); - conn->updateEndPoint(VertID::tar, connend); - } -} - - -// This method traverses the hyperedge tree and rewrites connector ends -// that may have changed junctions due to major hyperedge improvement. -// -void HyperedgeTreeEdge::updateConnEnds(HyperedgeTreeNode *ignored, - bool forward, ConnRefList& changedConns) -{ - HyperedgeTreeNode *endNode = NULL; - if (ends.first && (ends.first != ignored)) - { - endNode = ends.first; - ends.first->updateConnEnds(this, forward, changedConns); - } - - if (ends.second && (ends.second != ignored)) - { - endNode = ends.second; - ends.second->updateConnEnds(this, forward, changedConns); - } - - if (endNode->junction) - { - // We've reached a junction at the end of this connector, and it's - // not an endpoint of the hyperedge. So the connector ConnEnd to - // connect to the junction we have reached. - std::pair<ConnEnd, ConnEnd> existingEnds = conn->endpointConnEnds(); - ConnEnd existingEnd = (forward) ? - existingEnds.second : existingEnds.first; - if (existingEnd.junction() != endNode->junction) - { -#ifdef MAJOR_HYPEREDGE_IMPROVEMENT_DEBUG - fprintf(stderr, "HyperedgeImprover: changed %s of " - "connector %u (from junction %u to %u)\n", - (forward) ? "tar" : "src", conn->id(), - existingEnd.junction()->id(), endNode->junction->id()); -#endif - ConnEnd connend(endNode->junction); - unsigned short end = (forward) ? VertID::tar : VertID::src; - conn->updateEndPoint(end, connend); - - // Record that this connector was changed (so long as it wasn't - // already recorded). - if (changedConns.empty() || (changedConns.back() != conn)) - { - changedConns.push_back(conn); - } - } - } -} - -// This method traverses the hyperedge tree and returns a list of the junctions -// and connectors that make up the hyperedge. -// -void HyperedgeTreeEdge::listJunctionsAndConnectors(HyperedgeTreeNode *ignored, - JunctionRefList& junctions, ConnRefList& connectors) -{ - ConnRefList::iterator foundPosition = - std::find(connectors.begin(), connectors.end(), conn); - if (foundPosition == connectors.end()) - { - // Add connector if it isn't already in the list. - connectors.push_back(conn); - } - - if (ends.first != ignored) - { - ends.first->listJunctionsAndConnectors(this, junctions, connectors); - } - else if (ends.second != ignored) - { - ends.second->listJunctionsAndConnectors(this, junctions, connectors); - } -} - - -void HyperedgeTreeEdge::validateHyperedge( - const HyperedgeTreeNode *ignored, const size_t dist) const -{ -#ifdef MAJOR_HYPEREDGE_IMPROVEMENT_DEBUG - for (size_t d = 0; d < dist; ++d) - { - fprintf(stderr, " "); - } - fprintf(stderr, "-(%d)\n", conn->id()); -#endif - if (ends.first != ignored) - { - ends.first->validateHyperedge(this, dist); - } - else if (ends.second != ignored) - { - ends.second->validateHyperedge(this, dist); - } -} - - -// This method splits the current edge, adding a node at the given point. -// The current edge will connect the source node and the newly created node. -// A new edge will connect the new node and the node at the other end of the -// original edge. -// -void HyperedgeTreeEdge::splitFromNodeAtPoint(HyperedgeTreeNode *source, - const Point& point) -{ - // Make the source the first of the two nodes. - if (ends.second == source) - { - std::swap(ends.second, ends.first); - } - COLA_ASSERT(ends.first == source); - - // Remember the other end. - HyperedgeTreeNode *target = ends.second; - - // Create a new node for the split point at the given position. - HyperedgeTreeNode *split = new HyperedgeTreeNode(); - split->point = point; - - // Create a new edge between the split point and the other end. - new HyperedgeTreeEdge(split, target, conn); - - // Disconnect the current edge from the other end and connect it to - // the new split point node. - target->disconnectEdge(this); - ends.second = split; - split->edges.push_back(this); -} - - -// This method disconnects the hyperedge tree edge nodes that it's attached to. -// -void HyperedgeTreeEdge::disconnectEdge(void) -{ - COLA_ASSERT(ends.first != NULL); - COLA_ASSERT(ends.second != NULL); - - ends.first->disconnectEdge(this); - ends.second->disconnectEdge(this); - ends.first = NULL; - ends.second = NULL; -} - - -// This method traverses the hyperedge tree and removes from treeRoots any -// junction nodes. -// -bool HyperedgeTreeEdge::removeOtherJunctionsFrom(HyperedgeTreeNode *ignored, - JunctionSet& treeRoots) -{ - bool containsCycle = false; - if (ends.first && (ends.first != ignored)) - { - containsCycle |= ends.first->removeOtherJunctionsFrom(this, treeRoots); - } - - if (ends.second && (ends.second != ignored)) - { - containsCycle |= ends.second->removeOtherJunctionsFrom(this, treeRoots); - } - return containsCycle; -} - - -// This method traverses the hyperedge tree, clearing up the objects and -// memory used to store the tree. -// -void HyperedgeTreeEdge::deleteNodesExcept(HyperedgeTreeNode *ignored) -{ - if (ends.first && (ends.first != ignored)) - { - ends.first->deleteEdgesExcept(this); - delete ends.first; - } - ends.first = NULL; - - if (ends.second && (ends.second != ignored)) - { - ends.second->deleteEdgesExcept(this); - delete ends.second; - } - ends.second = NULL; -} - - -CmpNodesInDim::CmpNodesInDim(const size_t dim) - : m_dimension(dim) -{ -} - - -// Nodes in set are ordered by position along a line in a certain dimension, -// and then by Node pointer since multiple may exist at a particular position. -bool CmpNodesInDim::operator()(const HyperedgeTreeNode *lhs, - const HyperedgeTreeNode *rhs) const -{ - if (lhs->point[m_dimension] != rhs->point[m_dimension]) - { - return lhs->point[m_dimension] < rhs->point[m_dimension]; - } - return lhs < rhs; -} - -} - |