root / src / layout / heapembedding.cc @ 8aeaaccc
History  View  Annotate  Download (5.73 KB)
1 
//=========================================================================


2 
// HEAPEMBEDDING.CC  part of

3 
// OMNeT++/OMNEST

4 
// Discrete System Simulation in C++

5 
//

6 
// Author: Levente Meszaros

7 
//

8 
//=========================================================================

9  
10 
/**

11 
Copyright (C) 20062008 OpenSim Ltd.

12 

13 
This file is distributed WITHOUT ANY WARRANTY. See the file

14 
`license' for details on this and other legal matters.

15 
**/

16  
17 
#include "heapembedding.h" 
18  
19 
USING_NAMESPACE 
20  
21 
HeapEmbedding::HeapEmbedding(GraphComponent *graphComponent, double vertexSpacing)

22 
{ 
23 
this>graphComponent = graphComponent;

24 
this>vertexSpacing = vertexSpacing;

25 
} 
26  
27 
void HeapEmbedding::embed()

28 
{ 
29 
std::vector<Rc> rcs; // rectangles of vertices already positioned

30 
std::vector<Pt> pts; // candidate points where vertices may be positioned

31 
pts.push_back(Pt::getZero()); 
32  
33 
// delete all vertex positions

34 
for (int i = 0; i < graphComponent>getVertexCount(); i++) 
35 
graphComponent>getVertex(i)>rc.pt = Pt::getNil(); 
36  
37 
// go through vertices in spanning tree order

38 
for (int i = 0; i < (int)graphComponent>spanningTreeVertices.size(); i++) { 
39 
Vertex *vertex = graphComponent>spanningTreeVertices[i]; 
40 
Rs rs = vertex>rc.rs; 
41  
42 
// find the best minimizing the distance cost function

43 
double bestDistance = POSITIVE_INFINITY;

44 
Rc bestRc; 
45  
46 
// for all candidate points

47 
for (int j = 0; j < (int)pts.size(); j++) { 
48 
Pt pt = pts[j]; 
49  
50 
// align vertex to candidate points with its various points

51 
for (int k = 0; k < 8; k++) { 
52 
Rc candidateRc; 
53 
Pt ptCopy(pt); 
54  
55 
switch (k) {

56 
case 0: 
57 
// candidate point is top left

58 
candidateRc = Rc(ptCopy.subtract(0, 0, 0), rs); 
59 
break;

60 
case 1: 
61 
// candidate point is top center

62 
candidateRc = Rc(ptCopy.subtract(rs.width / 2, 0, 0), rs); 
63 
break;

64 
case 2: 
65 
// candidate point is top right

66 
candidateRc = Rc(ptCopy.subtract(rs.width, 0, 0), rs); 
67 
break;

68 
case 3: 
69 
// candidate point is center left

70 
candidateRc = Rc(ptCopy.subtract(0, rs.height / 2, 0), rs); 
71 
break;

72 
case 4: 
73 
// candidate point is center right

74 
candidateRc = Rc(ptCopy.subtract(rs.width, rs.height / 2, 0), rs); 
75 
break;

76 
case 5: 
77 
// candidate point is bottom left

78 
candidateRc = Rc(ptCopy.subtract(0, rs.height, 0), rs); 
79 
break;

80 
case 6: 
81 
// candidate point is bottom center

82 
candidateRc = Rc(ptCopy.subtract(rs.width / 2, rs.height, 0), rs); 
83 
break;

84 
case 7: 
85 
// candidate point is bottom right

86 
candidateRc = Rc(ptCopy.subtract(rs.width, rs.height, 0), rs);

87 
break;

88 
} 
89  
90 
// find an already positioned vertex which would intersect the candidate rectangle

91 
bool intersects = false; 
92 
for (int l = 0; l < (int)rcs.size(); l++) { 
93 
Rc rc = rcs[l]; 
94 
if (candidateRc.basePlaneProjectionIntersects(rc, true)) { 
95 
intersects = true;

96 
break;

97 
} 
98 
} 
99 
// if found one then this is a wrong candidate

100 
if (intersects)

101 
continue;

102  
103 
// calculate the distance sum to neighbours already positioned

104 
double distance = 0; 
105 
for (int k = 0; k < (int)vertex>neighbours.size(); k++) { 
106 
Vertex *neighbour = vertex>neighbours[k]; 
107  
108 
if (!neighbour>rc.pt.isNil())

109 
distance += candidateRc.getCenterCenter().getDistance(neighbour>rc.getCenterCenter()); 
110 
} 
111  
112 
// if better than the current best

113 
if (distance < bestDistance)

114 
{ 
115 
bestRc = candidateRc; 
116 
bestDistance = distance; 
117 
} 
118 
} 
119 
} 
120  
121 
// store position and rectangle

122 
vertex>rc.pt = bestRc.pt; 
123  
124 
// grow rectangle

125 
bestRc.pt.x = vertexSpacing; 
126 
bestRc.pt.y = vertexSpacing; 
127 
bestRc.rs.width += 2 * vertexSpacing;

128 
bestRc.rs.height += 2 * vertexSpacing;

129  
130 
// delete candidate points covered by best rc

131 
for (int j = 0; j < (int)pts.size(); j++) { 
132 
Pt pt = pts[j]; 
133  
134 
if (bestRc.basePlaneProjectionContains(pt, true)) 
135 
pts.erase(pts.begin() + j); 
136 
} 
137  
138 
// push new candidates

139 
pushPtUnlessRcsContains(pts, rcs, bestRc.getCenterTop()); 
140 
pushPtUnlessRcsContains(pts, rcs, bestRc.getCenterBottom()); 
141 
pushPtUnlessRcsContains(pts, rcs, bestRc.getLeftCenter()); 
142 
pushPtUnlessRcsContains(pts, rcs, bestRc.getRightCenter()); 
143  
144 
rcs.push_back(bestRc); 
145 
} 
146 
} 
147  
148 
void HeapEmbedding::pushPtUnlessRcsContains(std::vector<Pt>& pts, const std::vector<Rc>& rcs, const Pt& pt) 
149 
{ 
150 
for (int j = 0; j < (int)rcs.size(); j++) { 
151 
Rc rc = rcs[j]; 
152  
153 
if (rc.basePlaneProjectionContains(pt, true)) 
154 
return;

155 
} 
156  
157 
pts.push_back(pt); 
158 
} 