← Back to branch summary

~ubuntu-branches/ubuntu/quantal/mysql-workbench/quantal

« back to all changes in this revision

Viewing changes to modules/wb.model/src/graph_renderer.cpp

  • Committer: Package Import Robot
  • Author(s): Dmitry Smirnov
  • Date: 2012-03-01 21:57:30 UTC
  • Revision ID: package-import@ubuntu.com-20120301215730-o7y8av8y38n162ro
Tags: upstream-5.2.38+dfsg
Import upstream version 5.2.38+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
modules/wb.model/src/graph_renderer.cpp
 
1
#include <climits>
 
2
#include "stdafx.h"
 
3
#include <limits.h>
 
4
 
 
5
#include "graph_renderer.h"
 
6
 
 
7
#ifdef __GNUC__
 
8
const int GraphRenderer::K1F;
 
9
const int GraphRenderer::K1N;
 
10
const int GraphRenderer::K2;
 
11
const int GraphRenderer::K3;
 
12
#endif
 
13
 
 
14
/*
 
15
// equals for doubles
 
16
// algorithm by D.E.Knuth (TAOCP Vol.3 Sec. 4.2.2)
 
17
static bool eq(double d1, double d2)
 
18
{
 
19
  static int delta = 1;
 
20
 
 
21
  long long i1 = * (long long*) &d1;
 
22
  long long i2 = * (long long*) &d2;
 
23
 
 
24
  if(i1 < 0) 
 
25
  {
 
26
    i1 = -i1;//0x8000000000000000 - i1;
 
27
  }
 
28
  if(i2 < 0) 
 
29
  {
 
30
    i2 = -i2;//0x8000000000000000 - i2;
 
31
  }
 
32
 
 
33
  long long v = i1 - i2;
 
34
  if(v < 0)
 
35
  {
 
36
    v = -v;
 
37
  }
 
38
 
 
39
  return (v < delta);
 
40
}
 
41
 */
 
42
 
 
43
static inline bool edge_is_special(GraphEdge& edge)
 
44
{
 
45
  return edge.is_special();
 
46
}
 
47
 
 
48
static inline void reset_visited(GraphNode *node)
 
49
{
 
50
  node->set_visited(false);
 
51
}
 
52
 
 
53
double GraphNode::distance(const GraphNode& n1, const GraphNode& n2)
 
54
{
 
55
  double xdist, left, right, leftw;
 
56
  double ydist, top, bottom, toph;
 
57
 
 
58
  if(n1._left < n2._left) 
 
59
  {
 
60
    left = n1._left;
 
61
    leftw = n1._width;
 
62
    right = n2._left;
 
63
  } 
 
64
  else
 
65
  {
 
66
    left = n2._left;
 
67
    leftw = n2._width;
 
68
    right = n1._left;
 
69
  }
 
70
 
 
71
  xdist = right - left - leftw;
 
72
  if(xdist <= 0) 
 
73
  {
 
74
    xdist = 1;
 
75
  }
 
76
 
 
77
  if(n1._top < n2._top) 
 
78
  {
 
79
    top = n1._top;
 
80
    toph = n1._height;
 
81
    bottom = n2._top;
 
82
  } 
 
83
  else
 
84
  {
 
85
    top = n2._top;
 
86
    toph = n2._height;
 
87
    bottom = n1._top;
 
88
  }
 
89
 
 
90
  ydist = bottom - top - toph;
 
91
  if(ydist <= 0) 
 
92
  {
 
93
    ydist = 1;
 
94
  }
 
95
 
 
96
  return sqrt(xdist*xdist + ydist*ydist);
 
97
}
 
98
 
 
99
bool operator == (const GraphNode& n1, const GraphNode& n2) 
 
100
{
 
101
  return (n1._left == n2._left) && (n1._top == n2._top) && (n1._width == n2._width) && (n1._height == n2._height); 
 
102
}
 
103
 
 
104
GraphRenderer::GraphRenderer(double margin, double maxwidth, double maxheight) 
 
105
  : focus_recalced(false), _length(50), _left(0), _top(0), _right(200), _bottom(200), _avg_force(-1)
 
106
{
 
107
  _margin= margin;
 
108
  _maxw= maxwidth;
 
109
  _maxh= maxheight;
 
110
}
 
111
 
 
112
GraphRenderer::~GraphRenderer()
 
113
{
 
114
  GraphNodeRefList::iterator e= _allnodes.end();
 
115
  for(GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it)
 
116
  {
 
117
    delete *it;
 
118
  }
 
119
}
 
120
 
 
121
void GraphRenderer::mark_neighbours(const GraphNode& node)
 
122
{
 
123
  std::for_each(_allnodes.begin(), _allnodes.end(), reset_visited);
 
124
  
 
125
  for(GraphEdgeList::const_iterator it= _alledges.begin(); it != _alledges.end(); ++it)
 
126
  {
 
127
    GraphEdge e= *it;
 
128
    if(e.contains(node))
 
129
    {
 
130
      e.get_other(node).set_visited(true);    
 
131
    }
 
132
  }
 
133
}
 
134
 
 
135
bool GraphRenderer::is_focus_node(const GraphNode& node) const
 
136
{
 
137
  unsigned counter= 0;
 
138
 
 
139
  for(GraphEdgeList::const_iterator edgeit= _alledges.begin(); edgeit != _alledges.end(); edgeit++)
 
140
  {
 
141
    GraphEdge e= *edgeit;
 
142
    if(e.contains(node))
 
143
    {
 
144
      counter++;
 
145
      if(counter > 1)
 
146
        return true;
 
147
    }
 
148
  }
 
149
 
 
150
  return false;
 
151
}
 
152
 
 
153
// horizontal with vertical
 
154
static inline bool hv_lines_intersect(double x11, double x12, double y1, double x2, double y21, double y22)
 
155
{
 
156
  return (x2 >= x11) && (x2 <= x12) && (y1 >= y21) && (y1 <= y22);
 
157
}
 
158
 
 
159
static inline bool nodes_intersect(double l, double t, double w, double h,
 
160
                                   double ol, double ot, double ow, double oh)
 
161
{
 
162
    // to simplify things
 
163
    // this doesn't test full inclusion (which is very improbable)
 
164
    return hv_lines_intersect(l, l+w, t, ol, ot, ot+oh)
 
165
      || hv_lines_intersect(l, l+w, t+h, ol, ot, ot+oh)
 
166
      || hv_lines_intersect(l, l+w, t, ol+ow, ot, ot+oh)
 
167
      || hv_lines_intersect(l, l+w, t+h, ol+ow, ot, ot+oh)
 
168
      || hv_lines_intersect(ol, ol+ow, ot, l, t, t+h)
 
169
      || hv_lines_intersect(ol, ol+ow, ot+oh, l, t, t+h)
 
170
      || hv_lines_intersect(ol, ol+ow, ot, l+w, t, t+h)
 
171
      || hv_lines_intersect(ol, ol+ow, ot+oh, l+w, t, t+h);
 
172
}
 
173
 
 
174
bool GraphRenderer::has_intersections() const
 
175
{
 
176
  GraphNodeRefList::const_iterator e= _allnodes.end();
 
177
  for(GraphNodeRefList::const_iterator it= _allnodes.begin(); it != e; ++it)
 
178
  {
 
179
    GraphNode& node= **it;
 
180
    double l= node.left();
 
181
    double t= node.top();
 
182
    double w= node.width();
 
183
    double h= node.height();
 
184
 
 
185
    GraphNodeRefList::const_iterator it2= it;
 
186
    it2++;
 
187
    for(; it2 != e; it2++)
 
188
    {
 
189
      GraphNode& other= **it2;
 
190
      double ol= other.left();
 
191
      double ot= other.top();
 
192
      double ow= other.width();
 
193
      double oh= other.height();
 
194
 
 
195
      bool ix= nodes_intersect(l, t, w, h, ol, ot, ow, oh);
 
196
      if(ix)
 
197
        return true;
 
198
    }
 
199
  }
 
200
  return false;
 
201
}
 
202
 
 
203
void GraphRenderer::get_delta(const GraphNode& node, double *deltax, double *deltay)
 
204
{
 
205
  static const int NNODES= 2;
 
206
  
 
207
  mark_neighbours(node);
 
208
 
 
209
  double ccx= node.left();
 
210
  double ccy= node.top();
 
211
  bool node_is_focus= node.is_focus();
 
212
 
 
213
  double all_sum_x= 0.;
 
214
  double all_sum_y= 0.;
 
215
 
 
216
  GraphNodeRefList::iterator e= _allnodes.end();
 
217
  for(GraphNodeRefList::const_iterator it= _allnodes.begin(); it != e; ++it) 
 
218
  {
 
219
    const GraphNode* nei[NNODES];
 
220
    nei[0]= *it;
 
221
    if(nei[0] == &node)
 
222
    {
 
223
      if(++it == e)
 
224
        break;
 
225
      nei[0]= *it;
 
226
    }
 
227
    
 
228
    ++it;
 
229
    
 
230
    if(it != e)
 
231
    {
 
232
      nei[1]= *it;
 
233
      if(nei[1] == &node)
 
234
      {
 
235
        if(++it != e)
 
236
          nei[1]= *it;
 
237
      }
 
238
    }
 
239
 
 
240
    if(it == e)
 
241
    {
 
242
      nei[1]= nei[0]; // we waste calculations but save if() jumps
 
243
      --it;
 
244
    }
 
245
 
 
246
    double d0, d1;
 
247
    
 
248
    d0= GraphNode::distance(node, *nei[0]);
 
249
    d1= GraphNode::distance(node, *nei[1]);
 
250
 
 
251
    if(d0 == 0.)
 
252
      d0= 1.;
 
253
    if(d1 == 0.)
 
254
      d1= 1.;
 
255
 
 
256
    double dcx[NNODES];
 
257
    double dcy[NNODES];
 
258
    
 
259
    dcx[0]= ccx - nei[0]->left();
 
260
    dcy[0]= ccy - nei[0]->top();
 
261
    dcx[1]= ccx - nei[1]->left();
 
262
    dcy[1]= ccy - nei[1]->top();
 
263
 
 
264
    double vx0, vx1;
 
265
    double vy0, vy1;
 
266
    vx0= dcx[0];
 
267
    vy0= dcy[0];
 
268
    vx1= dcx[1];
 
269
    vy1= dcy[1];
 
270
 
 
271
    double dq0, dq1;
 
272
    dq0= d0*d0;
 
273
    dq1= d1*d1;
 
274
    
 
275
    bool neif[NNODES];
 
276
    neif[0]= nei[0]->is_focus();
 
277
    neif[1]= nei[1]->is_focus();
 
278
 
 
279
    vx0 *= GraphRenderer::K2;
 
280
    vy0 *= GraphRenderer::K2;
 
281
    vx1 *= GraphRenderer::K2;
 
282
    vy1 *= GraphRenderer::K2;
 
283
 
 
284
    vx0 /= dq0;
 
285
    vy0 /= dq0;
 
286
    vx1 /= dq1;
 
287
    vy1 /= dq1;
 
288
 
 
289
    all_sum_x += vx0;
 
290
    all_sum_y += vy0;
 
291
    all_sum_x += vx1;
 
292
    all_sum_y += vy1;
 
293
 
 
294
    if(neif[0])
 
295
    {
 
296
      all_sum_x += vx0;
 
297
      all_sum_y += vy0;
 
298
    }
 
299
    if(neif[1])
 
300
    {
 
301
      all_sum_x += vx1;
 
302
      all_sum_y += vy1;
 
303
    }
 
304
 
 
305
    if(nei[0]->is_visisted())
 
306
    {
 
307
      double k= _length - d0;
 
308
      
 
309
      vx0= k*dcx[0]/d0;
 
310
      vy0= k*dcy[0]/d0;
 
311
 
 
312
      k= (node_is_focus || neif[0]) ? GraphRenderer::K1F : GraphRenderer::K1N;
 
313
      vx0 /= k;
 
314
      vy0 /= k;
 
315
      
 
316
      all_sum_x += vx0;
 
317
      all_sum_y += vy0;
 
318
   }
 
319
 
 
320
    if(nei[1]->is_visisted())
 
321
    {
 
322
      double k= _length - d1;
 
323
 
 
324
      vx1= k*dcx[1]/d1;
 
325
      vy1= k*dcy[1]/d1;
 
326
 
 
327
      k= (node_is_focus || neif[1]) ? GraphRenderer::K1F : GraphRenderer::K1N;
 
328
      vx1 /= k;
 
329
      vy1 /= k;
 
330
      
 
331
      all_sum_x += vx1;
 
332
      all_sum_y += vy1;
 
333
    }
 
334
  }
 
335
 
 
336
  static const double t= 10.; // threshold
 
337
  static const double s= 4.;  // step
 
338
 
 
339
  if(all_sum_x >= t)
 
340
    *deltax= s;
 
341
  else if(all_sum_x <= -t)
 
342
    *deltax= -s;
 
343
  else
 
344
    *deltax= 0;
 
345
 
 
346
  if(all_sum_y >= t)
 
347
    *deltay= s;
 
348
  else if(all_sum_y <= -t)
 
349
    *deltay= -s;
 
350
  else
 
351
    *deltay= 0;
 
352
//!
 
353
/*
 
354
  *deltax= std::min(*deltax, _right - node.left() - node.width());
 
355
  *deltay= std::min(*deltay, _bottom - node.top() - node.height());
 
356
  *deltax= std::min(*deltax, _maxw - node.left() - node.width());
 
357
  *deltay= std::min(*deltay, _maxh - node.top() - node.height());
 
358
*/
 
359
}
 
360
 
 
361
GraphNode *GraphRenderer::add_node(double left, double top, double width, double height) 
 
362
{ 
 
363
  GraphNode *node= new GraphNode(left, top, width, height);
 
364
  _allnodes.push_back(node); 
 
365
  focus_recalced= false;
 
366
  return node;
 
367
}
 
368
 
 
369
void GraphRenderer::add_edge(GraphNode *n1, GraphNode *n2) 
 
370
{ 
 
371
  _alledges.push_back(GraphEdge(*n1, *n2)); 
 
372
  focus_recalced= false;
 
373
}
 
374
 
 
375
void GraphRenderer::add_special_edge(GraphNode *n1, GraphNode *n2) 
 
376
{ 
 
377
  _alledges.push_back(GraphEdge(*n1, *n2, true)); 
 
378
  focus_recalced= false;
 
379
}
 
380
 
 
381
void GraphRenderer::mark_reachable(GraphNode& node)
 
382
{
 
383
  if(node.is_visisted())
 
384
    return;
 
385
  
 
386
  node.set_visited(true);
 
387
 
 
388
  for(GraphRenderer::GraphEdgeList::iterator it= _alledges.begin(); it != _alledges.end(); ++it) 
 
389
  {
 
390
    GraphEdge& edge= *it;
 
391
    if(!edge.contains(node))
 
392
      continue;
 
393
    GraphNode& other= edge.get_other(node);
 
394
    mark_reachable(other);
 
395
  }
 
396
}
 
397
 
 
398
void GraphRenderer::concat_graph(GraphNode& node)
 
399
{
 
400
  mark_reachable(node);
 
401
  
 
402
  GraphNodeRefList::iterator e= _allnodes.end();
 
403
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it)
 
404
  {
 
405
    GraphNode& next= **it;
 
406
    if(!next.is_visisted())
 
407
    {
 
408
      add_special_edge(&node, &next);
 
409
      mark_reachable(next);
 
410
    }
 
411
  }
 
412
}
 
413
 
 
414
void GraphRenderer::recalc_focus_nodes()
 
415
{
 
416
  if(focus_recalced)
 
417
    return;
 
418
  
 
419
  GraphNodeRefList::iterator e= _allnodes.end();
 
420
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
421
  {
 
422
    GraphNode& node = **it;
 
423
    node.set_focus(is_focus_node(node));
 
424
  }
 
425
 
 
426
  // add edges to avoid unconnected nodes/pieces
 
427
  std::remove_if(_alledges.begin(), _alledges.end(), edge_is_special);
 
428
  std::for_each(_allnodes.begin(), _allnodes.end(), reset_visited);
 
429
  if(_allnodes.size() > 0)
 
430
  {
 
431
    GraphNode* node = _allnodes.front();
 
432
    concat_graph(*node);
 
433
  }
 
434
 
 
435
  focus_recalced= true;
 
436
}
 
437
 
 
438
void GraphRenderer::recalc_outer_rect()
 
439
{
 
440
  _left = INT_MAX;
 
441
  _top = INT_MAX;
 
442
  _right = INT_MIN;
 
443
  _bottom = INT_MIN;
 
444
 
 
445
  GraphNodeRefList::iterator e= _allnodes.end();
 
446
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
447
  {
 
448
    GraphNode& node = **it;
 
449
    double left = node.left();
 
450
    double top = node.top();
 
451
    double right = left + node.width();
 
452
    double bottom = top + node.height();
 
453
    
 
454
    if(_left > left) {
 
455
      _left = left;
 
456
    } 
 
457
    if(_right < right) {
 
458
      _right = right;
 
459
    }
 
460
    if(_top > top) {
 
461
      _top = top;
 
462
    } 
 
463
    if(_bottom < bottom) {
 
464
      _bottom = bottom;
 
465
    } 
 
466
  }
 
467
}
 
468
 
 
469
void GraphRenderer::recalc_positions()
 
470
{
 
471
  double xf, yf;
 
472
  CoordSet cs;
 
473
  _avg_force= 0;
 
474
 
 
475
  GraphRenderer::GraphNodeRefList::iterator e= _allnodes.end();
 
476
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
477
  {
 
478
    GraphNode& node= **it;
 
479
 
 
480
    if(!node.is_movable())
 
481
      continue;
 
482
 
 
483
    get_delta(node, &xf, &yf);
 
484
    node.setnewleft(node.left() + xf);
 
485
    node.setnewtop(node.top() + yf);
 
486
    _avg_force += sqrt(xf*xf + yf*yf);
 
487
    std::pair<CoordSet::iterator, bool> pr = cs.insert(CoordPair(node.newleft(), node.newtop()));
 
488
    while(!pr.second) 
 
489
    {
 
490
      node.setnewleft(node.newleft() + 1);
 
491
      node.setnewtop(node.newtop() + 1);
 
492
      pr = cs.insert(CoordPair(node.newleft(), node.newtop()));
 
493
    }
 
494
  }
 
495
 
 
496
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
497
  {
 
498
    GraphNode& node = **it;
 
499
    if(!node.is_movable())
 
500
      continue;
 
501
    node.apply();
 
502
  }
 
503
}
 
504
 
 
505
void GraphRenderer::rotate_point(double *x, double *y, double angle)
 
506
{
 
507
  double x0 = *x;
 
508
  double y0 = *y;
 
509
  double sina= sin(angle);
 
510
  double cosa= cos(angle);
 
511
  *x = x0*cosa + y0*sina;
 
512
  *y = -x0*sina + y0*cosa;
 
513
}
 
514
 
 
515
void GraphRenderer::move(double dx, double dy)
 
516
{
 
517
  GraphRenderer::GraphNodeRefList::iterator e= _allnodes.end();
 
518
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
519
  {
 
520
    GraphNode& node = **it;
 
521
    node.setnewleft(node.left() + dx);
 
522
    node.setnewtop(node.top() + dy);
 
523
    node.apply();
 
524
  }
 
525
}
 
526
 
 
527
void GraphRenderer::rotate()
 
528
{
 
529
  static double pi = 3.1415926535;
 
530
  static double step = pi/300.;
 
531
 
 
532
  double curmsd = 0, posmsd = 0, negmsd = 0;
 
533
  double yzero = (_top + _bottom)/2.;
 
534
  double xzero = (_left + _right)/2.;
 
535
 
 
536
  GraphRenderer::GraphNodeRefList::iterator e= _allnodes.end();
 
537
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
538
  {
 
539
    GraphNode& node = **it;
 
540
    
 
541
    if(!node.is_movable())
 
542
      continue;
 
543
 
 
544
    double x = node.centerx() - xzero;
 
545
    double y = node.centery() - yzero;
 
546
    double x1 = x;
 
547
    double y1 = y;
 
548
    double x2 = x;
 
549
    double y2 = y;
 
550
 
 
551
    rotate_point(&x1, &y1, step);
 
552
    rotate_point(&x2, &y2, -step);
 
553
 
 
554
    curmsd += y*y;
 
555
    posmsd += y1*y1;
 
556
    negmsd += y2*y2;
 
557
  }
 
558
 
 
559
  if(posmsd > negmsd)
 
560
  {
 
561
    step = -step;
 
562
  }
 
563
 
 
564
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
565
  {
 
566
    GraphNode& node = **it;
 
567
    
 
568
    if(!node.is_movable())
 
569
      continue;
 
570
 
 
571
    double x = node.left() - xzero;
 
572
    double y = node.top() - yzero;
 
573
    rotate_point(&x, &y, step);
 
574
 
 
575
    //!
 
576
    /*
 
577
    xzero= std::min(xzero, _right - node.width());
 
578
    yzero= std::min(yzero, _bottom - node.height());
 
579
    xzero= std::min(xzero, _maxw - node.width());
 
580
    yzero= std::min(yzero, _maxh - node.height());
 
581
    */
 
582
 
 
583
    node.setnewleft(x + xzero);
 
584
    node.setnewtop( y + yzero);
 
585
    node.apply();
 
586
  }
 
587
}
 
588
 
 
589
void GraphRenderer::shift_to_origin()
 
590
{
 
591
  GraphRenderer::GraphNodeRefList::iterator e= _allnodes.end();
 
592
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
593
  {
 
594
    GraphNode& node= **it;
 
595
    node.setnewleft(node.left() - _left + _margin);
 
596
    node.setnewtop(node.top() - _top + _margin);
 
597
    node.apply();
 
598
  }
 
599
 
 
600
  _right -= _left;
 
601
  _bottom -= _top;
 
602
  _left= _top= 0;
 
603
}
 
604
 
 
605
void GraphRenderer::scale(double xfactor, double yfactor)
 
606
{
 
607
  GraphRenderer::GraphNodeRefList::iterator e= _allnodes.end();
 
608
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
609
  {
 
610
    GraphNode& node= **it;
 
611
    node.setnewleft(node.left()*xfactor);
 
612
    node.setnewtop(node.top()*yfactor);
 
613
    node.apply();
 
614
  }
 
615
}
 
616
 
 
617
bool GraphRenderer::has_nonmovable_nodes() const
 
618
{
 
619
  GraphRenderer::GraphNodeRefList::const_iterator e= _allnodes.end();
 
620
  for(GraphRenderer::GraphNodeRefList::const_iterator it= _allnodes.begin(); it != e; ++it) 
 
621
  {
 
622
    GraphNode& node= **it;
 
623
    if(!node.is_movable())
 
624
      return true;
 
625
  }
 
626
  return false;
 
627
}
 
628
 
 
629
void GraphRenderer::scale_up()
 
630
{
 
631
  double scale_factor_x= 1;
 
632
  double scale_factor_y= 1;
 
633
  
 
634
  GraphNodeRefList::const_iterator e= _allnodes.end();
 
635
  for(GraphNodeRefList::const_iterator it= _allnodes.begin(); it != e; ++it)
 
636
  {
 
637
    GraphNode& node= **it;
 
638
    double l= node.left();
 
639
    double t= node.top();
 
640
    double w= node.width();
 
641
    double h= node.height();
 
642
 
 
643
    GraphNodeRefList::const_iterator it2= it;
 
644
    it2++;
 
645
    for(; it2 != e; it2++)
 
646
    {
 
647
      GraphNode& other= **it2;
 
648
      double ol= other.left();
 
649
      double ot= other.top();
 
650
      double ow= other.width();
 
651
      double oh= other.height();
 
652
 
 
653
      if(nodes_intersect(l, t, w, h, ol, ot, ow, oh))
 
654
      {
 
655
        double minl= 0;
 
656
        double maxl= 0;
 
657
        double minw= 0;
 
658
        
 
659
        if(l < ol)
 
660
        {
 
661
          minl= l;
 
662
          maxl= ol;
 
663
          minw= w;
 
664
        }
 
665
        else
 
666
        {
 
667
          minl= ol;
 
668
          maxl= l;
 
669
          minw= ow;
 
670
        }
 
671
 
 
672
        if((minl + minw + _margin) > maxl)
 
673
        {
 
674
          double f= (minw + _margin)/(maxl - minl);
 
675
          if(f > scale_factor_x)
 
676
            scale_factor_x= f;
 
677
        }
 
678
 
 
679
        if(t < ot)
 
680
        {
 
681
          minl= t;
 
682
          maxl= ot;
 
683
          minw= h;
 
684
        }
 
685
        else
 
686
        {
 
687
          minl= ot;
 
688
          maxl= t;
 
689
          minw= oh;
 
690
        }
 
691
 
 
692
        if((minl + minw + _margin) > maxl)
 
693
        {
 
694
          double f= (minw + _margin)/(maxl - minl);
 
695
          if(f > scale_factor_y)
 
696
            scale_factor_y= f;
 
697
        }
 
698
      }
 
699
    }
 
700
  }
 
701
 
 
702
  scale(scale_factor_x, scale_factor_y);
 
703
}
 
704
 
 
705
void GraphRenderer::scale_down()
 
706
{
 
707
  double maxw= _maxw - 2*_margin;
 
708
  double maxh= _maxh - 2*_margin;
 
709
  
 
710
  if((maxw >= (_right - _left)) && (maxh >= (_bottom - _top))) 
 
711
    return;
 
712
  
 
713
  double xfactor= maxw < (_right - _left) ? maxw/(_right - _left) : 1;
 
714
  double yfactor= maxh < (_bottom - _top) ? maxh/(_bottom - _top) : 1;
 
715
 
 
716
  scale(xfactor, yfactor);
 
717
}
 
718
 
 
719
void GraphRenderer::recalc()
 
720
{
 
721
  unsigned count= 0;
 
722
  unsigned iter_count= 200;
 
723
  bool has_nonmovable= has_nonmovable_nodes();
 
724
 
 
725
  double temp_maxw= _maxw;
 
726
  double temp_maxh= _maxh;
 
727
 
 
728
  _maxw= 200;
 
729
  _maxh= 200;
 
730
  
 
731
  if(!has_nonmovable)
 
732
  {
 
733
    recalc_outer_rect();
 
734
    scale_down();
 
735
  }
 
736
 
 
737
  _maxw= temp_maxw;
 
738
  _maxh= temp_maxh;
 
739
 
 
740
  recalc_focus_nodes();
 
741
 
 
742
  while(!is_steady() && (count < iter_count))
 
743
  {
 
744
    recalc_length();
 
745
    recalc_positions();
 
746
    rotate();
 
747
    recalc_outer_rect();
 
748
    count++;
 
749
  }
 
750
 
 
751
  if(!is_steady()) 
 
752
  {
 
753
    count= 0;
 
754
    recalc_focus_nodes();
 
755
    while(has_intersections() && (count < iter_count))
 
756
    {
 
757
      recalc_length();
 
758
      recalc_positions();
 
759
      rotate();
 
760
      recalc_outer_rect();
 
761
      count++;
 
762
    }
 
763
  }
 
764
 
 
765
  recalc_outer_rect();
 
766
  shift_to_origin();
 
767
 
 
768
  if(!has_nonmovable)
 
769
  {
 
770
    recalc_outer_rect();
 
771
    scale_up();
 
772
 
 
773
    recalc_outer_rect();
 
774
    scale_down();
 
775
 
 
776
    recalc_outer_rect();
 
777
    shift_to_origin();
 
778
  }
 
779
}
 
780
 
 
781
void GraphRenderer::get_outer_rect(double *left, double *top, double *right, double *bottom)
 
782
{
 
783
  *left= _left;
 
784
  *top= _top;
 
785
  *right= _right;
 
786
  *bottom= _bottom;
 
787
}
 
788
 
 
789
void GraphRenderer::recalc_length()
 
790
{
 
791
  int l[4] = {0};
 
792
  _density_ratio = 0.;
 
793
  double cx= (_left+_right)/2.;
 
794
  double cy= (_top+_bottom)/2.;
 
795
 
 
796
  GraphRenderer::GraphNodeRefList::iterator e= _allnodes.end();
 
797
  for(GraphRenderer::GraphNodeRefList::iterator it= _allnodes.begin(); it != e; ++it) 
 
798
  {
 
799
    GraphNode& node= **it;
 
800
    _density_ratio += node.width()*node.height();
 
801
    int idx= 0;
 
802
    idx += node.centerx() < cx ? 0 : 1;
 
803
    idx += node.centery() < cy ? 0 : 2;
 
804
    l[idx]++;
 
805
  }
 
806
  _density_ratio /= (_right - _left)*(_bottom - _top);
 
807
  _length= 1000.*_density_ratio*_density_ratio;
 
808
}