src/libavoid/router.cpp

   1 /*
   2  * vim: ts=4 sw=4 et tw=0 wm=0
   3  *
   4  * libavoid - Fast, Incremental, Object-avoiding Line Router
   5  *
   6  * Copyright (C) 2004-2009  Monash University
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  * See the file LICENSE.LGPL distributed with the library.
  13  *
  14  * Licensees holding a valid commercial license may use this file in
  15  * accordance with the commercial license agreement provided with the
  16  * library.
  17  *
  18  * This library is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  21  *
  22  * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
  23 */
  24
  25
  26 #include <algorithm>
  27 #include <cmath>
  28
  29 #include "libavoid/shape.h"
  30 #include "libavoid/router.h"
  31 #include "libavoid/visibility.h"
  32 #include "libavoid/connector.h"
  33 #include "libavoid/debug.h"
  34 #include "libavoid/orthogonal.h"
  35 #include "libavoid/assertions.h"
  36
  37 namespace Avoid {
  38
  39
  40 enum ActionType {
  41     ShapeMove,
  42     ShapeAdd,
  43     ShapeRemove,
  44     ConnChange
  45 };
  46
  47 typedef std::list<std::pair<unsigned int, ConnEnd> > ConnUpdateList;
  48
  49 class ActionInfo {
  50     public:
  51         ActionInfo(ActionType t, ShapeRef *s, const Polygon& p, bool fM)
  52             : type(t),
  53               objPtr(s),
  54               newPoly(p),
  55               firstMove(fM)
  56         {
  57             COLA_ASSERT(type == ShapeMove);
  58         }
  59         ActionInfo(ActionType t, ShapeRef *s)
  60             : type(t),
  61               objPtr(s)
  62         {
  63             COLA_ASSERT(type != ConnChange);
  64         }
  65         ActionInfo(ActionType t, ConnRef *c)
  66             : type(t),
  67               objPtr(c)
  68         {
  69             COLA_ASSERT(type == ConnChange);
  70         }
  71         ~ActionInfo()
  72         {
  73         }
  74         ShapeRef *shape(void) const
  75         {
  76             COLA_ASSERT((type == ShapeMove) || (type == ShapeAdd) ||
  77                     (type == ShapeRemove));
  78             return (static_cast<ShapeRef *> (objPtr));
  79         }
  80         ConnRef *conn(void) const
  81         {
  82             COLA_ASSERT(type == ConnChange);
  83             return (static_cast<ConnRef *> (objPtr));
  84         }
  85         bool operator==(const ActionInfo& rhs) const
  86         {
  87             return (type == rhs.type) && (objPtr == rhs.objPtr);
  88         }
  89         bool operator<(const ActionInfo& rhs) const
  90         {
  91             if (type != rhs.type)
  92             {
  93                 return type < rhs.type;
  94             }
  95             return objPtr < rhs.objPtr;
  96         }
  97         ActionType type;
  98         void *objPtr;
  99         Polygon newPoly;
 100         bool firstMove;
 101         ConnUpdateList conns;
 102 };
 103
 104
 105 Router::Router(const unsigned int flags)
 106     : visOrthogGraph(true),
 107       PartialTime(false),
 108       SimpleRouting(false),
 109       ClusteredRouting(true),
 110       // Poly-line algorithm options:
 111       IgnoreRegions(true),
 112       UseLeesAlgorithm(true),
 113       InvisibilityGrph(true),
 114       // General algorithm options:
 115       SelectiveReroute(true),
 116       PartialFeedback(false),
 117       RubberBandRouting(false),
 118       // Instrumentation:
 119       st_checked_edges(0),
 120 #ifdef LIBAVOID_SDL
 121       avoid_screen(NULL),
 122 #endif
 123       _largestAssignedId(0),
 124       _consolidateActions(true),
 125       _orthogonalNudgeDistance(4.0),
 126       // Mode options:
 127       _polyLineRouting(false),
 128       _orthogonalRouting(false),
 129       _staticGraphInvalidated(true),
 130       _inCrossingPenaltyReroutingStage(false)
 131 {
 132     // At least one of the Routing modes must be set.
 133     COLA_ASSERT(flags & (PolyLineRouting | OrthogonalRouting));
 134
 135     if (flags & PolyLineRouting)
 136     {
 137         _polyLineRouting = true;
 138     }
 139     if (flags & OrthogonalRouting)
 140     {
 141         _orthogonalRouting = true;
 142     }
 143
 144     for (size_t p = 0; p < lastPenaltyMarker; ++p)
 145     {
 146         _routingPenalties[p] = 0.0;
 147     }
 148     _routingPenalties[clusterCrossingPenalty] = 4000;
 149 }
 150
 151
 152 Router::~Router()
 153 {
 154     // Delete remaining connectors.
 155     ConnRefList::iterator conn = connRefs.begin();
 156     while (conn != connRefs.end())
 157     {
 158         db_printf("Deleting connector %u in ~Router()\n", (*conn)->id());
 159         delete *conn;
 160         conn = connRefs.begin();
 161     }
 162
 163     // Remove remaining shapes.
 164     ShapeRefList::iterator shape = shapeRefs.begin();
 165     while (shape != shapeRefs.end())
 166     {
 167         ShapeRef *shapePtr = *shape;
 168         db_printf("Deleting shape %u in ~Router()\n", shapePtr->id());
 169         if (shapePtr->isActive())
 170         {
 171             shapePtr->removeFromGraph();
 172             shapePtr->makeInactive();
 173         }
 174         delete shapePtr;
 175         shape = shapeRefs.begin();
 176     }
 177
 178     // Cleanup orphaned orthogonal graph vertices.
 179     destroyOrthogonalVisGraph();
 180
 181     COLA_ASSERT(connRefs.size() == 0);
 182     COLA_ASSERT(shapeRefs.size() == 0);
 183     COLA_ASSERT(visGraph.size() == 0);
 184     COLA_ASSERT(invisGraph.size() == 0);
 185 }
 186
 187
 188 void Router::modifyConnector(ConnRef *conn, const unsigned int type,
 189         const ConnEnd& connEnd)
 190 {
 191     ActionInfo modInfo(ConnChange, conn);
 192
 193     ActionInfoList::iterator found =
 194             find(actionList.begin(), actionList.end(), modInfo);
 195     if (found == actionList.end())
 196     {
 197         modInfo.conns.push_back(std::make_pair(type, connEnd));
 198         actionList.push_back(modInfo);
 199     }
 200     else
 201     {
 202         found->conns.push_back(std::make_pair(type, connEnd));
 203     }
 204
 205     if (!_consolidateActions)
 206     {
 207         processTransaction();
 208     }
 209 }
 210
 211
 212 void Router::modifyConnector(ConnRef *conn)
 213 {
 214     ActionInfo modInfo(ConnChange, conn);
 215
 216     ActionInfoList::iterator found =
 217             find(actionList.begin(), actionList.end(), modInfo);
 218     if (found == actionList.end())
 219     {
 220         actionList.push_back(modInfo);
 221     }
 222
 223     if (!_consolidateActions)
 224     {
 225         processTransaction();
 226     }
 227 }
 228
 229
 230 void Router::removeQueuedConnectorActions(ConnRef *conn)
 231 {
 232     ActionInfo modInfo(ConnChange, conn);
 233
 234     ActionInfoList::iterator found =
 235             find(actionList.begin(), actionList.end(), modInfo);
 236     if (found != actionList.end())
 237     {
 238         actionList.erase(found);
 239     }
 240 }
 241
 242
 243 void Router::addShape(ShapeRef *shape)
 244 {
 245     // There shouldn't be remove events or move events for the same shape
 246     // already in the action list.
 247     // XXX: Possibly we could handle this by ordering them intelligently.
 248     COLA_ASSERT(find(actionList.begin(), actionList.end(),
 249                 ActionInfo(ShapeRemove, shape)) == actionList.end());
 250     COLA_ASSERT(find(actionList.begin(), actionList.end(),
 251                 ActionInfo(ShapeMove, shape)) == actionList.end());
 252
 253     ActionInfo addInfo(ShapeAdd, shape);
 254
 255     ActionInfoList::iterator found =
 256             find(actionList.begin(), actionList.end(), addInfo);
 257     if (found == actionList.end())
 258     {
 259         actionList.push_back(addInfo);
 260     }
 261
 262     if (!_consolidateActions)
 263     {
 264         processTransaction();
 265     }
 266 }
 267
 268
 269 void Router::removeShape(ShapeRef *shape)
 270 {
 271     // There shouldn't be add events events for the same shape already
 272     // in the action list.
 273     // XXX: Possibly we could handle this by ordering them intelligently.
 274     COLA_ASSERT(find(actionList.begin(), actionList.end(),
 275                 ActionInfo(ShapeAdd, shape)) == actionList.end());
 276
 277     // Delete any ShapeMove entries for this shape in the action list.
 278     ActionInfoList::iterator found = find(actionList.begin(),
 279             actionList.end(), ActionInfo(ShapeMove, shape));
 280     if (found != actionList.end())
 281     {
 282         actionList.erase(found);
 283     }
 284
 285     // Add the ShapeRemove entry.
 286     ActionInfo remInfo(ShapeRemove, shape);
 287     found = find(actionList.begin(), actionList.end(), remInfo);
 288     if (found == actionList.end())
 289     {
 290         actionList.push_back(remInfo);
 291     }
 292
 293     if (!_consolidateActions)
 294     {
 295         processTransaction();
 296     }
 297 }
 298
 299
 300 void Router::moveShape(ShapeRef *shape, const double xDiff, const double yDiff)
 301 {
 302     Polygon newPoly = shape->polygon();
 303     newPoly.translate(xDiff, yDiff);
 304
 305     moveShape(shape, newPoly);
 306 }
 307
 308
 309 void Router::moveShape(ShapeRef *shape, const Polygon& newPoly,
 310         const bool first_move)
 311 {
 312     // There shouldn't be remove events or add events for the same shape
 313     // already in the action list.
 314     // XXX: Possibly we could handle this by ordering them intelligently.
 315     COLA_ASSERT(find(actionList.begin(), actionList.end(),
 316                 ActionInfo(ShapeRemove, shape)) == actionList.end());
 317
 318     if (find(actionList.begin(), actionList.end(),
 319                 ActionInfo(ShapeAdd, shape)) != actionList.end())
 320     {
 321         // The Add is enough, no need for the Move action too.
 322         return;
 323     }
 324
 325     ActionInfo moveInfo(ShapeMove, shape, newPoly, first_move);
 326     // Sanely cope with the case where the user requests moving the same
 327     // shape multiple times before rerouting connectors.
 328     ActionInfoList::iterator found =
 329             find(actionList.begin(), actionList.end(), moveInfo);
 330
 331     if (found != actionList.end())
 332     {
 333         if (!SimpleRouting)
 334         {
 335             db_printf("warning: multiple moves requested for shape %d "
 336                     "within a single transaction.\n", (int) shape->id());
 337         }
 338         // Just update the ActionInfo with the second polygon, but
 339         // leave the firstMove setting alone.
 340         found->newPoly = newPoly;
 341     }
 342     else
 343     {
 344         actionList.push_back(moveInfo);
 345     }
 346
 347     if (!_consolidateActions)
 348     {
 349         processTransaction();
 350     }
 351 }
 352
 353
 354 void Router::setStaticGraphInvalidated(const bool invalidated)
 355 {
 356     _staticGraphInvalidated = invalidated;
 357 }
 358
 359
 360 void Router::destroyOrthogonalVisGraph(void)
 361 {
 362     // Remove orthogonal visibility graph edges.
 363     visOrthogGraph.clear();
 364
 365     // Remove the now orphaned vertices.
 366     VertInf *curr = vertices.shapesBegin();
 367     while (curr)
 368     {
 369         if (curr->orphaned() && (curr->id == dummyOrthogID))
 370         {
 371             VertInf *following = vertices.removeVertex(curr);
 372             delete curr;
 373             curr = following;
 374             continue;
 375         }
 376         curr = curr->lstNext;
 377     }
 378 }
 379
 380
 381 void Router::regenerateStaticBuiltGraph(void)
 382 {
 383     // Here we do talks involved in updating the static-built visibility
 384     // graph (if necessary) before we do any routing.
 385     if (_staticGraphInvalidated)
 386     {
 387         if (_orthogonalRouting)
 388         {
 389             destroyOrthogonalVisGraph();
 390
 391             timers.Register(tmOrthogGraph, timerStart);
 392             // Regenerate a new visibility graph.
 393             generateStaticOrthogonalVisGraph(this);
 394
 395             timers.Stop();
 396         }
 397         _staticGraphInvalidated = false;
 398     }
 399 }
 400
 401
 402 bool Router::shapeInQueuedActionList(ShapeRef *shape) const
 403 {
 404     bool foundAdd = find(actionList.begin(), actionList.end(),
 405                 ActionInfo(ShapeAdd, shape)) != actionList.end();
 406     bool foundRem = find(actionList.begin(), actionList.end(),
 407                 ActionInfo(ShapeRemove, shape)) != actionList.end();
 408     bool foundMove = find(actionList.begin(), actionList.end(),
 409                 ActionInfo(ShapeMove, shape)) != actionList.end();
 410
 411     return (foundAdd || foundRem || foundMove);
 412 }
 413
 414
 415 bool Router::transactionUse(void) const
 416 {
 417     return _consolidateActions;
 418 }
 419
 420
 421 void Router::setTransactionUse(const bool transactions)
 422 {
 423     _consolidateActions = transactions;
 424 }
 425
 426
 427 bool Router::processTransaction(void)
 428 {
 429     bool notPartialTime = !(PartialFeedback && PartialTime);
 430     bool seenShapeMovesOrDeletes = false;
 431
 432     // If SimpleRouting, then don't update here.
 433     if (actionList.empty() || SimpleRouting)
 434     {
 435         return false;
 436     }
 437
 438     actionList.sort();
 439     ActionInfoList::iterator curr;
 440     ActionInfoList::iterator finish = actionList.end();
 441     for (curr = actionList.begin(); curr != finish; ++curr)
 442     {
 443         ActionInfo& actInf = *curr;
 444         if (!((actInf.type == ShapeRemove) || (actInf.type == ShapeMove)))
 445         {
 446             // Not a move or remove action, so don't do anything.
 447             continue;
 448         }
 449         seenShapeMovesOrDeletes = true;
 450
 451         ShapeRef *shape = actInf.shape();
 452         bool isMove = (actInf.type == ShapeMove);
 453         bool first_move = actInf.firstMove;
 454
 455         unsigned int pid = shape->id();
 456
 457         // o  Remove entries related to this shape's vertices
 458         shape->removeFromGraph();
 459
 460         if (SelectiveReroute && (!isMove || notPartialTime || first_move))
 461         {
 462             markConnectors(shape);
 463         }
 464
 465         adjustContainsWithDel(pid);
 466
 467         // Ignore this shape for visibility.
 468         // XXX: We don't really need to do this if we're not using Partial
 469         //      Feedback.  Without this the blocked edges still route
 470         //      around the shape until it leaves the connector.
 471         shape->makeInactive();
 472     }
 473
 474     if (seenShapeMovesOrDeletes && _polyLineRouting)
 475     {
 476         if (InvisibilityGrph)
 477         {
 478             for (curr = actionList.begin(); curr != finish; ++curr)
 479             {
 480                 ActionInfo& actInf = *curr;
 481                 if (!((actInf.type == ShapeRemove) ||
 482                             (actInf.type == ShapeMove)))
 483                 {
 484                     // Not a move or remove action, so don't do anything.
 485                     continue;
 486                 }
 487
 488                 // o  Check all edges that were blocked by this shape.
 489                 checkAllBlockedEdges(actInf.shape()->id());
 490             }
 491         }
 492         else
 493         {
 494             // check all edges not in graph
 495             checkAllMissingEdges();
 496         }
 497     }
 498
 499     for (curr = actionList.begin(); curr != finish; ++curr)
 500     {
 501         ActionInfo& actInf = *curr;
 502         if (!((actInf.type == ShapeAdd) || (actInf.type == ShapeMove)))
 503         {
 504             // Not a move or add action, so don't do anything.
 505             continue;
 506         }
 507
 508         ShapeRef *shape = actInf.shape();
 509         Polygon& newPoly = actInf.newPoly;
 510         bool isMove = (actInf.type == ShapeMove);
 511
 512         unsigned int pid = shape->id();
 513
 514         // Restore this shape for visibility.
 515         shape->makeActive();
 516
 517         if (isMove)
 518         {
 519             shape->setNewPoly(newPoly);
 520         }
 521         const Polygon& shapePoly = shape->polygon();
 522
 523         adjustContainsWithAdd(shapePoly, pid);
 524
 525         if (_polyLineRouting)
 526         {
 527             // o  Check all visibility edges to see if this one shape
 528             //    blocks them.
 529             if (!isMove || notPartialTime)
 530             {
 531                 newBlockingShape(shapePoly, pid);
 532             }
 533
 534             // o  Calculate visibility for the new vertices.
 535             if (UseLeesAlgorithm)
 536             {
 537                 shapeVisSweep(shape);
 538             }
 539             else
 540             {
 541                 shapeVis(shape);
 542             }
 543         }
 544     }
 545
 546     // Update connector endpoints.
 547     for (curr = actionList.begin(); curr != finish; ++curr)
 548     {
 549         ActionInfo& actInf = *curr;
 550         if (actInf.type != ConnChange)
 551         {
 552             continue;
 553         }
 554         for (ConnUpdateList::iterator conn = actInf.conns.begin();
 555                 conn != actInf.conns.end(); ++conn)
 556         {
 557             actInf.conn()->updateEndPoint(conn->first, conn->second);
 558         }
 559     }
 560     // Clear the actionList.
 561     actionList.clear();
 562
 563     _staticGraphInvalidated = true;
 564     rerouteAndCallbackConnectors();
 565
 566     return true;
 567 }
 568
 569
 570 void Router::addCluster(ClusterRef *cluster)
 571 {
 572     cluster->makeActive();
 573
 574     unsigned int pid = cluster->id();
 575     ReferencingPolygon& poly = cluster->polygon();
 576
 577     adjustClustersWithAdd(poly, pid);
 578 }
 579
 580
 581 void Router::delCluster(ClusterRef *cluster)
 582 {
 583     cluster->makeInactive();
 584
 585     unsigned int pid = cluster->id();
 586
 587     adjustClustersWithDel(pid);
 588 }
 589
 590
 591 void Router::setOrthogonalNudgeDistance(const double dist)
 592 {
 593     COLA_ASSERT(dist >= 0);
 594     _orthogonalNudgeDistance = dist;
 595 }
 596
 597
 598 double Router::orthogonalNudgeDistance(void) const
 599 {
 600     return _orthogonalNudgeDistance;
 601 }
 602
 603
 604 unsigned int Router::assignId(const unsigned int suggestedId)
 605 {
 606     // If the suggestedId is zero, then we assign the object the next
 607     // smallest unassigned ID, otherwise we trust the ID given is unique.
 608     unsigned int assignedId = (suggestedId == 0) ?
 609             (_largestAssignedId + 1) : suggestedId;
 610
 611     // Have the router record if this ID is larger than the _largestAssignedId.
 612     _largestAssignedId = std::max(_largestAssignedId, assignedId);
 613
 614     // If assertions are enabled, then we check that this ID really is unique.
 615     COLA_ASSERT(idIsUnique(assignedId));
 616
 617     return assignedId;
 618 }
 619
 620
 621     // Returns whether the given ID is unique among all objects known by the
 622     // router.  Outputs a warning if the ID is found ore than once.
 623     // It is expected this is only going to be called from assertions while
 624     // debugging, so efficiency is not an issue and we just iterate over all
 625     // objects.
 626 bool Router::idIsUnique(const unsigned int id) const
 627 {
 628     unsigned int count = 0;
 629
 630     // Examine shapes.
 631     for (ShapeRefList::const_iterator i = shapeRefs.begin();
 632             i != shapeRefs.end(); ++i)
 633     {
 634         if ((*i)->id() == id)
 635         {
 636             count++;
 637         }
 638     }
 639
 640     // Examine connectors.
 641     for (ConnRefList::const_iterator i = connRefs.begin();
 642             i != connRefs.end(); ++i)
 643     {
 644         if ((*i)->id() == id)
 645         {
 646             count++;
 647         }
 648     }
 649
 650     // Examine clusters.
 651     for (ClusterRefList::const_iterator i = clusterRefs.begin();
 652             i != clusterRefs.end(); ++i)
 653     {
 654         if ((*i)->id() == id)
 655         {
 656             count++;
 657         }
 658     }
 659
 660     if (count > 1)
 661     {
 662         db_printf("Warning:\tlibavoid object ID %d not unique.\n", id);
 663         return false;
 664     }
 665     return true;
 666 }
 667
 668
 669 //----------------------------------------------------------------------------
 670
 671 // XXX: attachedShapes and attachedConns both need to be rewritten
 672 //      for constant time lookup of attached objects once this info
 673 //      is stored better within libavoid.  Also they shouldn't need to
 674 //      be friends of ConnRef.
 675
 676     // Returns a list of connector Ids of all the connectors of type
 677     // 'type' attached to the shape with the ID 'shapeId'.
 678 void Router::attachedConns(IntList &conns, const unsigned int shapeId,
 679         const unsigned int type)
 680 {
 681     ConnRefList::const_iterator fin = connRefs.end();
 682     for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
 683     {
 684         if ((type & runningTo) && ((*i)->_dstId == shapeId))
 685         {
 686             conns.push_back((*i)->_id);
 687         }
 688         else if ((type & runningFrom) && ((*i)->_srcId == shapeId))
 689         {
 690             conns.push_back((*i)->_id);
 691         }
 692     }
 693 }
 694
 695
 696     // Returns a list of shape Ids of all the shapes attached to the
 697     // shape with the ID 'shapeId' with connection type 'type'.
 698 void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
 699         const unsigned int type)
 700 {
 701     ConnRefList::const_iterator fin = connRefs.end();
 702     for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
 703     {
 704         if ((type & runningTo) && ((*i)->_dstId == shapeId))
 705         {
 706             if ((*i)->_srcId != 0)
 707             {
 708                 // Only if there is a shape attached to the other end.
 709                 shapes.push_back((*i)->_srcId);
 710             }
 711         }
 712         else if ((type & runningFrom) && ((*i)->_srcId == shapeId))
 713         {
 714             if ((*i)->_dstId != 0)
 715             {
 716                 // Only if there is a shape attached to the other end.
 717                 shapes.push_back((*i)->_dstId);
 718             }
 719         }
 720     }
 721 }
 722
 723
 724     // It's intended this function is called after visibility changes
 725     // resulting from shape movement have happened.  It will alert
 726     // rerouted connectors (via a callback) that they need to be redrawn.
 727 void Router::rerouteAndCallbackConnectors(void)
 728 {
 729     std::set<ConnRef *> reroutedConns;
 730     ConnRefList::const_iterator fin = connRefs.end();
 731
 732     // Updating the orthogonal visibility graph if necessary.
 733     regenerateStaticBuiltGraph();
 734
 735     timers.Register(tmOrthogRoute, timerStart);
 736     for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
 737     {
 738         (*i)->_needs_repaint = false;
 739         bool rerouted = (*i)->generatePath();
 740         if (rerouted)
 741         {
 742             reroutedConns.insert(*i);
 743         }
 744     }
 745     timers.Stop();
 746
 747     // Find and reroute crossing connectors if crossing penalties are set.
 748     improveCrossings();
 749
 750     // Perform centring and nudging for othogonal routes.
 751     improveOrthogonalRoutes(this);
 752
 753     // Alert connectors that they need redrawing.
 754     for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
 755     {
 756         (*i)->_needs_repaint = true;
 757         (*i)->performCallback();
 758     }
 759 }
 760
 761
 762 typedef std::set<ConnRef *> ConnRefSet;
 763
 764 void Router::improveCrossings(void)
 765 {
 766     const double crossing_penalty = routingPenalty(crossingPenalty);
 767     const double shared_path_penalty = routingPenalty(fixedSharedPathPenalty);
 768     if ((crossing_penalty == 0) && (shared_path_penalty == 0))
 769     {
 770         // No penalties, return.
 771         return;
 772     }
 773
 774     // Find crossings and reroute connectors.
 775     _inCrossingPenaltyReroutingStage = true;
 776     ConnRefSet crossingConns;
 777     ConnRefList::iterator fin = connRefs.end();
 778     for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
 779     {
 780         Avoid::Polygon& iRoute = (*i)->routeRef();
 781         ConnRefList::iterator j = i;
 782         for (++j; j != fin; ++j)
 783         {
 784             if ((crossingConns.find(*i) != crossingConns.end()) &&
 785                     (crossingConns.find(*j) != crossingConns.end()))
 786             {
 787                 // We already know both these have crossings.
 788                 continue;
 789             }
 790             // Determine if this pair cross.
 791             Avoid::Polygon& jRoute = (*j)->routeRef();
 792             CrossingsInfoPair crossingInfo = std::make_pair(0, 0);
 793             bool meetsPenaltyCriteria = false;
 794             for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
 795             {
 796                 const bool finalSegment = ((jInd + 1) == jRoute.size());
 797                 CrossingsInfoPair crossingInfo = countRealCrossings(
 798                         iRoute, true, jRoute, jInd, false,
 799                         finalSegment, NULL, NULL, *i, *j);
 800
 801                 if ((shared_path_penalty > 0) &&
 802                     (crossingInfo.second & CROSSING_SHARES_PATH) &&
 803                     (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) &&
 804                     !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END))
 805                 {
 806                     // We are penalising fixedSharedPaths and there is a
 807                     // fixedSharedPath.
 808                     meetsPenaltyCriteria = true;
 809                     break;
 810                 }
 811                 else if ((crossing_penalty > 0) && (crossingInfo.first > 0))
 812                 {
 813                     // We are penalising crossings and this is a crossing.
 814                     meetsPenaltyCriteria = true;
 815                     break;
 816                 }
 817             }
 818             if (meetsPenaltyCriteria)
 819             {
 820                 crossingConns.insert(*i);
 821                 crossingConns.insert(*j);
 822             }
 823         }
 824     }
 825
 826     for (ConnRefSet::iterator i = crossingConns.begin();
 827             i != crossingConns.end(); ++i)
 828     {
 829         ConnRef *conn = *i;
 830         conn->makePathInvalid();
 831         // XXX: Could we free these routes here for extra savings?
 832         // conn->freeRoutes();
 833     }
 834     for (ConnRefSet::iterator i = crossingConns.begin();
 835             i != crossingConns.end(); ++i)
 836     {
 837         ConnRef *conn = *i;
 838         conn->generatePath();
 839     }
 840     _inCrossingPenaltyReroutingStage = false;
 841 }
 842
 843
 844 void Router::newBlockingShape(const Polygon& poly, int pid)
 845 {
 846     // o  Check all visibility edges to see if this one shape
 847     //    blocks them.
 848     EdgeInf *finish = visGraph.end();
 849     for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
 850     {
 851         EdgeInf *tmp = iter;
 852         iter = iter->lstNext;
 853
 854         if (tmp->getDist() != 0)
 855         {
 856             std::pair<VertID, VertID> ids(tmp->ids());
 857             VertID eID1 = ids.first;
 858             VertID eID2 = ids.second;
 859             std::pair<Point, Point> points(tmp->points());
 860             Point e1 = points.first;
 861             Point e2 = points.second;
 862             bool blocked = false;
 863
 864             bool countBorder = false;
 865             bool ep_in_poly1 = !(eID1.isShape) ?
 866                     inPoly(poly, e1, countBorder) : false;
 867             bool ep_in_poly2 = !(eID2.isShape) ?
 868                     inPoly(poly, e2, countBorder) : false;
 869             if (ep_in_poly1 || ep_in_poly2)
 870             {
 871                 // Don't check edges that have a connector endpoint
 872                 // and are inside the shape being added.
 873                 continue;
 874             }
 875
 876             bool seenIntersectionAtEndpoint = false;
 877             for (size_t pt_i = 0; pt_i < poly.size(); ++pt_i)
 878             {
 879                 size_t pt_n = (pt_i == (poly.size() - 1)) ? 0 : pt_i + 1;
 880                 const Point& pi = poly.ps[pt_i];
 881                 const Point& pn = poly.ps[pt_n];
 882                 if (segmentShapeIntersect(e1, e2, pi, pn,
 883                         seenIntersectionAtEndpoint))
 884                 {
 885                     blocked = true;
 886                     break;
 887                 }
 888             }
 889             if (blocked)
 890             {
 891                 db_printf("\tRemoving newly blocked edge (by shape %3d)"
 892                         "... \n\t\t", pid);
 893                 tmp->alertConns();
 894                 tmp->db_print();
 895                 if (InvisibilityGrph)
 896                 {
 897                     tmp->addBlocker(pid);
 898                 }
 899                 else
 900                 {
 901                     delete tmp;
 902                 }
 903             }
 904         }
 905     }
 906 }
 907
 908
 909 void Router::checkAllBlockedEdges(int pid)
 910 {
 911     COLA_ASSERT(InvisibilityGrph);
 912
 913     for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
 914     {
 915         EdgeInf *tmp = iter;
 916         iter = iter->lstNext;
 917
 918         if (tmp->_blocker == -1)
 919         {
 920             tmp->alertConns();
 921             tmp->checkVis();
 922         }
 923         else if (tmp->_blocker == pid)
 924         {
 925             tmp->checkVis();
 926         }
 927     }
 928 }
 929
 930
 931 void Router::checkAllMissingEdges(void)
 932 {
 933     COLA_ASSERT(!InvisibilityGrph);
 934
 935     VertInf *first = vertices.connsBegin();
 936
 937     VertInf *pend = vertices.end();
 938     for (VertInf *i = first; i != pend; i = i->lstNext)
 939     {
 940         VertID iID = i->id;
 941
 942         // Check remaining, earlier vertices
 943         for (VertInf *j = first ; j != i; j = j->lstNext)
 944         {
 945             VertID jID = j->id;
 946             if (!(iID.isShape) && (iID.objID != jID.objID))
 947             {
 948                 // Don't keep visibility between edges of different conns
 949                 continue;
 950             }
 951
 952             // See if the edge is already there?
 953             bool found = (EdgeInf::existingEdge(i, j) != NULL);
 954
 955             if (!found)
 956             {
 957                 // Didn't already exist, check.
 958                 bool knownNew = true;
 959                 EdgeInf::checkEdgeVisibility(i, j, knownNew);
 960             }
 961         }
 962     }
 963 }
 964
 965
 966 void Router::generateContains(VertInf *pt)
 967 {
 968     contains[pt->id].clear();
 969     enclosingClusters[pt->id].clear();
 970
 971     // Don't count points on the border as being inside.
 972     bool countBorder = false;
 973
 974     // Compute enclosing shapes.
 975     ShapeRefList::const_iterator finish = shapeRefs.end();
 976     for (ShapeRefList::const_iterator i = shapeRefs.begin(); i != finish; ++i)
 977     {
 978         if (inPoly((*i)->polygon(), pt->point, countBorder))
 979         {
 980             contains[pt->id].insert((*i)->id());
 981         }
 982     }
 983
 984     // Computer enclosing Clusters
 985     ClusterRefList::const_iterator clFinish = clusterRefs.end();
 986     for (ClusterRefList::const_iterator i = clusterRefs.begin();
 987             i != clFinish; ++i)
 988     {
 989         if (inPolyGen((*i)->polygon(), pt->point))
 990         {
 991             enclosingClusters[pt->id].insert((*i)->id());
 992         }
 993     }
 994 }
 995
 996
 997 void Router::adjustClustersWithAdd(const PolygonInterface& poly,
 998         const int p_cluster)
 999 {
1000     for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
1001             k = k->lstNext)
1002     {
1003         if (inPolyGen(poly, k->point))
1004         {
1005             enclosingClusters[k->id].insert(p_cluster);
1006         }
1007     }
1008 }
1009
1010
1011 void Router::adjustClustersWithDel(const int p_cluster)
1012 {
1013     for (ContainsMap::iterator k = enclosingClusters.begin();
1014             k != enclosingClusters.end(); ++k)
1015     {
1016         (*k).second.erase(p_cluster);
1017     }
1018 }
1019
1020
1021 void Router::adjustContainsWithAdd(const Polygon& poly, const int p_shape)
1022 {
1023     // Don't count points on the border as being inside.
1024     bool countBorder = false;
1025
1026     for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
1027             k = k->lstNext)
1028     {
1029         if (inPoly(poly, k->point, countBorder))
1030         {
1031             contains[k->id].insert(p_shape);
1032         }
1033     }
1034 }
1035
1036
1037 void Router::adjustContainsWithDel(const int p_shape)
1038 {
1039     for (ContainsMap::iterator k = contains.begin(); k != contains.end(); ++k)
1040     {
1041         (*k).second.erase(p_shape);
1042     }
1043 }
1044
1045
1046 #ifdef SELECTIVE_DEBUG
1047 static double AngleAFromThreeSides(const double a, const double b,
1048         const double c)
1049 {
1050     // returns angle A, the angle opposite from side a, in radians
1051     return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
1052 }
1053 #endif
1054
1055 void Router::markConnectors(ShapeRef *shape)
1056 {
1057     if (RubberBandRouting)
1058     {
1059         // When rubber-band routing, we do no reroute connectors that
1060         // may have a better route, only invalid connectors.
1061         return;
1062     }
1063
1064     COLA_ASSERT(SelectiveReroute);
1065
1066     ConnRefList::const_iterator end = connRefs.end();
1067     for (ConnRefList::const_iterator it = connRefs.begin(); it != end; ++it)
1068     {
1069         ConnRef *conn = (*it);
1070
1071         if (conn->_route.empty())
1072         {
1073             // Ignore uninitialised connectors.
1074             continue;
1075         }
1076         else if (conn->_needs_reroute_flag)
1077         {
1078             // Already marked, so skip.
1079             continue;
1080         }
1081
1082         Point start = conn->_route.ps[0];
1083         Point end = conn->_route.ps[conn->_route.size() - 1];
1084
1085         double conndist = conn->_route_dist;
1086
1087         double estdist;
1088         double e1, e2;
1089
1090         VertInf *beginV = shape->firstVert();
1091         VertInf *endV = shape->lastVert()->lstNext;
1092         for (VertInf *i = beginV; i != endV; i = i->lstNext)
1093         {
1094             const Point& p1 = i->point;
1095             const Point& p2 = i->shNext->point;
1096
1097             double offy;
1098             double a;
1099             double b;
1100             double c;
1101             double d;
1102
1103             double min;
1104             double max;
1105
1106             if (p1.y == p2.y)
1107             {
1108                 // Standard case
1109                 offy = p1.y;
1110                 a = start.x;
1111                 b = start.y - offy;
1112                 c = end.x;
1113                 d = end.y - offy;
1114
1115                 min = std::min(p1.x, p2.x);
1116                 max = std::max(p1.x, p2.x);
1117             }
1118             else if (p1.x == p2.x)
1119             {
1120                 // Other Standard case
1121                 offy = p1.x;
1122                 a = start.y;
1123                 b = start.x - offy;
1124                 c = end.y;
1125                 d = end.x - offy;
1126
1127                 min = std::min(p1.y, p2.y);
1128                 max = std::max(p1.y, p2.y);
1129             }
1130             else
1131             {
1132                 // Need to do rotation
1133                 Point n_p2(p2.x - p1.x, p2.y - p1.y);
1134                 Point n_start(start.x - p1.x, start.y - p1.y);
1135                 Point n_end(end.x - p1.x, end.y - p1.y);
1136                 //db_printf("n_p2:    (%.1f, %.1f)\n", n_p2.x, n_p2.y);
1137                 //db_printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
1138                 //db_printf("n_end:   (%.1f, %.1f)\n", n_end.x, n_end.y);
1139
1140                 double theta = 0 - atan2(n_p2.y, n_p2.x);
1141                 //db_printf("theta = %.2f\n", theta * (180 / PI));
1142
1143                 Point r_p1(0, 0);
1144                 Point r_p2 = n_p2;
1145                 start = n_start;
1146                 end = n_end;
1147
1148                 double cosv = cos(theta);
1149                 double sinv = sin(theta);
1150
1151                 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
1152                 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
1153                 start.x = cosv * n_start.x - sinv * n_start.y;
1154                 start.y = cosv * n_start.y + sinv * n_start.x;
1155                 end.x = cosv * n_end.x - sinv * n_end.y;
1156                 end.y = cosv * n_end.y + sinv * n_end.x;
1157                 //db_printf("r_p2:    (%.1f, %.1f)\n", r_p2.x, r_p2.y);
1158                 //db_printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
1159                 //db_printf("r_end:   (%.1f, %.1f)\n", end.x, end.y);
1160
1161                 // This might be slightly off.
1162                 if (fabs(r_p2.y) > 0.0001)
1163                 {
1164                     db_printf("r_p2.y: %f != 0\n", r_p2.y);
1165                 }
1166                 r_p2.y = 0;
1167
1168                 offy = r_p1.y;
1169                 a = start.x;
1170                 b = start.y - offy;
1171                 c = end.x;
1172                 d = end.y - offy;
1173
1174                 min = std::min(r_p1.x, r_p2.x);
1175                 max = std::max(r_p1.x, r_p2.x);
1176
1177             }
1178
1179             double x;
1180             if ((b + d) == 0)
1181             {
1182                 db_printf("WARNING: (b + d) == 0\n");
1183                 d = d * -1;
1184             }
1185
1186             if ((b == 0) && (d == 0))
1187             {
1188                 db_printf("WARNING: b == d == 0\n");
1189                 if (((a < min) && (c < min)) ||
1190                         ((a > max) && (c > max)))
1191                 {
1192                     // It's going to get adjusted.
1193                     x = a;
1194                 }
1195                 else
1196                 {
1197                     continue;
1198                 }
1199             }
1200             else
1201             {
1202                 x = ((b*c) + (a*d)) / (b + d);
1203             }
1204
1205             //db_printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
1206             //db_printf("x = %.1f\n", x);
1207
1208             x = std::max(min, x);
1209             x = std::min(max, x);
1210
1211             //db_printf("x = %.1f\n", x);
1212
1213             Point xp;
1214             if (p1.x == p2.x)
1215             {
1216                 xp.x = offy;
1217                 xp.y = x;
1218             }
1219             else
1220             {
1221                 xp.x = x;
1222                 xp.y = offy;
1223             }
1224             //db_printf("(%.1f, %.1f)\n", xp.x, xp.y);
1225
1226             e1 = euclideanDist(start, xp);
1227             e2 = euclideanDist(xp, end);
1228             estdist = e1 + e2;
1229
1230
1231             //db_printf("is %.1f < %.1f\n", estdist, conndist);
1232             if (estdist < conndist)
1233             {
1234 #ifdef SELECTIVE_DEBUG
1235                 //double angle = AngleAFromThreeSides(dist(start, end),
1236                 //        e1, e2);
1237                 db_printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
1238                         conn->_id, estdist, conndist);
1239 #endif
1240                 conn->_needs_reroute_flag = true;
1241                 break;
1242             }
1243
1244         }
1245     }
1246 }
1247
1248
1249 ConnType Router::validConnType(const ConnType select) const
1250 {
1251     if (select != ConnType_None)
1252     {
1253         if ((select == ConnType_Orthogonal) && _orthogonalRouting)
1254         {
1255             return ConnType_Orthogonal;
1256         }
1257         else if ((select == ConnType_PolyLine) && _polyLineRouting)
1258         {
1259             return ConnType_PolyLine;
1260         }
1261     }
1262
1263     if (_polyLineRouting)
1264     {
1265         return ConnType_PolyLine;
1266     }
1267     else if (_orthogonalRouting)
1268     {
1269         return ConnType_Orthogonal;
1270     }
1271     return ConnType_None;
1272 }
1273
1274
1275 void Router::setRoutingPenalty(const PenaltyType penType, const double penVal)
1276 {
1277     COLA_ASSERT(penType < lastPenaltyMarker);
1278     if (penVal < 0)
1279     {
1280         // Set some sensible penalty.
1281         switch (penType)
1282         {
1283             case segmentPenalty:
1284                 _routingPenalties[penType] = 50;
1285                 break;
1286             case fixedSharedPathPenalty:
1287                 _routingPenalties[penType] = 110;
1288                 break;
1289             case anglePenalty:
1290                 _routingPenalties[penType] = 50;
1291                 break;
1292             case crossingPenalty:
1293                 _routingPenalties[penType] = 200;
1294                 break;
1295             case clusterCrossingPenalty:
1296                 _routingPenalties[penType] = 4000;
1297                 break;
1298             default:
1299                 _routingPenalties[penType] = 50;
1300                 break;
1301         }
1302     }
1303     else
1304     {
1305         _routingPenalties[penType] = penVal;
1306     }
1307 }
1308
1309
1310 double Router::routingPenalty(const PenaltyType penType) const
1311 {
1312     COLA_ASSERT(penType < lastPenaltyMarker);
1313     return _routingPenalties[penType];
1314 }
1315
1316
1317 double& Router::penaltyRef(const PenaltyType penType)
1318 {
1319     COLA_ASSERT(penType < lastPenaltyMarker);
1320     return _routingPenalties[penType];
1321 }
1322
1323
1324 void Router::printInfo(void)
1325 {
1326     FILE *fp = stdout;
1327     fprintf(fp, "\nVisibility Graph info:\n");
1328     fprintf(fp, "----------------------\n");
1329
1330     unsigned int currshape = 0;
1331     int st_shapes = 0;
1332     int st_vertices = 0;
1333     int st_endpoints = 0;
1334     int st_valid_shape_visedges = 0;
1335     int st_valid_endpt_visedges = 0;
1336     int st_orthogonal_visedges = 0;
1337     int st_invalid_visedges = 0;
1338     VertInf *finish = vertices.end();
1339     for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
1340     {
1341         VertID pID = t->id;
1342
1343         if ((pID.isShape) && (pID.objID != currshape))
1344         {
1345             currshape = pID.objID;
1346             st_shapes++;
1347         }
1348         if (pID.isShape)
1349         {
1350             st_vertices++;
1351         }
1352         else
1353         {
1354             // The shape 0 ones are temporary and not considered.
1355             st_endpoints++;
1356         }
1357     }
1358     for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
1359             t = t->lstNext)
1360     {
1361         std::pair<VertID, VertID> idpair = t->ids();
1362
1363         if (!(idpair.first.isShape) || !(idpair.second.isShape))
1364         {
1365             st_valid_endpt_visedges++;
1366         }
1367         else
1368         {
1369             st_valid_shape_visedges++;
1370         }
1371     }
1372     for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
1373             t = t->lstNext)
1374     {
1375         st_invalid_visedges++;
1376     }
1377     for (EdgeInf *t = visOrthogGraph.begin(); t != visOrthogGraph.end();
1378             t = t->lstNext)
1379     {
1380         st_orthogonal_visedges++;
1381     }
1382     fprintf(fp, "Number of shapes: %d\n", st_shapes);
1383     fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
1384             st_vertices + st_endpoints, st_vertices, st_endpoints);
1385     fprintf(fp, "Number of orhtog_vis_edges: %d\n", st_orthogonal_visedges);
1386     fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
1387             "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
1388             st_valid_endpt_visedges, st_valid_shape_visedges +
1389             st_valid_endpt_visedges, st_valid_shape_visedges,
1390             st_valid_endpt_visedges, st_invalid_visedges);
1391     fprintf(fp, "----------------------\n");
1392     fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
1393     fprintf(fp, "----------------------\n");
1394
1395     fprintf(fp, "ADDS:  "); timers.Print(tmAdd, fp);
1396     fprintf(fp, "DELS:  "); timers.Print(tmDel, fp);
1397     fprintf(fp, "MOVS:  "); timers.Print(tmMov, fp);
1398     fprintf(fp, "***S:  "); timers.Print(tmSev, fp);
1399     fprintf(fp, "PTHS:  "); timers.Print(tmPth, fp);
1400     fprintf(fp, "OrthogGraph:  "); timers.Print(tmOrthogGraph, fp);
1401     fprintf(fp, "OrthogRoute:  "); timers.Print(tmOrthogRoute, fp);
1402     fprintf(fp, "OrthogCentre:  "); timers.Print(tmOrthogCentre, fp);
1403     fprintf(fp, "OrthogNudge:  "); timers.Print(tmOrthogNudge, fp);
1404     fprintf(fp, "\n");
1405     timers.Reset();
1406 }
1407
1408
1409 static const double LIMIT = 100000000;
1410
1411 static void reduceRange(double& val)
1412 {
1413     val = std::min(val, LIMIT);
1414     val = std::max(val, -LIMIT);
1415 }
1416
1417
1418 //=============================================================================
1419 // The following methods are for testing and debugging.
1420
1421
1422 bool Router::existsOrthogonalPathOverlap(void)
1423 {
1424     ConnRefList::iterator fin = connRefs.end();
1425     for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
1426     {
1427         Avoid::Polygon iRoute = (*i)->displayRoute();
1428         ConnRefList::iterator j = i;
1429         for (++j; j != fin; ++j)
1430         {
1431             // Determine if this pair overlap
1432             Avoid::Polygon jRoute = (*j)->displayRoute();
1433             CrossingsInfoPair crossingInfo = std::make_pair(0, 0);
1434             for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
1435             {
1436                 const bool finalSegment = ((jInd + 1) == jRoute.size());
1437                 CrossingsInfoPair crossingInfo = countRealCrossings(
1438                         iRoute, true, jRoute, jInd, true,
1439                         finalSegment, NULL, NULL, *i, *j);
1440
1441                 if ((crossingInfo.second & CROSSING_SHARES_PATH) &&
1442                     (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) &&
1443                     !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END))
1444                 {
1445                     // We looking for fixedSharedPaths and there is a
1446                     // fixedSharedPath.
1447                     return true;
1448                 }
1449             }
1450         }
1451     }
1452     return false;
1453 }
1454
1455
1456 bool Router::existsOrthogonalTouchingCorners(void)
1457 {
1458     ConnRefList::iterator fin = connRefs.end();
1459     for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
1460     {
1461         Avoid::Polygon iRoute = (*i)->displayRoute();
1462         ConnRefList::iterator j = i;
1463         for (++j; j != fin; ++j)
1464         {
1465             // Determine if this pair overlap
1466             Avoid::Polygon jRoute = (*j)->displayRoute();
1467             CrossingsInfoPair crossingInfo = std::make_pair(0, 0);
1468             for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
1469             {
1470                 const bool finalSegment = ((jInd + 1) == jRoute.size());
1471                 CrossingsInfoPair crossingInfo = countRealCrossings(
1472                         iRoute, true, jRoute, jInd, true,
1473                         finalSegment, NULL, NULL, *i, *j);
1474
1475                 if (crossingInfo.second & CROSSING_TOUCHES)
1476                 {
1477                     return true;
1478                 }
1479             }
1480         }
1481     }
1482     return false;
1483 }
1484
1485
1486 void Router::outputInstanceToSVG(std::string instanceName)
1487 {
1488     std::string filename;
1489     if (!instanceName.empty())
1490     {
1491         filename = instanceName;
1492     }
1493     else
1494     {
1495         filename = "libavoid-debug";
1496     }
1497     filename += ".svg";
1498     FILE *fp = fopen(filename.c_str(), "w");
1499
1500     if (fp == NULL)
1501     {
1502         return;
1503     }
1504
1505     double minX = LIMIT;
1506     double minY = LIMIT;
1507     double maxX = -LIMIT;
1508     double maxY = -LIMIT;
1509
1510     VertInf *curr = vertices.connsBegin();
1511     while (curr)
1512     {
1513         Point p = curr->point;
1514
1515         reduceRange(p.x);
1516         reduceRange(p.y);
1517
1518         if (p.x > -LIMIT)
1519         {
1520             minX = std::min(minX, p.x);
1521         }
1522         if (p.x < LIMIT)
1523         {
1524             maxX = std::max(maxX, p.x);
1525         }
1526         if (p.y > -LIMIT)
1527         {
1528             minY = std::min(minY, p.y);
1529         }
1530         if (p.y < LIMIT)
1531         {
1532             maxY = std::max(maxY, p.y);
1533         }
1534         curr = curr->lstNext;
1535     }
1536     minX -= 50;
1537     minY -= 50;
1538     maxX += 50;
1539     maxY += 50;
1540
1541     fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
1542     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);
1543
1544     // Output source code to generate this instance of the router.
1545     fprintf(fp, "<!-- Source code to generate this instance:\n");
1546     fprintf(fp, "#include \"libavoid/libavoid.h\"\n");
1547     fprintf(fp, "using namespace Avoid;\n");
1548     fprintf(fp, "int main(void) {\n");
1549     fprintf(fp, "    Router *router = new Router(\n");
1550     fprintf(fp, "            PolyLineRouting | OrthogonalRouting);\n");
1551     for (size_t p = 0; p < lastPenaltyMarker; ++p)
1552     {
1553         fprintf(fp, "    router->setRoutingPenalty((PenaltyType)%lu, %g);\n",
1554                 p, _routingPenalties[p]);
1555     }
1556     fprintf(fp, "    router->setOrthogonalNudgeDistance(%g);\n\n",
1557             orthogonalNudgeDistance());
1558     ShapeRefList::iterator shRefIt = shapeRefs.begin();
1559     while (shRefIt != shapeRefs.end())
1560     {
1561         ShapeRef *shRef = *shRefIt;
1562         fprintf(fp, "    Polygon poly%u(%lu);\n",
1563                 shRef->id(), shRef->polygon().size());
1564         for (size_t i = 0; i < shRef->polygon().size(); ++i)
1565         {
1566             fprintf(fp, "    poly%u.ps[%lu] = Point(%g, %g);\n",
1567                     shRef->id(), i, shRef->polygon().at(i).x,
1568                     shRef->polygon().at(i).y);
1569         }
1570         fprintf(fp, "    ShapeRef *shapeRef%u = new ShapeRef(router, poly%u, "
1571                 "%u);\n", shRef->id(), shRef->id(), shRef->id());
1572         fprintf(fp, "    router->addShape(shapeRef%u);\n\n", shRef->id());
1573         ++shRefIt;
1574     }
1575     ConnRefList::reverse_iterator revConnRefIt = connRefs.rbegin();
1576     while (revConnRefIt != connRefs.rend())
1577     {
1578         ConnRef *connRef = *revConnRefIt;
1579         fprintf(fp, "    ConnRef *connRef%u = new ConnRef(router, %u);\n",
1580                 connRef->id(), connRef->id());
1581         if (connRef->src())
1582         {
1583             fprintf(fp, "    ConnEnd srcPt%u(Point(%g, %g), %u);\n",
1584                     connRef->id(), connRef->src()->point.x,
1585                     connRef->src()->point.y, connRef->src()->visDirections);
1586             fprintf(fp, "    connRef%u->setSourceEndpoint(srcPt%u);\n",
1587                     connRef->id(), connRef->id());
1588         }
1589         if (connRef->dst())
1590         {
1591             fprintf(fp, "    ConnEnd dstPt%u(Point(%g, %g), %u);\n",
1592                     connRef->id(), connRef->dst()->point.x,
1593                     connRef->dst()->point.y, connRef->dst()->visDirections);
1594             fprintf(fp, "    connRef%u->setDestEndpoint(dstPt%u);\n",
1595                     connRef->id(), connRef->id());
1596         }
1597         fprintf(fp, "    connRef%u->setRoutingType((ConnType)%u);\n\n",
1598                 connRef->id(), connRef->routingType());
1599         ++revConnRefIt;
1600     }
1601     fprintf(fp, "    router->processTransaction();\n");
1602     fprintf(fp, "    router->outputInstanceToSVG();\n");
1603     fprintf(fp, "    delete router;\n");
1604     fprintf(fp, "    return 0;\n");
1605     fprintf(fp, "};\n");
1606     fprintf(fp, "-->\n");
1607
1608
1609     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1610             "inkscape:label=\"ShapesPoly\">\n");
1611     shRefIt = shapeRefs.begin();
1612     while (shRefIt != shapeRefs.end())
1613     {
1614         ShapeRef *shRef = *shRefIt;
1615
1616         fprintf(fp, "<path id=\"poly-%u\" style=\"stroke-width: 1px; "
1617                 "stroke: black; fill: blue; fill-opacity: 0.3;\" d=\"",
1618                 shRef->id());
1619         for (size_t i = 0; i < shRef->polygon().size(); ++i)
1620         {
1621             fprintf(fp, "%c %g,%g ", ((i == 0) ? 'M' : 'L'),
1622                     shRef->polygon().at(i).x, shRef->polygon().at(i).y);
1623         }
1624         fprintf(fp, "Z\" />\n");
1625         ++shRefIt;
1626     }
1627     fprintf(fp, "</g>\n");
1628
1629     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1630             "style=\"display: none;\" "
1631             "inkscape:label=\"ShapesRect\">\n");
1632     shRefIt = shapeRefs.begin();
1633     while (shRefIt != shapeRefs.end())
1634     {
1635         ShapeRef *shRef = *shRefIt;
1636         double minX, minY, maxX, maxY;
1637         shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY);
1638
1639         fprintf(fp, "<rect id=\"rect-%u\" x=\"%g\" y=\"%g\" width=\"%g\" height=\"%g\" "
1640                 "style=\"stroke-width: 1px; stroke: black; fill: blue; fill-opacity: 0.3;\" />\n",
1641                 shRef->id(), minX, minY, maxX - minX, maxY - minY);
1642         ++shRefIt;
1643     }
1644     fprintf(fp, "</g>\n");
1645
1646
1647     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1648             "inkscape:label=\"VisGraph\""
1649             ">\n");
1650     EdgeInf *finish = NULL;
1651     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1652             "style=\"display: none;\" "
1653             "inkscape:label=\"VisGraph-shape\""
1654             ">\n");
1655     finish = visGraph.end();
1656     for (EdgeInf *t = visGraph.begin(); t != finish; t = t->lstNext)
1657     {
1658         std::pair<VertID, VertID> ids = t->ids();
1659         bool isShape = (ids.first.isShape) && (ids.second.isShape);
1660         if (!isShape)
1661         {
1662             continue;
1663         }
1664         std::pair<Point, Point> ptpair = t->points();
1665         Point p1 = ptpair.first;
1666         Point p2 = ptpair.second;
1667
1668         reduceRange(p1.x);
1669         reduceRange(p1.y);
1670         reduceRange(p2.x);
1671         reduceRange(p2.y);
1672
1673         fprintf(fp, "<path d=\"M %g,%g L %g,%g\" "
1674                 "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
1675                 p1.x, p1.y, p2.x, p2.y,
1676                 (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" :
1677                 "red");
1678     }
1679     fprintf(fp, "</g>\n");
1680
1681     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1682             "style=\"display: none;\" "
1683             "inkscape:label=\"VisGraph-conn\""
1684             ">\n");
1685     finish = visGraph.end();
1686     for (EdgeInf *t = visGraph.begin(); t != finish; t = t->lstNext)
1687     {
1688         std::pair<VertID, VertID> ids = t->ids();
1689         bool isShape = (ids.first.isShape) && (ids.second.isShape);
1690         if (isShape)
1691         {
1692             continue;
1693         }
1694         std::pair<Point, Point> ptpair = t->points();
1695         Point p1 = ptpair.first;
1696         Point p2 = ptpair.second;
1697
1698         reduceRange(p1.x);
1699         reduceRange(p1.y);
1700         reduceRange(p2.x);
1701         reduceRange(p2.y);
1702
1703         fprintf(fp, "<path d=\"M %g,%g L %g,%g\" "
1704                 "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
1705                 p1.x, p1.y, p2.x, p2.y,
1706                 (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" :
1707                 "red");
1708     }
1709     fprintf(fp, "</g>\n");
1710     fprintf(fp, "</g>\n");
1711
1712     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1713             "style=\"display: none;\" "
1714             "inkscape:label=\"OrthogVisGraph\">\n");
1715     finish = visOrthogGraph.end();
1716     for (EdgeInf *t = visOrthogGraph.begin(); t != finish; t = t->lstNext)
1717     {
1718         std::pair<Point, Point> ptpair = t->points();
1719         Point p1 = ptpair.first;
1720         Point p2 = ptpair.second;
1721
1722         reduceRange(p1.x);
1723         reduceRange(p1.y);
1724         reduceRange(p2.x);
1725         reduceRange(p2.y);
1726
1727         std::pair<VertID, VertID> ids = t->ids();
1728
1729         fprintf(fp, "<path d=\"M %g,%g L %g,%g\" "
1730                 "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
1731                 p1.x, p1.y, p2.x, p2.y,
1732                 (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" :
1733                 "red");
1734     }
1735     fprintf(fp, "</g>\n");
1736
1737     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1738             "style=\"display: none;\" "
1739             "inkscape:label=\"RawConnectors\""
1740             ">\n");
1741     ConnRefList::iterator connRefIt = connRefs.begin();
1742     while (connRefIt != connRefs.end())
1743     {
1744         ConnRef *connRef = *connRefIt;
1745
1746         PolyLine route = connRef->route();
1747         if (!route.empty())
1748         {
1749             fprintf(fp, "<path id=\"raw-%u\" d=\"M %g,%g ", connRef->id(),
1750                     route.ps[0].x, route.ps[0].y);
1751             for (size_t i = 1; i < route.size(); ++i)
1752             {
1753                 fprintf(fp, "L %g,%g ", route.ps[i].x, route.ps[i].y);
1754             }
1755             fprintf(fp, "\" ");
1756             if (connRef->src() && connRef->dst())
1757             {
1758                 fprintf(fp, "debug=\"src: %d dst: %d\" ",
1759                         connRef->src()->visDirections,
1760                         connRef->dst()->visDirections);
1761             }
1762             fprintf(fp, "style=\"fill: none; stroke: black; "
1763                     "stroke-width: 1px;\" />\n");
1764         }
1765
1766         ++connRefIt;
1767     }
1768     fprintf(fp, "</g>\n");
1769
1770     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1771             "style=\"display: none;\" "
1772             "inkscape:label=\"CurvedDisplayConnectors\""
1773             ">\n");
1774     connRefIt = connRefs.begin();
1775     while (connRefIt != connRefs.end())
1776     {
1777         ConnRef *connRef = *connRefIt;
1778
1779         PolyLine route = connRef->displayRoute().curvedPolyline(8);
1780         if (!route.empty())
1781         {
1782             fprintf(fp, "<path id=\"curved-%u\" d=\"M %g,%g ", connRef->id(),
1783                     route.ps[0].x, route.ps[0].y);
1784             for (size_t i = 1; i < route.size(); ++i)
1785             {
1786                 if (route.ts[i] == 'C')
1787                 {
1788                     fprintf(fp, "%c %g,%g %g,%g %g,%g", route.ts[i],
1789                             route.ps[i].x, route.ps[i].y,
1790                             route.ps[i+1].x, route.ps[i+1].y,
1791                             route.ps[i+2].x, route.ps[i+2].y);
1792                     i += 2;
1793                 }
1794                 else
1795                 {
1796                     fprintf(fp, "%c %g,%g ", route.ts[i],
1797                             route.ps[i].x, route.ps[i].y);
1798                 }
1799             }
1800             fprintf(fp, "\" ");
1801             if (connRef->src() && connRef->dst())
1802             {
1803                 fprintf(fp, "debug=\"src: %d dst: %d\" ",
1804                         connRef->src()->visDirections,
1805                         connRef->dst()->visDirections);
1806             }
1807             fprintf(fp, "style=\"fill: none; stroke: black; "
1808                     "stroke-width: 1px;\" />\n");
1809         }
1810
1811         ++connRefIt;
1812     }
1813     fprintf(fp, "</g>\n");
1814
1815
1816     fprintf(fp, "<g inkscape:groupmode=\"layer\" "
1817             "inkscape:label=\"DisplayConnectors\""
1818             ">\n");
1819     connRefIt = connRefs.begin();
1820     while (connRefIt != connRefs.end())
1821     {
1822         ConnRef *connRef = *connRefIt;
1823
1824         PolyLine route = connRef->displayRoute();
1825         if (!route.empty())
1826         {
1827             fprintf(fp, "<path id=\"disp-%u\" d=\"M %g,%g ", connRef->id(),
1828                     route.ps[0].x, route.ps[0].y);
1829             for (size_t i = 1; i < route.size(); ++i)
1830             {
1831                 fprintf(fp, "L %g,%g ", route.ps[i].x, route.ps[i].y);
1832             }
1833             fprintf(fp, "\" ");
1834             if (connRef->src() && connRef->dst())
1835             {
1836                 fprintf(fp, "debug=\"src: %d dst: %d\" ",
1837                         connRef->src()->visDirections,
1838                         connRef->dst()->visDirections);
1839             }
1840             fprintf(fp, "style=\"fill: none; stroke: black; "
1841                     "stroke-width: 1px;\" />\n");
1842         }
1843
1844         ++connRefIt;
1845     }
1846     fprintf(fp, "</g>\n");
1847
1848
1849     fprintf(fp, "</svg>\n");
1850     fclose(fp);
1851 }
1852
1853
1854 }
1855