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-2014 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
23 */
24
25
26 #include <algorithm>
27 #include <cmath>
28 #include <cfloat>
29
30 #include "libavoid/shape.h"
31 #include "libavoid/router.h"
32 #include "libavoid/visibility.h"
33 #include "libavoid/connector.h"
34 #include "libavoid/junction.h"
35 #include "libavoid/viscluster.h"
36 #include "libavoid/connend.h"
37 #include "libavoid/debug.h"
38 #include "libavoid/orthogonal.h"
39 #include "libavoid/assertions.h"
40 #include "libavoid/connectionpin.h"
41
42
43 namespace Avoid {
44
45
Router(const unsigned int flags)46 Router::Router(const unsigned int flags)
47 : visOrthogGraph(),
48 PartialTime(false),
49 SimpleRouting(false),
50 ClusteredRouting(true),
51 // Poly-line algorithm options:
52 IgnoreRegions(true),
53 UseLeesAlgorithm(true),
54 InvisibilityGrph(true),
55 // General algorithm options:
56 SelectiveReroute(true),
57 PartialFeedback(false),
58 RubberBandRouting(false),
59 // Instrumentation:
60 st_checked_edges(0),
61 m_largest_assigned_id(0),
62 m_consolidate_actions(true),
63 m_currently_calling_destructors(false),
64 m_topology_addon(new TopologyAddonInterface()),
65 // Mode options:
66 m_allows_polyline_routing(false),
67 m_allows_orthogonal_routing(false),
68 m_static_orthogonal_graph_invalidated(true),
69 m_in_crossing_rerouting_stage(false),
70 m_settings_changes(false),
71 m_debug_handler(nullptr)
72 {
73 // At least one of the Routing modes must be set.
74 COLA_ASSERT(flags & (PolyLineRouting | OrthogonalRouting));
75
76 if (flags & PolyLineRouting)
77 {
78 m_allows_polyline_routing = true;
79 }
80 if (flags & OrthogonalRouting)
81 {
82 m_allows_orthogonal_routing = true;
83 }
84
85 for (size_t p = 0; p < lastRoutingParameterMarker; ++p)
86 {
87 m_routing_parameters[p] = 0.0;
88 }
89 m_routing_parameters[segmentPenalty] = 10;
90 m_routing_parameters[clusterCrossingPenalty] = 4000;
91 m_routing_parameters[idealNudgingDistance] = 4.0;
92
93 m_routing_options[nudgeOrthogonalSegmentsConnectedToShapes] = false;
94 m_routing_options[improveHyperedgeRoutesMovingJunctions] = true;
95 m_routing_options[penaliseOrthogonalSharedPathsAtConnEnds] = false;
96 m_routing_options[nudgeOrthogonalTouchingColinearSegments] = false;
97 m_routing_options[performUnifyingNudgingPreprocessingStep] = true;
98 m_routing_options[improveHyperedgeRoutesMovingAddingAndDeletingJunctions] =
99 false;
100 m_routing_options[nudgeSharedPathsWithCommonEndPoint] = true;
101
102 m_hyperedge_improver.setRouter(this);
103 m_hyperedge_rerouter.setRouter(this);
104 }
105
106
~Router()107 Router::~Router()
108 {
109 m_currently_calling_destructors = true;
110
111 // Delete remaining connectors.
112 ConnRefList::iterator conn = connRefs.begin();
113 while (conn != connRefs.end())
114 {
115 db_printf("Deleting connector %u in ~Router()\n", (*conn)->id());
116 delete *conn;
117 conn = connRefs.begin();
118 }
119
120 // Remove remaining obstacles (shapes and junctions).
121 ObstacleList::iterator obstacle = m_obstacles.begin();
122 while (obstacle != m_obstacles.end())
123 {
124 Obstacle *obstaclePtr = *obstacle;
125 ShapeRef *shape = dynamic_cast<ShapeRef *> (obstaclePtr);
126 db_printf("Deleting %s %u in ~Router()\n",
127 (shape) ? "shape" : "junction", obstaclePtr->id());
128 if (obstaclePtr->isActive())
129 {
130 obstaclePtr->removeFromGraph();
131 obstaclePtr->makeInactive();
132 }
133 delete obstaclePtr;
134 obstacle = m_obstacles.begin();
135 }
136 m_currently_calling_destructors = false;
137
138 // Cleanup orphaned orthogonal graph vertices.
139 destroyOrthogonalVisGraph();
140
141 COLA_ASSERT(m_obstacles.size() == 0);
142 COLA_ASSERT(connRefs.size() == 0);
143 COLA_ASSERT(visGraph.size() == 0);
144
145 delete m_topology_addon;
146 }
147
setDebugHandler(DebugHandler * handler)148 void Router::setDebugHandler(DebugHandler *handler)
149 {
150 m_debug_handler = handler;
151 }
152
debugHandler(void) const153 DebugHandler *Router::debugHandler(void) const
154 {
155 return m_debug_handler;
156 }
157
shapeContainingPoint(const Point & point)158 ShapeRef *Router::shapeContainingPoint(const Point& point)
159 {
160 // Count points on the border as being inside.
161 bool countBorder = true;
162
163 // Compute enclosing shapes.
164 ObstacleList::const_iterator finish = m_obstacles.end();
165 for (ObstacleList::const_iterator i = m_obstacles.begin(); i != finish; ++i)
166 {
167 ShapeRef *shape = dynamic_cast<ShapeRef *>(*i);
168 if (shape && inPoly(shape->routingPolygon(), point, countBorder))
169 {
170 return shape;
171 }
172 }
173 return nullptr;
174 }
175
modifyConnector(ConnRef * conn,const unsigned int type,const ConnEnd & connEnd,bool connPinMoveUpdate)176 void Router::modifyConnector(ConnRef *conn, const unsigned int type,
177 const ConnEnd& connEnd, bool connPinMoveUpdate)
178 {
179 ActionInfo modInfo(ConnChange, conn);
180
181 ActionInfoList::iterator found =
182 find(actionList.begin(), actionList.end(), modInfo);
183 if (found == actionList.end())
184 {
185 // Matching action not found, so add.
186 modInfo.conns.push_back(std::make_pair(type, connEnd));
187 actionList.push_back(modInfo);
188 }
189 else
190 {
191 // Update the found action as necessary.
192 found->addConnEndUpdate(type, connEnd, connPinMoveUpdate);
193 }
194
195 if (!m_consolidate_actions)
196 {
197 processTransaction();
198 }
199 }
200
201
modifyConnector(ConnRef * conn)202 void Router::modifyConnector(ConnRef *conn)
203 {
204 ActionInfo modInfo(ConnChange, conn);
205
206 ActionInfoList::iterator found =
207 find(actionList.begin(), actionList.end(), modInfo);
208 if (found == actionList.end())
209 {
210 actionList.push_back(modInfo);
211 }
212
213 if (!m_consolidate_actions)
214 {
215 processTransaction();
216 }
217 }
218
219
modifyConnectionPin(ShapeConnectionPin * pin)220 void Router::modifyConnectionPin(ShapeConnectionPin *pin)
221 {
222 ActionInfo modInfo(ConnectionPinChange, pin);
223
224 ActionInfoList::iterator found =
225 find(actionList.begin(), actionList.end(), modInfo);
226 if (found == actionList.end())
227 {
228 actionList.push_back(modInfo);
229 }
230
231 if (!m_consolidate_actions)
232 {
233 processTransaction();
234 }
235 }
236
237
removeObjectFromQueuedActions(const void * object)238 void Router::removeObjectFromQueuedActions(const void *object)
239 {
240 for (ActionInfoList::iterator curr = actionList.begin();
241 curr != actionList.end(); )
242 {
243 if (curr->objPtr == object)
244 {
245 curr = actionList.erase(curr);
246 }
247 else
248 {
249 ++curr;
250 }
251 }
252 }
253
254
addShape(ShapeRef * shape)255 void Router::addShape(ShapeRef *shape)
256 {
257 // There shouldn't be remove events or move events for the same shape
258 // already in the action list.
259 // XXX: Possibly we could handle this by ordering them intelligently.
260 COLA_ASSERT(find(actionList.begin(), actionList.end(),
261 ActionInfo(ShapeRemove, shape)) == actionList.end());
262 COLA_ASSERT(find(actionList.begin(), actionList.end(),
263 ActionInfo(ShapeMove, shape)) == actionList.end());
264
265 ActionInfo addInfo(ShapeAdd, shape);
266
267 ActionInfoList::iterator found =
268 find(actionList.begin(), actionList.end(), addInfo);
269 if (found == actionList.end())
270 {
271 actionList.push_back(addInfo);
272 }
273
274 if (!m_consolidate_actions)
275 {
276 processTransaction();
277 }
278 }
279
280
deleteShape(ShapeRef * shape)281 void Router::deleteShape(ShapeRef *shape)
282 {
283 // There shouldn't be add events events for the same shape already
284 // in the action list.
285 // XXX: Possibly we could handle this by ordering them intelligently.
286 COLA_ASSERT(find(actionList.begin(), actionList.end(),
287 ActionInfo(ShapeAdd, shape)) == actionList.end());
288
289 // Delete any ShapeMove entries for this shape in the action list.
290 ActionInfoList::iterator found = find(actionList.begin(),
291 actionList.end(), ActionInfo(ShapeMove, shape));
292 if (found != actionList.end())
293 {
294 actionList.erase(found);
295 }
296
297 // Add the ShapeRemove entry.
298 ActionInfo remInfo(ShapeRemove, shape);
299 found = find(actionList.begin(), actionList.end(), remInfo);
300 if (found == actionList.end())
301 {
302 actionList.push_back(remInfo);
303 }
304
305 if (!m_consolidate_actions)
306 {
307 processTransaction();
308 }
309 }
310
311
deleteConnector(ConnRef * connector)312 void Router::deleteConnector(ConnRef *connector)
313 {
314 m_currently_calling_destructors = true;
315 delete connector;
316 m_currently_calling_destructors = false;
317 }
318
moveShape(ShapeRef * shape,const double xDiff,const double yDiff)319 void Router::moveShape(ShapeRef *shape, const double xDiff, const double yDiff)
320 {
321 ActionInfo moveInfo(ShapeMove, shape, Polygon(), false);
322 ActionInfoList::iterator found =
323 find(actionList.begin(), actionList.end(), moveInfo);
324
325 Polygon newPoly;
326 if (found != actionList.end())
327 {
328 // The shape already has a queued move, so use that shape position.
329 newPoly = found->newPoly;
330 }
331 else
332 {
333 // Just use the existing position.
334 newPoly = shape->polygon();
335 }
336 newPoly.translate(xDiff, yDiff);
337
338 moveShape(shape, newPoly);
339 }
340
341
markAllObstaclesAsMoved(void)342 void Router::markAllObstaclesAsMoved(void)
343 {
344 for (ObstacleList::iterator obstacleIt = m_obstacles.begin();
345 obstacleIt != m_obstacles.end(); ++obstacleIt)
346 {
347 ShapeRef *shape = dynamic_cast<ShapeRef *> (*obstacleIt);
348 JunctionRef *junction = dynamic_cast<JunctionRef *> (*obstacleIt);
349 if (shape)
350 {
351 moveShape(shape, 0, 0);
352 }
353 else if (junction)
354 {
355 moveJunction(junction, 0, 0);
356 }
357 }
358 }
359
moveShape(ShapeRef * shape,const Polygon & newPoly,const bool first_move)360 void Router::moveShape(ShapeRef *shape, const Polygon& newPoly,
361 const bool first_move)
362 {
363 // There shouldn't be remove events or add events for the same shape
364 // already in the action list.
365 // XXX: Possibly we could handle this by ordering them intelligently.
366 COLA_ASSERT(find(actionList.begin(), actionList.end(),
367 ActionInfo(ShapeRemove, shape)) == actionList.end());
368
369 ActionInfoList::iterator found = find(actionList.begin(),
370 actionList.end(), ActionInfo(ShapeAdd, shape));
371 if (found != actionList.end())
372 {
373 // The Add is enough, no need for the Move action too.
374 // The shape will be added with it's existing polygon,
375 // so set this to be the newPoly passed for the move.
376 found->shape()->setNewPoly(newPoly);
377 return;
378 }
379
380 ActionInfo moveInfo(ShapeMove, shape, newPoly, first_move);
381 // Sanely cope with the case where the user requests moving the same
382 // shape multiple times before rerouting connectors.
383 found = find(actionList.begin(), actionList.end(), moveInfo);
384
385 if (found != actionList.end())
386 {
387 // Just update the ActionInfo with the second polygon, but
388 // leave the firstMove setting alone.
389 found->newPoly = newPoly;
390 }
391 else
392 {
393 actionList.push_back(moveInfo);
394 }
395
396 if (!m_consolidate_actions)
397 {
398 processTransaction();
399 }
400 }
401
402
setStaticGraphInvalidated(const bool invalidated)403 void Router::setStaticGraphInvalidated(const bool invalidated)
404 {
405 m_static_orthogonal_graph_invalidated = invalidated;
406 }
407
408
destroyOrthogonalVisGraph(void)409 void Router::destroyOrthogonalVisGraph(void)
410 {
411 // Remove orthogonal visibility graph edges.
412 visOrthogGraph.clear();
413
414 // Remove the now orphaned vertices.
415 VertInf *curr = vertices.shapesBegin();
416 while (curr)
417 {
418 if (curr->orphaned() && (curr->id == dummyOrthogID))
419 {
420 VertInf *following = vertices.removeVertex(curr);
421 delete curr;
422 curr = following;
423 continue;
424 }
425 curr = curr->lstNext;
426 }
427 }
428
429
regenerateStaticBuiltGraph(void)430 void Router::regenerateStaticBuiltGraph(void)
431 {
432 // Here we do talks involved in updating the static-built visibility
433 // graph (if necessary) before we do any routing.
434 if (m_static_orthogonal_graph_invalidated)
435 {
436 if (m_allows_orthogonal_routing)
437 {
438 destroyOrthogonalVisGraph();
439
440 TIMER_START(this, tmOrthogGraph);
441 // Regenerate a new visibility graph.
442 generateStaticOrthogonalVisGraph(this);
443
444 TIMER_STOP(this);
445 }
446 m_static_orthogonal_graph_invalidated = false;
447 }
448 }
449
450
transactionUse(void) const451 bool Router::transactionUse(void) const
452 {
453 return m_consolidate_actions;
454 }
455
456
setTransactionUse(const bool transactions)457 void Router::setTransactionUse(const bool transactions)
458 {
459 m_consolidate_actions = transactions;
460 }
461
462
463 // Processes the action list.
processActions(void)464 void Router::processActions(void)
465 {
466 bool notPartialTime = !(PartialFeedback && PartialTime);
467 bool seenShapeMovesOrDeletes = false;
468
469 m_transaction_start_time = clock();
470 m_abort_transaction = false;
471
472 std::list<unsigned int> deletedObstacles;
473 actionList.sort();
474 ActionInfoList::iterator curr;
475 ActionInfoList::iterator finish = actionList.end();
476 for (curr = actionList.begin(); curr != finish; ++curr)
477 {
478 ActionInfo& actInf = *curr;
479 if (!((actInf.type == ShapeRemove) || (actInf.type == ShapeMove) ||
480 (actInf.type == JunctionRemove) || (actInf.type == JunctionMove)))
481 {
482 // Not a move or remove action, so don't do anything.
483 continue;
484 }
485 seenShapeMovesOrDeletes = true;
486
487 Obstacle *obstacle = actInf.obstacle();
488 ShapeRef *shape = actInf.shape();
489 JunctionRef *junction = actInf.junction();
490 bool isMove = (actInf.type == ShapeMove) ||
491 (actInf.type == JunctionMove);;
492 bool first_move = actInf.firstMove;
493
494 unsigned int pid = obstacle->id();
495
496 // o Remove entries related to this shape's vertices
497 obstacle->removeFromGraph();
498
499 if (SelectiveReroute && (!isMove || notPartialTime || first_move))
500 {
501 markPolylineConnectorsNeedingReroutingForDeletedObstacle(obstacle);
502 }
503
504 adjustContainsWithDel(pid);
505
506 if (isMove)
507 {
508 if (shape)
509 {
510 shape->moveAttachedConns(actInf.newPoly);
511 }
512 else if (junction)
513 {
514 junction->moveAttachedConns(actInf.newPosition);
515 }
516 }
517
518 // Ignore this shape for visibility.
519 // XXX: We don't really need to do this if we're not using Partial
520 // Feedback. Without this the blocked edges still route
521 // around the shape until it leaves the connector.
522 obstacle->makeInactive();
523
524 if (!isMove)
525 {
526 // Free deleted obstacle.
527 m_currently_calling_destructors = true;
528 deletedObstacles.push_back(obstacle->id());
529 delete obstacle;
530 m_currently_calling_destructors = false;
531 }
532 }
533
534 if (seenShapeMovesOrDeletes && m_allows_polyline_routing)
535 {
536 if (InvisibilityGrph)
537 {
538 // Check edges for obstacles that were moved or removed.
539 for (curr = actionList.begin(); curr != finish; ++curr)
540 {
541 ActionInfo& actInf = *curr;
542 if ((actInf.type == ShapeMove) || (actInf.type == JunctionMove))
543 {
544 // o Check all edges that were blocked by moved obstacle.
545 checkAllBlockedEdges(actInf.obstacle()->id());
546 }
547 }
548
549 for (std::list<unsigned int>::iterator it = deletedObstacles.begin();
550 it != deletedObstacles.end(); ++it)
551 {
552 // o Check all edges that were blocked by deleted obstacle.
553 checkAllBlockedEdges(*it);
554 }
555 }
556 else
557 {
558 // check all edges not in graph
559 checkAllMissingEdges();
560 }
561 }
562
563 for (curr = actionList.begin(); curr != finish; ++curr)
564 {
565 ActionInfo& actInf = *curr;
566 if (!((actInf.type == ShapeAdd) || (actInf.type == ShapeMove) ||
567 (actInf.type == JunctionAdd) || (actInf.type == JunctionMove)))
568 {
569 // Not a move or add action, so don't do anything.
570 continue;
571 }
572
573 Obstacle *obstacle = actInf.obstacle();
574 ShapeRef *shape = actInf.shape();
575 JunctionRef *junction = actInf.junction();
576 Polygon& newPoly = actInf.newPoly;
577 bool isMove = (actInf.type == ShapeMove) ||
578 (actInf.type == JunctionMove);
579
580 unsigned int pid = obstacle->id();
581
582 // Restore this shape for visibility.
583 obstacle->makeActive();
584
585 if (isMove)
586 {
587 if (shape)
588 {
589 shape->setNewPoly(newPoly);
590 }
591 else
592 {
593 junction->setPosition(actInf.newPosition);
594 }
595 }
596 const Polygon& shapePoly = obstacle->routingPolygon();
597
598 adjustContainsWithAdd(shapePoly, pid);
599
600 if (m_allows_polyline_routing)
601 {
602 // o Check all visibility edges to see if this one shape
603 // blocks them.
604 if (!isMove || notPartialTime)
605 {
606 newBlockingShape(shapePoly, pid);
607 }
608
609 // o Calculate visibility for the new vertices.
610 if (UseLeesAlgorithm)
611 {
612 obstacle->computeVisibilitySweep();
613 }
614 else
615 {
616 obstacle->computeVisibilityNaive();
617 }
618 obstacle->updatePinPolyLineVisibility();
619 }
620 }
621
622 // Update connector endpoints.
623 for (curr = actionList.begin(); curr != finish; ++curr)
624 {
625 ActionInfo& actInf = *curr;
626 if (actInf.type != ConnChange)
627 {
628 continue;
629 }
630 for (ConnUpdateList::iterator conn = actInf.conns.begin();
631 conn != actInf.conns.end(); ++conn)
632 {
633 actInf.conn()->updateEndPoint(conn->first, conn->second);
634 }
635 }
636 // Clear the actionList.
637 actionList.clear();
638 }
639
processTransaction(void)640 bool Router::processTransaction(void)
641 {
642 // If SimpleRouting, then don't update here.
643 if ((actionList.empty() && (m_hyperedge_rerouter.count() == 0) &&
644 (m_settings_changes == false)) || SimpleRouting)
645 {
646 return false;
647 }
648 m_settings_changes = false;
649
650 processActions();
651
652 m_static_orthogonal_graph_invalidated = true;
653 rerouteAndCallbackConnectors();
654
655 return true;
656 }
657
658
addJunction(JunctionRef * junction)659 void Router::addJunction(JunctionRef *junction)
660 {
661 // There shouldn't be remove events or move events for the same junction
662 // already in the action list.
663 // XXX: Possibly we could handle this by ordering them intelligently.
664 COLA_ASSERT(find(actionList.begin(), actionList.end(),
665 ActionInfo(JunctionRemove, junction)) == actionList.end());
666 COLA_ASSERT(find(actionList.begin(), actionList.end(),
667 ActionInfo(JunctionMove, junction)) == actionList.end());
668
669 ActionInfo addInfo(JunctionAdd, junction);
670
671 ActionInfoList::iterator found =
672 find(actionList.begin(), actionList.end(), addInfo);
673 if (found == actionList.end())
674 {
675 actionList.push_back(addInfo);
676 }
677
678 if (!m_consolidate_actions)
679 {
680 processTransaction();
681 }
682 }
683
684
deleteJunction(JunctionRef * junction)685 void Router::deleteJunction(JunctionRef *junction)
686 {
687 // There shouldn't be add events events for the same junction already
688 // in the action list.
689 // XXX: Possibly we could handle this by ordering them intelligently.
690 COLA_ASSERT(find(actionList.begin(), actionList.end(),
691 ActionInfo(JunctionAdd, junction)) == actionList.end());
692
693 // Delete any ShapeMove entries for this shape in the action list.
694 ActionInfoList::iterator found = find(actionList.begin(),
695 actionList.end(), ActionInfo(JunctionMove, junction));
696 if (found != actionList.end())
697 {
698 actionList.erase(found);
699 }
700
701 // Add the ShapeRemove entry.
702 ActionInfo remInfo(JunctionRemove, junction);
703 found = find(actionList.begin(), actionList.end(), remInfo);
704 if (found == actionList.end())
705 {
706 actionList.push_back(remInfo);
707 }
708
709 if (!m_consolidate_actions)
710 {
711 processTransaction();
712 }
713 }
714
715
moveJunction(JunctionRef * junction,const double xDiff,const double yDiff)716 void Router::moveJunction(JunctionRef *junction, const double xDiff,
717 const double yDiff)
718 {
719 ActionInfo moveInfo(JunctionMove, junction, Point());
720 ActionInfoList::iterator found =
721 find(actionList.begin(), actionList.end(), moveInfo);
722
723 Point newPosition;
724 if (found != actionList.end())
725 {
726 // The junction already has a queued move, so use that position.
727 newPosition = found->newPosition;
728 }
729 else
730 {
731 // Just use the existing position.
732 newPosition = junction->position();
733 }
734 newPosition.x += xDiff;
735 newPosition.y += yDiff;
736
737 moveJunction(junction, newPosition);
738 }
739
740
moveJunction(JunctionRef * junction,const Point & newPosition)741 void Router::moveJunction(JunctionRef *junction, const Point& newPosition)
742 {
743 // There shouldn't be remove events or add events for the same junction
744 // already in the action list.
745 // XXX: Possibly we could handle this by ordering them intelligently.
746 COLA_ASSERT(find(actionList.begin(), actionList.end(),
747 ActionInfo(JunctionRemove, junction)) == actionList.end());
748
749 ActionInfoList::iterator found = find(actionList.begin(),
750 actionList.end(), ActionInfo(JunctionAdd, junction));
751 if (found != actionList.end())
752 {
753 // The Add is enough, no need for the Move action too.
754 // The junction will be added with the new position.
755 found->junction()->setPosition(newPosition);
756 return;
757 }
758
759 ActionInfo moveInfo(JunctionMove, junction, newPosition);
760 // Sanely cope with the case where the user requests moving the same
761 // shape multiple times before rerouting connectors.
762 found = find(actionList.begin(), actionList.end(), moveInfo);
763
764 if (found != actionList.end())
765 {
766 // Just update the ActionInfo with the second position.
767 found->newPosition = newPosition;
768 }
769 else
770 {
771 actionList.push_back(moveInfo);
772 }
773
774 if (!m_consolidate_actions)
775 {
776 processTransaction();
777 }
778 }
779
addCluster(ClusterRef * cluster)780 void Router::addCluster(ClusterRef *cluster)
781 {
782 cluster->makeActive();
783
784 unsigned int pid = cluster->id();
785 ReferencingPolygon& poly = cluster->polygon();
786
787 adjustClustersWithAdd(poly, pid);
788 }
789
790
deleteCluster(ClusterRef * cluster)791 void Router::deleteCluster(ClusterRef *cluster)
792 {
793 cluster->makeInactive();
794
795 unsigned int pid = cluster->id();
796
797 adjustClustersWithDel(pid);
798 }
799
800
newObjectId(void) const801 unsigned int Router::newObjectId(void) const
802 {
803 return m_largest_assigned_id + 1;
804 }
805
806
assignId(const unsigned int suggestedId)807 unsigned int Router::assignId(const unsigned int suggestedId)
808 {
809 // If the suggestedId is zero, then we assign the object the next
810 // smallest unassigned ID, otherwise we trust the ID given is unique.
811 unsigned int assignedId = (suggestedId == 0) ? newObjectId() : suggestedId;
812
813 // If assertions are enabled, then we check that this ID really is unique.
814 COLA_ASSERT(objectIdIsUnused(assignedId));
815
816 // Have the router record if this ID is larger than the largest assigned ID.
817 m_largest_assigned_id = std::max(m_largest_assigned_id, assignedId);
818
819 return assignedId;
820 }
821
822
823 // Returns whether the given ID is unique among all objects known by the
824 // router. It is expected this is only going to be called from assertions
825 // while debugging, so efficiency is not an issue and we just iterate over
826 // all objects.
objectIdIsUnused(const unsigned int id) const827 bool Router::objectIdIsUnused(const unsigned int id) const
828 {
829 // Examine shapes/junctions.
830 for (ObstacleList::const_iterator i = m_obstacles.begin();
831 i != m_obstacles.end(); ++i)
832 {
833 if ((*i)->id() == id)
834 {
835 return false;
836 }
837 }
838
839 // Examine connectors.
840 for (ConnRefList::const_iterator i = connRefs.begin();
841 i != connRefs.end(); ++i)
842 {
843 if ((*i)->id() == id)
844 {
845 return false;
846 }
847 }
848
849 // Examine clusters.
850 for (ClusterRefList::const_iterator i = clusterRefs.begin();
851 i != clusterRefs.end(); ++i)
852 {
853 if ((*i)->id() == id)
854 {
855 return false;
856 }
857 }
858
859 return true;
860 }
861
862
863 //----------------------------------------------------------------------------
864
865 // Returns a list of connector Ids of all the connectors of type
866 // 'type' attached to the shape with the ID 'shapeId'.
attachedConns(IntList & conns,const unsigned int shapeId,const unsigned int type)867 void Router::attachedConns(IntList &conns, const unsigned int shapeId,
868 const unsigned int type)
869 {
870 ConnRefList::const_iterator fin = connRefs.end();
871 for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
872 {
873 std::pair<Obstacle *, Obstacle *> anchors = (*i)->endpointAnchors();
874
875 if ((type & runningTo) &&
876 (anchors.second && (anchors.second->id() == shapeId)))
877 {
878 conns.push_back((*i)->id());
879 }
880 else if ((type & runningFrom) &&
881 (anchors.first && (anchors.first->id() == shapeId)))
882 {
883 conns.push_back((*i)->id());
884 }
885 }
886 }
887
888
889 // Returns a list of shape Ids of all the shapes attached to the
890 // shape with the ID 'shapeId' with connection type 'type'.
attachedShapes(IntList & shapes,const unsigned int shapeId,const unsigned int type)891 void Router::attachedShapes(IntList &shapes, const unsigned int shapeId,
892 const unsigned int type)
893 {
894 ConnRefList::const_iterator fin = connRefs.end();
895 for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
896 {
897 std::pair<Obstacle *, Obstacle *> anchors = (*i)->endpointAnchors();
898
899 if ((type & runningTo) &&
900 (anchors.second && (anchors.second->id() == shapeId)))
901 {
902 if (anchors.first)
903 {
904 // Only if there is a shape attached to the other end.
905 shapes.push_back(anchors.first->id());
906 }
907 }
908 else if ((type & runningFrom) &&
909 (anchors.first && (anchors.first->id() == shapeId)))
910 {
911 if (anchors.second)
912 {
913 // Only if there is a shape attached to the other end.
914 shapes.push_back(anchors.second->id());
915 }
916 }
917 }
918 }
919
920
921 // It's intended this function is called after visibility changes
922 // resulting from shape movement have happened. It will alert
923 // rerouted connectors (via a callback) that they need to be redrawn.
rerouteAndCallbackConnectors(void)924 void Router::rerouteAndCallbackConnectors(void)
925 {
926 ConnRefList reroutedConns;
927 ConnRefList::const_iterator fin = connRefs.end();
928
929 this->m_conn_reroute_flags.alertConns();
930
931 // Updating the orthogonal visibility graph if necessary.
932 regenerateStaticBuiltGraph();
933
934 for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
935 {
936 (*i)->freeActivePins();
937 }
938
939 // Calculate and return connectors that are part of hyperedges and will
940 // be completely rerouted by that code and thus don't need to have routes
941 // generated here.
942 ConnRefSet hyperedgeConns =
943 m_hyperedge_rerouter.calcHyperedgeConnectors();
944
945 // TODO: It might be worth sorting connectors and routing them from
946 // smallest to largest estimated cost. This way we likely get
947 // better exclusive pin assignment during initial routing.
948
949 size_t totalConns = connRefs.size();
950 size_t numOfReroutedConns = 0;
951 for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)
952 {
953 // Progress reporting and continuation check.
954 performContinuationCheck(TransactionPhaseRouteSearch,
955 numOfReroutedConns, totalConns);
956 ++numOfReroutedConns;
957
958 ConnRef *connector = *i;
959 if (hyperedgeConns.find(connector) != hyperedgeConns.end())
960 {
961 // This will be rerouted by the hyperedge code, so do nothing.
962 continue;
963 }
964
965 if (connector->hasFixedRoute())
966 {
967 // We don't reroute connectors with fixed routes.
968 continue;
969 }
970
971 TIMER_START(this, tmOrthogRoute);
972 connector->m_needs_repaint = false;
973 bool rerouted = connector->generatePath();
974 if (rerouted)
975 {
976 reroutedConns.push_back(connector);
977 }
978 TIMER_STOP(this);
979 }
980
981
982 // Perform any complete hyperedge rerouting that has been requested.
983 m_hyperedge_rerouter.performRerouting();
984
985 // Find and reroute crossing connectors if crossing penalties are set.
986 improveCrossings();
987
988 bool withMinorImprovements = routingOption(
989 improveHyperedgeRoutesMovingJunctions);
990 bool withMajorImprovements = routingOption(
991 improveHyperedgeRoutesMovingAddingAndDeletingJunctions);
992 if (withMinorImprovements || withMajorImprovements)
993 {
994 m_hyperedge_improver.clear();
995 m_hyperedge_improver.execute(withMajorImprovements);
996 }
997
998 // Perform centring and nudging for orthogonal routes.
999 improveOrthogonalRoutes(this);
1000
1001 // Find a list of all the deleted connectors in hyperedges.
1002 HyperedgeNewAndDeletedObjectLists changedHyperedgeObjs =
1003 m_hyperedge_improver.newAndDeletedObjectLists();
1004 ConnRefList deletedConns = changedHyperedgeObjs.deletedConnectorList;
1005 for (size_t index = 0; index < m_hyperedge_rerouter.count(); ++index)
1006 {
1007 changedHyperedgeObjs =
1008 m_hyperedge_rerouter.newAndDeletedObjectLists(index);
1009 deletedConns.merge(changedHyperedgeObjs.deletedConnectorList);
1010 }
1011
1012 // Alert connectors that they need redrawing.
1013 fin = reroutedConns.end();
1014 for (ConnRefList::const_iterator i = reroutedConns.begin(); i != fin; ++i)
1015 {
1016 ConnRef *conn = *i;
1017
1018 // Skip hyperedge connectors which have been deleted.
1019 ConnRefList::iterator findIt = std::find(
1020 deletedConns.begin(), deletedConns.end(), conn);
1021 if (findIt != deletedConns.end())
1022 {
1023 // Connector deleted, skip.
1024 continue;
1025 }
1026
1027 conn->m_needs_repaint = true;
1028 conn->performCallback();
1029 }
1030
1031 // Progress reporting.
1032 performContinuationCheck(TransactionPhaseCompleted, 1, 1);
1033 }
1034
1035 // Type holding a cost estimate and ConnRef.
1036 typedef std::pair<double, ConnRef *> ConnCostRef;
1037
1038 // A comparison class used to order a set of ConnCostRefs.
1039 class CmpConnCostRef
1040 {
1041 public:
CmpConnCostRef()1042 CmpConnCostRef()
1043 {
1044 }
operator ()(const ConnCostRef & u,const ConnCostRef & v) const1045 bool operator() (const ConnCostRef& u, const ConnCostRef& v) const
1046 {
1047 return (u.second->id() < v.second->id());
1048 }
1049 };
1050
1051 typedef std::set<ConnCostRef, CmpConnCostRef> ConnCostRefSet;
1052 typedef std::list<ConnCostRefSet> ConnCostRefSetList;
1053
1054
cheapEstimatedCost(ConnRef * lineRef)1055 static double cheapEstimatedCost(ConnRef *lineRef)
1056 {
1057 // We use an estimate of overall connector length, reduced by a count
1058 // of the number of segments. In the case of equal length, This causes
1059 // straight line connectors to be left alone and connectors with more
1060 // complex paths to be rerouted.
1061 bool isPolyLine = (lineRef->routingType() == ConnType_PolyLine);
1062 const PolyLine& route = lineRef->displayRoute();
1063 double length = 0;
1064
1065 for (size_t i = 1; i < route.size(); ++i)
1066 {
1067 const Point& a = route.ps[i - 1];
1068 const Point& b = route.ps[i];
1069
1070 double segmentLength = (isPolyLine) ?
1071 euclideanDist(a, b) : manhattanDist(a, b);
1072 length += segmentLength;
1073 }
1074 return length - (route.size() + 1);
1075 }
1076
1077 // A map of connectors to the set of connectors that cross them.
1078 typedef std::map<ConnRef *, std::set<ConnRef *> > CrossingConnectorsMap;
1079
1080 // A list of connector crossing maps that don't interact with each other.
1081 typedef std::list<CrossingConnectorsMap> CrossingConnectorsMapList;
1082
1083 // This class maintains the list of connector crossing maps and provides
1084 // methods for adding crossing connector pairs and getting the minimal sets
1085 // of connectors that can be removed from each group to prevent crossings.
1086 class CrossingConnectorsInfo
1087 {
1088 public:
1089
1090 // Add information that a pair of connectors cross.
addCrossing(ConnRef * conn1,ConnRef * conn2)1091 void addCrossing(ConnRef *conn1, ConnRef *conn2)
1092 {
1093 // Find the existing or new group that this crossing
1094 // should be recorded in.
1095 CrossingConnectorsMapList::iterator it =
1096 groupForCrossingConns(conn1, conn2);
1097 CrossingConnectorsMap& pairsSet = *it;
1098
1099 // Record the crossing.
1100 pairsSet[conn1].insert(conn2);
1101 pairsSet[conn2].insert(conn1);
1102 }
1103
1104 // This method builds and returns a list of non-interacting sets of
1105 // connectors (with crossing counts) that need to be removed so there
1106 // are no crossings. These are the connectors we reroute. Where
1107 // these connectors attach to exclusive connection pins, we return
1108 // and thus reroute all connectors attached to the exlcusive pins. We
1109 // do this so we are no so committed to possible bad pin assignemnts.
crossingSetsListToRemoveCrossingsFromGroups(void)1110 ConnCostRefSetList crossingSetsListToRemoveCrossingsFromGroups(void)
1111 {
1112 // A list of the minimal sets of connectors that cause crossings
1113 // in all groups of crossingconnectors.
1114 ConnCostRefSetList crossingSetsList;
1115
1116 // For each group of crossing connectors.
1117 for (CrossingConnectorsMapList::iterator it = pairsSetList.begin();
1118 it != pairsSetList.end(); ++it)
1119 {
1120 // The minimal set of crossing-causing connectors.
1121 // We will build this.
1122 ConnCostRefSet crossingSet;
1123
1124 // Set of exclusive pins that the crossing-causing connectors
1125 // attach to.
1126 std::set<ConnectionPinIds> exclusivePins;
1127
1128 // The group of all crossing pairs.
1129 CrossingConnectorsMap& pairsSet = *it;
1130
1131 // For each crossing-causing connector.
1132 ConnCostRef crossingCausingConnector;
1133 while ( (crossingCausingConnector =
1134 removeConnectorWithMostCrossings(pairsSet)).second != nullptr )
1135 {
1136 // Add it to our crossing-causing set.
1137 crossingSet.insert(crossingCausingConnector);
1138
1139 // Determine if it attaches to any exclusive pins and
1140 // record these.
1141 std::pair<ConnEnd, ConnEnd> ends =
1142 crossingCausingConnector.second->endpointConnEnds();
1143 // Look at one end.
1144 ShapeConnectionPin *pin = ends.first.m_active_pin;
1145 if (pin && pin->isExclusive())
1146 {
1147 exclusivePins.insert(pin->ids());
1148 }
1149 // Look at other end.
1150 pin = ends.second.m_active_pin;
1151 if (pin && pin->isExclusive())
1152 {
1153 exclusivePins.insert(pin->ids());
1154 }
1155 }
1156
1157 // For each of the remaining connectors which are not
1158 // crossing-causing, add them to our crossing set if they
1159 // attach to one of the exclusive pin classes which the
1160 // crossing-causing connectors attached to.
1161 for (CrossingConnectorsMap::const_iterator it2 =
1162 pairsSet.begin(); it2 != pairsSet.end(); ++it2)
1163 {
1164 ConnRef *conn = it2->first;
1165 std::pair<ConnEnd, ConnEnd> ends = conn->endpointConnEnds();
1166 // Look at one end.
1167 ShapeConnectionPin *pin = ends.first.m_active_pin;
1168 if (pin && pin->isExclusive())
1169 {
1170 if (exclusivePins.count(pin->ids()) > 0)
1171 {
1172 // Attaches to an exclusive pin and it matches
1173 // one attached to by the crossing-causing
1174 // connectors. So add the conn to the
1175 // crossing set and continue..
1176 crossingSet.insert(std::make_pair(0, conn));
1177 continue;
1178 }
1179 }
1180 // Look at other end.
1181 pin = ends.second.m_active_pin;
1182 if (pin && pin->isExclusive())
1183 {
1184 if (exclusivePins.count(pin->ids()) > 0)
1185 {
1186 // Attaches to an exclusive pin and it matches
1187 // one attached to by the crossing-causing
1188 // connectors. So add the conn to the
1189 // crossing set.
1190 crossingSet.insert(std::make_pair(0, conn));
1191 }
1192 }
1193 }
1194
1195 if (!crossingSet.empty())
1196 {
1197 crossingSetsList.push_back(crossingSet);
1198 }
1199 }
1200 return crossingSetsList;
1201 }
1202
1203 // Returns whether this pair of connector is already known to cross.
connsKnownToCross(ConnRef * conn1,ConnRef * conn2)1204 bool connsKnownToCross(ConnRef *conn1, ConnRef *conn2)
1205 {
1206 CrossingConnectorsMapList::iterator it1 = groupForConn(conn1);
1207 CrossingConnectorsMapList::iterator it2 = groupForConn(conn2);
1208
1209 // The connectors cross if
1210 if ((it1 == it2) && (it1 != pairsSetList.end()))
1211 {
1212 // They are in the same group and conn2 is in crossing
1213 // connectors set of conn1.
1214 CrossingConnectorsMap& pairsSet = *it1;
1215 return ((pairsSet.count(conn1) > 0) &&
1216 (pairsSet[conn1].count(conn2) > 0));
1217 }
1218 return false;
1219 }
1220
1221 private:
1222
1223 // Given a particular group (pairsSet), removes the connector with
1224 // the most crossings withing the group and returns it along with its
1225 // crossing count.
removeConnectorWithMostCrossings(CrossingConnectorsMap & pairsSet)1226 ConnCostRef removeConnectorWithMostCrossings(
1227 CrossingConnectorsMap& pairsSet)
1228 {
1229 // Tracking of the greatest number of crossings.
1230 ConnRef *candidateConnector = nullptr;
1231 size_t candidateCrossingCount = 0;
1232 double candidateEstimatedCost = 0;
1233
1234 // For each connector in the group...
1235 for (CrossingConnectorsMap::const_iterator it = pairsSet.begin();
1236 it != pairsSet.end(); ++it)
1237 {
1238 // ... check if it has any crossings.
1239 size_t crossings = it->second.size();
1240 if (crossings == 0)
1241 {
1242 // If not, skip.
1243 continue;
1244 }
1245
1246 // It has crossings. Determine if it has the most crossings
1247 // of the connectors we've seen, or if it is tied but has
1248 // a greater estimated cost. If so, it is our new candidate.
1249 double cost = cheapEstimatedCost(it->first);
1250 if ((crossings > candidateCrossingCount) ||
1251 ((crossings == candidateCrossingCount) &&
1252 (cost > candidateEstimatedCost)))
1253 {
1254 // Update with new candidate.
1255 candidateConnector = it->first;
1256 candidateCrossingCount = crossings;
1257 candidateEstimatedCost = cost;
1258 }
1259 }
1260
1261 if (candidateConnector == nullptr)
1262 {
1263 // If no candidate, return nullptr connector.
1264 return std::make_pair(0, (ConnRef *) nullptr);
1265 }
1266
1267 // Remove the candidate from the group. To do this we find the
1268 // set of all connectors it crosses.
1269 std::set<ConnRef *>& connSet = pairsSet[candidateConnector];
1270 // For each of these
1271 for (std::set<ConnRef *>::const_iterator it = connSet.begin();
1272 it != connSet.end(); ++it)
1273 {
1274 // we remove the candidate from their crossing lists
1275 pairsSet[*it].erase(candidateConnector);
1276 }
1277 // And then clear the crossing list for the candidate itself.
1278 connSet.clear();
1279
1280 // Return the candidate connector and its original crossing count.
1281 return std::make_pair(static_cast<double>(candidateCrossingCount), candidateConnector);
1282 }
1283
1284 // Returns the iterator to the group that the given conn is in,
1285 // if it is part of any crossing group.
groupForConn(ConnRef * conn)1286 CrossingConnectorsMapList::iterator groupForConn(ConnRef *conn)
1287 {
1288 // For each group...
1289 for (CrossingConnectorsMapList::iterator it = pairsSetList.begin();
1290 it != pairsSetList.end(); ++it)
1291 {
1292 // ... check if the connector is in it.
1293 if (it->count(conn) > 0)
1294 {
1295 // If so, return it.
1296 return it;
1297 }
1298 }
1299 // Connector was not in any existing group.
1300 return pairsSetList.end();
1301 }
1302
1303 // Given a pair of crossing connectors, returns an iterator to the
1304 // crossing connector group they are part of. If neither are part
1305 // of any group, one is created and returned. If one connector is
1306 // part of an exisitng group, that group is returned. If they are
1307 // part of two different groups, the groups are merged and the
1308 // merged group is returned.
groupForCrossingConns(ConnRef * conn1,ConnRef * conn2)1309 CrossingConnectorsMapList::iterator groupForCrossingConns(
1310 ConnRef *conn1, ConnRef *conn2)
1311 {
1312 CrossingConnectorsMapList::iterator it1 = groupForConn(conn1);
1313 CrossingConnectorsMapList::iterator it2 = groupForConn(conn2);
1314
1315 // groupIt will be the iterator to the appropriate group.
1316 CrossingConnectorsMapList::iterator groupIt = pairsSetList.end();
1317
1318 if ((it1 == pairsSetList.end()) && (it2 == pairsSetList.end()))
1319 {
1320 // Neither are part of a group. Create one.
1321 CrossingConnectorsMap newSet;
1322 groupIt = pairsSetList.insert(pairsSetList.end(), newSet);
1323 }
1324 else if ((it1 != pairsSetList.end()) && (it2 == pairsSetList.end()))
1325 {
1326 // it1 is the appropriate existing group.
1327 groupIt = it1;
1328 }
1329 else if ((it1 == pairsSetList.end()) && (it2 != pairsSetList.end()))
1330 {
1331 // it2 is the appropriate exisitng group.
1332 groupIt = it2;
1333 }
1334 else if (it1 != it2)
1335 {
1336 // There are two different existing groups, so merge them.
1337 COLA_ASSERT(it1 != pairsSetList.end());
1338 COLA_ASSERT(it2 != pairsSetList.end());
1339 it1->insert(it2->begin(), it2->end());
1340 pairsSetList.erase(it2);
1341 groupIt = it1;
1342 }
1343 else
1344 {
1345 // These are already part of the same group. Do nothing.
1346 COLA_ASSERT(it1 == it2);
1347 groupIt = it1;
1348 }
1349 return groupIt;
1350 }
1351
1352 CrossingConnectorsMapList pairsSetList;
1353 };
1354
1355
performContinuationCheck(unsigned int phaseNumber,size_t stepNumber,size_t totalSteps)1356 void Router::performContinuationCheck(unsigned int phaseNumber,
1357 size_t stepNumber, size_t totalSteps)
1358 {
1359 // Compute the elapsed time in msec since the beginning of the transaction.
1360 unsigned int elapsedMsec = (unsigned int)
1361 ((clock() - m_transaction_start_time) /
1362 (CLOCKS_PER_SEC / (double) 1000));
1363
1364 bool shouldContinue = shouldContinueTransactionWithProgress(elapsedMsec,
1365 phaseNumber, TransactionPhaseCompleted,
1366 stepNumber / (double)totalSteps);
1367 if (shouldContinue == false)
1368 {
1369 // Host program has asked us not to continue the transaction.
1370 m_abort_transaction = true;
1371 }
1372 }
1373
1374
shouldContinueTransactionWithProgress(unsigned int elapsedTime,unsigned int phaseNumber,unsigned int totalPhases,double proportion)1375 bool Router::shouldContinueTransactionWithProgress(unsigned int elapsedTime,
1376 unsigned int phaseNumber, unsigned int totalPhases,
1377 double proportion)
1378 {
1379 COLA_UNUSED(elapsedTime);
1380 COLA_UNUSED(phaseNumber);
1381 COLA_UNUSED(totalPhases);
1382 COLA_UNUSED(proportion);
1383
1384 #if 0
1385 printf("Progress: %8u, phase %u of %u... %.2f%%\n", elapsedTime,
1386 phaseNumber, totalPhases, proportion * 100);
1387 #endif
1388
1389 // We always continue. Subclasses can override this behaviour.
1390 return true;
1391 }
1392
1393
1394 class CmpOrderedConnCostRef
1395 {
1396 public:
CmpOrderedConnCostRef()1397 CmpOrderedConnCostRef()
1398 {
1399 }
operator ()(const ConnCostRef & u,const ConnCostRef & v) const1400 bool operator() (const ConnCostRef& u, const ConnCostRef& v) const
1401 {
1402 return (u.first < v.first);
1403 }
1404 };
1405 typedef std::list<ConnCostRef> ConnCostRefList;
1406
1407
improveCrossings(void)1408 void Router::improveCrossings(void)
1409 {
1410 const double crossing_penalty = routingParameter(crossingPenalty);
1411 const double shared_path_penalty = routingParameter(fixedSharedPathPenalty);
1412 if ((crossing_penalty == 0) && (shared_path_penalty == 0))
1413 {
1414 // No penalties, return.
1415 return;
1416 }
1417
1418 // Information on crossing connector groups.
1419 CrossingConnectorsInfo crossingConnInfo;
1420
1421 size_t numOfConns = connRefs.size();
1422 size_t numOfConnsChecked = 0;
1423
1424 // Find crossings and reroute connectors.
1425 m_in_crossing_rerouting_stage = true;
1426 ConnRefList::iterator fin = connRefs.end();
1427 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
1428 {
1429 // Progress reporting and continuation check.
1430 ++numOfConnsChecked;
1431 performContinuationCheck(TransactionPhaseCrossingDetection,
1432 numOfConnsChecked, numOfConns);
1433 if (m_abort_transaction)
1434 {
1435 m_in_crossing_rerouting_stage = false;
1436 return;
1437 }
1438
1439 Avoid::Polygon& iRoute = (*i)->routeRef();
1440 if (iRoute.size() == 0)
1441 {
1442 // Rerouted hyperedges will have an empty route.
1443 // We can't reroute these.
1444 continue;
1445 }
1446 ConnRefList::iterator j = i;
1447 for (++j; j != fin; ++j)
1448 {
1449 if (crossingConnInfo.connsKnownToCross(*i, *j))
1450 {
1451 // We already know both these have crossings.
1452 continue;
1453 }
1454
1455 // Determine if this pair cross.
1456 Avoid::Polygon& jRoute = (*j)->routeRef();
1457 ConnectorCrossings cross(iRoute, true, jRoute, *i, *j);
1458 for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
1459 {
1460 const bool finalSegment = ((jInd + 1) == jRoute.size());
1461 cross.countForSegment(jInd, finalSegment);
1462
1463 if ((shared_path_penalty > 0) &&
1464 (cross.crossingFlags & CROSSING_SHARES_PATH) &&
1465 (cross.crossingFlags & CROSSING_SHARES_FIXED_SEGMENT) &&
1466 (m_routing_options[penaliseOrthogonalSharedPathsAtConnEnds] ||
1467 !(cross.crossingFlags & CROSSING_SHARES_PATH_AT_END)))
1468 {
1469 // We are penalising fixedSharedPaths and there is a
1470 // fixedSharedPath.
1471 crossingConnInfo.addCrossing(*i, *j);
1472 break;
1473 }
1474 else if ((crossing_penalty > 0) && (cross.crossingCount > 0))
1475 {
1476 // We are penalising crossings and this is a crossing.
1477 crossingConnInfo.addCrossing(*i, *j);
1478 break;
1479 }
1480 }
1481 }
1482 }
1483
1484 // Find the list of connector sets that need to be removed to avoid any
1485 // crossings in all crossing groups. This is our candidate set for
1486 // rerouting. Where these connectors connect to exlusive pins, all
1487 // connectors attached to exclusive pins with the same IDs will also
1488 // be rerouted, starting with the shortest.
1489 ConnCostRefSetList crossingConnsGroups =
1490 crossingConnInfo.crossingSetsListToRemoveCrossingsFromGroups();
1491
1492 // At this point we have a list containing crossings for rerouting.
1493 // We do this rerouting via two passes, for each group of interacting
1494 // crossing connectors:
1495 // 1) clear existing routes and free pin assignments, and
1496 // 2) compute new routes.
1497 unsigned int numOfConnsToReroute = 1;
1498 unsigned int numOfConnsRerouted = 1;
1499 for (ConnCostRefSetList::iterator setIt = crossingConnsGroups.begin();
1500 setIt != crossingConnsGroups.end(); ++setIt)
1501 {
1502 // Sort the connectors we will be rerouting from lowest to
1503 // highest cost.
1504 ConnCostRefList orderedConnList(setIt->begin(), setIt->end());
1505 orderedConnList.sort(CmpOrderedConnCostRef());
1506
1507 // Perform rerouting of this set of connectors.
1508 for (int pass = 0; pass < 2; ++pass)
1509 {
1510 for (ConnCostRefList::iterator connIt = orderedConnList.begin();
1511 connIt != orderedConnList.end(); ++connIt)
1512 {
1513 ConnRef *conn = connIt->second;
1514 if (pass == 0)
1515 {
1516 ++numOfConnsToReroute;
1517
1518 // Mark the fixed shared path as being invalid.
1519 conn->makePathInvalid();
1520
1521 // Free the previous path, so it is not noticed by other
1522 // connectors during rerouting.
1523 conn->freeRoutes();
1524
1525 // Free pin assignments.
1526 conn->freeActivePins();
1527 }
1528 else if (pass == 1)
1529 {
1530 // Progress reporting and continuation check.
1531 performContinuationCheck(TransactionPhaseRerouteSearch,
1532 numOfConnsRerouted, numOfConnsToReroute);
1533 if (m_abort_transaction)
1534 {
1535 m_in_crossing_rerouting_stage = false;
1536 return;
1537 }
1538 ++numOfConnsRerouted;
1539
1540 // Recompute this path.
1541 conn->generatePath();
1542 }
1543 }
1544 }
1545 }
1546 m_in_crossing_rerouting_stage = false;
1547 }
1548
1549
newBlockingShape(const Polygon & poly,int pid)1550 void Router::newBlockingShape(const Polygon& poly, int pid)
1551 {
1552 // o Check all visibility edges to see if this one shape
1553 // blocks them.
1554 EdgeInf *finish = visGraph.end();
1555 for (EdgeInf *iter = visGraph.begin(); iter != finish ; )
1556 {
1557 EdgeInf *tmp = iter;
1558 iter = iter->lstNext;
1559
1560 if (tmp->getDist() != 0)
1561 {
1562 std::pair<VertID, VertID> ids(tmp->ids());
1563 VertID eID1 = ids.first;
1564 VertID eID2 = ids.second;
1565 std::pair<Point, Point> points(tmp->points());
1566 Point e1 = points.first;
1567 Point e2 = points.second;
1568 bool blocked = false;
1569
1570 bool countBorder = false;
1571 bool ep_in_poly1 = (eID1.isConnPt()) ?
1572 inPoly(poly, e1, countBorder) : false;
1573 bool ep_in_poly2 = (eID2.isConnPt()) ?
1574 inPoly(poly, e2, countBorder) : false;
1575 if (ep_in_poly1 || ep_in_poly2)
1576 {
1577 // Don't check edges that have a connector endpoint
1578 // and are inside the shape being added.
1579 continue;
1580 }
1581
1582 bool seenIntersectionAtEndpoint = false;
1583 for (size_t pt_i = 0; pt_i < poly.size(); ++pt_i)
1584 {
1585 size_t pt_n = (pt_i == (poly.size() - 1)) ? 0 : pt_i + 1;
1586 const Point& pi = poly.ps[pt_i];
1587 const Point& pn = poly.ps[pt_n];
1588 if (segmentShapeIntersect(e1, e2, pi, pn,
1589 seenIntersectionAtEndpoint))
1590 {
1591 blocked = true;
1592 break;
1593 }
1594 }
1595 if (blocked)
1596 {
1597 db_printf("\tRemoving newly blocked edge (by shape %3d)"
1598 "... \n\t\t", pid);
1599 tmp->alertConns();
1600 tmp->db_print();
1601 if (InvisibilityGrph)
1602 {
1603 tmp->addBlocker(pid);
1604 }
1605 else
1606 {
1607 delete tmp;
1608 }
1609 }
1610 }
1611 }
1612 }
1613
1614
checkAllBlockedEdges(int pid)1615 void Router::checkAllBlockedEdges(int pid)
1616 {
1617 COLA_ASSERT(InvisibilityGrph);
1618
1619 for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )
1620 {
1621 EdgeInf *tmp = iter;
1622 iter = iter->lstNext;
1623
1624 if (tmp->blocker() == -1)
1625 {
1626 tmp->alertConns();
1627 tmp->checkVis();
1628 }
1629 else if (tmp->blocker() == pid)
1630 {
1631 tmp->checkVis();
1632 }
1633 }
1634 }
1635
1636
checkAllMissingEdges(void)1637 void Router::checkAllMissingEdges(void)
1638 {
1639 COLA_ASSERT(!InvisibilityGrph);
1640
1641 VertInf *first = vertices.connsBegin();
1642
1643 VertInf *pend = vertices.end();
1644 for (VertInf *i = first; i != pend; i = i->lstNext)
1645 {
1646 VertID iID = i->id;
1647
1648 // Check remaining, earlier vertices
1649 for (VertInf *j = first ; j != i; j = j->lstNext)
1650 {
1651 VertID jID = j->id;
1652 if (iID.isConnPt() && !iID.isConnectionPin() &&
1653 (iID.objID != jID.objID))
1654 {
1655 // Don't keep visibility between edges of different conns
1656 continue;
1657 }
1658
1659 // See if the edge is already there?
1660 bool found = (EdgeInf::existingEdge(i, j) != nullptr);
1661
1662 if (!found)
1663 {
1664 // Didn't already exist, check.
1665 bool knownNew = true;
1666 EdgeInf::checkEdgeVisibility(i, j, knownNew);
1667 }
1668 }
1669 }
1670 }
1671
1672
generateContains(VertInf * pt)1673 void Router::generateContains(VertInf *pt)
1674 {
1675 contains[pt->id].clear();
1676 enclosingClusters[pt->id].clear();
1677
1678 // Don't count points on the border as being inside.
1679 bool countBorder = false;
1680
1681 // Compute enclosing shapes.
1682 ObstacleList::const_iterator finish = m_obstacles.end();
1683 for (ObstacleList::const_iterator i = m_obstacles.begin(); i != finish; ++i)
1684 {
1685 if (inPoly((*i)->routingPolygon(), pt->point, countBorder))
1686 {
1687 contains[pt->id].insert((*i)->id());
1688 }
1689 }
1690
1691 // Computer enclosing Clusters
1692 ClusterRefList::const_iterator clFinish = clusterRefs.end();
1693 for (ClusterRefList::const_iterator i = clusterRefs.begin();
1694 i != clFinish; ++i)
1695 {
1696 if (inPolyGen((*i)->polygon(), pt->point))
1697 {
1698 enclosingClusters[pt->id].insert((*i)->id());
1699 }
1700 }
1701 }
1702
1703
adjustClustersWithAdd(const PolygonInterface & poly,const int p_cluster)1704 void Router::adjustClustersWithAdd(const PolygonInterface& poly,
1705 const int p_cluster)
1706 {
1707 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
1708 k = k->lstNext)
1709 {
1710 if (inPolyGen(poly, k->point))
1711 {
1712 enclosingClusters[k->id].insert(p_cluster);
1713 }
1714 }
1715 }
1716
1717
adjustClustersWithDel(const int p_cluster)1718 void Router::adjustClustersWithDel(const int p_cluster)
1719 {
1720 for (ContainsMap::iterator k = enclosingClusters.begin();
1721 k != enclosingClusters.end(); ++k)
1722 {
1723 (*k).second.erase(p_cluster);
1724 }
1725 }
1726
1727
adjustContainsWithAdd(const Polygon & poly,const int p_shape)1728 void Router::adjustContainsWithAdd(const Polygon& poly, const int p_shape)
1729 {
1730 // Don't count points on the border as being inside.
1731 bool countBorder = false;
1732
1733 for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();
1734 k = k->lstNext)
1735 {
1736 if (inPoly(poly, k->point, countBorder))
1737 {
1738 contains[k->id].insert(p_shape);
1739 }
1740 }
1741 }
1742
1743
adjustContainsWithDel(const int p_shape)1744 void Router::adjustContainsWithDel(const int p_shape)
1745 {
1746 for (ContainsMap::iterator k = contains.begin(); k != contains.end(); ++k)
1747 {
1748 (*k).second.erase(p_shape);
1749 }
1750 }
1751
1752
1753 #ifdef SELECTIVE_DEBUG
AngleAFromThreeSides(const double a,const double b,const double c)1754 static double AngleAFromThreeSides(const double a, const double b,
1755 const double c)
1756 {
1757 // returns angle A, the angle opposite from side a, in radians
1758 return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));
1759 }
1760 #endif
1761
1762 // Given an deleted obstacle, uses a simple heauristic to determine polyline
1763 // connectors that may now have a better path through the region occupied by
1764 // the shape and mark them as needing to be rerouted.
1765 // See the "Incremental Connector Routing" paper which explains this code.
1766 //
markPolylineConnectorsNeedingReroutingForDeletedObstacle(Obstacle * obstacle)1767 void Router::markPolylineConnectorsNeedingReroutingForDeletedObstacle(
1768 Obstacle *obstacle)
1769 {
1770 if (RubberBandRouting)
1771 {
1772 // When rubber-band routing, we do not reroute connectors that
1773 // may have a better route, only invalid connectors.
1774 return;
1775 }
1776
1777 COLA_ASSERT(SelectiveReroute);
1778
1779 // For each connector...
1780 ConnRefList::const_iterator end = connRefs.end();
1781 for (ConnRefList::const_iterator it = connRefs.begin(); it != end; ++it)
1782 {
1783 ConnRef *conn = (*it);
1784
1785 if (conn->m_route.empty())
1786 {
1787 // Ignore uninitialised connectors.
1788 continue;
1789 }
1790 else if (conn->m_needs_reroute_flag)
1791 {
1792 // Already marked, so skip.
1793 continue;
1794 }
1795 else if (conn->routingType() != ConnType_PolyLine)
1796 {
1797 // This test only works for polyline connectors, so skip others.
1798 continue;
1799 }
1800
1801 Point start = conn->m_route.ps[0];
1802 Point end = conn->m_route.ps[conn->m_route.size() - 1];
1803
1804 double conndist = conn->m_route_dist;
1805
1806 double estdist;
1807 double e1, e2;
1808
1809 // For each vertex of the obstacle...
1810 VertInf *beginV = obstacle->firstVert();
1811 VertInf *endV = obstacle->lastVert()->lstNext;
1812 for (VertInf *i = beginV; i != endV; i = i->lstNext)
1813 {
1814 const Point& p1 = i->point;
1815 const Point& p2 = i->shNext->point;
1816
1817 double offy;
1818 double a;
1819 double b;
1820 double c;
1821 double d;
1822
1823 double min;
1824 double max;
1825
1826 if (p1.y == p2.y)
1827 {
1828 // Standard case
1829 offy = p1.y;
1830 a = start.x;
1831 b = start.y - offy;
1832 c = end.x;
1833 d = end.y - offy;
1834
1835 min = std::min(p1.x, p2.x);
1836 max = std::max(p1.x, p2.x);
1837 }
1838 else if (p1.x == p2.x)
1839 {
1840 // Other Standard case
1841 offy = p1.x;
1842 a = start.y;
1843 b = start.x - offy;
1844 c = end.y;
1845 d = end.x - offy;
1846
1847 min = std::min(p1.y, p2.y);
1848 max = std::max(p1.y, p2.y);
1849 }
1850 else
1851 {
1852 // Need to do rotation
1853 Point n_p2(p2.x - p1.x, p2.y - p1.y);
1854 Point n_start(start.x - p1.x, start.y - p1.y);
1855 Point n_end(end.x - p1.x, end.y - p1.y);
1856 //db_printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);
1857 //db_printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);
1858 //db_printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);
1859
1860 double theta = 0 - atan2(n_p2.y, n_p2.x);
1861 //db_printf("theta = %.2f\n", theta * (180 / PI));
1862
1863 Point r_p1(0, 0);
1864 Point r_p2 = n_p2;
1865 start = n_start;
1866 end = n_end;
1867
1868 double cosv = cos(theta);
1869 double sinv = sin(theta);
1870
1871 r_p2.x = cosv * n_p2.x - sinv * n_p2.y;
1872 r_p2.y = cosv * n_p2.y + sinv * n_p2.x;
1873 start.x = cosv * n_start.x - sinv * n_start.y;
1874 start.y = cosv * n_start.y + sinv * n_start.x;
1875 end.x = cosv * n_end.x - sinv * n_end.y;
1876 end.y = cosv * n_end.y + sinv * n_end.x;
1877 //db_printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);
1878 //db_printf("r_start: (%.1f, %.1f)\n", start.x, start.y);
1879 //db_printf("r_end: (%.1f, %.1f)\n", end.x, end.y);
1880
1881 // This might be slightly off.
1882 if (fabs(r_p2.y) > 0.0001)
1883 {
1884 db_printf("r_p2.y: %f != 0\n", r_p2.y);
1885 }
1886 r_p2.y = 0;
1887
1888 offy = r_p1.y;
1889 a = start.x;
1890 b = start.y - offy;
1891 c = end.x;
1892 d = end.y - offy;
1893
1894 min = std::min(r_p1.x, r_p2.x);
1895 max = std::max(r_p1.x, r_p2.x);
1896
1897 }
1898
1899 double x;
1900 if ((b + d) == 0)
1901 {
1902 db_printf("WARNING: (b + d) == 0\n");
1903 d = d * -1;
1904 }
1905
1906 if ((b == 0) && (d == 0))
1907 {
1908 db_printf("WARNING: b == d == 0\n");
1909 if (((a < min) && (c < min)) ||
1910 ((a > max) && (c > max)))
1911 {
1912 // It's going to get adjusted.
1913 x = a;
1914 }
1915 else
1916 {
1917 continue;
1918 }
1919 }
1920 else
1921 {
1922 x = ((b*c) + (a*d)) / (b + d);
1923 }
1924
1925 //db_printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);
1926 //db_printf("x = %.1f\n", x);
1927
1928 x = std::max(min, x);
1929 x = std::min(max, x);
1930
1931 //db_printf("x = %.1f\n", x);
1932
1933 Point xp;
1934 if (p1.x == p2.x)
1935 {
1936 xp.x = offy;
1937 xp.y = x;
1938 }
1939 else
1940 {
1941 xp.x = x;
1942 xp.y = offy;
1943 }
1944 //db_printf("(%.1f, %.1f)\n", xp.x, xp.y);
1945
1946 e1 = euclideanDist(start, xp);
1947 e2 = euclideanDist(xp, end);
1948 estdist = e1 + e2;
1949
1950
1951 //db_printf("is %.1f < %.1f\n", estdist, conndist);
1952 if (estdist < conndist)
1953 {
1954 #ifdef SELECTIVE_DEBUG
1955 //double angle = AngleAFromThreeSides(dist(start, end),
1956 // e1, e2);
1957 db_printf("[%3d] - Possible better path found (%.1f < %.1f)\n",
1958 conn->_id, estdist, conndist);
1959 #endif
1960 conn->m_needs_reroute_flag = true;
1961 break;
1962 }
1963
1964 }
1965 }
1966 }
1967
1968
validConnType(const ConnType select) const1969 ConnType Router::validConnType(const ConnType select) const
1970 {
1971 if (select != ConnType_None)
1972 {
1973 if ((select == ConnType_Orthogonal) && m_allows_orthogonal_routing)
1974 {
1975 return ConnType_Orthogonal;
1976 }
1977 else if ((select == ConnType_PolyLine) && m_allows_polyline_routing)
1978 {
1979 return ConnType_PolyLine;
1980 }
1981 }
1982
1983 if (m_allows_polyline_routing)
1984 {
1985 return ConnType_PolyLine;
1986 }
1987 else if (m_allows_orthogonal_routing)
1988 {
1989 return ConnType_Orthogonal;
1990 }
1991 return ConnType_None;
1992 }
1993
1994
setRoutingParameter(const RoutingParameter parameter,const double value)1995 void Router::setRoutingParameter(const RoutingParameter parameter,
1996 const double value)
1997 {
1998 COLA_ASSERT(parameter < lastRoutingParameterMarker);
1999 if (value < 0)
2000 {
2001 // Set some sensible parameter value for the parameter being 'active'.
2002 switch (parameter)
2003 {
2004 case segmentPenalty:
2005 m_routing_parameters[parameter] = 50;
2006 break;
2007 case fixedSharedPathPenalty:
2008 m_routing_parameters[parameter] = 110;
2009 break;
2010 case anglePenalty:
2011 m_routing_parameters[parameter] = 50;
2012 break;
2013 case crossingPenalty:
2014 m_routing_parameters[parameter] = 200;
2015 break;
2016 case clusterCrossingPenalty:
2017 m_routing_parameters[parameter] = 4000;
2018 break;
2019 case idealNudgingDistance:
2020 m_routing_parameters[parameter] = 4.0;
2021 break;
2022 case portDirectionPenalty:
2023 m_routing_parameters[parameter] = 100;
2024 break;
2025 default:
2026 m_routing_parameters[parameter] = 50;
2027 break;
2028 }
2029 }
2030 else
2031 {
2032 m_routing_parameters[parameter] = value;
2033 }
2034 m_settings_changes = true;
2035 }
2036
2037
routingParameter(const RoutingParameter parameter) const2038 double Router::routingParameter(const RoutingParameter parameter) const
2039 {
2040 COLA_ASSERT(parameter < lastRoutingParameterMarker);
2041 return m_routing_parameters[parameter];
2042 }
2043
2044
setRoutingOption(const RoutingOption option,const bool value)2045 void Router::setRoutingOption(const RoutingOption option, const bool value)
2046 {
2047 COLA_ASSERT(option < lastRoutingOptionMarker);
2048 m_routing_options[option] = value;
2049 m_settings_changes = true;
2050 }
2051
2052
routingOption(const RoutingOption option) const2053 bool Router::routingOption(const RoutingOption option) const
2054 {
2055 COLA_ASSERT(option < lastRoutingOptionMarker);
2056 return m_routing_options[option];
2057 }
2058
2059
setRoutingPenalty(const RoutingParameter penType,const double penValue)2060 void Router::setRoutingPenalty(const RoutingParameter penType,
2061 const double penValue)
2062 {
2063 setRoutingParameter(penType, penValue);
2064 }
2065
registerSettingsChange(void)2066 void Router::registerSettingsChange(void)
2067 {
2068 m_settings_changes = true;
2069 }
2070
hyperedgeRerouter(void)2071 HyperedgeRerouter *Router::hyperedgeRerouter(void)
2072 {
2073 return &m_hyperedge_rerouter;
2074 }
2075
2076
isInCrossingPenaltyReroutingStage(void) const2077 bool Router::isInCrossingPenaltyReroutingStage(void) const
2078 {
2079 return m_in_crossing_rerouting_stage;
2080 }
2081
2082
printInfo(void)2083 void Router::printInfo(void)
2084 {
2085 FILE *fp = stdout;
2086 fprintf(fp, "\nVisibility Graph info:\n");
2087 fprintf(fp, "----------------------\n");
2088
2089 unsigned int currshape = 0;
2090 int st_shapes = 0;
2091 int st_vertices = 0;
2092 int st_endpoints = 0;
2093 int st_valid_shape_visedges = 0;
2094 int st_valid_endpt_visedges = 0;
2095 int st_orthogonal_visedges = 0;
2096 int st_invalid_visedges = 0;
2097 VertInf *finish = vertices.end();
2098 for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)
2099 {
2100 VertID pID = t->id;
2101
2102 if (!(pID.isConnPt()) && (pID.objID != currshape))
2103 {
2104 currshape = pID.objID;
2105 st_shapes++;
2106 }
2107 if (!(pID.isConnPt()))
2108 {
2109 st_vertices++;
2110 }
2111 else
2112 {
2113 // The shape 0 ones are temporary and not considered.
2114 st_endpoints++;
2115 }
2116 }
2117 for (EdgeInf *t = visGraph.begin(); t != visGraph.end();
2118 t = t->lstNext)
2119 {
2120 std::pair<VertID, VertID> idpair = t->ids();
2121
2122 if (idpair.first.isConnPt() || idpair.second.isConnPt())
2123 {
2124 st_valid_endpt_visedges++;
2125 }
2126 else
2127 {
2128 st_valid_shape_visedges++;
2129 }
2130 }
2131 for (EdgeInf *t = invisGraph.begin(); t != invisGraph.end();
2132 t = t->lstNext)
2133 {
2134 st_invalid_visedges++;
2135 }
2136 for (EdgeInf *t = visOrthogGraph.begin(); t != visOrthogGraph.end();
2137 t = t->lstNext)
2138 {
2139 st_orthogonal_visedges++;
2140 }
2141 fprintf(fp, "Number of shapes: %d\n", st_shapes);
2142 fprintf(fp, "Number of vertices: %d (%d real, %d endpoints)\n",
2143 st_vertices + st_endpoints, st_vertices, st_endpoints);
2144 fprintf(fp, "Number of orthog_vis_edges: %d\n", st_orthogonal_visedges);
2145 fprintf(fp, "Number of vis_edges: %d (%d valid [%d normal, %d endpt], "
2146 "%d invalid)\n", st_valid_shape_visedges + st_invalid_visedges +
2147 st_valid_endpt_visedges, st_valid_shape_visedges +
2148 st_valid_endpt_visedges, st_valid_shape_visedges,
2149 st_valid_endpt_visedges, st_invalid_visedges);
2150 fprintf(fp, "----------------------\n");
2151 fprintf(fp, "checkVisEdge tally: %d\n", st_checked_edges);
2152 fprintf(fp, "----------------------\n");
2153
2154 #ifdef AVOID_PROFILE
2155 timers.printAll(fp);
2156 timers.reset();
2157 #endif
2158 }
2159
2160
2161 static const double LIMIT = 100000000;
2162
reduceRange(double & val)2163 static void reduceRange(double& val)
2164 {
2165 val = std::min(val, LIMIT);
2166 val = std::max(val, -LIMIT);
2167 }
2168
2169
2170 //=============================================================================
2171 // The following methods are for testing and debugging.
2172
2173
existsOrthogonalSegmentOverlap(const bool atEnds)2174 bool Router::existsOrthogonalSegmentOverlap(const bool atEnds)
2175 {
2176 ConnRefList::iterator fin = connRefs.end();
2177 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
2178 {
2179 Avoid::Polygon iRoute = (*i)->displayRoute();
2180 ConnRefList::iterator j = i;
2181 for (++j; j != fin; ++j)
2182 {
2183 // Determine if this pair overlap
2184 Avoid::Polygon jRoute = (*j)->displayRoute();
2185 ConnectorCrossings cross(iRoute, true, jRoute, *i, *j);
2186 cross.checkForBranchingSegments = true;
2187 for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
2188 {
2189 const bool finalSegment = ((jInd + 1) == jRoute.size());
2190 cross.countForSegment(jInd, finalSegment);
2191
2192 if ((cross.crossingFlags & CROSSING_SHARES_PATH) &&
2193 (atEnds ||
2194 !(cross.crossingFlags & CROSSING_SHARES_PATH_AT_END)))
2195 {
2196 // We are looking for fixedSharedPaths and there is a
2197 // fixedSharedPath.
2198 return true;
2199 }
2200 }
2201 }
2202 }
2203 return false;
2204 }
2205
2206
existsOrthogonalFixedSegmentOverlap(const bool atEnds)2207 bool Router::existsOrthogonalFixedSegmentOverlap(const bool atEnds)
2208 {
2209 ConnRefList::iterator fin = connRefs.end();
2210 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
2211 {
2212 Avoid::Polygon iRoute = (*i)->displayRoute();
2213 ConnRefList::iterator j = i;
2214 for (++j; j != fin; ++j)
2215 {
2216 // Determine if this pair overlap
2217 Avoid::Polygon jRoute = (*j)->displayRoute();
2218 ConnectorCrossings cross(iRoute, true, jRoute, *i, *j);
2219 cross.checkForBranchingSegments = true;
2220 for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
2221 {
2222 const bool finalSegment = ((jInd + 1) == jRoute.size());
2223 cross.countForSegment(jInd, finalSegment);
2224
2225 if ((cross.crossingFlags & CROSSING_SHARES_PATH) &&
2226 (cross.crossingFlags & CROSSING_SHARES_FIXED_SEGMENT) &&
2227 (atEnds ||
2228 !(cross.crossingFlags & CROSSING_SHARES_PATH_AT_END)))
2229 {
2230 // We are looking for fixedSharedPaths and there is a
2231 // fixedSharedPath.
2232 return true;
2233 }
2234 }
2235 }
2236 }
2237 return false;
2238 }
2239
2240
existsOrthogonalTouchingPaths(void)2241 bool Router::existsOrthogonalTouchingPaths(void)
2242 {
2243 ConnRefList::iterator fin = connRefs.end();
2244 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
2245 {
2246 Avoid::Polygon iRoute = (*i)->displayRoute();
2247 ConnRefList::iterator j = i;
2248 for (++j; j != fin; ++j)
2249 {
2250 // Determine if this pair overlap
2251 Avoid::Polygon jRoute = (*j)->displayRoute();
2252 ConnectorCrossings cross(iRoute, true, jRoute, *i, *j);
2253 cross.checkForBranchingSegments = true;
2254 for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
2255 {
2256 const bool finalSegment = ((jInd + 1) == jRoute.size());
2257 cross.countForSegment(jInd, finalSegment);
2258
2259 if (cross.crossingFlags & CROSSING_TOUCHES)
2260 {
2261 return true;
2262 }
2263 }
2264 }
2265 }
2266 return false;
2267 }
2268
2269
2270 // Counts the number of crossings between all connectors.
2271 //
2272 // If optimisedForConnectorType is set, This will only count crossings
2273 // between orthogonal connectors if they appear at segment endpoints.
2274 // Thus, it can be used on raw connectors but not on simplified orthogonal
2275 // connectors.
2276 //
existsCrossings(const bool optimisedForConnectorType)2277 int Router::existsCrossings(const bool optimisedForConnectorType)
2278 {
2279 int count = 0;
2280 ConnRefList::iterator fin = connRefs.end();
2281 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
2282 {
2283 Avoid::Polygon iRoute = (*i)->displayRoute();
2284 ConnRefList::iterator j = i;
2285 for (++j; j != fin; ++j)
2286 {
2287 // Determine if this pair overlap
2288 Avoid::Polygon jRoute = (*j)->displayRoute();
2289 ConnRef *iConn = (optimisedForConnectorType) ? *i : nullptr;
2290 ConnRef *jConn = (optimisedForConnectorType) ? *j : nullptr;
2291 ConnectorCrossings cross(iRoute, true, jRoute, iConn, jConn);
2292 cross.checkForBranchingSegments = true;
2293 for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)
2294 {
2295 const bool finalSegment = ((jInd + 1) == jRoute.size());
2296
2297 // Normal crossings aren't counted if we pass the pointers
2298 // for the connectors, so don't pass them.
2299 cross.countForSegment(jInd, finalSegment);
2300
2301 count += cross.crossingCount;
2302 }
2303 }
2304 }
2305 return count;
2306 }
2307
2308 // Looks for non-orthogonal segments in orthogonal connectors and
2309 // returns true if it finds any.
existsInvalidOrthogonalPaths(void)2310 bool Router::existsInvalidOrthogonalPaths(void)
2311 {
2312 // For each connector...
2313 ConnRefList::iterator fin = connRefs.end();
2314 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)
2315 {
2316 // If it is an orthogonal connector...
2317 if ((*i)->routingType() == Avoid::ConnType_Orthogonal)
2318 {
2319 // Check each segment of the path...
2320 Avoid::Polygon iRoute = (*i)->displayRoute();
2321 for (size_t iInd = 1; iInd < iRoute.size(); ++iInd)
2322 {
2323 // And if it isn't either vertical or horizontal...
2324 if ( (iRoute.at(iInd - 1).x != iRoute.at(iInd).x) &&
2325 (iRoute.at(iInd - 1).y != iRoute.at(iInd).y) )
2326 {
2327 // Then we've found an invalid path.
2328 return true;
2329 }
2330 }
2331 }
2332 }
2333 return false;
2334 }
2335
2336
setTopologyAddon(TopologyAddonInterface * topologyAddon)2337 void Router::setTopologyAddon(TopologyAddonInterface *topologyAddon)
2338 {
2339 COLA_ASSERT(m_topology_addon);
2340 delete m_topology_addon;
2341 if (topologyAddon)
2342 {
2343 m_topology_addon = topologyAddon->clone();
2344 }
2345 else
2346 {
2347 m_topology_addon = new TopologyAddonInterface();
2348 }
2349 registerSettingsChange();
2350 }
2351
improveOrthogonalTopology(void)2352 void Router::improveOrthogonalTopology(void)
2353 {
2354 COLA_ASSERT(m_topology_addon);
2355 m_topology_addon->improveOrthogonalTopology(this);
2356 }
2357
outputInstanceToSVG(std::string instanceName)2358 void Router::outputInstanceToSVG(std::string instanceName)
2359 {
2360 std::string filename;
2361 if (!instanceName.empty())
2362 {
2363 filename = instanceName;
2364 }
2365 else
2366 {
2367 filename = "libavoid-debug";
2368 }
2369 filename += ".svg";
2370 FILE *fp = fopen(filename.c_str(), "w");
2371
2372 if (fp == nullptr)
2373 {
2374 return;
2375 }
2376
2377 double minX = LIMIT;
2378 double minY = LIMIT;
2379 double maxX = -LIMIT;
2380 double maxY = -LIMIT;
2381
2382 VertInf *curr = vertices.connsBegin();
2383 while (curr)
2384 {
2385 Point p = curr->point;
2386
2387 reduceRange(p.x);
2388 reduceRange(p.y);
2389
2390 if (p.x > -LIMIT)
2391 {
2392 minX = std::min(minX, p.x);
2393 }
2394 if (p.x < LIMIT)
2395 {
2396 maxX = std::max(maxX, p.x);
2397 }
2398 if (p.y > -LIMIT)
2399 {
2400 minY = std::min(minY, p.y);
2401 }
2402 if (p.y < LIMIT)
2403 {
2404 maxY = std::max(maxY, p.y);
2405 }
2406 curr = curr->lstNext;
2407 }
2408 minX -= 8;
2409 minY -= 8;
2410 maxX += 8;
2411 maxY += 8;
2412
2413 fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
2414 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);
2415
2416 // Output source code to generate this instance of the router.
2417 fprintf(fp, "<!-- Source code to generate this instance:\n");
2418 fprintf(fp, "#include \"libavoid/libavoid.h\"\n");
2419 if (m_topology_addon->outputCode(nullptr))
2420 {
2421 fprintf(fp, "#include \"libcola/cola.h\"\n");
2422 fprintf(fp, "#include \"libtopology/orthogonal_topology.h\"\n");
2423 fprintf(fp, "using namespace cola;\n");
2424 }
2425 fprintf(fp, "using namespace Avoid;\n");
2426 fprintf(fp, "int main(void) {\n");
2427 fprintf(fp, " Router *router = new Router(");
2428 if (m_allows_polyline_routing)
2429 {
2430 fprintf(fp, "PolyLineRouting");
2431 }
2432 if (m_allows_polyline_routing && m_allows_orthogonal_routing)
2433 {
2434 fprintf(fp, " | ");
2435 }
2436 if (m_allows_orthogonal_routing)
2437 {
2438 fprintf(fp, "OrthogonalRouting");
2439 }
2440 fprintf(fp, ");\n");
2441 for (size_t p = 0; p < lastRoutingParameterMarker; ++p)
2442 {
2443 fprintf(fp, " router->setRoutingParameter((RoutingParameter)%lu, %g);\n",
2444 (unsigned long)p, m_routing_parameters[p]);
2445 }
2446 for (size_t p = 0; p < lastRoutingOptionMarker; ++p)
2447 {
2448 fprintf(fp, " router->setRoutingOption((RoutingOption)%lu, %s);\n",
2449 (unsigned long)p, (m_routing_options[p]) ? "true" : "false");
2450 }
2451 fprintf(fp, " Polygon polygon;\n");
2452 fprintf(fp, " ConnRef *connRef = nullptr;\n");
2453 fprintf(fp, " ConnEnd srcPt;\n");
2454 fprintf(fp, " ConnEnd dstPt;\n");
2455 fprintf(fp, " ConnEnd heConnPt;\n");
2456 fprintf(fp, " PolyLine newRoute;\n");
2457 fprintf(fp, " ShapeConnectionPin *connPin = nullptr;\n");
2458 fprintf(fp, "\n");
2459 ClusterRefList::reverse_iterator revClusterRefIt = clusterRefs.rbegin();
2460 while (revClusterRefIt != clusterRefs.rend())
2461 {
2462 ClusterRef *cRef = *revClusterRefIt;
2463 fprintf(fp, " polygon = Polygon(%lu);\n",
2464 (unsigned long)cRef->polygon().size());
2465 for (size_t i = 0; i <cRef->polygon().size(); ++i)
2466 {
2467 fprintf(fp, " polygon.ps[%lu] = Point(%g, %g);\n",
2468 (unsigned long)i, cRef->polygon().at(i).x,
2469 cRef->polygon().at(i).y);
2470 }
2471 fprintf(fp, " new ClusterRef(router, polygon, %u);\n", cRef->id());
2472 ++revClusterRefIt;
2473 }
2474 ObstacleList::reverse_iterator revObstacleIt = m_obstacles.rbegin();
2475 while (revObstacleIt != m_obstacles.rend())
2476 {
2477 Obstacle *obstacle = *revObstacleIt;
2478 obstacle->outputCode(fp);
2479 ++revObstacleIt;
2480 }
2481 ConnRefList::reverse_iterator revConnRefIt = connRefs.rbegin();
2482 while (revConnRefIt != connRefs.rend())
2483 {
2484 ConnRef *connRef = *revConnRefIt;
2485 connRef->outputCode(fp);
2486 ++revConnRefIt;
2487 }
2488
2489 m_topology_addon->outputCode(fp);
2490
2491 fprintf(fp, " router->processTransaction();\n");
2492 fprintf(fp, " router->outputInstanceToSVG();\n");
2493
2494 m_topology_addon->outputDeletionCode(fp);
2495 fprintf(fp, " delete router;\n");
2496 fprintf(fp, " return 0;\n");
2497 fprintf(fp, "};\n");
2498 fprintf(fp, "-->\n");
2499
2500 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2501 "inkscape:label=\"Clusters\">\n");
2502 revClusterRefIt = clusterRefs.rbegin();
2503 while (revClusterRefIt != clusterRefs.rend())
2504 {
2505 ClusterRef *cRef = *revClusterRefIt;
2506 fprintf(fp, "<path id=\"cluster-%u\" style=\"stroke-width: 1px; "
2507 "stroke: black; fill: green; opacity: 0.1;\" d=\"",
2508 cRef->id());
2509 for (size_t i = 0; i < cRef->polygon().size(); ++i)
2510 {
2511 fprintf(fp, "%c %g %g ", ((i == 0) ? 'M' : 'L'),
2512 cRef->polygon().at(i).x, cRef->polygon().at(i).y);
2513 }
2514 fprintf(fp, "Z\" />\n");
2515
2516 fprintf(fp, "<path id=\"cluster-%u-rect\" style=\"stroke-width: 1px; "
2517 "stroke: black; fill: green; opacity: 0.1;\" d=\"",
2518 cRef->id());
2519 for (size_t i = 0; i < cRef->rectangularPolygon().size(); ++i)
2520 {
2521 fprintf(fp, "%c %g %g ", ((i == 0) ? 'M' : 'L'),
2522 cRef->rectangularPolygon().at(i).x,
2523 cRef->rectangularPolygon().at(i).y);
2524 }
2525 fprintf(fp, "Z\" />\n");
2526 ++revClusterRefIt;
2527 }
2528 fprintf(fp, "</g>\n");
2529
2530 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2531 "style=\"display: none;\" "
2532 "inkscape:label=\"ShapePolygons\">\n");
2533 ObstacleList::iterator obstacleIt = m_obstacles.begin();
2534 while (obstacleIt != m_obstacles.end())
2535 {
2536 Obstacle *obstacle = *obstacleIt;
2537 bool isShape = (nullptr != dynamic_cast<ShapeRef *> (obstacle));
2538
2539 if ( ! isShape )
2540 {
2541 // Don't output obstacles here, for now.
2542 ++obstacleIt;
2543 continue;
2544 }
2545
2546 fprintf(fp, "<path id=\"poly-%u\" style=\"stroke-width: 1px; "
2547 "stroke: black; fill: %s; fill-opacity: 0.3;\" d=\"",
2548 obstacle->id(), (isShape) ? "grey" : "red");
2549 for (size_t i = 0; i < obstacle->polygon().size(); ++i)
2550 {
2551 fprintf(fp, "%c %g %g ", ((i == 0) ? 'M' : 'L'),
2552 obstacle->polygon().at(i).x, obstacle->polygon().at(i).y);
2553 }
2554 fprintf(fp, "Z\" />\n");
2555 ++obstacleIt;
2556 }
2557 fprintf(fp, "</g>\n");
2558
2559 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2560 "style=\"display: none;\" "
2561 "inkscape:label=\"ObstaclePolygons\">\n");
2562 obstacleIt = m_obstacles.begin();
2563 while (obstacleIt != m_obstacles.end())
2564 {
2565 Obstacle *obstacle = *obstacleIt;
2566 bool isShape = (nullptr != dynamic_cast<ShapeRef *> (obstacle));
2567
2568 if ( ! isShape )
2569 {
2570 // Don't output obstacles here, for now.
2571 ++obstacleIt;
2572 continue;
2573 }
2574
2575 Polygon polygon = obstacle->routingPolygon();
2576 fprintf(fp, "<path id=\"poly-%u\" style=\"stroke-width: 1px; "
2577 "stroke: black; fill: %s; fill-opacity: 0.3;\" d=\"",
2578 obstacle->id(), (isShape) ? "grey" : "red");
2579 for (size_t i = 0; i < polygon.size(); ++i)
2580 {
2581 fprintf(fp, "%c %g %g ", ((i == 0) ? 'M' : 'L'),
2582 polygon.at(i).x, polygon.at(i).y);
2583 }
2584 fprintf(fp, "Z\" />\n");
2585 ++obstacleIt;
2586 }
2587 fprintf(fp, "</g>\n");
2588
2589 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2590 "style=\"display: none;\" "
2591 "inkscape:label=\"IdealJunctions\">\n");
2592 for (ObstacleList::iterator obstacleIt = m_obstacles.begin();
2593 obstacleIt != m_obstacles.end(); ++obstacleIt)
2594 {
2595 JunctionRef *junction = dynamic_cast<JunctionRef *> (*obstacleIt);
2596 if (junction)
2597 {
2598 fprintf(fp, "<circle id=\"idealJunction-%u\" cx=\"%g\" cy=\"%g\" "
2599 "r=\"8\" style=\"stroke: none; fill: %s; "
2600 "fill-opacity: 0.5;\" />\n", junction->id(),
2601 junction->recommendedPosition().x,
2602 junction->recommendedPosition().y, "green");
2603 }
2604
2605 }
2606 fprintf(fp, "</g>\n");
2607
2608 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2609 "inkscape:label=\"ObstacleRects\">\n");
2610 obstacleIt = m_obstacles.begin();
2611 while (obstacleIt != m_obstacles.end())
2612 {
2613 Obstacle *obstacle = *obstacleIt;
2614 bool isShape = (nullptr != dynamic_cast<ShapeRef *> (obstacle));
2615
2616 if ( ! isShape )
2617 {
2618 // Don't output obstacles here, for now.
2619 ++obstacleIt;
2620 continue;
2621 }
2622
2623 Box bBox = obstacle->routingBox();
2624
2625 fprintf(fp, "<rect id=\"rect-%u\" x=\"%g\" y=\"%g\" width=\"%g\" "
2626 "height=\"%g\" style=\"stroke-width: 1px; stroke: black; "
2627 "fill: grey; stroke-opacity: 0.1; fill-opacity: 0.1;\" />\n",
2628 obstacle->id(), bBox.min.x, bBox.min.y,
2629 bBox.max.x - bBox.min.x, bBox.max.y - bBox.min.y);
2630 ++obstacleIt;
2631 }
2632 fprintf(fp, "</g>\n");
2633
2634 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2635 "inkscape:label=\"VisGraph\""
2636 ">\n");
2637 EdgeInf *finish = nullptr;
2638 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2639 "style=\"display: none;\" "
2640 "inkscape:label=\"VisGraph-shape\""
2641 ">\n");
2642 finish = visGraph.end();
2643 for (EdgeInf *t = visGraph.begin(); t != finish; t = t->lstNext)
2644 {
2645 std::pair<VertID, VertID> ids = t->ids();
2646 bool isConn = ids.first.isConnPt() || ids.second.isConnPt();
2647 if (isConn)
2648 {
2649 continue;
2650 }
2651 std::pair<Point, Point> ptpair = t->points();
2652 Point p1 = ptpair.first;
2653 Point p2 = ptpair.second;
2654
2655 reduceRange(p1.x);
2656 reduceRange(p1.y);
2657 reduceRange(p2.x);
2658 reduceRange(p2.y);
2659
2660 fprintf(fp, "<path d=\"M %g %g L %g %g\" "
2661 "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
2662 p1.x, p1.y, p2.x, p2.y,
2663 (ids.first.isConnPt() || ids.second.isConnPt()) ? "blue" :
2664 "red");
2665 }
2666 fprintf(fp, "</g>\n");
2667 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2668 "style=\"display: none;\" "
2669 "inkscape:label=\"VisGraph-conn\""
2670 ">\n");
2671 finish = visGraph.end();
2672 for (EdgeInf *t = visGraph.begin(); t != finish; t = t->lstNext)
2673 {
2674 std::pair<VertID, VertID> ids = t->ids();
2675 bool isConn = ids.first.isConnPt() || ids.second.isConnPt();
2676 if (!isConn)
2677 {
2678 continue;
2679 }
2680 std::pair<Point, Point> ptpair = t->points();
2681 Point p1 = ptpair.first;
2682 Point p2 = ptpair.second;
2683
2684 reduceRange(p1.x);
2685 reduceRange(p1.y);
2686 reduceRange(p2.x);
2687 reduceRange(p2.y);
2688
2689 fprintf(fp, "<path d=\"M %g %g L %g %g\" "
2690 "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
2691 p1.x, p1.y, p2.x, p2.y,
2692 (ids.first.isConnPt() || ids.second.isConnPt()) ? "blue" :
2693 "red");
2694 }
2695 fprintf(fp, "</g>\n");
2696 fprintf(fp, "</g>\n");
2697
2698 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2699 "style=\"display: none;\" "
2700 "inkscape:label=\"OrthogVisGraph\">\n");
2701 finish = visOrthogGraph.end();
2702 for (EdgeInf *t = visOrthogGraph.begin(); t != finish; t = t->lstNext)
2703 {
2704 std::pair<Point, Point> ptpair = t->points();
2705 Point p1 = ptpair.first;
2706 Point p2 = ptpair.second;
2707
2708 reduceRange(p1.x);
2709 reduceRange(p1.y);
2710 reduceRange(p2.x);
2711 reduceRange(p2.y);
2712
2713 std::pair<VertID, VertID> ids = t->ids();
2714
2715 fprintf(fp, "<path d=\"M %g %g L %g %g\" "
2716 "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n",
2717 p1.x, p1.y, p2.x, p2.y,
2718 (ids.first.isConnPt() || ids.second.isConnPt()) ? "green" :
2719 "red");
2720 }
2721 fprintf(fp, "</g>\n");
2722
2723 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2724 "style=\"display: none;\" "
2725 "inkscape:label=\"RawConnectors\""
2726 ">\n");
2727 ConnRefList::iterator connRefIt = connRefs.begin();
2728 while (connRefIt != connRefs.end())
2729 {
2730 ConnRef *connRef = *connRefIt;
2731
2732 PolyLine route = connRef->route();
2733 if (!route.empty())
2734 {
2735 fprintf(fp, "<path id=\"raw-%u\" d=\"M %g %g ", connRef->id(),
2736 route.ps[0].x, route.ps[0].y);
2737 for (size_t i = 1; i < route.size(); ++i)
2738 {
2739 fprintf(fp, "L %g %g ", route.ps[i].x, route.ps[i].y);
2740 }
2741 fprintf(fp, "\" ");
2742 if (connRef->src() && connRef->dst())
2743 {
2744 fprintf(fp, "debug=\"src: %d dst: %d\" ",
2745 connRef->src()->visDirections,
2746 connRef->dst()->visDirections);
2747 }
2748 fprintf(fp, "style=\"fill: none; stroke: black; "
2749 "stroke-width: 1px;\" />\n");
2750 }
2751
2752 ++connRefIt;
2753 }
2754 fprintf(fp, "</g>\n");
2755
2756 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2757 "style=\"display: none;\" "
2758 "inkscape:label=\"CurvedDisplayConnectors\""
2759 ">\n");
2760 connRefIt = connRefs.begin();
2761 while (connRefIt != connRefs.end())
2762 {
2763 ConnRef *connRef = *connRefIt;
2764
2765 PolyLine route = connRef->displayRoute().curvedPolyline(8);
2766 if (!route.empty())
2767 {
2768 fprintf(fp, "<path id=\"curved-%u\" d=\"M %g %g ", connRef->id(),
2769 route.ps[0].x, route.ps[0].y);
2770 for (size_t i = 1; i < route.size(); ++i)
2771 {
2772 if (route.ts[i] == 'C')
2773 {
2774 fprintf(fp, "%c %g %g %g %g %g %g", route.ts[i],
2775 route.ps[i].x, route.ps[i].y,
2776 route.ps[i+1].x, route.ps[i+1].y,
2777 route.ps[i+2].x, route.ps[i+2].y);
2778 i += 2;
2779 }
2780 else
2781 {
2782 fprintf(fp, "%c %g %g ", route.ts[i],
2783 route.ps[i].x, route.ps[i].y);
2784 }
2785 }
2786 fprintf(fp, "\" ");
2787 if (connRef->src() && connRef->dst())
2788 {
2789 fprintf(fp, "debug=\"src: %d dst: %d\" ",
2790 connRef->src()->visDirections,
2791 connRef->dst()->visDirections);
2792 }
2793 fprintf(fp, "style=\"fill: none; stroke: black; "
2794 "stroke-width: 1px;\" />\n");
2795 }
2796
2797 ++connRefIt;
2798 }
2799 fprintf(fp, "</g>\n");
2800
2801
2802 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2803 "inkscape:label=\"DisplayConnectors\""
2804 ">\n");
2805 connRefIt = connRefs.begin();
2806 while (connRefIt != connRefs.end())
2807 {
2808 ConnRef *connRef = *connRefIt;
2809
2810 PolyLine route = connRef->displayRoute();
2811 if (!route.empty())
2812 {
2813 fprintf(fp, "<path id=\"disp-%u\" d=\"M %g %g ", connRef->id(),
2814 route.ps[0].x, route.ps[0].y);
2815 for (size_t i = 1; i < route.size(); ++i)
2816 {
2817 fprintf(fp, "L %g %g ", route.ps[i].x, route.ps[i].y);
2818 }
2819 fprintf(fp, "\" ");
2820 if (connRef->src() && connRef->dst())
2821 {
2822 fprintf(fp, "debug=\"src: %d dst: %d\" ",
2823 connRef->src()->visDirections,
2824 connRef->dst()->visDirections);
2825 }
2826 fprintf(fp, "style=\"fill: none; stroke: black; "
2827 "stroke-width: 1px;\" />\n");
2828 }
2829
2830 ++connRefIt;
2831 }
2832 fprintf(fp, "</g>\n");
2833
2834 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2835 "inkscape:label=\"ConnectorCheckpoints\""
2836 ">\n");
2837 connRefIt = connRefs.begin();
2838 while (connRefIt != connRefs.end())
2839 {
2840 ConnRef *connRef = *connRefIt;
2841
2842 for (size_t i = 0; i < connRef->m_checkpoints.size(); ++i)
2843 {
2844 fprintf(fp, "<circle id=\"checkpoint-%u-%d\" cx=\"%g\" cy=\"%g\" "
2845 "r=\"8\" style=\"stroke: none; fill: red; "
2846 "fill-opacity: 0.25;\" />\n", connRef->id(), (int) i,
2847 connRef->m_checkpoints[i].point.x,
2848 connRef->m_checkpoints[i].point.y);
2849 }
2850
2851 ++connRefIt;
2852 }
2853 fprintf(fp, "</g>\n");
2854
2855
2856 fprintf(fp, "</svg>\n");
2857 fclose(fp);
2858 //printInfo();
2859 }
2860
outputDiagramSVG(std::string instanceName,LineReps * lineReps)2861 void Router::outputDiagramSVG(std::string instanceName, LineReps *lineReps)
2862 {
2863 std::string filename;
2864 if (!instanceName.empty())
2865 {
2866 filename = instanceName;
2867 }
2868 else
2869 {
2870 filename = "libavoid-diagram";
2871 }
2872 filename += ".svg";
2873 FILE *fp = fopen(filename.c_str(), "w");
2874
2875 if (fp == nullptr)
2876 {
2877 return;
2878 }
2879
2880 double minX = LIMIT;
2881 double minY = LIMIT;
2882 double maxX = -LIMIT;
2883 double maxY = -LIMIT;
2884
2885 VertInf *curr = vertices.connsBegin();
2886 while (curr)
2887 {
2888 Point p = curr->point;
2889
2890 reduceRange(p.x);
2891 reduceRange(p.y);
2892
2893 if (p.x > -LIMIT)
2894 {
2895 minX = std::min(minX, p.x);
2896 }
2897 if (p.x < LIMIT)
2898 {
2899 maxX = std::max(maxX, p.x);
2900 }
2901 if (p.y > -LIMIT)
2902 {
2903 minY = std::min(minY, p.y);
2904 }
2905 if (p.y < LIMIT)
2906 {
2907 maxY = std::max(maxY, p.y);
2908 }
2909 curr = curr->lstNext;
2910 }
2911 minX -= 8;
2912 minY -= 8;
2913 maxX += 8;
2914 maxY += 8;
2915
2916 fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n");
2917 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);
2918
2919 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2920 "inkscape:label=\"ShapesRect\">\n");
2921 ObstacleList::iterator obstacleIt = m_obstacles.begin();
2922 while (obstacleIt != m_obstacles.end())
2923 {
2924 Obstacle *obstacle = *obstacleIt;
2925 bool isShape = (nullptr != dynamic_cast<ShapeRef *> (obstacle));
2926
2927 if ( ! isShape )
2928 {
2929 // Don't output non-shape obstacles here, for now.
2930 ++obstacleIt;
2931 continue;
2932 }
2933
2934 Box bBox = obstacle->polygon().offsetBoundingBox(0.0);
2935
2936 fprintf(fp, "<rect id=\"rect-%u\" x=\"%g\" y=\"%g\" width=\"%g\" "
2937 "height=\"%g\" style=\"stroke-width: 1px; stroke: black; "
2938 "fill: grey; stroke-opacity: 0.5; fill-opacity: 0.4;\" />\n",
2939 obstacle->id(), bBox.min.x, bBox.min.y,
2940 bBox.max.x - bBox.min.x, bBox.max.y - bBox.min.y);
2941 ++obstacleIt;
2942 }
2943 fprintf(fp, "</g>\n");
2944
2945 fprintf(fp, "<g inkscape:groupmode=\"layer\" "
2946 "inkscape:label=\"DisplayConnectors\""
2947 ">\n");
2948 ConnRefList::iterator connRefIt = connRefs.begin();
2949 while (connRefIt != connRefs.end())
2950 {
2951 ConnRef *connRef = *connRefIt;
2952
2953 PolyLine route = connRef->displayRoute();
2954 if (!route.empty())
2955 {
2956 fprintf(fp, "<path id=\"disp-%u\" d=\"M %g %g ", connRef->id(),
2957 route.ps[0].x, route.ps[0].y);
2958 for (size_t i = 1; i < route.size(); ++i)
2959 {
2960 fprintf(fp, "L %g %g ", route.ps[i].x, route.ps[i].y);
2961 }
2962 fprintf(fp, "\" ");
2963 fprintf(fp, "style=\"fill: none; stroke: black; "
2964 "stroke-width: 1px;\" />\n");
2965
2966 /*
2967 for (size_t i = 1; i < route.size(); ++i)
2968 {
2969 if (route.segmentHasCheckpoint[i - 1])
2970 {
2971 fprintf(fp, "<path d=\"M %g %g ",
2972 route.ps[i - 1].x, route.ps[i - 1].y);
2973 fprintf(fp, "L %g %g\" ", route.ps[i].x, route.ps[i].y);
2974 fprintf(fp, "style=\"fill: none; stroke: red; "
2975 "stroke-width: 1px; stroke-opacity: 1;\" />\n");
2976 }
2977 }
2978 */
2979 }
2980
2981 ++connRefIt;
2982 }
2983 fprintf(fp, "</g>\n");
2984
2985 if (lineReps)
2986 {
2987
2988 for (LineReps::iterator it = lineReps->begin(); it != lineReps->end();
2989 ++it)
2990 {
2991 fprintf(fp, "<path d=\"M %g %g ",
2992 it->begin.x, it->begin.y);
2993 fprintf(fp, "L %g %g\" ", it->end.x, it->end.y);
2994 fprintf(fp, "style=\"fill: none; stroke: red; "
2995 "stroke-width: 1px; stroke-opacity: 0.7;\" />\n");
2996 }
2997 }
2998
2999 fprintf(fp, "</svg>\n");
3000 fclose(fp);
3001 }
3002
outputDiagram(std::string instanceName)3003 void Router::outputDiagram(std::string instanceName)
3004 {
3005 outputDiagramText(instanceName);
3006 #ifdef SVG_OUTPUT
3007 outputInstanceToSVG(instanceName);
3008 #endif
3009 }
3010
outputDiagramText(std::string instanceName)3011 void Router::outputDiagramText(std::string instanceName)
3012 {
3013 std::string filename;
3014 if (!instanceName.empty())
3015 {
3016 filename = instanceName;
3017 }
3018 else
3019 {
3020 filename = "libavoid-diagram";
3021 }
3022 filename += ".txt";
3023 FILE *fp = fopen(filename.c_str(), "w");
3024
3025 if (fp == nullptr)
3026 {
3027 return;
3028 }
3029
3030 ObstacleList::iterator obstacleIt = m_obstacles.begin();
3031 while (obstacleIt != m_obstacles.end())
3032 {
3033 Obstacle *obstacle = *obstacleIt;
3034 bool isShape = (nullptr != dynamic_cast<ShapeRef *> (obstacle));
3035
3036 if ( ! isShape )
3037 {
3038 // Don't output non-shape obstacles here, for now.
3039 ++obstacleIt;
3040 continue;
3041 }
3042
3043 Box bBox = obstacle->polygon().offsetBoundingBox(0.0);
3044
3045 fprintf(fp, "rect\n");
3046 fprintf(fp, "id=%u\n", obstacle->id());
3047 fprintf(fp, "x=%g\n", bBox.min.x);
3048 fprintf(fp, "y=%g\n", bBox.min.y);
3049 fprintf(fp, "width=%g\n", bBox.max.x - bBox.min.x);
3050 fprintf(fp, "height=%g\n", bBox.max.y - bBox.min.y);
3051 fprintf(fp, "\n");
3052
3053 ++obstacleIt;
3054 }
3055
3056 ConnRefList::iterator connRefIt = connRefs.begin();
3057 while (connRefIt != connRefs.end())
3058 {
3059 ConnRef *connRef = *connRefIt;
3060
3061 PolyLine route = connRef->displayRoute();
3062 if (!route.empty())
3063 {
3064 fprintf(fp, "path\n");
3065 fprintf(fp, "id=%u\n", connRef->id());
3066 for (size_t i = 0; i < route.size(); ++i)
3067 {
3068 fprintf(fp, "p%zu: %g %g ", i, route.ps[i].x, route.ps[i].y);
3069 fprintf(fp, "\n");
3070 }
3071 fprintf(fp, "\n");
3072 }
3073
3074 ++connRefIt;
3075 }
3076
3077 fprintf(fp, "\n");
3078
3079 fclose(fp);
3080 }
3081
3082 HyperedgeNewAndDeletedObjectLists
newAndDeletedObjectListsFromHyperedgeImprovement(void) const3083 Router::newAndDeletedObjectListsFromHyperedgeImprovement(void) const
3084 {
3085 return m_hyperedge_improver.newAndDeletedObjectLists();
3086 }
3087
3088
ConnRerouteFlagDelegate()3089 ConnRerouteFlagDelegate::ConnRerouteFlagDelegate()
3090 {
3091 }
3092
~ConnRerouteFlagDelegate()3093 ConnRerouteFlagDelegate::~ConnRerouteFlagDelegate()
3094 {
3095 }
3096
addConn(ConnRef * conn)3097 bool *ConnRerouteFlagDelegate::addConn(ConnRef *conn)
3098 {
3099 m_mapping.push_back(std::make_pair(conn, false));
3100 return &(m_mapping.back().second);
3101 }
3102
removeConn(ConnRef * conn)3103 void ConnRerouteFlagDelegate::removeConn(ConnRef *conn)
3104 {
3105 std::list<std::pair<ConnRef *, bool> >::iterator it;
3106 for (it = m_mapping.begin(); it != m_mapping.end(); ++it)
3107 {
3108 if (it->first == conn)
3109 {
3110 it->first = nullptr;
3111 }
3112 }
3113 }
3114
3115
alertConns(void)3116 void ConnRerouteFlagDelegate::alertConns(void)
3117 {
3118 std::list<std::pair<ConnRef *, bool> >::iterator it;
3119 for (it = m_mapping.begin(); it != m_mapping.end(); ++it)
3120 {
3121 if ((it->first != nullptr) && (it->second == true))
3122 {
3123 it->second = false;
3124 it->first->m_needs_reroute_flag = true;
3125 }
3126 }
3127 }
3128
3129
3130 }
3131
3132