diff options
Diffstat (limited to 'src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.cpp')
| -rw-r--r-- | src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.cpp | 1232 |
1 files changed, 1232 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.cpp b/src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.cpp new file mode 100644 index 0000000..bf7c357 --- /dev/null +++ b/src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.cpp @@ -0,0 +1,1232 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * + * Copyright (C) 2009-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 <sstream> +#include <iomanip> + +#include "libavoid/router.h" +#include "libavoid/shape.h" +#include "libavoid/junction.h" +#include "libavoid/vpsc.h" +#include "libavoid/assertions.h" +#include "libavoid/hyperedgetree.h" +#include "libavoid/hyperedgeimprover.h" +#include "libavoid/scanline.h" +#include "libavoid/debug.h" + +namespace Avoid { + +class HyperedgeShiftSegment : public ShiftSegment +{ + public: + HyperedgeShiftSegment(HyperedgeTreeNode *n1, HyperedgeTreeNode *n2, + const size_t dim, bool immovable) + : ShiftSegment(dim), + nodes((dim + 1) % 2), + isImmovable(immovable), + m_balance_count(0), + m_balance_count_set(false), + m_at_limit(false) + { + nodes.insert(n1); + nodes.insert(n2); + n1->shiftSegmentNodeSet = &nodes; + n2->shiftSegmentNodeSet = &nodes; + + minSpaceLimit = -CHANNEL_MAX; + maxSpaceLimit = CHANNEL_MAX; + } + virtual ~HyperedgeShiftSegment() + { + for (OrderedHENodeSet::const_iterator curr = nodes.begin(); + curr != nodes.end(); ++curr) + { + (*curr)->shiftSegmentNodeSet = nullptr; + } + } + + Point& lowPoint(void) + { + return (*nodes.begin())->point; + } + Point& highPoint(void) + { + return (*nodes.rbegin())->point; + } + const Point& lowPoint(void) const + { + return (*nodes.begin())->point; + } + const Point& highPoint(void) const + { + return (*nodes.rbegin())->point; + } + // Counts the number of segments diverging on each side and returns + // a count: a negative number if there a more on the lower side, + // a positive number if there are more on the upper side, or zero if + // there are an equal number of segments. + void setBalanceCount(void) + { + size_t altDim = (dimension + 1) % 2; + m_next_pos_lower = minSpaceLimit; + m_next_pos_upper = maxSpaceLimit; + m_balance_count = 0; + if ( isImmovable ) + { + m_balance_count_set = true; + return; + } + for (OrderedHENodeSet::const_iterator curr = nodes.begin(); + curr != nodes.end(); ++curr) + { + const Point& currPoint = (*curr)->point; + for (std::list<HyperedgeTreeEdge *>::const_iterator currEdge = + (*curr)->edges.begin(); currEdge != (*curr)->edges.end(); + ++currEdge) + { + const HyperedgeTreeNode *node = (*currEdge)->followFrom(*curr); + const Point& otherPoint = node->point; + if (currPoint[altDim] == otherPoint[altDim]) + { + if (otherPoint[dimension] < currPoint[dimension]) + { + m_next_pos_lower = std::max(m_next_pos_lower, + otherPoint[dimension]); + --m_balance_count; + } + else if (otherPoint[dimension] > currPoint[dimension]) + { + m_next_pos_upper = std::min(m_next_pos_upper, + otherPoint[dimension]); + ++m_balance_count; + } + } + } + } + m_balance_count_set = true; + } + int balanceCount(void) const + { + COLA_ASSERT( m_balance_count_set ); + return m_balance_count; + } + void adjustPosition(void) + { + COLA_ASSERT(m_balance_count_set); + COLA_ASSERT(m_balance_count != 0); + + double newPos = (m_balance_count < 0) ? + m_next_pos_lower : m_next_pos_upper; + double limit = (m_balance_count < 0) ? + minSpaceLimit : maxSpaceLimit; + if (lowPoint()[dimension] == newPos) + { + // If aren't actually moving this segment, then mark it + // as at-limit. + // XXX This seems to be because of a segment with an + // incorrectly marked limit, possibly due to a + // junction positioned within a shape. + m_at_limit = true; + } + + for (OrderedHENodeSet::iterator curr = nodes.begin(); + curr != nodes.end(); ++curr) + { + (*curr)->point[dimension] = newPos; + } + + if (newPos == limit) + { + m_at_limit = true; + } + + // Add nodes from collapsed segments, in case they are not part of + // a segment that will be merged. + for (OrderedHENodeSet::iterator curr = nodes.begin(); + curr != nodes.end(); ++curr) + { + Point& currPoint = (*curr)->point; + for (std::list<HyperedgeTreeEdge *>::iterator currEdge = + (*curr)->edges.begin(); currEdge != (*curr)->edges.end(); + ++currEdge) + { + HyperedgeTreeNode *node = (*currEdge)->followFrom(*curr); + Point& otherPoint = node->point; + if (currPoint == otherPoint) + { + nodes.insert(node); + node->shiftSegmentNodeSet = &nodes; + } + } + } + } + bool overlapsWith(const ShiftSegment *rhs, const size_t dim) const + { + size_t altDim = (dim + 1) % 2; + const Point& lowPt = lowPoint(); + const Point& highPt = highPoint(); + const Point& rhsLowPt = rhs->lowPoint(); + const Point& rhsHighPt = rhs->highPoint(); + if ( (lowPt[altDim] <= rhsHighPt[altDim]) && + (rhsLowPt[altDim] <= highPt[altDim])) + { + // The segments overlap. + if ( (minSpaceLimit <= rhs->maxSpaceLimit) && + (rhs->minSpaceLimit <= maxSpaceLimit) ) + { + return true; + } + } + return false; + } + bool immovable(void) const + { + return isImmovable; + } + bool settled(void) const + { + return isImmovable || m_at_limit || (balanceCount() == 0); + } + bool mergesWith(HyperedgeShiftSegment *other) + { + size_t altDim = (dimension + 1) % 2; + const Point& lowPt = lowPoint(); + const Point& highPt = highPoint(); + const Point& otherLowPt = other->lowPoint(); + const Point& otherHighPt = other->highPoint(); + if ( (lowPt[dimension] == otherLowPt[dimension]) && + (lowPt[altDim] <= otherHighPt[altDim]) && + (otherLowPt[altDim] <= highPt[altDim])) + { + isImmovable |= other->isImmovable; + m_at_limit |= m_at_limit; + minSpaceLimit = std::max(minSpaceLimit, other->minSpaceLimit); + maxSpaceLimit = std::min(maxSpaceLimit, other->maxSpaceLimit); + nodes.insert(other->nodes.begin(), other->nodes.end()); + other->nodes.clear(); + for (OrderedHENodeSet::iterator curr = nodes.begin(); + curr != nodes.end(); ++curr) + { + (*curr)->shiftSegmentNodeSet = &nodes; + } + setBalanceCount(); + return true; + } + setBalanceCount(); + return false; + } + + std::set<HyperedgeTreeNode *, CmpNodesInDim> nodes; + bool isImmovable; +private: + int m_balance_count; + bool m_balance_count_set; + double m_next_pos_lower; + double m_next_pos_upper; + bool m_at_limit; +}; + +#if 0 +// UNUSED +static bool CmpHyperedgeSegmentDirOrder(const ShiftSegment *lhsSuper, + const ShiftSegment *rhsSuper) +{ + const HyperedgeShiftSegment *lhs = + dynamic_cast<const HyperedgeShiftSegment *> (lhsSuper); + const HyperedgeShiftSegment *rhs = + dynamic_cast<const HyperedgeShiftSegment *> (rhsSuper); + + return fabs(lhs->balanceCount()) > fabs(rhs->balanceCount()); +} +#endif + + +// Constructor. +HyperedgeImprover::HyperedgeImprover() + : m_router(nullptr) +{ + clear(); +} + +void HyperedgeImprover::setRouter(Router *router) +{ + m_router = router; +} + +void HyperedgeImprover::clear(void) +{ + m_hyperedge_tree_junctions.clear(); + m_hyperedge_tree_roots.clear(); + m_root_shift_segments.clear(); + m_all_shift_segments.clear(); + m_new_junctions.clear(); + m_deleted_junctions.clear(); + m_new_connectors.clear(); + m_deleted_connectors.clear(); + m_changed_connectors.clear(); + m_debug_count = 0; +} + +// Helper method for buildHyperedgeSegments() for hyperedge tree nodes. +void HyperedgeImprover::createShiftSegmentsForDimensionExcluding( + HyperedgeTreeNode *node, const size_t dim, HyperedgeTreeEdge *ignore, + ShiftSegmentList& segments) +{ + for (std::list<HyperedgeTreeEdge *>::iterator curr = node->edges.begin(); + curr != node->edges.end(); ++curr) + { + HyperedgeTreeEdge *edge = *curr; + if (edge != ignore) + { + createShiftSegmentsForDimensionExcluding(edge, dim, + node, segments); + } + } +} + +// Helper method for buildHyperedgeSegments() for hyperedge tree edges. +void HyperedgeImprover::createShiftSegmentsForDimensionExcluding( + HyperedgeTreeEdge *edge, const size_t dim, HyperedgeTreeNode *ignore, + ShiftSegmentList& segments) +{ + if (edge->hasOrientation(dim) && ! edge->zeroLength()) + { + bool immovable = (edge->ends.first->isImmovable() || + edge->ends.second->isImmovable()); + + HyperedgeShiftSegment *newSegment = + new HyperedgeShiftSegment(edge->ends.first, + edge->ends.second, dim, immovable); + segments.push_back(newSegment); + } + + if (edge->ends.first && (edge->ends.first != ignore)) + { + createShiftSegmentsForDimensionExcluding(edge->ends.first, dim, + edge, segments); + } + + if (edge->ends.second && (edge->ends.second != ignore)) + { + createShiftSegmentsForDimensionExcluding(edge->ends.second, dim, + edge, segments); + } +} + +// During creation and nudging of shift segments it is often necessary +// to merge collinear or overlapping segments. This method does the +// merging for these cases. Effectively merging is done by adding +// additional vertex pointers to the shift segment. +void HyperedgeImprover::mergeOverlappingSegments(ShiftSegmentList& segments) +{ + for (ShiftSegmentList::iterator curr = segments.begin(); + curr != segments.end(); ++curr) + { + HyperedgeShiftSegment *edge1 = + static_cast<HyperedgeShiftSegment *> (*curr); + for (ShiftSegmentList::iterator curr2 = segments.begin(); + curr2 != segments.end(); ) + { + if (curr2 == curr) + { + ++curr2; + continue; + } + HyperedgeShiftSegment *edge2 = + static_cast<HyperedgeShiftSegment *> (*curr2); + if (edge1->mergesWith(edge2)) + { + delete edge2; + curr2 = segments.erase(curr2); + } + else + { + ++curr2; + } + } + } +} + +// Given a hyperedge tree and a dimension, this method creates shift +// segments for all edges in that orientation. These segments are the +// objects on which the local improvement nudging operates, and they +// in turn make changes back to the hyperedge tree. +void HyperedgeImprover::buildHyperedgeSegments(const size_t dim) +{ + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + ShiftSegmentList& segments = m_root_shift_segments[*curr]; + + HyperedgeTreeNode *node = m_hyperedge_tree_junctions[*curr]; + createShiftSegmentsForDimensionExcluding(node, dim, nullptr, segments); + + // Merge overlapping segment. + mergeOverlappingSegments(segments); + + m_all_shift_segments.insert(m_all_shift_segments.begin(), + segments.begin(), segments.end()); + } +} + +// This method looks for and corrects situations where the middle section +// of a zigzag is optimised away by bringing the outside segments in line +// and leading to the middle segment being zero length. These zero length +// edges are removed. +void HyperedgeImprover::removeZeroLengthEdges(void) +{ + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + HyperedgeTreeNode *node = m_hyperedge_tree_junctions[*curr]; + + removeZeroLengthEdges(node, nullptr); + } +} + +// This method looks for and correct situations where multiple overlapping +// edges lead to a junction and one or more of these segments could be +// removed by moving the junction (and thus divergence point) along the +// edge. +void HyperedgeImprover::moveJunctionsAlongCommonEdges(void) +{ + for (JunctionHyperedgeTreeNodeMap::iterator curr = + m_hyperedge_tree_junctions.begin(); + curr != m_hyperedge_tree_junctions.end(); ) + { + HyperedgeTreeNode *node = curr->second; + + bool nodeMapHasChanged = false; + // For each junction, try and move it. + while ((node = moveJunctionAlongCommonEdge(node, nodeMapHasChanged))) + { + if (node) + { + // Junction has moved, rewrite the pointer in + // the m_hyperedge_tree_junctions map. + curr->second = node; + } + } + + if (nodeMapHasChanged) + { + // Objects have been added to m_hyperedge_tree_junctions and + // this may be earlier than our current iterator, so restart. + curr = m_hyperedge_tree_junctions.begin(); + } + else + { + ++curr; + } + } +} + +// This method traverses the hyperedge tree removing zero length edges. +// +void HyperedgeImprover::removeZeroLengthEdges(HyperedgeTreeEdge *self, + HyperedgeTreeNode *ignored) +{ + if (self->ends.first != ignored) + { + removeZeroLengthEdges(self->ends.first, self); + } + + if (self->ends.second != ignored) + { + removeZeroLengthEdges(self->ends.second, self); + } +} + + +// This method traverses the hyperedge tree removing zero length edges. +// +void HyperedgeImprover::removeZeroLengthEdges(HyperedgeTreeNode *self, + HyperedgeTreeEdge *ignored) +{ + for (std::list<HyperedgeTreeEdge *>::iterator curr = self->edges.begin(); + curr != self->edges.end(); ++curr) + { + HyperedgeTreeEdge *edge = *curr; + if (edge != ignored) + { + if (!edge->hasFixedRoute && edge->zeroLength()) + { + HyperedgeTreeNode *other = edge->followFrom(self); + HyperedgeTreeNode *target = nullptr; + HyperedgeTreeNode *source = nullptr; + if (other->junction && ! self->junction) + { + target = other; + source = self; + } + else if ( ! other->junction && self->junction) + { + target = self; + source = other; + } + else if ( ! other->junction && ! self->junction) + { + target = self; + source = other; + } + else if ( other->junction && self->junction && + m_can_make_major_changes) + { + // Only delete junctions if we can make major changes. + +#ifdef MAJOR_HYPEREDGE_IMPROVEMENT_DEBUG + fprintf(stderr, "HyperedgeImprover: Coalescing junctions " + "%u and %u:\n", self->junction->id(), + other->junction->id()); + fprintf(stderr, " Deleted junction %u\n", + other->junction->id()); + fprintf(stderr, " Deleted connector %u\n", + edge->conn->id()); +#endif + + // Delete one of the junctions. + m_deleted_junctions.push_back(other->junction); + m_hyperedge_tree_junctions.erase(other->junction); + if (m_hyperedge_tree_roots.count(other->junction) > 0) + { + // If 'other' was the root for the hyperedge, we need + // to make 'self' the new root. + m_hyperedge_tree_roots.erase(other->junction); + m_hyperedge_tree_roots.insert(self->junction); + // It should already be in the junctions list. + COLA_ASSERT(m_hyperedge_tree_junctions. + count(self->junction) == 1); + } + other->junction = nullptr; + + // Delete the connector on the zero length edge. + m_deleted_connectors.push_back(edge->conn); + edge->conn = nullptr; + + target = self; + source = other; + } + + if (target) + { + edge->disconnectEdge(); + delete edge; + target->spliceEdgesFrom(source); + delete source; + removeZeroLengthEdges(target, ignored); + return; + } + } + + // Recursive call. + removeZeroLengthEdges(edge, self); + } + } +} + + + +// Given a set of hyperedge shift segments in a particular dimension, +// with limits and balance values precomputed, this method shifts and +// merges segments to improve the overall cost (length + bend penalties) +// for the hyperedge. +void HyperedgeImprover::nudgeHyperedgeSegments(size_t dimension, + unsigned int& versionNumber) +{ + // For each hyperedge... + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + ++m_debug_count; + versionNumber = (int)dimension * 10000; + versionNumber += m_debug_count * 1000; + + // Calculate the balance for each shift segment. + ShiftSegmentList& segmentList = m_root_shift_segments[*curr]; + for (ShiftSegmentList::iterator currSeg = segmentList.begin(); + currSeg != segmentList.end(); ) + { + HyperedgeShiftSegment *segment = + static_cast<HyperedgeShiftSegment *> (*currSeg); + segment->setBalanceCount(); + + ++currSeg; + } + + //segmentList.sort(CmpHyperedgeSegmentDirOrder); + + bool change = false; + ShiftSegmentList::iterator currSeg = segmentList.begin(); + while (currSeg != segmentList.end()) + { + // While we haven't considered every segment... + + HyperedgeShiftSegment *segment = + static_cast<HyperedgeShiftSegment *> (*currSeg); + + if ( ! segment->settled() ) + { + // The segment is not settled, so move it to the next + // ideal position and then merge it with overlapping + // segments. Note, the merged segment will have a new + // balance value calculated for it. + segment->adjustPosition(); + outputHyperedgesToSVG(++versionNumber, segment); + mergeOverlappingSegments(segmentList); + change = true; + } + + if (change) + { + // We made a change, so start again from the beginning + // of the list of segments. + change = false; + currSeg = segmentList.begin(); + } + else + { + // Consider the next segment. + ++currSeg; + } + } + } +} + +// Write the paths from an improved hyperedgetree object back as routes +// to the component connectors that form the hyperedge. +void HyperedgeImprover::writeHyperedgeSegmentsBackToConnPaths(void) +{ + // Write segments in two passes. The first to clear the existing + // connector routes and the second to build and set new routes. + for (size_t pass = 0; pass < 2; ++pass) + { + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + HyperedgeTreeNode *node = m_hyperedge_tree_junctions[*curr]; + + node->writeEdgesToConns(nullptr, pass); + } + } +} + +// Output the hyperedge tree to an SVG file, optionally highlighting +// a segment of interest (usually the segment being moved). +void HyperedgeImprover::outputHyperedgesToSVG(unsigned int pass, + HyperedgeShiftSegment *activeSegment) +{ +#ifndef HYPEREDGE_DEBUG + return; +#endif + + // Reasonable initial limit for diagram bounds. + const double LIMIT = 100000000; + + std::stringstream filename; + filename << "DEBUG/hyperedges-" << std::setfill('0') << std::setw(5) << pass << ".svg"; + FILE *fp = fopen(filename.str().c_str(), "w"); + + double minX = LIMIT; + double minY = LIMIT; + double maxX = -LIMIT; + double maxY = -LIMIT; + + VertInf *curr = m_router->vertices.connsBegin(); + while (curr) + { + Point p = curr->point; + + 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 -= 50; + minY -= 50; + maxX += 50; + maxY += 50; + + + 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_router->m_obstacles.begin(); + while (obstacleIt != m_router->m_obstacles.end()) + { + Obstacle *obstacle = *obstacleIt; + bool isShape = (nullptr != dynamic_cast<ShapeRef *> (obstacle)); + + if ( ! isShape ) + { + // Don't output 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: %s; " + "fill: blue; fill-opacity: 0.3;\" />\n", + obstacle->id(), bBox.min.x, bBox.min.y, + bBox.max.x - bBox.min.x, bBox.max.y - bBox.min.y, + (isShape) ? "blue" : "red"); + ++obstacleIt; + } + fprintf(fp, "</g>\n"); + + fprintf(fp, "<g inkscape:groupmode=\"layer\" " + "inkscape:label=\"Hyperedge-%u\">\n", pass); + if (activeSegment) + { + fprintf(fp, "<path d=\"M %g %g L %g %g\" " + "style=\"fill: none; stroke: %s; stroke-width: 12px; " + "stroke-opacity: 0.5;\" />\n", + activeSegment->lowPoint().x, activeSegment->lowPoint().y, + activeSegment->highPoint().x, activeSegment->highPoint().y, + activeSegment->settled() ? "red" : "orange"); + } + + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + HyperedgeTreeNode *node = m_hyperedge_tree_junctions[*curr]; + + node->outputEdgesExcept(fp, nullptr); + } + fprintf(fp, "</g>\n"); + fprintf(fp, "</svg>\n"); + + fclose(fp); +} + +// Given a junction, this method follows the attached connectors and +// junctions to determine a hyperedge and returns the set of vertices +// representing its endpoints. +void HyperedgeImprover::getEndpoints(JunctionRef *junction, JunctionRef *ignore, + std::set<VertInf *>& endpoints) +{ + for (std::set<ConnEnd *>::iterator curr = + junction->m_following_conns.begin(); + curr != junction->m_following_conns.end(); ++curr) + { + ConnEnd *connEnd = *curr; + COLA_ASSERT(connEnd->m_conn_ref != nullptr); + ConnRef *connRef = connEnd->m_conn_ref; + std::pair<Obstacle *, Obstacle *> anchors = + connRef->endpointAnchors(); + + JunctionRef *junction1 = + dynamic_cast<JunctionRef *> (anchors.first); + if (junction1) + { + if (junction1 != junction && junction1 != ignore) + { + getEndpoints(junction1, junction, endpoints); + } + } + else + { + endpoints.insert(connRef->m_src_vert); + } + + JunctionRef *junction2 = + dynamic_cast<JunctionRef *> (anchors.second); + if (junction2) + { + if (junction2 != junction && junction2 != ignore) + { + getEndpoints(junction2, junction, endpoints); + } + } + else + { + endpoints.insert(connRef->m_dst_vert); + } + } +} + +// Execute local improvement process. +void HyperedgeImprover::execute(bool canMakeMajorChanges) +{ + m_can_make_major_changes = canMakeMajorChanges; + + // Build Hyperedge trees. + ConnRefList::iterator connRefIt = m_router->connRefs.begin(); + while (connRefIt != m_router->connRefs.end()) + { + ConnRef *connRef = *connRefIt; + JunctionRef *jFront = nullptr; + JunctionRef *jBack = nullptr; + + if (connRef->m_src_connend) + { + jFront = connRef->m_src_connend->junction(); + } + + if (connRef->m_dst_connend) + { + jBack = connRef->m_dst_connend->junction(); + } + + if ( ! jFront && ! jBack ) + { + ++connRefIt; + continue; + } + + bool seenFront = (m_hyperedge_tree_junctions.find(jFront) != + m_hyperedge_tree_junctions.end()); + bool seenBack = (m_hyperedge_tree_junctions.find(jBack) != + m_hyperedge_tree_junctions.end()); + + HyperedgeTreeNode *nodeFront = nullptr; + HyperedgeTreeNode *nodeBack = nullptr; + + if (jFront) + { + if ( ! seenFront) + { + nodeFront = new HyperedgeTreeNode(); + nodeFront->point = jFront->position(); + nodeFront->junction = jFront; + + m_hyperedge_tree_junctions[jFront] = nodeFront; + } + else + { + nodeFront = m_hyperedge_tree_junctions[jFront]; + } + } + else + { + nodeFront = new HyperedgeTreeNode(); + } + + if (jBack) + { + if ( ! seenBack) + { + nodeBack = new HyperedgeTreeNode(); + nodeBack->point = jBack->position(); + nodeBack->junction = jBack; + + m_hyperedge_tree_junctions[jBack] = nodeBack; + } + else + { + nodeBack = m_hyperedge_tree_junctions[jBack]; + } + } + else + { + nodeBack = new HyperedgeTreeNode(); + } + + PolyLine& route = connRef->displayRoute(); + HyperedgeTreeNode *prev = nullptr; + for (unsigned int i = 1; i < route.size(); ++i) + { + HyperedgeTreeNode *node; + if (i + 1 == route.size()) + { + node = nodeBack; + } + else + { + node = new HyperedgeTreeNode(); + } + node->point = route.at(i); + if (i == 1) + { + prev = nodeFront; + nodeFront->point = route.at(0); + nodeFront->isConnectorSource = true; + } + new HyperedgeTreeEdge(prev, node, connRef); + prev = node; + } + ++connRefIt; + } + + // Make a list that contains a single junction from each tree. + for (JunctionHyperedgeTreeNodeMap::iterator curr = + m_hyperedge_tree_junctions.begin(); + curr != m_hyperedge_tree_junctions.end(); ++curr) + { + HyperedgeTreeNode *node = curr->second; + m_hyperedge_tree_roots.insert(node->junction); + } + JunctionRefList cyclicHyperedgeTreeRoots; + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + HyperedgeTreeNode *node = m_hyperedge_tree_junctions[*curr]; + bool containsCycle = node->removeOtherJunctionsFrom(nullptr, + m_hyperedge_tree_roots); + if (containsCycle) + { + // This hyperedge has a cycle. We will need to remove it. + cyclicHyperedgeTreeRoots.push_back(node->junction); + } + } + // Remove roots of cyclic hyperedges, we can't improve these. + for (JunctionRefList::iterator curr = cyclicHyperedgeTreeRoots.begin(); + curr != cyclicHyperedgeTreeRoots.end(); ++curr) + { + JunctionRef *junction = *curr; + err_printf("Warning: Skipping cyclic hyperedge rooted at junction %u\n", + junction->id()); + m_hyperedge_tree_roots.erase(junction); + } + + TIMER_START(m_router, tmHyperedgeImprove); + + // Debug output. + unsigned int versionNumber = 1; + outputHyperedgesToSVG(versionNumber); + + // Remove zero length edges. + removeZeroLengthEdges(); + + // Move junctions to divergence points. + moveJunctionsAlongCommonEdges(); + + // Debug output. + outputHyperedgesToSVG(++versionNumber); + + for (size_t count = 0; count < 4; ++count) + { + size_t dimension = count % 2; + + // Set a version number for debug output. + versionNumber = 100 * (int)(dimension + 1); + + // Build shift segments. + buildHyperedgeSegments(dimension); + // Calculate channel information for this dimension. + buildOrthogonalChannelInfo(m_router, dimension, m_all_shift_segments); + // Nudge hyperedge segments to locally improve the route. + nudgeHyperedgeSegments(dimension, versionNumber); + // Remove resulting zero length edges. + removeZeroLengthEdges(); + // Move junctions to divergence points. + moveJunctionsAlongCommonEdges(); + // Debug output. + outputHyperedgesToSVG(++versionNumber); + + // Clean up shift segments. + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + ShiftSegmentList& segmentList = m_root_shift_segments[*curr]; + for_each(segmentList.begin(), segmentList.end(), + delete_object()); + } + m_root_shift_segments.clear(); + m_all_shift_segments.clear(); + } + + // Rewrite updated connector attachments to junctions. + if (m_can_make_major_changes) + { + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + HyperedgeTreeNode *treeRoot = m_hyperedge_tree_junctions[*curr]; + COLA_ASSERT(treeRoot); + treeRoot->updateConnEnds(nullptr, m_router, m_changed_connectors); + + // Validate the rewrtten connections. + treeRoot->validateHyperedge(nullptr, 0); + } + } + + // Write back final recommended positions to junctions. + for (JunctionHyperedgeTreeNodeMap::iterator curr = + m_hyperedge_tree_junctions.begin(); + curr != m_hyperedge_tree_junctions.end(); ++curr) + { + HyperedgeTreeNode *node = curr->second; + + node->junction->setRecommendedPosition(node->point); + } + + // Write paths from the hyperedge tree back into individual + // connector routes. + writeHyperedgeSegmentsBackToConnPaths(); + + // Free HyperedgeTree structure. + for (JunctionSet::iterator curr = m_hyperedge_tree_roots.begin(); + curr != m_hyperedge_tree_roots.end(); ++curr) + { + HyperedgeTreeNode *node = m_hyperedge_tree_junctions[*curr]; + + node->deleteEdgesExcept(nullptr); + delete node; + } + + // Tell the router that we are deleting the objects used for the + // previous path for the hyperedge. + for (ConnRefList::iterator curr = m_deleted_connectors.begin(); + curr != m_deleted_connectors.end(); ++curr) + { + // Clear visibility assigned for connection pins. + (*curr)->assignConnectionPinVisibility(false); + + m_router->deleteConnector(*curr); + } + for (JunctionRefList::iterator curr = m_deleted_junctions.begin(); + curr != m_deleted_junctions.end(); ++curr) + { + m_router->deleteJunction(*curr); + } + + TIMER_STOP(m_router); +} + + +HyperedgeNewAndDeletedObjectLists + HyperedgeImprover::newAndDeletedObjectLists(void) const +{ + HyperedgeNewAndDeletedObjectLists result; + + result.newJunctionList = m_new_junctions; + result.deletedJunctionList = m_deleted_junctions; + result.newConnectorList = m_new_connectors; + result.deletedConnectorList = m_deleted_connectors; + result.changedConnectorList = m_changed_connectors; + + return result; +} + + +// This method moves the junction at the given node along any shared paths +// (so long as this action would not create any additional shared paths), +// while also removing and freeing merged edges and nodes in the process. +// It returns the new node where the junction is now located. +// +HyperedgeTreeNode *HyperedgeImprover::moveJunctionAlongCommonEdge( + HyperedgeTreeNode *self, bool& nodeMapHasChanged) +{ + COLA_ASSERT(self->junction); + + HyperedgeTreeNode *newSelf = nullptr; + std::vector<HyperedgeTreeEdge *> commonEdges; + std::vector<HyperedgeTreeEdge *> otherEdges; + + // Consider each edge from this node in turn. + for (std::list<HyperedgeTreeEdge *>::iterator curr = self->edges.begin(); + curr != self->edges.end(); ++curr) + { + HyperedgeTreeEdge *currEdge = *curr; + HyperedgeTreeNode *currNode = currEdge->followFrom(self); + commonEdges.clear(); + otherEdges.clear(); + + if (currNode->junction) + { + // Don't shift junctions onto other junctions. + continue; + } + if (currEdge->hasFixedRoute) + { + // Don't move junctions along fixed edges. + continue; + } + + // The current edge is a common edge we are looking to shift along. + commonEdges.push_back(currEdge); + + // Consider each of the other edges. + for (std::list<HyperedgeTreeEdge *>::iterator curr2 = + self->edges.begin(); curr2 != self->edges.end(); ++curr2) + { + if (curr == curr2) + { + // Except the current (curr) one. + continue; + } + + HyperedgeTreeEdge *otherEdge = *curr2; + if (otherEdge->hasFixedRoute) + { + // Don't shift junctions along fixed route connectors. + otherEdges.push_back(otherEdge); + continue; + } + + HyperedgeTreeNode *otherNode = otherEdge->followFrom(self); + if (otherNode->point == currNode->point) + { + // A common edge can be at the same point, but can't have + // a junction at it. + if (otherNode->junction) + { + otherEdges.push_back(otherEdge); + } + else + { + commonEdges.push_back(otherEdge); + } + } + else if (pointOnLine(self->point, otherNode->point, + currNode->point)) + { + // A common edge can be a (longer) collinear line, but we + // need to split the longer line at the other end of curr. + otherEdge->splitFromNodeAtPoint(self, currNode->point); + commonEdges.push_back(otherEdge); + } + else + { + // If the edge goes in another direction it is not common. + otherEdges.push_back(otherEdge); + } + } + + // For the purpose of these changes a junction is considered fixed + // only when not performing major improvements. + bool selfFixed = self->junction->positionFixed() && + !m_can_make_major_changes; + + if ((commonEdges.size() > 1) && (otherEdges.size() <= 1) && !selfFixed) + { + // One of the common nodes becomes the target node, we move + // all connections from the other common nodes to this node. + // We also move the junction there and remove it from the + // current node. + HyperedgeTreeNode *targetNode = commonEdges[0]->followFrom(self); + for (size_t i = 1; i < commonEdges.size(); ++i) + { + HyperedgeTreeNode *thisNode = commonEdges[i]->followFrom(self); + commonEdges[i]->disconnectEdge(); + targetNode->spliceEdgesFrom(thisNode); + delete thisNode; + delete commonEdges[i]; + } + targetNode->junction = self->junction; + self->junction = nullptr; + + if (otherEdges.empty()) + { + // Nothing else connected to this node, so remove the node + // and the edge to the target node. + commonEdges[0]->disconnectEdge(); + + delete commonEdges[0]; + delete self; + } + else + { + // We need to mark commonEdges[0] as being from the connector + // of the otherEdges[0]. + commonEdges[0]->conn = otherEdges[0]->conn; + } + newSelf = targetNode; + + break; + } + else if (m_can_make_major_changes && (commonEdges.size() > 1) && + (otherEdges.size() > 1)) + { + // Case where this is one junction we need to split into two, + // because we have a common path leading to it that we want to + // move the junction along, but multiple other edges leaving + // this junction that need to stay in place. + + // One of the common nodes becomes the target node, we move + // all connections from the other common nodes to this node. + // We will also create a new junction there. + HyperedgeTreeNode *targetNode = commonEdges[0]->followFrom(self); + for (size_t i = 1; i < commonEdges.size(); ++i) + { + HyperedgeTreeNode *thisNode = commonEdges[i]->followFrom(self); + commonEdges[i]->disconnectEdge(); + targetNode->spliceEdgesFrom(thisNode); + delete thisNode; + delete commonEdges[i]; + } + + // Create the additional junction at the target node for + // the otherEdges to attach to. + targetNode->junction = new JunctionRef(m_router, targetNode->point); + m_router->removeObjectFromQueuedActions(targetNode->junction); + targetNode->junction->makeActive(); + m_hyperedge_tree_junctions[targetNode->junction] = targetNode; + nodeMapHasChanged = true; + m_new_junctions.push_back(targetNode->junction); + + // And we create a new connector between the original junction + // and the new junction. + ConnRef *conn = new ConnRef(m_router); + m_router->removeObjectFromQueuedActions(conn); + conn->makeActive(); + conn->m_initialised = true; + ConnEnd srcConnend(targetNode->junction); + conn->updateEndPoint(VertID::src, srcConnend); + ConnEnd tarConnend(self->junction); + conn->updateEndPoint(VertID::tar, tarConnend); + commonEdges[0]->conn = conn; + m_new_connectors.push_back(conn); + +#ifdef MAJOR_HYPEREDGE_IMPROVEMENT_DEBUG + fprintf(stderr, "HyperedgeImprover: Split junction %u:\n", + self->junction->id()); + fprintf(stderr, " Added junction %u\n", + targetNode->junction->id()); + fprintf(stderr, " Added connector %u " + "(between junctions %u and %u)\n", conn->id(), + self->junction->id(), targetNode->junction->id()); +#endif + + newSelf = self; + + break; + } + } + + return newSelf; +} + + + + +} |