1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
*
* Copyright (C) 2011-2014 Monash University
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
* See the file LICENSE.LGPL distributed with the library.
*
* Licensees holding a valid commercial license may use this file in
* accordance with the commercial license agreement provided with the
* library.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*
* Author(s): Michael Wybrow
*/
#ifndef AVOID_IMPROVEHYPEREDGES_H
#define AVOID_IMPROVEHYPEREDGES_H
#include <map>
#include <set>
#include <list>
namespace Avoid {
struct HyperedgeTreeNode;
struct HyperedgeTreeEdge;
class HyperedgeShiftSegment;
class ConnRef;
class JunctionRef;
class ShiftSegment;
class VertInf;
typedef std::list<ShiftSegment *> ShiftSegmentList;
typedef std::map<JunctionRef *, ShiftSegmentList> RootSegmentsMap;
typedef std::map<JunctionRef *, HyperedgeTreeNode *>
JunctionHyperedgeTreeNodeMap;
typedef std::set<JunctionRef *> JunctionSet;
typedef std::list<ConnRef *> ConnRefList;
typedef std::list<JunctionRef *> JunctionRefList;
class HyperedgeImprover
{
public:
// Constructor.
HyperedgeImprover();
void clear(void);
// Set the router that this HyperedgeImprover will act upon.
void setRouter(Router *router);
// Returns lists of junctions and connectors created and deleted during
// hyperedge improvement.
HyperedgeNewAndDeletedObjectLists newAndDeletedObjectLists(void) const;
// Execute local improvement process.
void execute(bool canMakeMajorChanges);
private:
// Helper method for buildHyperedgeSegments() for hyperedge tree nodes.
void createShiftSegmentsForDimensionExcluding(HyperedgeTreeNode *node,
const size_t dim, HyperedgeTreeEdge *ignore,
ShiftSegmentList& segments);
// Helper method for buildHyperedgeSegments() for hyperedge tree edges.
void createShiftSegmentsForDimensionExcluding(HyperedgeTreeEdge *edge,
const size_t dim, HyperedgeTreeNode *ignore,
ShiftSegmentList& segments);
// During creation and nudging of shift segments it is often necessary
// to merge collinear or overlapping segments. This method does the
// merging for these cases. Effectively merging is done by adding
// additional vertex pointers to the shift segment.
void mergeOverlappingSegments(ShiftSegmentList& segments);
// Given a hyperedge tree and a dimension, this method creates shift
// segments for all edges in that orientation. These segments are the
// objects on which the local improvement nudging operates, and they
// in turn make changes back to the hyperedge tree.
void buildHyperedgeSegments(const size_t dim);
// This method looks for and corrects situations where the middle section
// of a zigzag is optimised away by bringing the outside segments in line
// and leading to the middle segment being zero length. These zero length
// edges are removed.
void removeZeroLengthEdges(void);
// This method looks for and correct situations where multiple overlapping
// edges lead to a junction and one or more of these segments could be
// removed by moving the junction (and thus divergence point) along the
// edge.
void moveJunctionsAlongCommonEdges(void);
// Given a set of hyperedge shift segments in a particular dimension,
// with limits and balance values precomputed, this method shifts and
// merges segments to improve the overall cost (length + bend penalties)
// for the hyperedge.
void nudgeHyperedgeSegments(size_t dimension, unsigned int& versionNumber);
// Write the paths from an improved hyperedgetree object back as routes
// to the component connectors that form the hyperedge.
void writeHyperedgeSegmentsBackToConnPaths(void);
// Output the hyperedge tree to an SVG file, optionally highlighting
// a segment of interest (usually the segment being moved).
void outputHyperedgesToSVG(unsigned int pass,
HyperedgeShiftSegment *activeSegment = nullptr);
// Given a junction, this method follows the attached connectors and
// junctions to determine a hyperedge and returns the set of vertices
// representing its endpoints.
void getEndpoints(JunctionRef *junction, JunctionRef *ignore,
std::set<VertInf *>& endpoints);
// This method moves the junction at the given node along any shared paths
// (so long as this action would not create any additional shared paths),
// while also removing and freeing merged edges and nodes in the process.
// It returns the new node where the junction is now located.
HyperedgeTreeNode *moveJunctionAlongCommonEdge(HyperedgeTreeNode *self,
bool& nodeMapHasChanged);
// This method traverses the hyperedge tree removing zero length edges.
//
void removeZeroLengthEdges(HyperedgeTreeNode *self,
HyperedgeTreeEdge *ignored);
// This method traverses the hyperedge tree removing zero length edges.
//
void removeZeroLengthEdges(HyperedgeTreeEdge *self,
HyperedgeTreeNode *ignored);
Router *m_router;
JunctionHyperedgeTreeNodeMap m_hyperedge_tree_junctions;
JunctionSet m_hyperedge_tree_roots;
RootSegmentsMap m_root_shift_segments;
ShiftSegmentList m_all_shift_segments;
JunctionRefList m_new_junctions;
JunctionRefList m_deleted_junctions;
ConnRefList m_new_connectors;
ConnRefList m_deleted_connectors;
ConnRefList m_changed_connectors;
int m_debug_count;
bool m_can_make_major_changes;
};
}
#endif
|
