Project

General

Profile

Statistics
| Branch: | Revision:

root / src / layout / forcedirectedembedding.h @ 8aeaaccc

History | View | Annotate | Download (11.8 KB)

1 01873262 Georg Kunz
//=========================================================================
2
//  FORCEDIRECTEDEMBEDDING.H - part of
3
//                  OMNeT++/OMNEST
4
//           Discrete System Simulation in C++
5
//
6
//  Author: Levente Meszaros
7
//
8
//=========================================================================
9
10
/*--------------------------------------------------------------*
11
  Copyright (C) 2006-2008 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
#ifndef __FORCEDIRECTEDEMBEDDING_H
18
#define __FORCEDIRECTEDEMBEDDING_H
19
20
#include <algorithm>
21
#include <time.h>
22
#include <iostream>
23
#include "intxtypes.h"
24
#include "geometry.h"
25
#include "forcedirectedparametersbase.h"
26
27
NAMESPACE_BEGIN
28
29
class LAYOUT_API ForceDirectedEmbedding
30
{
31
    protected:
32
        /**
33
         * True means internal state for the layout has been initialized.
34
         * Initialization is not done during construction time,
35
         * but it is done not later than the first call to embed.
36
         */
37
        bool initialized;
38
39
        /**
40
         * True indicates that the embedding is complete, this state may be reset by calling reinitialize.
41
         */
42
        bool finished;
43
44
        /**
45
         * Total number of calculation cycles in the main loop since the last reinitialize call.
46
         */
47
        int cycle;
48
49
        /**
50
         * Total number of calculation probe cycles in the inner loop since the last reinitialize call.
51
         */
52
        int probCycle;
53
54
        /**
55
         * The total number of ticks spent on calculation since the last reinitialize call.
56
         */
57
        long elapsedTicks;
58
59
        /**
60
         * Total virtual calculation time since the last reinitialize call.
61
         */
62
        double elapsedTime;
63
64
        /**
65
         * Total kinetic energy seen in all cycles since the last reinitialize call.
66
         */
67
        double kineticEnergySum;
68
69
        /**
70
         * Total mass of bodies.
71
         */
72
        double totalMass;
73
74
        /**
75
         * Last calculated acceleration error.
76
         */
77
        double lastAccelerationError;
78
79
        /**
80
         * Last calculated maximum velocity.
81
         */
82
        double lastMaxVelocity;
83
84
        /**
85
         * Last calculated maximum acceleration.
86
         */
87
        double lastMaxAcceleration;
88
89
        // positions
90
        std::vector<Pt> pn;
91
        // accelerations
92
        std::vector<Pt> an;
93
        // velocities
94
        std::vector<Pt> vn;
95
        // acceleration approximations
96
        std::vector<Pt> a1;
97
        std::vector<Pt> a2;
98
        std::vector<Pt> a3;
99
        std::vector<Pt> a4;
100
        // velocity deltas
101
        std::vector<Pt> dvn;
102
        std::vector<Pt> tvn;
103
        // position deltas
104
        std::vector<Pt> dpn;
105
        std::vector<Pt> tpn;
106
107
        /**
108
         * The calculation will find a solution for these variables.
109
         * Members are destructed.
110
         */
111
        std::vector<Variable *> variables;
112
113
        /**
114
         * Used to generate forces in each cycle of the calculation.
115
         * Members are destructed.
116
         */
117
        std::vector<IForceProvider *> forceProviders;
118
119
        /**
120
         * The various bodies which are part of the calculation.
121
         * Members are destructed.
122
         */
123
        std::vector<IBody *> bodies;
124
125
    public:
126
        /**
127
         * Algorithm parameters.
128
         */
129
        ForceDirectedParameters parameters;
130
131
        /**
132
         * Valid debug levels are: 0, 1, 2, 3, 4.
133
         * Higher debug level will print more debug messages to the standard output during embedding.
134
         * Debug level 0 means embedding will not print anything.
135
         */
136
        int debugLevel;
137
138
        /**
139
         * When true embedding stops at every cycle to be able to inspect the state of the embedding.
140
         * Call embed again to continue.
141
         */
142
        bool inspected;
143
144
        /**
145
         * A value between 0 and 1, where 0 means initialized state and 1 means finished state.
146
         * This will be updated according to the current internal state during the solution.
147
         * The value might decrease during the calculation although it is expected to increase most of the time.
148
         */
149
        double relaxFactor;
150
151
        /**
152
         * The total time spent on calculation since the last reinitialize call.
153
         */
154
        double elapsedCalculationTime;
155
156
        /**
157
         * Time step is automatically updated during the solution. It will always
158
         * have the highest value so that the acceleration error is less than the max
159
         * acceleration error. The time step is either multiplied or divided by the
160
         * time step multiplier according to the current acceleration error.
161
         */
162
        double updatedTimeStep;
163
164
    public:
165
        ForceDirectedEmbedding();
166
        virtual ~ForceDirectedEmbedding();
167
168
        const std::vector<Variable *>& getVariables() const {
169
            return variables;
170
        }
171
172
        const std::vector<IForceProvider *>& getForceProviders() const {
173
            return forceProviders;
174
        }
175
176
        void addForceProvider(IForceProvider *forceProvider) {
177
            forceProviders.push_back(forceProvider);
178
            forceProvider->setForceDirectedEmbedding(this);
179
        }
180
181
        void removeForceProvider(IForceProvider *forceProvider) {
182
            std::vector<IForceProvider *>::iterator it = std::find(forceProviders.begin(), forceProviders.end(), forceProvider);
183
184
            if (it != forceProviders.end())
185
                forceProviders.erase(it);
186
        }
187
188
        const std::vector<IBody *>& getBodies() const {
189
            return bodies;
190
        }
191
192
        void addBody(IBody *body) {
193
            bodies.push_back(body);
194
            body->setForceDirectedEmbedding(this);
195
196
            Variable *variable = body->getVariable();
197
            if (std::find(variables.begin(), variables.end(), variable) == variables.end()) {
198
                variable->setForceDirectedEmbedding(this);
199
                variables.push_back(variable);
200
            }
201
        }
202
203
        bool getFinished() {
204
            return finished;
205
        }
206
207
        /**
208
         * Sets the default parameters.
209
         */
210
        ForceDirectedParameters getParameters(int32 seed = 0);
211
212
        /**
213
         * Clears all results from previous calculations and sets initial values.
214
         */
215
        void reinitialize();
216
217
        /**
218
         * Calculate the total current kinetic energy.
219
         */
220
        double getKineticEnergy() {
221
            double sum = 0;
222
            for (int i = 0; i < (int)variables.size(); i++)
223
                sum +=  variables[i]->getKineticEnergy();
224
225
            return sum;
226
        }
227
228
        /**
229
         * Calculate the total current potential energy.
230
         */
231
        double getPotentialEnergy() {
232
            double sum = 0;
233
            for (int i = 0; i < (int)forceProviders.size(); i++)
234
                sum += forceProviders[i]->getPotentialEnergy();
235
236
            return sum;
237
        }
238
239
        double getEnergyBasedFrictionCoefficient(double time) {
240
            return 3 * totalMass / time * log((getPotentialEnergy() + getKineticEnergy()) / parameters.velocityRelaxLimit);
241
        }
242
243
        Rc getBoundingRectangle();
244
245
        /**
246
         * Find the solution for the differential equation using a
247
         * modified Runge-Kutta 4th order algorithm.
248
         *
249
         * a1 = a[pn, vn]
250
         * a2 = a[pn + h / 2 * vn + h * h / 8 * a1, vn + h / 2 * a1]
251
         * a3 = a[pn + h / 2 * vn + h * h / 8 * a1, vn + h / 2 * a2]
252
         * a4 = a[pn + h * vn + h * h / 2 * a3, vn + h * a3]
253
         *
254
         * pn+1 = pn + h * vn + h * h / 6 * [a1 + a2 + a3]
255
         * vn+1 = vn + h / 6 * (a1 + 2 * a2 + 2 * a3 + a4)
256
         *
257
         * This algorithm adaptively modifies timeStep and friction.
258
         */
259
        void embed();
260
261
        /**
262
         * Writes internal debug information into the given stream.
263
         */
264
        void writeDebugInformation(std::ostream& ostream);
265
266
    protected:
267
        /**
268
         * Create a Pt array filled with zeros.
269
         */
270
        std::vector<Pt> createPtArray() {
271
            std::vector<Pt> pts;
272
273
            for (int i = 0; i < (int)variables.size(); i++)
274
                pts.push_back(Pt::getZero());
275
276
            return pts;
277
        }
278
279
        /**
280
         * Calculate the average relative error of any corresponding pair between a1, a2, a3 and a4
281
         * relative to the absolute a values.
282
         */
283
        double averageRelativeError(const std::vector<Pt>& a1, const std::vector<Pt>& a2,
284
                                 const std::vector<Pt>& a3, const std::vector<Pt>& a4)
285
        {
286
            double sum1 = 0;
287
            double sum2 = 0;
288
            Assert(a1.size() == a2.size() && a2.size() == a3.size() && a3.size() == a4.size());
289
290
            for (int i = 0; i < (int)a1.size(); i++) {
291
                sum1 += a1[i].getDistance(a2[i]);
292
                sum1 += a2[i].getDistance(a3[i]);
293
                sum1 += a3[i].getDistance(a4[i]);
294
295
                sum2 += a1[i].getLength();
296
                sum2 += a2[i].getLength();
297
                sum2 += a3[i].getLength();
298
                sum2 += a4[i].getLength();
299
            }
300
301
            sum1 /= a1.size() * 3;
302
            sum2 /= a1.size() * 4;
303
304
            return sum2 == 0 ? 0 : sum1 / sum2;
305
        }
306
307
        /**
308
         * Calculate the maximum difference of any corresponding pair between a1, a2, a3 and a4.
309
         */
310
        double maximumDifference(const std::vector<Pt>& a1, const std::vector<Pt>& a2,
311
                                 const std::vector<Pt>& a3, const std::vector<Pt>& a4)
312
        {
313
            double max = 0;
314
            Assert(a1.size() == a2.size() && a2.size() == a3.size() && a3.size() == a4.size());
315
316
            for (int i = 0; i < (int)a1.size(); i++) {
317
                max = std::max(max, a1[i].getDistance(a2[i]));
318
                max = std::max(max, a2[i].getDistance(a3[i]));
319
                max = std::max(max, a3[i].getDistance(a4[i]));
320
            }
321
322
            return max;
323
        }
324
325
        /**
326
         * pts = a + b * c
327
         */
328
        void addMultiplied(std::vector<Pt>& pts, const std::vector<Pt>& a, double b, const std::vector<Pt>& c)
329
        {
330
            Assert(a.size() == c.size());
331
            Assert(pts.size() == c.size());
332
333
            for (int i = 0; i < (int)pts.size(); i++)
334
                pts[i].assign(c[i]).multiply(b).add(a[i]);
335
        }
336
337
        /**
338
         * pts += a * b
339
         */
340
        void incrementWithMultiplied(std::vector<Pt>& pts, double a, const std::vector<Pt>& b)
341
        {
342
            Pt pt;
343
            Assert(pts.size() == b.size());
344
345
            for (int i = 0; i < (int)pts.size(); i++) {
346
                pt.assign(b[i]).multiply(a);
347
                pts[i].add(pt);
348
            }
349
        }
350
351
        /**
352
         * pts = a + b
353
         */
354
        void add(std::vector<Pt>& pts, const std::vector<Pt>& a, const std::vector<Pt>& b)
355
        {
356
            Assert(a.size() == b.size());
357
358
            for (int i = 0; i < (int)pts.size(); i++)
359
                pts[i].assign(a[i]).add(b[i]);
360
        }
361
362
        /**
363
         * pts += a
364
         */
365
        void increment(std::vector<Pt>& pts, const std::vector<Pt>& a)
366
        {
367
            Assert(pts.size() == a.size());
368
369
            for (int i = 0; i < (int)pts.size(); i++)
370
                pts[i].add(a[i]);
371
        }
372
373
        /**
374
         * pts *= a
375
         */
376
        void multiply(std::vector<Pt>& pts, double a)
377
        {
378
            for (int i = 0; i < (int)pts.size(); i++)
379
                pts[i].multiply(a);
380
        }
381
382
        /**
383
         * an = b[pn, vn]
384
         */
385
        void a(std::vector<Pt>& an, const std::vector<Pt>& pn, const std::vector<Pt>& vn);
386
387
        /**
388
         * Convert measured ticks to milliseconds.
389
         */
390
        double ticksToMilliseconds(long ticks) {
391
            return (double)ticks / CLOCKS_PER_SEC * 1000;
392
        }
393
};
394
395
NAMESPACE_END
396
397
#endif