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