diff options
Diffstat (limited to 'src/libavoid/router.cpp')
| -rw-r--r-- | src/libavoid/router.cpp | 3131 |
1 files changed, 0 insertions, 3131 deletions
diff --git a/src/libavoid/router.cpp b/src/libavoid/router.cpp deleted file mode 100644 index 84f919f3d..000000000 --- a/src/libavoid/router.cpp +++ /dev/null @@ -1,3131 +0,0 @@ -/* - * vim: ts=4 sw=4 et tw=0 wm=0 - * - * libavoid - Fast, Incremental, Object-avoiding Line Router - * - * Copyright (C) 2004-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 <cmath> -#include <cfloat> - -#include "libavoid/shape.h" -#include "libavoid/router.h" -#include "libavoid/visibility.h" -#include "libavoid/connector.h" -#include "libavoid/junction.h" -#include "libavoid/viscluster.h" -#include "libavoid/connend.h" -#include "libavoid/debug.h" -#include "libavoid/orthogonal.h" -#include "libavoid/assertions.h" -#include "libavoid/connectionpin.h" - - -namespace Avoid { - - -Router::Router(const unsigned int flags) - : visOrthogGraph(), - PartialTime(false), - SimpleRouting(false), - ClusteredRouting(true), - // Poly-line algorithm options: - IgnoreRegions(true), - UseLeesAlgorithm(true), - InvisibilityGrph(true), - // General algorithm options: - SelectiveReroute(true), - PartialFeedback(false), - RubberBandRouting(false), - // Instrumentation: - st_checked_edges(0), - m_largest_assigned_id(0), - m_consolidate_actions(true), - m_currently_calling_destructors(false), - m_topology_addon(new TopologyAddonInterface()), - // Mode options: - m_allows_polyline_routing(false), - m_allows_orthogonal_routing(false), - m_static_orthogonal_graph_invalidated(true), - m_in_crossing_rerouting_stage(false), - m_settings_changes(false), - m_debug_handler(NULL) -{ - // At least one of the Routing modes must be set. - COLA_ASSERT(flags & (PolyLineRouting | OrthogonalRouting)); - - if (flags & PolyLineRouting) - { - m_allows_polyline_routing = true; - } - if (flags & OrthogonalRouting) - { - m_allows_orthogonal_routing = true; - } - - for (size_t p = 0; p < lastRoutingParameterMarker; ++p) - { - m_routing_parameters[p] = 0.0; - } - m_routing_parameters[segmentPenalty] = 10; - m_routing_parameters[clusterCrossingPenalty] = 4000; - m_routing_parameters[idealNudgingDistance] = 4.0; - - m_routing_options[nudgeOrthogonalSegmentsConnectedToShapes] = false; - m_routing_options[improveHyperedgeRoutesMovingJunctions] = true; - m_routing_options[penaliseOrthogonalSharedPathsAtConnEnds] = false; - m_routing_options[nudgeOrthogonalTouchingColinearSegments] = false; - m_routing_options[performUnifyingNudgingPreprocessingStep] = true; - m_routing_options[improveHyperedgeRoutesMovingAddingAndDeletingJunctions] = - false; - m_routing_options[nudgeSharedPathsWithCommonEndPoint] = true; - - m_hyperedge_improver.setRouter(this); - m_hyperedge_rerouter.setRouter(this); -} - - -Router::~Router() -{ - m_currently_calling_destructors = true; - - // Delete remaining connectors. - ConnRefList::iterator conn = connRefs.begin(); - while (conn != connRefs.end()) - { - db_printf("Deleting connector %u in ~Router()\n", (*conn)->id()); - delete *conn; - conn = connRefs.begin(); - } - - // Remove remaining obstacles (shapes and junctions). - ObstacleList::iterator obstacle = m_obstacles.begin(); - while (obstacle != m_obstacles.end()) - { - Obstacle *obstaclePtr = *obstacle; - ShapeRef *shape = dynamic_cast<ShapeRef *> (obstaclePtr); - db_printf("Deleting %s %u in ~Router()\n", - (shape) ? "shape" : "junction", obstaclePtr->id()); - if (obstaclePtr->isActive()) - { - obstaclePtr->removeFromGraph(); - obstaclePtr->makeInactive(); - } - delete obstaclePtr; - obstacle = m_obstacles.begin(); - } - m_currently_calling_destructors = false; - - // Cleanup orphaned orthogonal graph vertices. - destroyOrthogonalVisGraph(); - - COLA_ASSERT(m_obstacles.size() == 0); - COLA_ASSERT(connRefs.size() == 0); - COLA_ASSERT(visGraph.size() == 0); - - delete m_topology_addon; -} - -void Router::setDebugHandler(DebugHandler *handler) -{ - m_debug_handler = handler; -} - -DebugHandler *Router::debugHandler(void) const -{ - return m_debug_handler; -} - -ShapeRef *Router::shapeContainingPoint(const Point& point) -{ - // Count points on the border as being inside. - bool countBorder = true; - - // Compute enclosing shapes. - ObstacleList::const_iterator finish = m_obstacles.end(); - for (ObstacleList::const_iterator i = m_obstacles.begin(); i != finish; ++i) - { - ShapeRef *shape = dynamic_cast<ShapeRef *>(*i); - if (shape && inPoly(shape->routingPolygon(), point, countBorder)) - { - return shape; - } - } - return NULL; -} - -void Router::modifyConnector(ConnRef *conn, const unsigned int type, - const ConnEnd& connEnd, bool connPinMoveUpdate) -{ - ActionInfo modInfo(ConnChange, conn); - - ActionInfoList::iterator found = - find(actionList.begin(), actionList.end(), modInfo); - if (found == actionList.end()) - { - // Matching action not found, so add. - modInfo.conns.push_back(std::make_pair(type, connEnd)); - actionList.push_back(modInfo); - } - else - { - // Update the found action as necessary. - found->addConnEndUpdate(type, connEnd, connPinMoveUpdate); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - - -void Router::modifyConnector(ConnRef *conn) -{ - ActionInfo modInfo(ConnChange, conn); - - ActionInfoList::iterator found = - find(actionList.begin(), actionList.end(), modInfo); - if (found == actionList.end()) - { - actionList.push_back(modInfo); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - - -void Router::modifyConnectionPin(ShapeConnectionPin *pin) -{ - ActionInfo modInfo(ConnectionPinChange, pin); - - ActionInfoList::iterator found = - find(actionList.begin(), actionList.end(), modInfo); - if (found == actionList.end()) - { - actionList.push_back(modInfo); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - - -void Router::removeObjectFromQueuedActions(const void *object) -{ - for (ActionInfoList::iterator curr = actionList.begin(); - curr != actionList.end(); ) - { - if (curr->objPtr == object) - { - curr = actionList.erase(curr); - } - else - { - ++curr; - } - } -} - - -void Router::addShape(ShapeRef *shape) -{ - // There shouldn't be remove events or move events for the same shape - // already in the action list. - // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), - ActionInfo(ShapeRemove, shape)) == actionList.end()); - COLA_ASSERT(find(actionList.begin(), actionList.end(), - ActionInfo(ShapeMove, shape)) == actionList.end()); - - ActionInfo addInfo(ShapeAdd, shape); - - ActionInfoList::iterator found = - find(actionList.begin(), actionList.end(), addInfo); - if (found == actionList.end()) - { - actionList.push_back(addInfo); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - - -void Router::deleteShape(ShapeRef *shape) -{ - // There shouldn't be add events events for the same shape already - // in the action list. - // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), - ActionInfo(ShapeAdd, shape)) == actionList.end()); - - // Delete any ShapeMove entries for this shape in the action list. - ActionInfoList::iterator found = find(actionList.begin(), - actionList.end(), ActionInfo(ShapeMove, shape)); - if (found != actionList.end()) - { - actionList.erase(found); - } - - // Add the ShapeRemove entry. - ActionInfo remInfo(ShapeRemove, shape); - found = find(actionList.begin(), actionList.end(), remInfo); - if (found == actionList.end()) - { - actionList.push_back(remInfo); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - - -void Router::deleteConnector(ConnRef *connector) -{ - m_currently_calling_destructors = true; - delete connector; - m_currently_calling_destructors = false; -} - -void Router::moveShape(ShapeRef *shape, const double xDiff, const double yDiff) -{ - ActionInfo moveInfo(ShapeMove, shape, Polygon(), false); - ActionInfoList::iterator found = - find(actionList.begin(), actionList.end(), moveInfo); - - Polygon newPoly; - if (found != actionList.end()) - { - // The shape already has a queued move, so use that shape position. - newPoly = found->newPoly; - } - else - { - // Just use the existing position. - newPoly = shape->polygon(); - } - newPoly.translate(xDiff, yDiff); - - moveShape(shape, newPoly); -} - - -void Router::markAllObstaclesAsMoved(void) -{ - for (ObstacleList::iterator obstacleIt = m_obstacles.begin(); - obstacleIt != m_obstacles.end(); ++obstacleIt) - { - ShapeRef *shape = dynamic_cast<ShapeRef *> (*obstacleIt); - JunctionRef *junction = dynamic_cast<JunctionRef *> (*obstacleIt); - if (shape) - { - moveShape(shape, 0, 0); - } - else if (junction) - { - moveJunction(junction, 0, 0); - } - } -} - -void Router::moveShape(ShapeRef *shape, const Polygon& newPoly, - const bool first_move) -{ - // There shouldn't be remove events or add events for the same shape - // already in the action list. - // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), - ActionInfo(ShapeRemove, shape)) == actionList.end()); - - ActionInfoList::iterator found = find(actionList.begin(), - actionList.end(), ActionInfo(ShapeAdd, shape)); - if (found != actionList.end()) - { - // The Add is enough, no need for the Move action too. - // The shape will be added with it's existing polygon, - // so set this to be the newPoly passed for the move. - found->shape()->setNewPoly(newPoly); - return; - } - - ActionInfo moveInfo(ShapeMove, shape, newPoly, first_move); - // Sanely cope with the case where the user requests moving the same - // shape multiple times before rerouting connectors. - found = find(actionList.begin(), actionList.end(), moveInfo); - - if (found != actionList.end()) - { - // Just update the ActionInfo with the second polygon, but - // leave the firstMove setting alone. - found->newPoly = newPoly; - } - else - { - actionList.push_back(moveInfo); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - - -void Router::setStaticGraphInvalidated(const bool invalidated) -{ - m_static_orthogonal_graph_invalidated = invalidated; -} - - -void Router::destroyOrthogonalVisGraph(void) -{ - // Remove orthogonal visibility graph edges. - visOrthogGraph.clear(); - - // Remove the now orphaned vertices. - VertInf *curr = vertices.shapesBegin(); - while (curr) - { - if (curr->orphaned() && (curr->id == dummyOrthogID)) - { - VertInf *following = vertices.removeVertex(curr); - delete curr; - curr = following; - continue; - } - curr = curr->lstNext; - } -} - - -void Router::regenerateStaticBuiltGraph(void) -{ - // Here we do talks involved in updating the static-built visibility - // graph (if necessary) before we do any routing. - if (m_static_orthogonal_graph_invalidated) - { - if (m_allows_orthogonal_routing) - { - destroyOrthogonalVisGraph(); - - TIMER_START(this, tmOrthogGraph); - // Regenerate a new visibility graph. - generateStaticOrthogonalVisGraph(this); - - TIMER_STOP(this); - } - m_static_orthogonal_graph_invalidated = false; - } -} - - -bool Router::transactionUse(void) const -{ - return m_consolidate_actions; -} - - -void Router::setTransactionUse(const bool transactions) -{ - m_consolidate_actions = transactions; -} - - -// Processes the action list. -void Router::processActions(void) -{ - bool notPartialTime = !(PartialFeedback && PartialTime); - bool seenShapeMovesOrDeletes = false; - - m_transaction_start_time = clock(); - m_abort_transaction = false; - - std::list<unsigned int> deletedObstacles; - actionList.sort(); - ActionInfoList::iterator curr; - ActionInfoList::iterator finish = actionList.end(); - for (curr = actionList.begin(); curr != finish; ++curr) - { - ActionInfo& actInf = *curr; - if (!((actInf.type == ShapeRemove) || (actInf.type == ShapeMove) || - (actInf.type == JunctionRemove) || (actInf.type == JunctionMove))) - { - // Not a move or remove action, so don't do anything. - continue; - } - seenShapeMovesOrDeletes = true; - - Obstacle *obstacle = actInf.obstacle(); - ShapeRef *shape = actInf.shape(); - JunctionRef *junction = actInf.junction(); - bool isMove = (actInf.type == ShapeMove) || - (actInf.type == JunctionMove);; - bool first_move = actInf.firstMove; - - unsigned int pid = obstacle->id(); - - // o Remove entries related to this shape's vertices - obstacle->removeFromGraph(); - - if (SelectiveReroute && (!isMove || notPartialTime || first_move)) - { - markPolylineConnectorsNeedingReroutingForDeletedObstacle(obstacle); - } - - adjustContainsWithDel(pid); - - if (isMove) - { - if (shape) - { - shape->moveAttachedConns(actInf.newPoly); - } - else if (junction) - { - junction->moveAttachedConns(actInf.newPosition); - } - } - - // Ignore this shape for visibility. - // XXX: We don't really need to do this if we're not using Partial - // Feedback. Without this the blocked edges still route - // around the shape until it leaves the connector. - obstacle->makeInactive(); - - if (!isMove) - { - // Free deleted obstacle. - m_currently_calling_destructors = true; - deletedObstacles.push_back(obstacle->id()); - delete obstacle; - m_currently_calling_destructors = false; - } - } - - if (seenShapeMovesOrDeletes && m_allows_polyline_routing) - { - if (InvisibilityGrph) - { - // Check edges for obstacles that were moved or removed. - for (curr = actionList.begin(); curr != finish; ++curr) - { - ActionInfo& actInf = *curr; - if ((actInf.type == ShapeMove) || (actInf.type == JunctionMove)) - { - // o Check all edges that were blocked by moved obstacle. - checkAllBlockedEdges(actInf.obstacle()->id()); - } - } - - for (std::list<unsigned int>::iterator it = deletedObstacles.begin(); - it != deletedObstacles.end(); ++it) - { - // o Check all edges that were blocked by deleted obstacle. - checkAllBlockedEdges(*it); - } - } - else - { - // check all edges not in graph - checkAllMissingEdges(); - } - } - - for (curr = actionList.begin(); curr != finish; ++curr) - { - ActionInfo& actInf = *curr; - if (!((actInf.type == ShapeAdd) || (actInf.type == ShapeMove) || - (actInf.type == JunctionAdd) || (actInf.type == JunctionMove))) - { - // Not a move or add action, so don't do anything. - continue; - } - - Obstacle *obstacle = actInf.obstacle(); - ShapeRef *shape = actInf.shape(); - JunctionRef *junction = actInf.junction(); - Polygon& newPoly = actInf.newPoly; - bool isMove = (actInf.type == ShapeMove) || - (actInf.type == JunctionMove); - - unsigned int pid = obstacle->id(); - - // Restore this shape for visibility. - obstacle->makeActive(); - - if (isMove) - { - if (shape) - { - shape->setNewPoly(newPoly); - } - else - { - junction->setPosition(actInf.newPosition); - } - } - const Polygon& shapePoly = obstacle->routingPolygon(); - - adjustContainsWithAdd(shapePoly, pid); - - if (m_allows_polyline_routing) - { - // o Check all visibility edges to see if this one shape - // blocks them. - if (!isMove || notPartialTime) - { - newBlockingShape(shapePoly, pid); - } - - // o Calculate visibility for the new vertices. - if (UseLeesAlgorithm) - { - obstacle->computeVisibilitySweep(); - } - else - { - obstacle->computeVisibilityNaive(); - } - obstacle->updatePinPolyLineVisibility(); - } - } - - // Update connector endpoints. - for (curr = actionList.begin(); curr != finish; ++curr) - { - ActionInfo& actInf = *curr; - if (actInf.type != ConnChange) - { - continue; - } - for (ConnUpdateList::iterator conn = actInf.conns.begin(); - conn != actInf.conns.end(); ++conn) - { - actInf.conn()->updateEndPoint(conn->first, conn->second); - } - } - // Clear the actionList. - actionList.clear(); -} - -bool Router::processTransaction(void) -{ - // If SimpleRouting, then don't update here. - if ((actionList.empty() && (m_hyperedge_rerouter.count() == 0) && - (m_settings_changes == false)) || SimpleRouting) - { - return false; - } - m_settings_changes = false; - - processActions(); - - m_static_orthogonal_graph_invalidated = true; - rerouteAndCallbackConnectors(); - - return true; -} - - -void Router::addJunction(JunctionRef *junction) -{ - // There shouldn't be remove events or move events for the same junction - // already in the action list. - // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), - ActionInfo(JunctionRemove, junction)) == actionList.end()); - COLA_ASSERT(find(actionList.begin(), actionList.end(), - ActionInfo(JunctionMove, junction)) == actionList.end()); - - ActionInfo addInfo(JunctionAdd, junction); - - ActionInfoList::iterator found = - find(actionList.begin(), actionList.end(), addInfo); - if (found == actionList.end()) - { - actionList.push_back(addInfo); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - - -void Router::deleteJunction(JunctionRef *junction) -{ - // There shouldn't be add events events for the same junction already - // in the action list. - // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), - ActionInfo(JunctionAdd, junction)) == actionList.end()); - - // Delete any ShapeMove entries for this shape in the action list. - ActionInfoList::iterator found = find(actionList.begin(), - actionList.end(), ActionInfo(JunctionMove, junction)); - if (found != actionList.end()) - { - actionList.erase(found); - } - - // Add the ShapeRemove entry. - ActionInfo remInfo(JunctionRemove, junction); - found = find(actionList.begin(), actionList.end(), remInfo); - if (found == actionList.end()) - { - actionList.push_back(remInfo); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - - -void Router::moveJunction(JunctionRef *junction, const double xDiff, - const double yDiff) -{ - ActionInfo moveInfo(JunctionMove, junction, Point()); - ActionInfoList::iterator found = - find(actionList.begin(), actionList.end(), moveInfo); - - Point newPosition; - if (found != actionList.end()) - { - // The junction already has a queued move, so use that position. - newPosition = found->newPosition; - } - else - { - // Just use the existing position. - newPosition = junction->position(); - } - newPosition.x += xDiff; - newPosition.y += yDiff; - - moveJunction(junction, newPosition); -} - - -void Router::moveJunction(JunctionRef *junction, const Point& newPosition) -{ - // There shouldn't be remove events or add events for the same junction - // already in the action list. - // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), - ActionInfo(JunctionRemove, junction)) == actionList.end()); - - ActionInfoList::iterator found = find(actionList.begin(), - actionList.end(), ActionInfo(JunctionAdd, junction)); - if (found != actionList.end()) - { - // The Add is enough, no need for the Move action too. - // The junction will be added with the new position. - found->junction()->setPosition(newPosition); - return; - } - - ActionInfo moveInfo(JunctionMove, junction, newPosition); - // Sanely cope with the case where the user requests moving the same - // shape multiple times before rerouting connectors. - found = find(actionList.begin(), actionList.end(), moveInfo); - - if (found != actionList.end()) - { - // Just update the ActionInfo with the second position. - found->newPosition = newPosition; - } - else - { - actionList.push_back(moveInfo); - } - - if (!m_consolidate_actions) - { - processTransaction(); - } -} - -void Router::addCluster(ClusterRef *cluster) -{ - cluster->makeActive(); - - unsigned int pid = cluster->id(); - ReferencingPolygon& poly = cluster->polygon(); - - adjustClustersWithAdd(poly, pid); -} - - -void Router::deleteCluster(ClusterRef *cluster) -{ - cluster->makeInactive(); - - unsigned int pid = cluster->id(); - - adjustClustersWithDel(pid); -} - - -unsigned int Router::newObjectId(void) const -{ - return m_largest_assigned_id + 1; -} - - -unsigned int Router::assignId(const unsigned int suggestedId) -{ - // If the suggestedId is zero, then we assign the object the next - // smallest unassigned ID, otherwise we trust the ID given is unique. - unsigned int assignedId = (suggestedId == 0) ? newObjectId() : suggestedId; - - // If assertions are enabled, then we check that this ID really is unique. - COLA_ASSERT(objectIdIsUnused(assignedId)); - - // Have the router record if this ID is larger than the largest assigned ID. - m_largest_assigned_id = std::max(m_largest_assigned_id, assignedId); - - return assignedId; -} - - - // Returns whether the given ID is unique among all objects known by the - // router. It is expected this is only going to be called from assertions - // while debugging, so efficiency is not an issue and we just iterate over - // all objects. -bool Router::objectIdIsUnused(const unsigned int id) const -{ - // Examine shapes/junctions. - for (ObstacleList::const_iterator i = m_obstacles.begin(); - i != m_obstacles.end(); ++i) - { - if ((*i)->id() == id) - { - return false; - } - } - - // Examine connectors. - for (ConnRefList::const_iterator i = connRefs.begin(); - i != connRefs.end(); ++i) - { - if ((*i)->id() == id) - { - return false; - } - } - - // Examine clusters. - for (ClusterRefList::const_iterator i = clusterRefs.begin(); - i != clusterRefs.end(); ++i) - { - if ((*i)->id() == id) - { - return false; - } - } - - return true; -} - - -//---------------------------------------------------------------------------- - - // Returns a list of connector Ids of all the connectors of type - // 'type' attached to the shape with the ID 'shapeId'. -void Router::attachedConns(IntList &conns, const unsigned int shapeId, - const unsigned int type) -{ - ConnRefList::const_iterator fin = connRefs.end(); - for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) - { - std::pair<Obstacle *, Obstacle *> anchors = (*i)->endpointAnchors(); - - if ((type & runningTo) && - (anchors.second && (anchors.second->id() == shapeId))) - { - conns.push_back((*i)->id()); - } - else if ((type & runningFrom) && - (anchors.first && (anchors.first->id() == shapeId))) - { - conns.push_back((*i)->id()); - } - } -} - - - // Returns a list of shape Ids of all the shapes attached to the - // shape with the ID 'shapeId' with connection type 'type'. -void Router::attachedShapes(IntList &shapes, const unsigned int shapeId, - const unsigned int type) -{ - ConnRefList::const_iterator fin = connRefs.end(); - for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) - { - std::pair<Obstacle *, Obstacle *> anchors = (*i)->endpointAnchors(); - - if ((type & runningTo) && - (anchors.second && (anchors.second->id() == shapeId))) - { - if (anchors.first) - { - // Only if there is a shape attached to the other end. - shapes.push_back(anchors.first->id()); - } - } - else if ((type & runningFrom) && - (anchors.first && (anchors.first->id() == shapeId))) - { - if (anchors.second) - { - // Only if there is a shape attached to the other end. - shapes.push_back(anchors.second->id()); - } - } - } -} - - - // It's intended this function is called after visibility changes - // resulting from shape movement have happened. It will alert - // rerouted connectors (via a callback) that they need to be redrawn. -void Router::rerouteAndCallbackConnectors(void) -{ - ConnRefList reroutedConns; - ConnRefList::const_iterator fin = connRefs.end(); - - this->m_conn_reroute_flags.alertConns(); - - // Updating the orthogonal visibility graph if necessary. - regenerateStaticBuiltGraph(); - - for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) - { - (*i)->freeActivePins(); - } - - // Calculate and return connectors that are part of hyperedges and will - // be completely rerouted by that code and thus don't need to have routes - // generated here. - ConnRefSet hyperedgeConns = - m_hyperedge_rerouter.calcHyperedgeConnectors(); - - // TODO: It might be worth sorting connectors and routing them from - // smallest to largest estimated cost. This way we likely get - // better exclusive pin assignment during initial routing. - - size_t totalConns = connRefs.size(); - size_t numOfReroutedConns = 0; - for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) - { - // Progress reporting and continuation check. - performContinuationCheck(TransactionPhaseRouteSearch, - numOfReroutedConns, totalConns); - ++numOfReroutedConns; - - ConnRef *connector = *i; - if (hyperedgeConns.find(connector) != hyperedgeConns.end()) - { - // This will be rerouted by the hyperedge code, so do nothing. - continue; - } - - if (connector->hasFixedRoute()) - { - // We don't reroute connectors with fixed routes. - continue; - } - - TIMER_START(this, tmOrthogRoute); - connector->m_needs_repaint = false; - bool rerouted = connector->generatePath(); - if (rerouted) - { - reroutedConns.push_back(connector); - } - TIMER_STOP(this); - } - - - // Perform any complete hyperedge rerouting that has been requested. - m_hyperedge_rerouter.performRerouting(); - - // Find and reroute crossing connectors if crossing penalties are set. - improveCrossings(); - - bool withMinorImprovements = routingOption( - improveHyperedgeRoutesMovingJunctions); - bool withMajorImprovements = routingOption( - improveHyperedgeRoutesMovingAddingAndDeletingJunctions); - if (withMinorImprovements || withMajorImprovements) - { - m_hyperedge_improver.clear(); - m_hyperedge_improver.execute(withMajorImprovements); - } - - // Perform centring and nudging for orthogonal routes. - improveOrthogonalRoutes(this); - - // Find a list of all the deleted connectors in hyperedges. - HyperedgeNewAndDeletedObjectLists changedHyperedgeObjs = - m_hyperedge_improver.newAndDeletedObjectLists(); - ConnRefList deletedConns = changedHyperedgeObjs.deletedConnectorList; - for (size_t index = 0; index < m_hyperedge_rerouter.count(); ++index) - { - changedHyperedgeObjs = - m_hyperedge_rerouter.newAndDeletedObjectLists(index); - deletedConns.merge(changedHyperedgeObjs.deletedConnectorList); - } - - // Alert connectors that they need redrawing. - fin = reroutedConns.end(); - for (ConnRefList::const_iterator i = reroutedConns.begin(); i != fin; ++i) - { - ConnRef *conn = *i; - - // Skip hyperedge connectors which have been deleted. - ConnRefList::iterator findIt = std::find( - deletedConns.begin(), deletedConns.end(), conn); - if (findIt != deletedConns.end()) - { - // Connector deleted, skip. - continue; - } - - conn->m_needs_repaint = true; - conn->performCallback(); - } - - // Progress reporting. - performContinuationCheck(TransactionPhaseCompleted, 1, 1); -} - -// Type holding a cost estimate and ConnRef. -typedef std::pair<double, ConnRef *> ConnCostRef; - -// A comparison class used to order a set of ConnCostRefs. -class CmpConnCostRef -{ - public: - CmpConnCostRef() - { - } - bool operator() (const ConnCostRef& u, const ConnCostRef& v) const - { - return (u.second->id() < v.second->id()); - } -}; - -typedef std::set<ConnCostRef, CmpConnCostRef> ConnCostRefSet; -typedef std::list<ConnCostRefSet> ConnCostRefSetList; - - -static double cheapEstimatedCost(ConnRef *lineRef) -{ - // We use an estimate of overall connector length, reduced by a count - // of the number of segments. In the case of equal length, This causes - // straight line connectors to be left alone and connectors with more - // complex paths to be rerouted. - bool isPolyLine = (lineRef->routingType() == ConnType_PolyLine); - const PolyLine& route = lineRef->displayRoute(); - double length = 0; - - for (size_t i = 1; i < route.size(); ++i) - { - const Point& a = route.ps[i - 1]; - const Point& b = route.ps[i]; - - double segmentLength = (isPolyLine) ? - euclideanDist(a, b) : manhattanDist(a, b); - length += segmentLength; - } - return length - (route.size() + 1); -} - -// A map of connectors to the set of connectors that cross them. -typedef std::map<ConnRef *, std::set<ConnRef *> > CrossingConnectorsMap; - -// A list of connector crossing maps that don't interact with each other. -typedef std::list<CrossingConnectorsMap> CrossingConnectorsMapList; - -// This class maintains the list of connector crossing maps and provides -// methods for adding crossing connector pairs and getting the minimal sets -// of connectors that can be removed from each group to prevent crossings. -class CrossingConnectorsInfo -{ - public: - - // Add information that a pair of connectors cross. - void addCrossing(ConnRef *conn1, ConnRef *conn2) - { - // Find the existing or new group that this crossing - // should be recorded in. - CrossingConnectorsMapList::iterator it = - groupForCrossingConns(conn1, conn2); - CrossingConnectorsMap& pairsSet = *it; - - // Record the crossing. - pairsSet[conn1].insert(conn2); - pairsSet[conn2].insert(conn1); - } - - // This method builds and returns a list of non-interacting sets of - // connectors (with crossing counts) that need to be removed so there - // are no crossings. These are the connectors we reroute. Where - // these connectors attach to exclusive connection pins, we return - // and thus reroute all connectors attached to the exlcusive pins. We - // do this so we are no so committed to possible bad pin assignemnts. - ConnCostRefSetList crossingSetsListToRemoveCrossingsFromGroups(void) - { - // A list of the minimal sets of connectors that cause crossings - // in all groups of crossingconnectors. - ConnCostRefSetList crossingSetsList; - - // For each group of crossing connectors. - for (CrossingConnectorsMapList::iterator it = pairsSetList.begin(); - it != pairsSetList.end(); ++it) - { - // The minimal set of crossing-causing connectors. - // We will build this. - ConnCostRefSet crossingSet; - - // Set of exclusive pins that the crossing-causing connectors - // attach to. - std::set<ConnectionPinIds> exclusivePins; - - // The group of all crossing pairs. - CrossingConnectorsMap& pairsSet = *it; - - // For each crossing-causing connector. - ConnCostRef crossingCausingConnector; - while ( (crossingCausingConnector = - removeConnectorWithMostCrossings(pairsSet)).second != NULL ) - { - // Add it to our crossing-causing set. - crossingSet.insert(crossingCausingConnector); - - // Determine if it attaches to any exclusive pins and - // record these. - std::pair<ConnEnd, ConnEnd> ends = - crossingCausingConnector.second->endpointConnEnds(); - // Look at one end. - ShapeConnectionPin *pin = ends.first.m_active_pin; - if (pin && pin->isExclusive()) - { - exclusivePins.insert(pin->ids()); - } - // Look at other end. - pin = ends.second.m_active_pin; - if (pin && pin->isExclusive()) - { - exclusivePins.insert(pin->ids()); - } - } - - // For each of the remaining connectors which are not - // crossing-causing, add them to our crossing set if they - // attach to one of the exclusive pin classes which the - // crossing-causing connectors attached to. - for (CrossingConnectorsMap::const_iterator it2 = - pairsSet.begin(); it2 != pairsSet.end(); ++it2) - { - ConnRef *conn = it2->first; - std::pair<ConnEnd, ConnEnd> ends = conn->endpointConnEnds(); - // Look at one end. - ShapeConnectionPin *pin = ends.first.m_active_pin; - if (pin && pin->isExclusive()) - { - if (exclusivePins.count(pin->ids()) > 0) - { - // Attaches to an exclusive pin and it matches - // one attached to by the crossing-causing - // connectors. So add the conn to the - // crossing set and continue.. - crossingSet.insert(std::make_pair(0, conn)); - continue; - } - } - // Look at other end. - pin = ends.second.m_active_pin; - if (pin && pin->isExclusive()) - { - if (exclusivePins.count(pin->ids()) > 0) - { - // Attaches to an exclusive pin and it matches - // one attached to by the crossing-causing - // connectors. So add the conn to the - // crossing set. - crossingSet.insert(std::make_pair(0, conn)); - } - } - } - - if (!crossingSet.empty()) - { - crossingSetsList.push_back(crossingSet); - } - } - return crossingSetsList; - } - - // Returns whether this pair of connector is already known to cross. - bool connsKnownToCross(ConnRef *conn1, ConnRef *conn2) - { - CrossingConnectorsMapList::iterator it1 = groupForConn(conn1); - CrossingConnectorsMapList::iterator it2 = groupForConn(conn2); - - // The connectors cross if - if ((it1 == it2) && (it1 != pairsSetList.end())) - { - // They are in the same group and conn2 is in crossing - // connectors set of conn1. - CrossingConnectorsMap& pairsSet = *it1; - return ((pairsSet.count(conn1) > 0) && - (pairsSet[conn1].count(conn2) > 0)); - } - return false; - } - - private: - - // Given a particular group (pairsSet), removes the connector with - // the most crossings withing the group and returns it along with its - // crossing count. - ConnCostRef removeConnectorWithMostCrossings( - CrossingConnectorsMap& pairsSet) - { - // Tracking of the greatest number of crossings. - ConnRef *candidateConnector = NULL; - size_t candidateCrossingCount = 0; - double candidateEstimatedCost = 0; - - // For each connector in the group... - for (CrossingConnectorsMap::const_iterator it = pairsSet.begin(); - it != pairsSet.end(); ++it) - { - // ... check if it has any crossings. - size_t crossings = it->second.size(); - if (crossings == 0) - { - // If not, skip. - continue; - } - - // It has crossings. Determine if it has the most crossings - // of the connectors we've seen, or if it is tied but has - // a greater estimated cost. If so, it is our new candidate. - double cost = cheapEstimatedCost(it->first); - if ((crossings > candidateCrossingCount) || - ((crossings == candidateCrossingCount) && - (cost > candidateEstimatedCost))) - { - // Update with new candidate. - candidateConnector = it->first; - candidateCrossingCount = crossings; - candidateEstimatedCost = cost; - } - } - - if (candidateConnector == NULL) - { - // If no candidate, return NULL connector. - return std::make_pair(0, (ConnRef *) NULL); - } - - // Remove the candidate from the group. To do this we find the - // set of all connectors it crosses. - std::set<ConnRef *>& connSet = pairsSet[candidateConnector]; - // For each of these - for (std::set<ConnRef *>::const_iterator it = connSet.begin(); - it != connSet.end(); ++it) - { - // we remove the candidate from their crossing lists - pairsSet[*it].erase(candidateConnector); - } - // And then clear the crossing list for the candidate itself. - connSet.clear(); - - // Return the candidate connector and its original crossing count. - return std::make_pair(candidateCrossingCount, candidateConnector); - } - - // Returns the iterator to the group that the given conn is in, - // if it is part of any crossing group. - CrossingConnectorsMapList::iterator groupForConn(ConnRef *conn) - { - // For each group... - for (CrossingConnectorsMapList::iterator it = pairsSetList.begin(); - it != pairsSetList.end(); ++it) - { - // ... check if the connector is in it. - if (it->count(conn) > 0) - { - // If so, return it. - return it; - } - } - // Connector was not in any existing group. - return pairsSetList.end(); - } - - // Given a pair of crossing connectors, returns an iterator to the - // crossing connector group they are part of. If neither are part - // of any group, one is created and returned. If one connector is - // part of an exisitng group, that group is returned. If they are - // part of two different groups, the groups are merged and the - // merged group is returned. - CrossingConnectorsMapList::iterator groupForCrossingConns( - ConnRef *conn1, ConnRef *conn2) - { - CrossingConnectorsMapList::iterator it1 = groupForConn(conn1); - CrossingConnectorsMapList::iterator it2 = groupForConn(conn2); - - // groupIt will be the iterator to the appropriate group. - CrossingConnectorsMapList::iterator groupIt = pairsSetList.end(); - - if ((it1 == pairsSetList.end()) && (it2 == pairsSetList.end())) - { - // Neither are part of a group. Create one. - CrossingConnectorsMap newSet; - groupIt = pairsSetList.insert(pairsSetList.end(), newSet); - } - else if ((it1 != pairsSetList.end()) && (it2 == pairsSetList.end())) - { - // it1 is the appropriate existing group. - groupIt = it1; - } - else if ((it1 == pairsSetList.end()) && (it2 != pairsSetList.end())) - { - // it2 is the appropriate exisitng group. - groupIt = it2; - } - else if (it1 != it2) - { - // There are two different existing groups, so merge them. - COLA_ASSERT(it1 != pairsSetList.end()); - COLA_ASSERT(it2 != pairsSetList.end()); - it1->insert(it2->begin(), it2->end()); - pairsSetList.erase(it2); - groupIt = it1; - } - else - { - // These are already part of the same group. Do nothing. - COLA_ASSERT(it1 == it2); - groupIt = it1; - } - return groupIt; - } - - CrossingConnectorsMapList pairsSetList; -}; - - -void Router::performContinuationCheck(unsigned int phaseNumber, - size_t stepNumber, size_t totalSteps) -{ - // Compute the elapsed time in msec since the beginning of the transaction. - unsigned int elapsedMsec = (unsigned int) - ((clock() - m_transaction_start_time) / - (CLOCKS_PER_SEC / (double) 1000)); - - bool shouldContinue = shouldContinueTransactionWithProgress(elapsedMsec, - phaseNumber, TransactionPhaseCompleted, - stepNumber / (double)totalSteps); - if (shouldContinue == false) - { - // Host program has asked us not to continue the transaction. - m_abort_transaction = true; - } -} - - -bool Router::shouldContinueTransactionWithProgress(unsigned int elapsedTime, - unsigned int phaseNumber, unsigned int totalPhases, - double proportion) -{ - COLA_UNUSED(elapsedTime); - COLA_UNUSED(phaseNumber); - COLA_UNUSED(totalPhases); - COLA_UNUSED(proportion); - -#if 0 - printf("Progress: %8u, phase %u of %u... %.2f%%\n", elapsedTime, - phaseNumber, totalPhases, proportion * 100); -#endif - - // We always continue. Subclasses can override this behaviour. - return true; -} - - -class CmpOrderedConnCostRef -{ - public: - CmpOrderedConnCostRef() - { - } - bool operator() (const ConnCostRef& u, const ConnCostRef& v) const - { - return (u.first < v.first); - } -}; -typedef std::list<ConnCostRef> ConnCostRefList; - - -void Router::improveCrossings(void) -{ - const double crossing_penalty = routingParameter(crossingPenalty); - const double shared_path_penalty = routingParameter(fixedSharedPathPenalty); - if ((crossing_penalty == 0) && (shared_path_penalty == 0)) - { - // No penalties, return. - return; - } - - // Information on crossing connector groups. - CrossingConnectorsInfo crossingConnInfo; - - size_t numOfConns = connRefs.size(); - size_t numOfConnsChecked = 0; - - // Find crossings and reroute connectors. - m_in_crossing_rerouting_stage = true; - ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) - { - // Progress reporting and continuation check. - ++numOfConnsChecked; - performContinuationCheck(TransactionPhaseCrossingDetection, - numOfConnsChecked, numOfConns); - if (m_abort_transaction) - { - m_in_crossing_rerouting_stage = false; - return; - } - - Avoid::Polygon& iRoute = (*i)->routeRef(); - if (iRoute.size() == 0) - { - // Rerouted hyperedges will have an empty route. - // We can't reroute these. - continue; - } - ConnRefList::iterator j = i; - for (++j; j != fin; ++j) - { - if (crossingConnInfo.connsKnownToCross(*i, *j)) - { - // We already know both these have crossings. - continue; - } - - // Determine if this pair cross. - Avoid::Polygon& jRoute = (*j)->routeRef(); - ConnectorCrossings cross(iRoute, true, jRoute, *i, *j); - for (size_t jInd = 1; jInd < jRoute.size(); ++jInd) - { - const bool finalSegment = ((jInd + 1) == jRoute.size()); - cross.countForSegment(jInd, finalSegment); - - if ((shared_path_penalty > 0) && - (cross.crossingFlags & CROSSING_SHARES_PATH) && - (cross.crossingFlags & CROSSING_SHARES_FIXED_SEGMENT) && - (m_routing_options[penaliseOrthogonalSharedPathsAtConnEnds] || - !(cross.crossingFlags & CROSSING_SHARES_PATH_AT_END))) - { - // We are penalising fixedSharedPaths and there is a - // fixedSharedPath. - crossingConnInfo.addCrossing(*i, *j); - break; - } - else if ((crossing_penalty > 0) && (cross.crossingCount > 0)) - { - // We are penalising crossings and this is a crossing. - crossingConnInfo.addCrossing(*i, *j); - break; - } - } - } - } - - // Find the list of connector sets that need to be removed to avoid any - // crossings in all crossing groups. This is our candidate set for - // rerouting. Where these connectors connect to exlusive pins, all - // connectors attached to exclusive pins with the same IDs will also - // be rerouted, starting with the shortest. - ConnCostRefSetList crossingConnsGroups = - crossingConnInfo.crossingSetsListToRemoveCrossingsFromGroups(); - - // At this point we have a list containing crossings for rerouting. - // We do this rerouting via two passes, for each group of interacting - // crossing connectors: - // 1) clear existing routes and free pin assignments, and - // 2) compute new routes. - unsigned int numOfConnsToReroute = 1; - unsigned int numOfConnsRerouted = 1; - for (ConnCostRefSetList::iterator setIt = crossingConnsGroups.begin(); - setIt != crossingConnsGroups.end(); ++setIt) - { - // Sort the connectors we will be rerouting from lowest to - // highest cost. - ConnCostRefList orderedConnList(setIt->begin(), setIt->end()); - orderedConnList.sort(CmpOrderedConnCostRef()); - - // Perform rerouting of this set of connectors. - for (int pass = 0; pass < 2; ++pass) - { - for (ConnCostRefList::iterator connIt = orderedConnList.begin(); - connIt != orderedConnList.end(); ++connIt) - { - ConnRef *conn = connIt->second; - if (pass == 0) - { - ++numOfConnsToReroute; - - // Mark the fixed shared path as being invalid. - conn->makePathInvalid(); - - // Free the previous path, so it is not noticed by other - // connectors during rerouting. - conn->freeRoutes(); - - // Free pin assignments. - conn->freeActivePins(); - } - else if (pass == 1) - { - // Progress reporting and continuation check. - performContinuationCheck(TransactionPhaseRerouteSearch, - numOfConnsRerouted, numOfConnsToReroute); - if (m_abort_transaction) - { - m_in_crossing_rerouting_stage = false; - return; - } - ++numOfConnsRerouted; - - // Recompute this path. - conn->generatePath(); - } - } - } - } - m_in_crossing_rerouting_stage = false; -} - - -void Router::newBlockingShape(const Polygon& poly, int pid) -{ - // o Check all visibility edges to see if this one shape - // blocks them. - EdgeInf *finish = visGraph.end(); - for (EdgeInf *iter = visGraph.begin(); iter != finish ; ) - { - EdgeInf *tmp = iter; - iter = iter->lstNext; - - if (tmp->getDist() != 0) - { - std::pair<VertID, VertID> ids(tmp->ids()); - VertID eID1 = ids.first; - VertID eID2 = ids.second; - std::pair<Point, Point> points(tmp->points()); - Point e1 = points.first; - Point e2 = points.second; - bool blocked = false; - - bool countBorder = false; - bool ep_in_poly1 = (eID1.isConnPt()) ? - inPoly(poly, e1, countBorder) : false; - bool ep_in_poly2 = (eID2.isConnPt()) ? - inPoly(poly, e2, countBorder) : false; - if (ep_in_poly1 || ep_in_poly2) - { - // Don't check edges that have a connector endpoint - // and are inside the shape being added. - continue; - } - - bool seenIntersectionAtEndpoint = false; - for (size_t pt_i = 0; pt_i < poly.size(); ++pt_i) - { - size_t pt_n = (pt_i == (poly.size() - 1)) ? 0 : pt_i + 1; - const Point& pi = poly.ps[pt_i]; - const Point& pn = poly.ps[pt_n]; - if (segmentShapeIntersect(e1, e2, pi, pn, - seenIntersectionAtEndpoint)) - { - blocked = true; - break; - } - } - if (blocked) - { - db_printf("\tRemoving newly blocked edge (by shape %3d)" - "... \n\t\t", pid); - tmp->alertConns(); - tmp->db_print(); - if (InvisibilityGrph) - { - tmp->addBlocker(pid); - } - else - { - delete tmp; - } - } - } - } -} - - -void Router::checkAllBlockedEdges(int pid) -{ - COLA_ASSERT(InvisibilityGrph); - - for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; ) - { - EdgeInf *tmp = iter; - iter = iter->lstNext; - - if (tmp->blocker() == -1) - { - tmp->alertConns(); - tmp->checkVis(); - } - else if (tmp->blocker() == pid) - { - tmp->checkVis(); - } - } -} - - -void Router::checkAllMissingEdges(void) -{ - COLA_ASSERT(!InvisibilityGrph); - - VertInf *first = vertices.connsBegin(); - - VertInf *pend = vertices.end(); - for (VertInf *i = first; i != pend; i = i->lstNext) - { - VertID iID = i->id; - - // Check remaining, earlier vertices - for (VertInf *j = first ; j != i; j = j->lstNext) - { - VertID jID = j->id; - if (iID.isConnPt() && !iID.isConnectionPin() && - (iID.objID != jID.objID)) - { - // Don't keep visibility between edges of different conns - continue; - } - - // See if the edge is already there? - bool found = (EdgeInf::existingEdge(i, j) != NULL); - - if (!found) - { - // Didn't already exist, check. - bool knownNew = true; - EdgeInf::checkEdgeVisibility(i, j, knownNew); - } - } - } -} - - -void Router::generateContains(VertInf *pt) -{ - contains[pt->id].clear(); - enclosingClusters[pt->id].clear(); - - // Don't count points on the border as being inside. - bool countBorder = false; - - // Compute enclosing shapes. - ObstacleList::const_iterator finish = m_obstacles.end(); - for (ObstacleList::const_iterator i = m_obstacles.begin(); i != finish; ++i) - { - if (inPoly((*i)->routingPolygon(), pt->point, countBorder)) - { - contains[pt->id].insert((*i)->id()); - } - } - - // Computer enclosing Clusters - ClusterRefList::const_iterator clFinish = clusterRefs.end(); - for (ClusterRefList::const_iterator i = clusterRefs.begin(); - i != clFinish; ++i) - { - if (inPolyGen((*i)->polygon(), pt->point)) - { - enclosingClusters[pt->id].insert((*i)->id()); - } - } -} - - -void Router::adjustClustersWithAdd(const PolygonInterface& poly, - const int p_cluster) -{ - for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin(); - k = k->lstNext) - { - if (inPolyGen(poly, k->point)) - { - enclosingClusters[k->id].insert(p_cluster); - } - } -} - - -void Router::adjustClustersWithDel(const int p_cluster) -{ - for (ContainsMap::iterator k = enclosingClusters.begin(); - k != enclosingClusters.end(); ++k) - { - (*k).second.erase(p_cluster); - } -} - - -void Router::adjustContainsWithAdd(const Polygon& poly, const int p_shape) -{ - // Don't count points on the border as being inside. - bool countBorder = false; - - for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin(); - k = k->lstNext) - { - if (inPoly(poly, k->point, countBorder)) - { - contains[k->id].insert(p_shape); - } - } -} - - -void Router::adjustContainsWithDel(const int p_shape) -{ - for (ContainsMap::iterator k = contains.begin(); k != contains.end(); ++k) - { - (*k).second.erase(p_shape); - } -} - - -#ifdef SELECTIVE_DEBUG -static double AngleAFromThreeSides(const double a, const double b, - const double c) -{ - // returns angle A, the angle opposite from side a, in radians - return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c)); -} -#endif - -// Given an deleted obstacle, uses a simple heauristic to determine polyline -// connectors that may now have a better path through the region occupied by -// the shape and mark them as needing to be rerouted. -// See the "Incremental Connector Routing" paper which explains this code. -// -void Router::markPolylineConnectorsNeedingReroutingForDeletedObstacle( - Obstacle *obstacle) -{ - if (RubberBandRouting) - { - // When rubber-band routing, we do not reroute connectors that - // may have a better route, only invalid connectors. - return; - } - - COLA_ASSERT(SelectiveReroute); - - // For each connector... - ConnRefList::const_iterator end = connRefs.end(); - for (ConnRefList::const_iterator it = connRefs.begin(); it != end; ++it) - { - ConnRef *conn = (*it); - - if (conn->m_route.empty()) - { - // Ignore uninitialised connectors. - continue; - } - else if (conn->m_needs_reroute_flag) - { - // Already marked, so skip. - continue; - } - else if (conn->routingType() != ConnType_PolyLine) - { - // This test only works for polyline connectors, so skip others. - continue; - } - - Point start = conn->m_route.ps[0]; - Point end = conn->m_route.ps[conn->m_route.size() - 1]; - - double conndist = conn->m_route_dist; - - double estdist; - double e1, e2; - - // For each vertex of the obstacle... - VertInf *beginV = obstacle->firstVert(); - VertInf *endV = obstacle->lastVert()->lstNext; - for (VertInf *i = beginV; i != endV; i = i->lstNext) - { - const Point& p1 = i->point; - const Point& p2 = i->shNext->point; - - double offy; - double a; - double b; - double c; - double d; - - double min; - double max; - - if (p1.y == p2.y) - { - // Standard case - offy = p1.y; - a = start.x; - b = start.y - offy; - c = end.x; - d = end.y - offy; - - min = std::min(p1.x, p2.x); - max = std::max(p1.x, p2.x); - } - else if (p1.x == p2.x) - { - // Other Standard case - offy = p1.x; - a = start.y; - b = start.x - offy; - c = end.y; - d = end.x - offy; - - min = std::min(p1.y, p2.y); - max = std::max(p1.y, p2.y); - } - else - { - // Need to do rotation - Point n_p2(p2.x - p1.x, p2.y - p1.y); - Point n_start(start.x - p1.x, start.y - p1.y); - Point n_end(end.x - p1.x, end.y - p1.y); - //db_printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y); - //db_printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y); - //db_printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y); - - double theta = 0 - atan2(n_p2.y, n_p2.x); - //db_printf("theta = %.2f\n", theta * (180 / PI)); - - Point r_p1(0, 0); - Point r_p2 = n_p2; - start = n_start; - end = n_end; - - double cosv = cos(theta); - double sinv = sin(theta); - - r_p2.x = cosv * n_p2.x - sinv * n_p2.y; - r_p2.y = cosv * n_p2.y + sinv * n_p2.x; - start.x = cosv * n_start.x - sinv * n_start.y; - start.y = cosv * n_start.y + sinv * n_start.x; - end.x = cosv * n_end.x - sinv * n_end.y; - end.y = cosv * n_end.y + sinv * n_end.x; - //db_printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y); - //db_printf("r_start: (%.1f, %.1f)\n", start.x, start.y); - //db_printf("r_end: (%.1f, %.1f)\n", end.x, end.y); - - // This might be slightly off. - if (fabs(r_p2.y) > 0.0001) - { - db_printf("r_p2.y: %f != 0\n", r_p2.y); - } - r_p2.y = 0; - - offy = r_p1.y; - a = start.x; - b = start.y - offy; - c = end.x; - d = end.y - offy; - - min = std::min(r_p1.x, r_p2.x); - max = std::max(r_p1.x, r_p2.x); - - } - - double x; - if ((b + d) == 0) - { - db_printf("WARNING: (b + d) == 0\n"); - d = d * -1; - } - - if ((b == 0) && (d == 0)) - { - db_printf("WARNING: b == d == 0\n"); - if (((a < min) && (c < min)) || - ((a > max) && (c > max))) - { - // It's going to get adjusted. - x = a; - } - else - { - continue; - } - } - else - { - x = ((b*c) + (a*d)) / (b + d); - } - - //db_printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d); - //db_printf("x = %.1f\n", x); - - x = std::max(min, x); - x = std::min(max, x); - - //db_printf("x = %.1f\n", x); - - Point xp; - if (p1.x == p2.x) - { - xp.x = offy; - xp.y = x; - } - else - { - xp.x = x; - xp.y = offy; - } - //db_printf("(%.1f, %.1f)\n", xp.x, xp.y); - - e1 = euclideanDist(start, xp); - e2 = euclideanDist(xp, end); - estdist = e1 + e2; - - - //db_printf("is %.1f < %.1f\n", estdist, conndist); - if (estdist < conndist) - { -#ifdef SELECTIVE_DEBUG - //double angle = AngleAFromThreeSides(dist(start, end), - // e1, e2); - db_printf("[%3d] - Possible better path found (%.1f < %.1f)\n", - conn->_id, estdist, conndist); -#endif - conn->m_needs_reroute_flag = true; - break; - } - - } - } -} - - -ConnType Router::validConnType(const ConnType select) const -{ - if (select != ConnType_None) - { - if ((select == ConnType_Orthogonal) && m_allows_orthogonal_routing) - { - return ConnType_Orthogonal; - } - else if ((select == ConnType_PolyLine) && m_allows_polyline_routing) - { - return ConnType_PolyLine; - } - } - - if (m_allows_polyline_routing) - { - return ConnType_PolyLine; - } - else if (m_allows_orthogonal_routing) - { - return ConnType_Orthogonal; - } - return ConnType_None; -} - - -void Router::setRoutingParameter(const RoutingParameter parameter, - const double value) -{ - COLA_ASSERT(parameter < lastRoutingParameterMarker); - if (value < 0) - { - // Set some sensible parameter value for the parameter being 'active'. - switch (parameter) - { - case segmentPenalty: - m_routing_parameters[parameter] = 50; - break; - case fixedSharedPathPenalty: - m_routing_parameters[parameter] = 110; - break; - case anglePenalty: - m_routing_parameters[parameter] = 50; - break; - case crossingPenalty: - m_routing_parameters[parameter] = 200; - break; - case clusterCrossingPenalty: - m_routing_parameters[parameter] = 4000; - break; - case idealNudgingDistance: - m_routing_parameters[parameter] = 4.0; - break; - case portDirectionPenalty: - m_routing_parameters[parameter] = 100; - break; - default: - m_routing_parameters[parameter] = 50; - break; - } - } - else - { - m_routing_parameters[parameter] = value; - } - m_settings_changes = true; -} - - -double Router::routingParameter(const RoutingParameter parameter) const -{ - COLA_ASSERT(parameter < lastRoutingParameterMarker); - return m_routing_parameters[parameter]; -} - - -void Router::setRoutingOption(const RoutingOption option, const bool value) -{ - COLA_ASSERT(option < lastRoutingOptionMarker); - m_routing_options[option] = value; - m_settings_changes = true; -} - - -bool Router::routingOption(const RoutingOption option) const -{ - COLA_ASSERT(option < lastRoutingOptionMarker); - return m_routing_options[option]; -} - - -void Router::setRoutingPenalty(const RoutingParameter penType, - const double penValue) -{ - setRoutingParameter(penType, penValue); -} - -void Router::registerSettingsChange(void) -{ - m_settings_changes = true; -} - -HyperedgeRerouter *Router::hyperedgeRerouter(void) -{ - return &m_hyperedge_rerouter; -} - - -bool Router::isInCrossingPenaltyReroutingStage(void) const -{ - return m_in_crossing_rerouting_stage; -} - - -void Router::printInfo(void) -{ - FILE *fp = stdout; - fprintf(fp, "\nVisibility Graph info:\n"); - fprintf(fp, "----------------------\n"); - - unsigned int currshape = 0; - int st_shapes = 0; - int st_vertices = 0; - int st_endpoints = 0; - int st_valid_shape_visedges = 0; - int st_valid_endpt_visedges = 0; - int st_orthogonal_visedges = 0; - int st_invalid_visedges = 0; - VertInf *finish = vertices.end(); - for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext) - { - VertID pID = t->id; - - if (!(pID.isConnPt()) && (pID.objID != currshape)) - { - currshape = pID.objID; - st_shapes++; - } - if (!(pID.isConnPt())) - { - st_vertices++; - } - else - { - // The shape 0 ones are temporary and not considered. - st_endpoints++; - } - } - for (EdgeInf *t = visGraph.begin(); t != visGraph.end(); - t = t->lstNext) - { - std::pair<VertID, VertID> idpair = t->ids(); - - if (idpair.first.isConnPt() || idpair.second.isConnPt()) - { - st_valid_endpt_visedges++; - } - else - { - st_valid_shape_visedges++; - } - } - for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end(); - t = t->lstNext) - { - st_invalid_visedges++; - } - for (EdgeInf *t = visOrthogGraph.begin(); t != visOrthogGraph.end(); - t = t->lstNext) - { - st_orthogonal_visedges++; - } - fprintf(fp, "Number of shapes: %d\n", st_shapes); - fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n", - st_vertices + st_endpoints, st_vertices, st_endpoints); - fprintf(fp, "Number of orthog_vis_edges: %d\n", st_orthogonal_visedges); - fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], " - "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges + - st_valid_endpt_visedges, st_valid_shape_visedges + - st_valid_endpt_visedges, st_valid_shape_visedges, - st_valid_endpt_visedges, st_invalid_visedges); - fprintf(fp, "----------------------\n"); - fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges); - fprintf(fp, "----------------------\n"); - -#ifdef AVOID_PROFILE - timers.printAll(fp); - timers.reset(); -#endif -} - - -static const double LIMIT = 100000000; - -static void reduceRange(double& val) -{ - val = std::min(val, LIMIT); - val = std::max(val, -LIMIT); -} - - -//============================================================================= -// The following methods are for testing and debugging. - - -bool Router::existsOrthogonalSegmentOverlap(const bool atEnds) -{ - ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) - { - Avoid::Polygon iRoute = (*i)->displayRoute(); - ConnRefList::iterator j = i; - for (++j; j != fin; ++j) - { - // Determine if this pair overlap - Avoid::Polygon jRoute = (*j)->displayRoute(); - ConnectorCrossings cross(iRoute, true, jRoute, *i, *j); - cross.checkForBranchingSegments = true; - for (size_t jInd = 1; jInd < jRoute.size(); ++jInd) - { - const bool finalSegment = ((jInd + 1) == jRoute.size()); - cross.countForSegment(jInd, finalSegment); - - if ((cross.crossingFlags & CROSSING_SHARES_PATH) && - (atEnds || - !(cross.crossingFlags & CROSSING_SHARES_PATH_AT_END))) - { - // We are looking for fixedSharedPaths and there is a - // fixedSharedPath. - return true; - } - } - } - } - return false; -} - - -bool Router::existsOrthogonalFixedSegmentOverlap(const bool atEnds) -{ - ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) - { - Avoid::Polygon iRoute = (*i)->displayRoute(); - ConnRefList::iterator j = i; - for (++j; j != fin; ++j) - { - // Determine if this pair overlap - Avoid::Polygon jRoute = (*j)->displayRoute(); - ConnectorCrossings cross(iRoute, true, jRoute, *i, *j); - cross.checkForBranchingSegments = true; - for (size_t jInd = 1; jInd < jRoute.size(); ++jInd) - { - const bool finalSegment = ((jInd + 1) == jRoute.size()); - cross.countForSegment(jInd, finalSegment); - - if ((cross.crossingFlags & CROSSING_SHARES_PATH) && - (cross.crossingFlags & CROSSING_SHARES_FIXED_SEGMENT) && - (atEnds || - !(cross.crossingFlags & CROSSING_SHARES_PATH_AT_END))) - { - // We are looking for fixedSharedPaths and there is a - // fixedSharedPath. - return true; - } - } - } - } - return false; -} - - -bool Router::existsOrthogonalTouchingPaths(void) -{ - ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) - { - Avoid::Polygon iRoute = (*i)->displayRoute(); - ConnRefList::iterator j = i; - for (++j; j != fin; ++j) - { - // Determine if this pair overlap - Avoid::Polygon jRoute = (*j)->displayRoute(); - ConnectorCrossings cross(iRoute, true, jRoute, *i, *j); - cross.checkForBranchingSegments = true; - for (size_t jInd = 1; jInd < jRoute.size(); ++jInd) - { - const bool finalSegment = ((jInd + 1) == jRoute.size()); - cross.countForSegment(jInd, finalSegment); - - if (cross.crossingFlags & CROSSING_TOUCHES) - { - return true; - } - } - } - } - return false; -} - - -// Counts the number of crossings between all connectors. -// -// If optimisedForConnectorType is set, This will only count crossings -// between orthogonal connectors if they appear at segment endpoints. -// Thus, it can be used on raw connectors but not on simplified orthogonal -// connectors. -// -int Router::existsCrossings(const bool optimisedForConnectorType) -{ - int count = 0; - ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) - { - Avoid::Polygon iRoute = (*i)->displayRoute(); - ConnRefList::iterator j = i; - for (++j; j != fin; ++j) - { - // Determine if this pair overlap - Avoid::Polygon jRoute = (*j)->displayRoute(); - ConnRef *iConn = (optimisedForConnectorType) ? *i : NULL; - ConnRef *jConn = (optimisedForConnectorType) ? *j : NULL; - ConnectorCrossings cross(iRoute, true, jRoute, iConn, jConn); - cross.checkForBranchingSegments = true; - for (size_t jInd = 1; jInd < jRoute.size(); ++jInd) - { - const bool finalSegment = ((jInd + 1) == jRoute.size()); - - // Normal crossings aren't counted if we pass the pointers - // for the connectors, so don't pass them. - cross.countForSegment(jInd, finalSegment); - - count += cross.crossingCount; - } - } - } - return count; -} - -// Looks for non-orthogonal segments in orthogonal connectors and -// returns true if it finds any. -bool Router::existsInvalidOrthogonalPaths(void) -{ - // For each connector... - ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) - { - // If it is an orthogonal connector... - if ((*i)->routingType() == Avoid::ConnType_Orthogonal) - { - // Check each segment of the path... - Avoid::Polygon iRoute = (*i)->displayRoute(); - for (size_t iInd = 1; iInd < iRoute.size(); ++iInd) - { - // And if it isn't either vertical or horizontal... - if ( (iRoute.at(iInd - 1).x != iRoute.at(iInd).x) && - (iRoute.at(iInd - 1).y != iRoute.at(iInd).y) ) - { - // Then we've found an invalid path. - return true; - } - } - } - } - return false; -} - - -void Router::setTopologyAddon(TopologyAddonInterface *topologyAddon) -{ - COLA_ASSERT(m_topology_addon); - delete m_topology_addon; - if (topologyAddon) - { - m_topology_addon = topologyAddon->clone(); - } - else - { - m_topology_addon = new TopologyAddonInterface(); - } - registerSettingsChange(); -} - -void Router::improveOrthogonalTopology(void) -{ - COLA_ASSERT(m_topology_addon); - m_topology_addon->improveOrthogonalTopology(this); -} - -void Router::outputInstanceToSVG(std::string instanceName) -{ - std::string filename; - if (!instanceName.empty()) - { - filename = instanceName; - } - else - { - filename = "libavoid-debug"; - } - filename += ".svg"; - FILE *fp = fopen(filename.c_str(), "w"); - - if (fp == NULL) - { - return; - } - - double minX = LIMIT; - double minY = LIMIT; - double maxX = -LIMIT; - double maxY = -LIMIT; - - VertInf *curr = vertices.connsBegin(); - while (curr) - { - Point p = curr->point; - - reduceRange(p.x); - reduceRange(p.y); - - if (p.x > -LIMIT) - { - minX = std::min(minX, p.x); - } - if (p.x < LIMIT) - { - maxX = std::max(maxX, p.x); - } - if (p.y > -LIMIT) - { - minY = std::min(minY, p.y); - } - if (p.y < LIMIT) - { - maxY = std::max(maxY, p.y); - } - curr = curr->lstNext; - } - minX -= 8; - minY -= 8; - maxX += 8; - maxY += 8; - - fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"); - fprintf(fp, "<svg xmlns:inkscape=\"http://www.inkscape.org/namespaces/inkscape\" xmlns=\"http://www.w3.org/2000/svg\" width=\"100%%\" height=\"100%%\" viewBox=\"%g %g %g %g\">\n", minX, minY, maxX - minX, maxY - minY); - - // Output source code to generate this instance of the router. - fprintf(fp, "<!-- Source code to generate this instance:\n"); - fprintf(fp, "#include \"libavoid/libavoid.h\"\n"); - if (m_topology_addon->outputCode(NULL)) - { - fprintf(fp, "#include \"libcola/cola.h\"\n"); - fprintf(fp, "#include \"libtopology/orthogonal_topology.h\"\n"); - fprintf(fp, "using namespace cola;\n"); - } - fprintf(fp, "using namespace Avoid;\n"); - fprintf(fp, "int main(void) {\n"); - fprintf(fp, " Router *router = new Router("); - if (m_allows_polyline_routing) - { - fprintf(fp, "PolyLineRouting"); - } - if (m_allows_polyline_routing && m_allows_orthogonal_routing) - { - fprintf(fp, " | "); - } - if (m_allows_orthogonal_routing) - { - fprintf(fp, "OrthogonalRouting"); - } - fprintf(fp, ");\n"); - for (size_t p = 0; p < lastRoutingParameterMarker; ++p) - { - fprintf(fp, " router->setRoutingParameter((RoutingParameter)%lu, %g);\n", - (unsigned long)p, m_routing_parameters[p]); - } - for (size_t p = 0; p < lastRoutingOptionMarker; ++p) - { - fprintf(fp, " router->setRoutingOption((RoutingOption)%lu, %s);\n", - (unsigned long)p, (m_routing_options[p]) ? "true" : "false"); - } - fprintf(fp, " Polygon polygon;\n"); - fprintf(fp, " ConnRef *connRef = NULL;\n"); - fprintf(fp, " ConnEnd srcPt;\n"); - fprintf(fp, " ConnEnd dstPt;\n"); - fprintf(fp, " ConnEnd heConnPt;\n"); - fprintf(fp, " PolyLine newRoute;\n"); - fprintf(fp, " ShapeConnectionPin *connPin = NULL;\n"); - fprintf(fp, "\n"); - ClusterRefList::reverse_iterator revClusterRefIt = clusterRefs.rbegin(); - while (revClusterRefIt != clusterRefs.rend()) - { - ClusterRef *cRef = *revClusterRefIt; - fprintf(fp, " polygon = Polygon(%lu);\n", - (unsigned long)cRef->polygon().size()); - for (size_t i = 0; i <cRef->polygon().size(); ++i) - { - fprintf(fp, " polygon.ps[%lu] = Point(%g, %g);\n", - (unsigned long)i, cRef->polygon().at(i).x, - cRef->polygon().at(i).y); - } - fprintf(fp, " new ClusterRef(router, polygon, %u);\n", cRef->id()); - ++revClusterRefIt; - } - ObstacleList::reverse_iterator revObstacleIt = m_obstacles.rbegin(); - while (revObstacleIt != m_obstacles.rend()) - { - Obstacle *obstacle = *revObstacleIt; - obstacle->outputCode(fp); - ++revObstacleIt; - } - ConnRefList::reverse_iterator revConnRefIt = connRefs.rbegin(); - while (revConnRefIt != connRefs.rend()) - { - ConnRef *connRef = *revConnRefIt; - connRef->outputCode(fp); - ++revConnRefIt; - } - - m_topology_addon->outputCode(fp); - - fprintf(fp, " router->processTransaction();\n"); - fprintf(fp, " router->outputInstanceToSVG();\n"); - - m_topology_addon->outputDeletionCode(fp); - fprintf(fp, " delete router;\n"); - fprintf(fp, " return 0;\n"); - fprintf(fp, "};\n"); - fprintf(fp, "-->\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "inkscape:label=\"Clusters\">\n"); - revClusterRefIt = clusterRefs.rbegin(); - while (revClusterRefIt != clusterRefs.rend()) - { - ClusterRef *cRef = *revClusterRefIt; - fprintf(fp, "<path id=\"cluster-%u\" style=\"stroke-width: 1px; " - "stroke: black; fill: green; opacity: 0.1;\" d=\"", - cRef->id()); - for (size_t i = 0; i < cRef->polygon().size(); ++i) - { - fprintf(fp, "%c %g %g ", ((i == 0) ? 'M' : 'L'), - cRef->polygon().at(i).x, cRef->polygon().at(i).y); - } - fprintf(fp, "Z\" />\n"); - - fprintf(fp, "<path id=\"cluster-%u-rect\" style=\"stroke-width: 1px; " - "stroke: black; fill: green; opacity: 0.1;\" d=\"", - cRef->id()); - for (size_t i = 0; i < cRef->rectangularPolygon().size(); ++i) - { - fprintf(fp, "%c %g %g ", ((i == 0) ? 'M' : 'L'), - cRef->rectangularPolygon().at(i).x, - cRef->rectangularPolygon().at(i).y); - } - fprintf(fp, "Z\" />\n"); - ++revClusterRefIt; - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "style=\"display: none;\" " - "inkscape:label=\"ShapePolygons\">\n"); - ObstacleList::iterator obstacleIt = m_obstacles.begin(); - while (obstacleIt != m_obstacles.end()) - { - Obstacle *obstacle = *obstacleIt; - bool isShape = (NULL != dynamic_cast<ShapeRef *> (obstacle)); - - if ( ! isShape ) - { - // Don't output obstacles here, for now. - ++obstacleIt; - continue; - } - - fprintf(fp, "<path id=\"poly-%u\" style=\"stroke-width: 1px; " - "stroke: black; fill: %s; fill-opacity: 0.3;\" d=\"", - obstacle->id(), (isShape) ? "grey" : "red"); - for (size_t i = 0; i < obstacle->polygon().size(); ++i) - { - fprintf(fp, "%c %g %g ", ((i == 0) ? 'M' : 'L'), - obstacle->polygon().at(i).x, obstacle->polygon().at(i).y); - } - fprintf(fp, "Z\" />\n"); - ++obstacleIt; - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "style=\"display: none;\" " - "inkscape:label=\"ObstaclePolygons\">\n"); - obstacleIt = m_obstacles.begin(); - while (obstacleIt != m_obstacles.end()) - { - Obstacle *obstacle = *obstacleIt; - bool isShape = (NULL != dynamic_cast<ShapeRef *> (obstacle)); - - if ( ! isShape ) - { - // Don't output obstacles here, for now. - ++obstacleIt; - continue; - } - - Polygon polygon = obstacle->routingPolygon(); - fprintf(fp, "<path id=\"poly-%u\" style=\"stroke-width: 1px; " - "stroke: black; fill: %s; fill-opacity: 0.3;\" d=\"", - obstacle->id(), (isShape) ? "grey" : "red"); - for (size_t i = 0; i < polygon.size(); ++i) - { - fprintf(fp, "%c %g %g ", ((i == 0) ? 'M' : 'L'), - polygon.at(i).x, polygon.at(i).y); - } - fprintf(fp, "Z\" />\n"); - ++obstacleIt; - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "style=\"display: none;\" " - "inkscape:label=\"IdealJunctions\">\n"); - for (ObstacleList::iterator obstacleIt = m_obstacles.begin(); - obstacleIt != m_obstacles.end(); ++obstacleIt) - { - JunctionRef *junction = dynamic_cast<JunctionRef *> (*obstacleIt); - if (junction) - { - fprintf(fp, "<circle id=\"idealJunction-%u\" cx=\"%g\" cy=\"%g\" " - "r=\"8\" style=\"stroke: none; fill: %s; " - "fill-opacity: 0.5;\" />\n", junction->id(), - junction->recommendedPosition().x, - junction->recommendedPosition().y, "green"); - } - - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "inkscape:label=\"ObstacleRects\">\n"); - obstacleIt = m_obstacles.begin(); - while (obstacleIt != m_obstacles.end()) - { - Obstacle *obstacle = *obstacleIt; - bool isShape = (NULL != dynamic_cast<ShapeRef *> (obstacle)); - - if ( ! isShape ) - { - // Don't output obstacles here, for now. - ++obstacleIt; - continue; - } - - Box bBox = obstacle->routingBox(); - - fprintf(fp, "<rect id=\"rect-%u\" x=\"%g\" y=\"%g\" width=\"%g\" " - "height=\"%g\" style=\"stroke-width: 1px; stroke: black; " - "fill: grey; stroke-opacity: 0.1; fill-opacity: 0.1;\" />\n", - obstacle->id(), bBox.min.x, bBox.min.y, - bBox.max.x - bBox.min.x, bBox.max.y - bBox.min.y); - ++obstacleIt; - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "inkscape:label=\"VisGraph\"" - ">\n"); - EdgeInf *finish = NULL; - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "style=\"display: none;\" " - "inkscape:label=\"VisGraph-shape\"" - ">\n"); - finish = visGraph.end(); - for (EdgeInf *t = visGraph.begin(); t != finish; t = t->lstNext) - { - std::pair<VertID, VertID> ids = t->ids(); - bool isConn = ids.first.isConnPt() || ids.second.isConnPt(); - if (isConn) - { - continue; - } - std::pair<Point, Point> ptpair = t->points(); - Point p1 = ptpair.first; - Point p2 = ptpair.second; - - reduceRange(p1.x); - reduceRange(p1.y); - reduceRange(p2.x); - reduceRange(p2.y); - - fprintf(fp, "<path d=\"M %g %g L %g %g\" " - "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", - p1.x, p1.y, p2.x, p2.y, - (ids.first.isConnPt() || ids.second.isConnPt()) ? "blue" : - "red"); - } - fprintf(fp, "</g>\n"); - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "style=\"display: none;\" " - "inkscape:label=\"VisGraph-conn\"" - ">\n"); - finish = visGraph.end(); - for (EdgeInf *t = visGraph.begin(); t != finish; t = t->lstNext) - { - std::pair<VertID, VertID> ids = t->ids(); - bool isConn = ids.first.isConnPt() || ids.second.isConnPt(); - if (!isConn) - { - continue; - } - std::pair<Point, Point> ptpair = t->points(); - Point p1 = ptpair.first; - Point p2 = ptpair.second; - - reduceRange(p1.x); - reduceRange(p1.y); - reduceRange(p2.x); - reduceRange(p2.y); - - fprintf(fp, "<path d=\"M %g %g L %g %g\" " - "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", - p1.x, p1.y, p2.x, p2.y, - (ids.first.isConnPt() || ids.second.isConnPt()) ? "blue" : - "red"); - } - fprintf(fp, "</g>\n"); - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "style=\"display: none;\" " - "inkscape:label=\"OrthogVisGraph\">\n"); - finish = visOrthogGraph.end(); - for (EdgeInf *t = visOrthogGraph.begin(); t != finish; t = t->lstNext) - { - std::pair<Point, Point> ptpair = t->points(); - Point p1 = ptpair.first; - Point p2 = ptpair.second; - - reduceRange(p1.x); - reduceRange(p1.y); - reduceRange(p2.x); - reduceRange(p2.y); - - std::pair<VertID, VertID> ids = t->ids(); - - fprintf(fp, "<path d=\"M %g %g L %g %g\" " - "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", - p1.x, p1.y, p2.x, p2.y, - (ids.first.isConnPt() || ids.second.isConnPt()) ? "green" : - "red"); - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "style=\"display: none;\" " - "inkscape:label=\"RawConnectors\"" - ">\n"); - ConnRefList::iterator connRefIt = connRefs.begin(); - while (connRefIt != connRefs.end()) - { - ConnRef *connRef = *connRefIt; - - PolyLine route = connRef->route(); - if (!route.empty()) - { - fprintf(fp, "<path id=\"raw-%u\" d=\"M %g %g ", connRef->id(), - route.ps[0].x, route.ps[0].y); - for (size_t i = 1; i < route.size(); ++i) - { - fprintf(fp, "L %g %g ", route.ps[i].x, route.ps[i].y); - } - fprintf(fp, "\" "); - if (connRef->src() && connRef->dst()) - { - fprintf(fp, "debug=\"src: %d dst: %d\" ", - connRef->src()->visDirections, - connRef->dst()->visDirections); - } - fprintf(fp, "style=\"fill: none; stroke: black; " - "stroke-width: 1px;\" />\n"); - } - - ++connRefIt; - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "style=\"display: none;\" " - "inkscape:label=\"CurvedDisplayConnectors\"" - ">\n"); - connRefIt = connRefs.begin(); - while (connRefIt != connRefs.end()) - { - ConnRef *connRef = *connRefIt; - - PolyLine route = connRef->displayRoute().curvedPolyline(8); - if (!route.empty()) - { - fprintf(fp, "<path id=\"curved-%u\" d=\"M %g %g ", connRef->id(), - route.ps[0].x, route.ps[0].y); - for (size_t i = 1; i < route.size(); ++i) - { - if (route.ts[i] == 'C') - { - fprintf(fp, "%c %g %g %g %g %g %g", route.ts[i], - route.ps[i].x, route.ps[i].y, - route.ps[i+1].x, route.ps[i+1].y, - route.ps[i+2].x, route.ps[i+2].y); - i += 2; - } - else - { - fprintf(fp, "%c %g %g ", route.ts[i], - route.ps[i].x, route.ps[i].y); - } - } - fprintf(fp, "\" "); - if (connRef->src() && connRef->dst()) - { - fprintf(fp, "debug=\"src: %d dst: %d\" ", - connRef->src()->visDirections, - connRef->dst()->visDirections); - } - fprintf(fp, "style=\"fill: none; stroke: black; " - "stroke-width: 1px;\" />\n"); - } - - ++connRefIt; - } - fprintf(fp, "</g>\n"); - - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "inkscape:label=\"DisplayConnectors\"" - ">\n"); - connRefIt = connRefs.begin(); - while (connRefIt != connRefs.end()) - { - ConnRef *connRef = *connRefIt; - - PolyLine route = connRef->displayRoute(); - if (!route.empty()) - { - fprintf(fp, "<path id=\"disp-%u\" d=\"M %g %g ", connRef->id(), - route.ps[0].x, route.ps[0].y); - for (size_t i = 1; i < route.size(); ++i) - { - fprintf(fp, "L %g %g ", route.ps[i].x, route.ps[i].y); - } - fprintf(fp, "\" "); - if (connRef->src() && connRef->dst()) - { - fprintf(fp, "debug=\"src: %d dst: %d\" ", - connRef->src()->visDirections, - connRef->dst()->visDirections); - } - fprintf(fp, "style=\"fill: none; stroke: black; " - "stroke-width: 1px;\" />\n"); - } - - ++connRefIt; - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "inkscape:label=\"ConnectorCheckpoints\"" - ">\n"); - connRefIt = connRefs.begin(); - while (connRefIt != connRefs.end()) - { - ConnRef *connRef = *connRefIt; - - for (size_t i = 0; i < connRef->m_checkpoints.size(); ++i) - { - fprintf(fp, "<circle id=\"checkpoint-%u-%d\" cx=\"%g\" cy=\"%g\" " - "r=\"8\" style=\"stroke: none; fill: red; " - "fill-opacity: 0.25;\" />\n", connRef->id(), (int) i, - connRef->m_checkpoints[i].point.x, - connRef->m_checkpoints[i].point.y); - } - - ++connRefIt; - } - fprintf(fp, "</g>\n"); - - - fprintf(fp, "</svg>\n"); - fclose(fp); - //printInfo(); -} - -void Router::outputDiagramSVG(std::string instanceName, LineReps *lineReps) -{ - std::string filename; - if (!instanceName.empty()) - { - filename = instanceName; - } - else - { - filename = "libavoid-diagram"; - } - filename += ".svg"; - FILE *fp = fopen(filename.c_str(), "w"); - - if (fp == NULL) - { - return; - } - - double minX = LIMIT; - double minY = LIMIT; - double maxX = -LIMIT; - double maxY = -LIMIT; - - VertInf *curr = vertices.connsBegin(); - while (curr) - { - Point p = curr->point; - - reduceRange(p.x); - reduceRange(p.y); - - if (p.x > -LIMIT) - { - minX = std::min(minX, p.x); - } - if (p.x < LIMIT) - { - maxX = std::max(maxX, p.x); - } - if (p.y > -LIMIT) - { - minY = std::min(minY, p.y); - } - if (p.y < LIMIT) - { - maxY = std::max(maxY, p.y); - } - curr = curr->lstNext; - } - minX -= 8; - minY -= 8; - maxX += 8; - maxY += 8; - - fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n"); - fprintf(fp, "<svg xmlns:inkscape=\"http://www.inkscape.org/namespaces/inkscape\" xmlns=\"http://www.w3.org/2000/svg\" width=\"100%%\" height=\"100%%\" viewBox=\"%g %g %g %g\">\n", minX, minY, maxX - minX, maxY - minY); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "inkscape:label=\"ShapesRect\">\n"); - ObstacleList::iterator obstacleIt = m_obstacles.begin(); - while (obstacleIt != m_obstacles.end()) - { - Obstacle *obstacle = *obstacleIt; - bool isShape = (NULL != dynamic_cast<ShapeRef *> (obstacle)); - - if ( ! isShape ) - { - // Don't output non-shape obstacles here, for now. - ++obstacleIt; - continue; - } - - Box bBox = obstacle->polygon().offsetBoundingBox(0.0); - - fprintf(fp, "<rect id=\"rect-%u\" x=\"%g\" y=\"%g\" width=\"%g\" " - "height=\"%g\" style=\"stroke-width: 1px; stroke: black; " - "fill: grey; stroke-opacity: 0.5; fill-opacity: 0.4;\" />\n", - obstacle->id(), bBox.min.x, bBox.min.y, - bBox.max.x - bBox.min.x, bBox.max.y - bBox.min.y); - ++obstacleIt; - } - fprintf(fp, "</g>\n"); - - fprintf(fp, "<g inkscape:groupmode=\"layer\" " - "inkscape:label=\"DisplayConnectors\"" - ">\n"); - ConnRefList::iterator connRefIt = connRefs.begin(); - while (connRefIt != connRefs.end()) - { - ConnRef *connRef = *connRefIt; - - PolyLine route = connRef->displayRoute(); - if (!route.empty()) - { - fprintf(fp, "<path id=\"disp-%u\" d=\"M %g %g ", connRef->id(), - route.ps[0].x, route.ps[0].y); - for (size_t i = 1; i < route.size(); ++i) - { - fprintf(fp, "L %g %g ", route.ps[i].x, route.ps[i].y); - } - fprintf(fp, "\" "); - fprintf(fp, "style=\"fill: none; stroke: black; " - "stroke-width: 1px;\" />\n"); - - /* - for (size_t i = 1; i < route.size(); ++i) - { - if (route.segmentHasCheckpoint[i - 1]) - { - fprintf(fp, "<path d=\"M %g %g ", - route.ps[i - 1].x, route.ps[i - 1].y); - fprintf(fp, "L %g %g\" ", route.ps[i].x, route.ps[i].y); - fprintf(fp, "style=\"fill: none; stroke: red; " - "stroke-width: 1px; stroke-opacity: 1;\" />\n"); - } - } - */ - } - - ++connRefIt; - } - fprintf(fp, "</g>\n"); - - if (lineReps) - { - - for (LineReps::iterator it = lineReps->begin(); it != lineReps->end(); - ++it) - { - fprintf(fp, "<path d=\"M %g %g ", - it->begin.x, it->begin.y); - fprintf(fp, "L %g %g\" ", it->end.x, it->end.y); - fprintf(fp, "style=\"fill: none; stroke: red; " - "stroke-width: 1px; stroke-opacity: 0.7;\" />\n"); - } - } - - fprintf(fp, "</svg>\n"); - fclose(fp); -} - -void Router::outputDiagram(std::string instanceName) -{ - outputDiagramText(instanceName); -#ifdef SVG_OUTPUT - outputInstanceToSVG(instanceName); -#endif -} - -void Router::outputDiagramText(std::string instanceName) -{ - std::string filename; - if (!instanceName.empty()) - { - filename = instanceName; - } - else - { - filename = "libavoid-diagram"; - } - filename += ".txt"; - FILE *fp = fopen(filename.c_str(), "w"); - - if (fp == NULL) - { - return; - } - - ObstacleList::iterator obstacleIt = m_obstacles.begin(); - while (obstacleIt != m_obstacles.end()) - { - Obstacle *obstacle = *obstacleIt; - bool isShape = (NULL != dynamic_cast<ShapeRef *> (obstacle)); - - if ( ! isShape ) - { - // Don't output non-shape obstacles here, for now. - ++obstacleIt; - continue; - } - - Box bBox = obstacle->polygon().offsetBoundingBox(0.0); - - fprintf(fp, "rect\n"); - fprintf(fp, "id=%u\n", obstacle->id()); - fprintf(fp, "x=%g\n", bBox.min.x); - fprintf(fp, "y=%g\n", bBox.min.y); - fprintf(fp, "width=%g\n", bBox.max.x - bBox.min.x); - fprintf(fp, "height=%g\n", bBox.max.y - bBox.min.y); - fprintf(fp, "\n"); - - ++obstacleIt; - } - - ConnRefList::iterator connRefIt = connRefs.begin(); - while (connRefIt != connRefs.end()) - { - ConnRef *connRef = *connRefIt; - - PolyLine route = connRef->displayRoute(); - if (!route.empty()) - { - fprintf(fp, "path\n"); - fprintf(fp, "id=%u\n", connRef->id()); - for (size_t i = 0; i < route.size(); ++i) - { - fprintf(fp, "p%lu: %g %g ", i, route.ps[i].x, route.ps[i].y); - fprintf(fp, "\n"); - } - fprintf(fp, "\n"); - } - - ++connRefIt; - } - - fprintf(fp, "\n"); - - fclose(fp); -} - -HyperedgeNewAndDeletedObjectLists - Router::newAndDeletedObjectListsFromHyperedgeImprovement(void) const -{ - return m_hyperedge_improver.newAndDeletedObjectLists(); -} - - -ConnRerouteFlagDelegate::ConnRerouteFlagDelegate() -{ -} - -ConnRerouteFlagDelegate::~ConnRerouteFlagDelegate() -{ -} - -bool *ConnRerouteFlagDelegate::addConn(ConnRef *conn) -{ - m_mapping.push_back(std::make_pair(conn, false)); - return &(m_mapping.back().second); -} - -void ConnRerouteFlagDelegate::removeConn(ConnRef *conn) -{ - std::list<std::pair<ConnRef *, bool> >::iterator it; - for (it = m_mapping.begin(); it != m_mapping.end(); ++it) - { - if (it->first == conn) - { - it->first = NULL; - } - } -} - - -void ConnRerouteFlagDelegate::alertConns(void) -{ - std::list<std::pair<ConnRef *, bool> >::iterator it; - for (it = m_mapping.begin(); it != m_mapping.end(); ++it) - { - if ((it->first != NULL) && (it->second == true)) - { - it->second = false; - it->first->m_needs_reroute_flag = true; - } - } -} - - -} - |