Put adaptagrams into its own folder

1 files changed, 0 insertions, 1231 deletions

diff --git a/src/libavoid/hyperedgeimprover.cpp b/src/libavoid/hyperedgeimprover.cpp
deleted file mode 100644
index 62d026093..000000000
--- a/src/libavoid/hyperedgeimprover.cpp
+++ /dev/null
@@ -1,1231 +0,0 @@
-/*
- * 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 "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 = NULL;
-            }
-        }
-
-        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(NULL)
-{
-    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, NULL, 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, NULL);
-    }
-}
-
-// 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 = NULL;
-                HyperedgeTreeNode *source = NULL;
-                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 = NULL;
-
-                    // Delete the connector on the zero length edge.
-                    m_deleted_connectors.push_back(edge->conn);
-                    edge->conn = NULL;
-
-                    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(NULL, 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;
-
-    char filename[50];
-    sprintf(filename, "DEBUG/hyperedges-%05u.svg", pass);
-    FILE *fp = fopen(filename, "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 = (NULL != 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, NULL);
-    }
-    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 != NULL);
-        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 = NULL;
-        JunctionRef *jBack = NULL;
-
-        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 = NULL;
-        HyperedgeTreeNode *nodeBack = NULL;
-
-        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 = NULL;
-        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(NULL, 
-                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(NULL, m_router, m_changed_connectors);
-        
-            // Validate the rewrtten connections.
-            treeRoot->validateHyperedge(NULL, 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(NULL);
-        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 = NULL;
-    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 = NULL;
-
-            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;
-}
-
-
-
-
-}
-