Project

General

Profile

Statistics
| Branch: | Revision:

root / src / layout / forcedirectedgraphlayouter.cc @ 8aeaaccc

History | View | Annotate | Download (23.2 KB)

1 01873262 Georg Kunz
//==========================================================================
2
//  FORCEDIRECTEDGRAPHLAYOUTER.CC - 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
#include <stdio.h>
18
#include <time.h>
19
#include <math.h>
20
#include <float.h>
21
#include <stdlib.h>
22
#include <sstream>
23
24
#include "commonutil.h"
25
#include "forcedirectedgraphlayouter.h"
26
#include "startreeembedding.h"
27
#include "heapembedding.h"
28
#include "platmisc.h"
29
30
USING_NAMESPACE
31
32
33
ForceDirectedGraphLayouter::ForceDirectedGraphLayouter()
34
{
35
    hasFixedNode = false;
36
    hasMovableNode = false;
37
    hasAnchoredNode = false;
38
        hasEdgeToBorder = false;
39
40
    topBorder = NULL;
41
    bottomBorder = NULL;
42
    leftBorder = NULL;
43
    rightBorder = NULL;
44
45
    expectedEmbeddingWidth = -1;
46
    expectedEmbeddingHeight = -1;
47
    expectedEdgeLength = -1;
48
    pointLikeDistance = true;
49
    slippery = false;
50
}
51
52
void ForceDirectedGraphLayouter::setParameters()
53
{
54
    // random seed
55
    embedding.parameters = embedding.getParameters(lcgRandom.getSeed());
56
57
    // timing parameters
58
    embedding.parameters.minTimeStep = environment->getDoubleParameter("mits", 0, embedding.parameters.minTimeStep);
59
    embedding.parameters.maxTimeStep = environment->getDoubleParameter("mats", 0, embedding.parameters.maxTimeStep);
60
    embedding.parameters.minAccelerationError = environment->getDoubleParameter("miae", 0, embedding.parameters.minAccelerationError);
61
    embedding.parameters.maxAccelerationError = environment->getDoubleParameter("maae", 0, embedding.parameters.maxAccelerationError);
62
63
    // various algorithm parameters
64
    embedding.parameters.defaultSlippery = environment->getBoolParameter("sp", 0, slippery);
65
    embedding.parameters.defaultPointLikeDistance = environment->getBoolParameter("pld", 0, pointLikeDistance);
66
    embedding.parameters.defaultSpringCoefficient = environment->getDoubleParameter("sc", 0, privUniform(0.1, 1));
67
    embedding.parameters.defaultSpringReposeLength = environment->getDoubleParameter("srl", 0, privUniform(expectedEdgeLength / 2, expectedEdgeLength));
68
    embedding.parameters.electricRepulsionCoefficient = environment->getDoubleParameter("erc", 0, privUniform(10000, 100000));
69
    embedding.parameters.frictionCoefficient = environment->getDoubleParameter("fc", 0, privUniform(1, 5));
70
    embedding.parameters.velocityRelaxLimit = environment->getDoubleParameter("vrl", 0, 0.2);
71
    embedding.parameters.maxCalculationTime = environment->getDoubleParameter("mct", 0, privUniform(1000, 20000));
72
73
    // 3d
74
    threeDFactor = environment->getDoubleParameter("3df", 0, privRand01() < 0.5 ? 0 : privUniform(0, 1));
75
    threeDCoefficient = environment->getDoubleParameter("3dc", 0, privUniform(0, 10));
76
77
    // which embedding to use
78
    preEmbedding = environment->getBoolParameter("pe", 0, privRand01() < 0.5);
79
    forceDirectedEmbedding = environment->getBoolParameter("fde", 0, true);
80
81
    // debug parameters
82
    debugWaitTime = environment->getDoubleParameter("dwt", 0, 0);
83
    showForces = environment->getBoolParameter("sf", 0, false);
84
    showSummaForce = environment->getBoolParameter("ssf", 0, false);
85
}
86
87
void ForceDirectedGraphLayouter::addBody(cModule *mod, IBody *body)
88
{
89
    embedding.addBody(body);
90
    moduleToBodyMap[mod] = body;
91
}
92
93
IBody *ForceDirectedGraphLayouter::findBody(cModule *mod)
94
{
95
    std::map<cModule *, IBody *>::iterator it = moduleToBodyMap.find(mod);
96
97
    if (it != moduleToBodyMap.end())
98
        return it->second;
99
    else
100
        return NULL;
101
}
102
103
Variable *ForceDirectedGraphLayouter::ensureAnchorVariable(const char *anchorName)
104
{
105
    std::map<std::string, Variable *>::iterator it = anchorNameToVariableMap.find(anchorName);
106
107
    if (it != anchorNameToVariableMap.end())
108
        return it->second;
109
    else
110
        return anchorNameToVariableMap[anchorName] = new Variable(Pt::getNil());
111
}
112
113
void ForceDirectedGraphLayouter::calculateExpectedMeasures()
114
{
115
    const std::vector<IBody *>& bodies = embedding.getBodies();
116
117
    // body sizes
118
    int count = 0;
119
    double maxBodyLength = 0;
120
121
    // expected measures
122
    double expectedEmbeddingSize = 0;
123
    double averageBodyLength = 0;
124
125
    for (int i = 0; i < (int)bodies.size(); i++) {
126
        IBody *body = bodies[i];
127
128
        if (!dynamic_cast<WallBody *>(body)) {
129
            double length = body->getSize().getDiagonalLength();
130
            count++;
131
            maxBodyLength = std::max(maxBodyLength, length);
132
            averageBodyLength += length;
133
            expectedEmbeddingSize += body->getSize().getArea();
134
        }
135
    }
136
137
    // use pointLikeDistance if there is no too big bodies compared to the others
138
    // this will make the embedding faster
139
    Assert(!isNaN(averageBodyLength));
140
    averageBodyLength /= count;
141
    pointLikeDistance = maxBodyLength < 2 * averageBodyLength;
142
    // FIXME: fix the following to be able to nicely layout big and small nodes in the same embedding
143
    // this means the node rectangles will be used properly when calculating the distance and vector between them
144
    // slippery = pointLikeDistance && privRand01() < 0.5;
145
146
    // minimum length plus averageBodyLength
147
    double minEdgeLength = 20 + 2400 / (20 + bodies.size());
148
    expectedEdgeLength = pointLikeDistance ? minEdgeLength + averageBodyLength : minEdgeLength;
149
150
    // calculate expected embedding size
151
    expectedEmbeddingSize += 2 * pow(expectedEdgeLength, 2) * bodies.size();
152
    expectedEmbeddingSize = sqrt(expectedEmbeddingSize);
153
    Assert(!isNaN(expectedEmbeddingSize));
154
    expectedEmbeddingWidth = width ? width : expectedEmbeddingSize + 2 * border;
155
    expectedEmbeddingHeight = height ? height : expectedEmbeddingSize + 2 * border;
156
}
157
158
void ForceDirectedGraphLayouter::setRandomPositions()
159
{
160
    // assign values to not yet assigned coordinates
161
    const std::vector<Variable *>& variables = embedding.getVariables();
162
    for (int i = 0; i < (int)variables.size(); i++) {
163
        Pt pt(variables[i]->getPosition());
164
165
        if (isNaN(pt.x))
166
            pt.x = privUniform(border, expectedEmbeddingWidth - border);
167
168
        if (isNaN(pt.y))
169
            pt.y = privUniform(border, expectedEmbeddingHeight - border);
170
171
        if (isNaN(pt.z))
172
            pt.z = (privRand01() - 0.5) * sqrt(expectedEmbeddingWidth * expectedEmbeddingHeight) * threeDFactor;
173
174
        variables[i]->assignPosition(pt);
175
    }
176
}
177
178
void ForceDirectedGraphLayouter::ensureBorders()
179
{
180
    // top and bottom borders are handled together
181
    if (!topBorder && (height || hasFixedNode || hasEdgeToBorder)) {
182
        topBorder = new WallBody(true, NaN);
183
        bottomBorder = new WallBody(true, NaN);
184
        }
185
    // left and right borders are handled together
186
        if (!leftBorder && (width || hasFixedNode || hasEdgeToBorder)) {
187
        leftBorder = new WallBody(false, NaN);
188
        rightBorder = new WallBody(false, NaN);
189
    }
190
}
191
192
void ForceDirectedGraphLayouter::addBorderForceProviders()
193
{
194
    // add electric repulsion to all bodies
195
    const std::vector<IBody *>& bodies = embedding.getBodies();
196
    for (int i = 0; i < (int)bodies.size(); i++) {
197
        IBody *body = bodies[i];
198
                if (topBorder) {
199
            embedding.addForceProvider(new VerticalElectricRepulsion(topBorder, body));
200
            embedding.addForceProvider(new VerticalElectricRepulsion(bottomBorder, body));
201
                }
202
                if (leftBorder) {
203
            embedding.addForceProvider(new HorizontalElectricRepulsion(leftBorder, body));
204
            embedding.addForceProvider(new HorizontalElectricRepulsion(rightBorder, body));
205
                }
206
    }
207
        if (topBorder) {
208
        // the positions for non constrained variables are not yet set
209
        topBorder->setVariable(hasFixedNode || height ? new PointConstrainedVariable(Pt(NaN, 0, NaN)) : new Variable(Pt::getNil()));
210
        bottomBorder->setVariable(height ? new PointConstrainedVariable(Pt(NaN, height, NaN)) : new Variable(Pt::getNil()));
211
        embedding.addBody(topBorder);
212
        embedding.addBody(bottomBorder);
213
            if (!height)
214
                embedding.addForceProvider(new VerticalSpring(topBorder, bottomBorder, -1, expectedEmbeddingHeight));
215
        }
216
        if (leftBorder) {
217
        // the positions for non constrained variables are not yet set
218
        leftBorder->setVariable(hasFixedNode || width ? new PointConstrainedVariable(Pt(0, NaN, NaN)) : new Variable(Pt::getNil()));
219
        rightBorder->setVariable(width ? new PointConstrainedVariable(Pt(width, NaN, NaN)) : new Variable(Pt::getNil()));
220
        embedding.addBody(leftBorder);
221
        embedding.addBody(rightBorder);
222
            if (!width)
223
                embedding.addForceProvider(new HorizonalSpring(leftBorder, rightBorder, -1, expectedEmbeddingWidth));
224
        }
225
}
226
227
void ForceDirectedGraphLayouter::setBorderPositions()
228
{
229
    double distance = 100;
230
    double top = DBL_MAX, bottom = DBL_MIN;
231
    double left = DBL_MAX, right = DBL_MIN;
232
233
    if (!width || !height) {
234
        const std::vector<IBody *>& bodies = embedding.getBodies();
235
        for (int i = 0; i < (int)bodies.size(); i++) {
236
            IBody *body = bodies[i];
237
238
            if (!dynamic_cast<WallBody *>(body)) {
239
                if (!height) {
240
                    top = std::min(top, body->getTop());
241
                    bottom = std::max(bottom, body->getBottom());
242
                }
243
                if (!width) {
244
                    left = std::min(left, body->getLeft());
245
                    right = std::max(right, body->getRight());
246
                }
247
            }
248
        }
249
    }
250
251
    // ensure all bodies are within the box specified by the borders
252
    if (topBorder) {
253
        topBorder->setPosition(hasFixedNode || height ? 0 : top - distance);
254
        bottomBorder->setPosition(height ? height : bottom + distance);
255
    }
256
    if (leftBorder) {
257
        leftBorder->setPosition(hasFixedNode || width ? 0 : left - distance);
258
        rightBorder->setPosition(width ? width : right + distance);
259
    }
260
}
261
262
void ForceDirectedGraphLayouter::addElectricRepulsions()
263
{
264
    const std::vector<IBody *>& bodies = embedding.getBodies();
265
    for (int i = 0; i < (int)bodies.size(); i++)
266
        for (int j = i + 1; j < (int)bodies.size(); j++) {
267
            IBody *body1 = bodies[i];
268
            IBody *body2 = bodies[j];
269
            Variable *variable1 = body1->getVariable();
270
            Variable *variable2 = body2->getVariable();
271
272
            // ignore wall bodies
273
            if (!dynamic_cast<WallBody *>(body1) &&
274
                !dynamic_cast<WallBody *>(body2) &&
275
                variable1 != variable2)
276
            {
277
                Vertex *vertex1 = graphComponent.findVertex(variable1);
278
                Vertex *vertex2 = graphComponent.findVertex(variable2);
279
280
                Assert(vertex1);
281
                Assert(vertex2);
282
283
                // check if the two are in the same connected component
284
                if (vertex1->connectedSubComponent != vertex2->connectedSubComponent)
285
                    embedding.addForceProvider(new ElectricRepulsion(body1, body2, expectedEdgeLength / 2, expectedEdgeLength));
286
                else
287
                    embedding.addForceProvider(new ElectricRepulsion(body1, body2));
288
            }
289
        }
290
}
291
292
void ForceDirectedGraphLayouter::addBasePlaneSprings()
293
{
294
    const std::vector<IBody *>& bodies = embedding.getBodies();
295
    for (int i = 0; i < (int)bodies.size(); i++) {
296
          IBody *body = bodies[i];
297
298
        if (!dynamic_cast<WallBody *>(body))
299
            embedding.addForceProvider(new BasePlaneSpring(body, threeDCoefficient, 0));
300
    }
301
}
302
303
Rc ForceDirectedGraphLayouter::getBoundingBox(Rs &rs)
304
{
305
    double top = DBL_MAX, bottom = DBL_MIN;
306
    double left = DBL_MAX, right = DBL_MIN;
307
308
    const std::vector<IBody *>& bodies = embedding.getBodies();
309
    for (int i = 0; i < (int)bodies.size(); i++) {
310
        IBody *body = bodies[i];
311
312
        if (!dynamic_cast<WallBody *>(body)) {
313
            if (body->getBottom() > bottom)
314
                rs.height = body->getSize().height;
315
            top = std::min(top, body->getTop());
316
            bottom = std::max(bottom, body->getBottom());
317
            if (body->getRight() > right)
318
                rs.width = body->getSize().width;
319
            left = std::min(left, body->getLeft());
320
            right = std::max(right, body->getRight());
321
        }
322
    }
323
324
    return Rc(Pt(left, top, 0), Rs(right - left, bottom - top));
325
}
326
327
void ForceDirectedGraphLayouter::scale(Pt pt)
328
{
329
    const std::vector<Variable *>& variables = embedding.getVariables();
330
    for (int i = 0; i < (int)variables.size(); i++)
331
        variables[i]->assignPosition(Pt(variables[i]->getPosition()).multiply(pt));
332
}
333
334
void ForceDirectedGraphLayouter::translate(Pt pt)
335
{
336
    const std::vector<Variable *>& variables = embedding.getVariables();
337
    for (int i = 0; i < (int)variables.size(); i++) {
338
        variables[i]->assignPosition(Pt(variables[i]->getPosition()).add(pt));
339
    }
340
}
341
342
void ForceDirectedGraphLayouter::addMovableNode(cModule *mod, int width, int height)
343
{
344
    hasMovableNode = true;
345
346
    // this is a free variable and body
347
    Variable *variable = new Variable(Pt::getNil());
348
    addBody(mod, new Body(variable, Rs(width, height)));
349
350
    graphComponent.addVertex(new Vertex(Pt::getNil(), Rs(width, height), variable));
351
}
352
353
void ForceDirectedGraphLayouter::addFixedNode(cModule *mod, int x, int y, int width, int height)
354
{
355
    hasFixedNode = true;
356
        ensureBorders();
357
358
    // a fix node is a constrained variable which can only move on the z axes
359
    Variable *variable = new PointConstrainedVariable(Pt(x, y, NaN));
360
    IBody *body = new Body(variable, Rs(width, height));
361
    addBody(mod, body);
362
363
    graphComponent.addVertex(new Vertex(Pt(x - width / 2, y - height / 2, NaN), Rs(width, height), variable));
364
}
365
366
void ForceDirectedGraphLayouter::addAnchoredNode(cModule *mod, const char *anchorname, int offx, int offy, int width, int height)
367
{
368
    hasAnchoredNode = true;
369
370
    // an anchored node is a relatively (to a variable, namely the anchor) positioned body
371
    Variable *variable = ensureAnchorVariable(anchorname);
372
    addBody(mod, new RelativelyPositionedBody(variable, Pt(offx, offy, 0), Rs(width, height)));
373
374
    // update vertex size
375
    Vertex *vertex = graphComponent.findVertex(variable);
376
    if (!vertex)
377
        graphComponent.addVertex(new Vertex(Pt::getNil(), Rs(offx + width / 2, offy + height / 2), variable));
378
    else {
379
        Rs rs = vertex->rc.rs;
380
        vertex->rc.rs = Rs(std::max(rs.width, (double)(offx + width / 2)), std::max(rs.height, (double)(offy + height / 2)));
381
    }
382
}
383
384
void ForceDirectedGraphLayouter::addEdge(cModule *from, cModule *to, int len)
385
{
386
    // an edge is a spring
387
    // the -1 edge length will be replaced with expectedEdgeLength
388
    Spring *spring = new Spring(findBody(from), findBody(to), -1, len ? len : -1);
389
    embedding.addForceProvider(spring);
390
391
    // and also an edge in the graph
392
    graphComponent.addEdge(new Edge(graphComponent.findVertex(spring->getBody1()->getVariable()),
393
                                    graphComponent.findVertex(spring->getBody2()->getVariable())));
394
}
395
396
void ForceDirectedGraphLayouter::addEdgeToBorder(cModule *from, int len)
397
{
398
        hasEdgeToBorder = true;
399
        ensureBorders();
400
    IBody *body = findBody(from);
401
402
    // add a force provider which uses four springs each connected to a wall
403
    // the least expanded spring will provided an attraction force
404
    std::vector<AbstractSpring *> springs;
405
    springs.push_back(new VerticalSpring(topBorder, body, -1, !len ? -1 : len));
406
    springs.push_back(new VerticalSpring(bottomBorder, body, -1, !len ? -1 : len));
407
    springs.push_back(new HorizonalSpring(leftBorder, body, -1, !len ? -1 : len));
408
    springs.push_back(new HorizonalSpring(rightBorder, body, -1, !len ? -1 : len));
409
    embedding.addForceProvider(new LeastExpandedSpring(springs));
410
}
411
412
void ForceDirectedGraphLayouter::executePreEmbedding() {
413
    GraphComponent childrenComponentsStar;
414
    Vertex *childrenComponentsStarRoot = NULL;
415
416
    // first pre embed all connected components, one by one
417
    for (std::vector<GraphComponent *>::iterator it = graphComponent.connectedSubComponents.begin(); it != graphComponent.connectedSubComponents.end(); it++) {
418
        GraphComponent *childComponent = *it;
419
        childComponent->calculateSpanningTree();
420
421
        // use tree embedding if connected component is a tree
422
        if (childComponent->getVertexCount() == childComponent->getEdgeCount() + 1 || privRand01() < 0.5) {
423
            StarTreeEmbedding starTreeEmbedding(childComponent, expectedEdgeLength);
424
            starTreeEmbedding.embed();
425
        }
426
        else {
427
            HeapEmbedding heapEmbedding(childComponent, expectedEdgeLength);
428
            heapEmbedding.embed();
429
        }
430
431
        // add a new vertex to component graph for each embedded sub component
432
        Vertex *childComponentVertex = new Vertex(Pt::getNil(), childComponent->getBoundingRectangle().rs, NULL);
433
        if (!childrenComponentsStarRoot)
434
            childrenComponentsStarRoot = childComponentVertex;
435
436
        childrenComponentsStar.addVertex(childComponentVertex);
437
        childrenComponentsStar.addEdge(new Edge(childrenComponentsStarRoot, childComponentVertex));
438
    }
439
440
    // embed component graph
441
    childrenComponentsStar.calculateSpanningTree();
442
    HeapEmbedding heapEmbedding(&childrenComponentsStar, expectedEdgeLength);
443
    heapEmbedding.embed();
444
445
    // position all vertices on the plane so that they do not overlap
446
    // adding coordinates in the connected component and in the component graph
447
    for (int i = 0; i < (int)graphComponent.connectedSubComponents.size(); i++) {
448
        Vertex *childComponentVertex = childrenComponentsStar.getVertex(i);
449
        GraphComponent *childComponent = graphComponent.connectedSubComponents[i];
450
451
        for (int i = 0; i < childComponent->getVertexCount(); i++) {
452
            Vertex *vertex = childComponent->getVertex(i);
453
            Variable *variable = (Variable *)vertex->identity;
454
            Pt pt = vertex->rc.getCenterCenter();
455
            pt.add(childComponentVertex->rc.pt);
456
            pt.z = NaN;
457
            variable->assignPosition(pt);
458
        }
459
    }
460
461
    // ensure all vertices are within the bounding box if it is specified
462
    Rs rs; // the size of the biggest right and bottom vertex
463
    Rc rc = getBoundingBox(rs);
464
    scale(Pt(width ? (width - border * 2 - rs.width) / (rc.rs.width - rs.width) : 1,
465
             height ? (height - border * 2 - rs.height) / (rc.rs.height - rs.height) : 1, NaN));
466
    // ensure all vertices have positive coordinates
467
    rc = getBoundingBox(rs);
468
    translate(Pt(-rc.pt.x + border, -rc.pt.y + border, 0));
469
}
470
471
void ForceDirectedGraphLayouter::execute()
472
{
473
    if (hasMovableNode) {
474
        calculateExpectedMeasures();
475
        setParameters();
476
477
        // always calculate graph components
478
        graphComponent.calculateConnectedSubComponents();
479
480
        // execute pre-embedding if requested
481
        if (preEmbedding) {
482
            executePreEmbedding();
483
484
            // draw initial pre embedding result
485
            if (environment->inspected())
486
                debugDraw();
487
        }
488
489
        // execute force directed embedding if requested
490
        if (forceDirectedEmbedding) {
491
                        if (width || height)
492
                                ensureBorders();
493
                        if (topBorder || leftBorder)
494
                addBorderForceProviders();
495
496
            addElectricRepulsions();
497
498
            if (threeDFactor > 0)
499
                addBasePlaneSprings();
500
501
            embedding.addForceProvider(new Drag());
502
503
            // assign random values to missing positions
504
            setRandomPositions();
505
506
            if (topBorder || leftBorder)
507
                setBorderPositions();
508
509
            //embedding.debug = 3;
510
            embedding.inspected = true;
511
            embedding.reinitialize();
512
513
            while (!embedding.getFinished() && environment->okToProceed()) {
514
                embedding.embed();
515
516
                if (environment->inspected())
517
                    debugDraw();
518
            }
519
520
            // ensure all vertices have positive coordinates even when there were no borders
521
            Rs rs;
522
            Rc rc = getBoundingBox(rs);
523
            translate(Pt(hasFixedNode || width ? 0 : -rc.pt.x + border, hasFixedNode || height ? 0 : -rc.pt.y + border, 0));
524
        }
525
526
        // set random positions if no embedding was used
527
        if (!preEmbedding && !forceDirectedEmbedding)
528
            setRandomPositions();
529
    }
530
}
531
532
void ForceDirectedGraphLayouter::getNodePosition(cModule *mod, int& x, int& y)
533
{
534
    IBody *body = findBody(mod);
535
    const Pt& pt = body->getPosition();
536
    x = (int) pt.x;
537
    y = (int) pt.y;
538
}
539
540
void ForceDirectedGraphLayouter::debugDraw()
541
{
542
    environment->clearGraphics();
543
544
    // draw bodies
545
    const std::vector<IBody *>& bodies = embedding.getBodies();
546
    for (int i = 0; i < (int)bodies.size(); i++) {
547
        IBody *body = bodies[i];
548
        Pt pt(body->getPosition());
549
        Rs rs = body->getSize();
550
        pt.subtract(Pt(rs.width / 2, rs.height / 2, 0));
551
552
        // wall bodies are long lines
553
        if (dynamic_cast<WallBody *>(body)) {
554
            if (rs.width == POSITIVE_INFINITY) {
555
                pt.x = leftBorder ? leftBorder->getPosition().x : -1000;
556
                rs.width = leftBorder ? rightBorder->getPosition().x - leftBorder->getPosition().x : 2000;
557
            }
558
559
            if (rs.height == POSITIVE_INFINITY) {
560
                pt.y = topBorder ? topBorder->getPosition().y : -1000;
561
                rs.height = topBorder ? bottomBorder->getPosition().y - topBorder->getPosition().y : 2000;
562
            }
563
        }
564
565
        environment->drawRectangle(pt.x , pt.y, pt.x + rs.width, pt.y + rs.height, "{node bbox}", "black");
566
        char text[100];
567
        sprintf(text,"%g", pt.z);
568
        environment->drawText(pt.x, pt.y, text, "{node bbox}", "black");
569
    }
570
571
    // draw springs
572
    const std::vector<IForceProvider *>& forceProviders = embedding.getForceProviders();
573
    for (int i = 0; i < (int)forceProviders.size(); i++) {
574
        Spring *spring = dynamic_cast<Spring *>(forceProviders[i]);
575
        if (spring) {
576
            const Pt& pt1 = spring->getBody1()->getPosition();
577
            const Pt& pt2 = spring->getBody2()->getPosition();
578
            environment->drawLine(pt1.x, pt1.y, pt2.x, pt2.y, "{edge bbox}", "black");
579
        }
580
    }
581
582
    // draw forces
583
    double forceScale = 10;
584
    const std::vector<Variable *>& variables = embedding.getVariables();
585
    for (int i = 0; i < (int)variables.size(); i++) {
586
        Variable *variable = variables[i];
587
        const Pt& pt1 = variable->getPosition();
588
589
        if (showForces) {
590
            std::vector<Pt> forces = variable->getForces();
591
592
            for (int j = 0; j < (int)forces.size(); j++) {
593
                Pt pt2(pt1);
594
                Pt force(forces[j]);
595
                force.multiply(forceScale);
596
                pt2.add(force);
597
                environment->drawLine(pt1.x, pt1.y, pt2.x, pt2.y, "force", "red");
598
            }
599
        }
600
601
        if (showSummaForce) {
602
            Pt pt2(pt1);
603
            Pt force(variable->getForce());
604
            force.multiply(forceScale);
605
            pt2.add(force);
606
            environment->drawLine(pt1.x, pt1.y, pt2.x, pt2.y, "force", "blue");
607
        }
608
    }
609
610
    // write force directed embedding internal state info
611
    std::stringstream info;
612
    embedding.writeDebugInformation(info);
613
    environment->showGraphics(info.str().c_str());
614
615
    usleep((int)(debugWaitTime*1000));
616
}