← Back to branch summary

~ubuntu-branches/ubuntu/precise/graphviz/precise-security

« back to all changes in this revision

Viewing changes to lib/neatogen/neatoinit.c

  • Committer: Bazaar Package Importer
  • Author(s): David Claughton
  • Date: 2010-03-24 22:45:18 UTC
  • mfrom: (1.2.7 upstream) (6.1.7 sid)
  • Revision ID: james.westby@ubuntu.com-20100324224518-do441tthbqjaqjzd
Tags: 2.26.3-4
http://bugs.debian.org/575255
Add patch to fix segfault in circo. Backported from upstream snapshot
release.  Thanks to Francis Russell for his work on this.
(Closes: #575255)

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/neatogen/neatoinit.c
1
 
/* $Id: neatoinit.c,v 1.45 2008/05/21 15:21:47 erg Exp $ $Revision: 1.45 $ */
 
1
/* $Id: neatoinit.c,v 1.86 2009/10/15 17:28:19 erg Exp $ $Revision: 1.86 $ */
2
2
/* vim:set shiftwidth=4 ts=8: */
3
3
 
4
4
/**********************************************************
23
23
#ifndef WIN32
24
24
#include <unistd.h>
25
25
#endif
 
26
#include <ctype.h>
 
27
 
26
28
#include "neato.h"
27
29
#include "pack.h"
28
30
#include "stress.h"
31
33
#endif
32
34
#include "kkutils.h"
33
35
#include "pointset.h"
34
 
#include <ctype.h>
35
36
 
36
37
#ifndef HAVE_SRAND48
37
38
#define srand48 srand
45
46
 
46
47
void neato_init_node(node_t * n)
47
48
{
 
49
#ifdef WITH_CGRAPH
 
50
    agbindrec(n, "Agnodeinfo_t", sizeof(Agnodeinfo_t), TRUE);   //node custom data
 
51
#endif /* WITH_CGRAPH */
48
52
    common_init_node(n);
49
 
    ND_pos(n) = N_NEW(GD_ndim(n->graph), double);
50
 
    gv_nodesize(n, GD_flip(n->graph));
 
53
    ND_pos(n) = N_NEW(GD_ndim(agraphof(n)), double);
 
54
    gv_nodesize(n, GD_flip(agraphof(n)));
51
55
}
52
56
 
53
57
static void neato_init_edge(edge_t * e)
54
58
{
 
59
#ifdef WITH_CGRAPH
 
60
        agbindrec(e, "Agedgeinfo_t", sizeof(Agedgeinfo_t), TRUE);       //node custom data
 
61
#endif /* WITH_CGRAPH */
55
62
    common_init_edge(e);
 
63
#ifndef WITH_CGRAPH
56
64
 
 
65
#endif /* WITH_CGRAPH */
57
66
    ED_factor(e) = late_double(e, E_weight, 1.0, 1.0);
58
67
}
59
68
 
66
75
    if (posptr == NULL)
67
76
        return FALSE;
68
77
    pvec = ND_pos(np);
 
78
#ifndef WITH_CGRAPH
69
79
    p = agxget(np, posptr->index);
 
80
#else
 
81
    p = agxget(np, posptr);
 
82
#endif
70
83
    if (p[0]) {
71
84
        c = '\0';
72
85
        if ((Ndim >= 3) && 
79
92
            }
80
93
            if (Ndim > 3)
81
94
                jitter_d(np, nG, 3);
82
 
            if ((c == '!')
83
 
                || (pinptr && mapbool(agxget(np, pinptr->index))))
 
95
#ifndef WITH_CGRAPH
 
96
            if ((c == '!') || (pinptr && mapbool(agxget(np, pinptr->index))))
 
97
#else
 
98
            if ((c == '!') || (pinptr && mapbool(agxget(np, pinptr))))
 
99
#endif
84
100
                ND_pinned(np) = P_PIN;
85
101
            return TRUE;
86
102
        }
92
108
                    pvec[i] = pvec[i] / PSinputscale;
93
109
            }
94
110
            if (Ndim > 2) {
95
 
                if (N_z && (p = agxget(np, N_z->index)) && 
96
 
                           (sscanf(p,"%lf",&z) == 1)) { 
 
111
#ifndef WITH_CGRAPH
 
112
                if (N_z && (p = agxget(np, N_z->index)) && (sscanf(p,"%lf",&z) == 1)) { 
 
113
#else
 
114
                if (N_z && (p = agxget(np, N_z)) && (sscanf(p,"%lf",&z) == 1)) { 
 
115
#endif
97
116
                    if (PSinputscale > 0.0) {
98
117
                        pvec[2] = z / PSinputscale;
99
118
                    }
104
123
                else
105
124
                    jitter3d(np, nG);
106
125
            }
107
 
            if ((c == '!')
108
 
                || (pinptr && mapbool(agxget(np, pinptr->index))))
 
126
#ifndef WITH_CGRAPH
 
127
            if ((c == '!') || (pinptr && mapbool(agxget(np, pinptr->index))))
 
128
#else
 
129
            if ((c == '!') || (pinptr && mapbool(agxget(np, pinptr))))
 
130
#endif
109
131
                ND_pinned(np) = P_PIN;
110
132
            return TRUE;
111
133
        } else
112
134
            agerr(AGERR, "node %s, position %s, expected two doubles\n",
113
 
                  np->name, p);
 
135
                  agnameof(np), p);
114
136
    }
115
137
    return FALSE;
116
138
}
122
144
    int nG = agnnodes(g);
123
145
    attrsym_t *N_pin;
124
146
 
125
 
    N_pos = agfindattr(g->proto->n, "pos");
126
 
    N_pin = agfindattr(g->proto->n, "pin");
 
147
    N_pos = agfindnodeattr(g, "pos");
 
148
    N_pin = agfindnodeattr(g, "pin");
127
149
 
128
150
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
129
151
        neato_init_node(n);
139
161
{
140
162
    if (Nop || (Pack < 0))
141
163
        free_scan_graph(g);
142
 
    if (g != g->root) memset(&(g->u), 0, sizeof(Agraphinfo_t));
 
164
    if (g != agroot(g))
 
165
#ifndef WITH_CGRAPH
 
166
        memset(&(g->u), 0, sizeof(Agraphinfo_t));
 
167
#else /* WITH_CGRAPH */
 
168
        agclean(g, AGRAPH , "Agraphinfo_t");
 
169
#endif /* WITH_CGRAPH */
143
170
}
144
171
 
145
172
void neato_cleanup(graph_t * g)
176
203
static void set_elabel(edge_t * e, textlabel_t * l, char *name)
177
204
{
178
205
    double x, y;
179
 
    point pt;
180
206
    char *lp;
181
207
    lp = agget(e, name);
182
208
    if (lp && (sscanf(lp, "%lf,%lf", &x, &y) == 2)) {
183
 
        pt.x = (int) (x);
184
 
        pt.y = (int) (y);
185
 
        l->p = pt;
 
209
        l->pos = pointfof(x, y);
186
210
        l->set = TRUE;
187
211
    }
188
212
}
190
214
#ifdef IPSEPCOLA
191
215
static cluster_data* cluster_map(graph_t *mastergraph, graph_t *g)
192
216
{
 
217
#ifndef WITH_CGRAPH
193
218
    /* search meta-graph to find clusters */
194
 
    graph_t *mg, *subg;
 
219
    graph_t *mg;
195
220
    node_t *mm, *mn;
 
221
    edge_t *me;
 
222
#endif
 
223
    graph_t *subg;
196
224
    node_t *n;
197
 
    edge_t *me;
198
225
     /* array of arrays of node indices in each cluster */
199
226
    int **cs,*cn;
200
227
    int i,j,nclusters=0;
202
229
    cluster_data *cdata = GNEW(cluster_data);
203
230
 
204
231
    cdata->ntoplevel = agnnodes(g);
 
232
#ifndef WITH_CGRAPH
205
233
    mm = mastergraph->meta_node;
206
 
    mg = mm->graph;
 
234
    mg = agraphof(mm); 
207
235
    for (me = agfstout(mg, mm); me; me = agnxtout(mg, me)) {
208
 
        mn = me->head;
 
236
        mn = aghead(me);
209
237
        subg = agusergraph(mn);
210
 
        if (!strncmp(subg->name, "cluster", 7)) {
 
238
#else
 
239
    for (subg = agfstsubg(mastergraph); subg; subg = agnxtsubg(subg)) {
 
240
#endif
 
241
        if (!strncmp(agnameof(subg), "cluster", 7)) {
211
242
            nclusters++;
212
243
        }
213
244
    }
215
246
    cdata->nclusters = nclusters;
216
247
    cs = cdata->clusters = N_GNEW(nclusters,int*);
217
248
    cn = cdata->clustersizes = N_GNEW(nclusters,int);
 
249
#ifndef WITH_CGRAPH
218
250
    /* fprintf(stderr,"search %d clusters...\n",nclusters); */
219
251
    for (me = agfstout(mg, mm); me; me = agnxtout(mg, me)) {
220
252
        mn = me->head;
221
253
        subg = agusergraph(mn);
 
254
#else
 
255
    for (subg = agfstsubg(mastergraph); subg; subg = agnxtsubg(subg)) {
 
256
#endif
222
257
        /* clusters are processed by separate calls to ordered_edges */
223
 
        if (!strncmp(subg->name, "cluster", 7)) {
 
258
        if (!strncmp(agnameof(subg), "cluster", 7)) {
224
259
            int *c;
225
260
 
226
261
            *cn = agnnodes(subg);
231
266
                node_t *gn;
232
267
                int ind = 0;
233
268
                for (gn = agfstnode(g); gn; gn = agnxtnode(g, gn)) {
234
 
                    if(gn->id==n->id) break;
 
269
                    if(AGID(gn)==AGID(n)) break;
235
270
                    ind++;
236
271
                }
237
 
                /* fprintf(stderr,"  node=%s, id=%d, ind=%d\n",n->name,n->id,ind); */
 
272
                /* fprintf(stderr,"  node=%s, id=%d, ind=%d\n",agnameof(n),n->id,ind); */
238
273
                *c++=ind;
239
274
                assigned[ind]=TRUE;
240
275
                cdata->ntoplevel--;
274
309
{
275
310
    char *pos;
276
311
    int i, n, npts, nc;
277
 
    point *ps = 0;
278
 
    point *pp;
 
312
    pointf *ps = 0;
 
313
    pointf *pp;
279
314
    double x, y;
280
315
    int sflag = 0, eflag = 0;
281
 
    point sp = { 0, 0 }, ep = {
282
 
    0, 0};
 
316
    pointf sp = { 0, 0 }, ep = { 0, 0};
283
317
    bezier *newspl;
284
318
    int more = 1;
285
319
    int stype, etype;
286
320
 
 
321
#ifndef WITH_CGRAPH
287
322
    pos = agxget(e, E_pos->index);
 
323
#else
 
324
    pos = agxget(e, E_pos);
 
325
#endif
288
326
    if (*pos == '\0')
289
327
        return 0;
290
328
 
295
333
        if (i == 2) {
296
334
            sflag = 1;
297
335
            pos = pos + nc;
298
 
            sp.x = (int) (x);
299
 
            sp.y = (int) (y);
 
336
            sp.x = x;
 
337
            sp.y = y;
300
338
        }
301
339
 
302
340
        /* check for e head */
304
342
        if (i == 2) {
305
343
            eflag = 1;
306
344
            pos = pos + nc;
307
 
            ep.x = (int) (x);
308
 
            ep.y = (int) (y);
 
345
            ep.x = x;
 
346
            ep.y = y;
309
347
        }
310
348
 
311
349
        npts = numFields((unsigned char *) pos);        /* count potential points */
314
352
            gv_free_splines(e);
315
353
            return 0;
316
354
        }
317
 
        ps = ALLOC(n, 0, point);
 
355
        ps = ALLOC(n, 0, pointf);
318
356
        pp = ps;
319
357
        while (n) {
320
358
            i = sscanf(pos, "%lf,%lf%n", &x, &y, &nc);
324
362
                return 0;
325
363
            }
326
364
            pos = pos + nc;
327
 
            pp->x = (int) (x);
328
 
            pp->y = (int) (y);
 
365
            pp->x = x;
 
366
            pp->y = y;
329
367
            pp++;
330
368
            n--;
331
369
        }
381
419
    node_t *n;
382
420
    edge_t *e;
383
421
    int nedges = 0;
384
 
    attrsym_t *E_pos = agfindattr(g->proto->e, "pos");
 
422
    attrsym_t *E_pos = agfindedgeattr(g, "pos");
385
423
 
386
424
    if (!E_pos || (Nop < 2))
387
425
        return NoEdges;
406
444
 * Scans for a correct bb attribute. If available, sets it
407
445
 * in the graph and returns 1.
408
446
 */
409
 
#define BS "%d,%d,%d,%d"
 
447
#define BS "%lf,%lf,%lf,%lf"
410
448
 
411
449
static int chkBB(Agraph_t * g, attrsym_t * G_bb)
412
450
{
413
451
    char *s;
414
 
    box bb;
 
452
    boxf bb;
415
453
 
 
454
#ifndef WITH_CGRAPH
416
455
    s = agxget(g, G_bb->index);
 
456
#else
 
457
    s = agxget(g, G_bb);
 
458
#endif
417
459
    if (sscanf(s, BS, &bb.LL.x, &bb.LL.y, &bb.UR.x, &bb.UR.y) == 4) {
418
460
        if (bb.LL.y > bb.UR.y) {
419
461
        /* If the LL.y coordinate is bigger than the UR.y coordinate,
420
462
         * we assume the input was produced using -y, so we normalize
421
463
         * the bb. 
422
464
         */
423
 
            int tmp = bb.LL.y;
 
465
            double tmp = bb.LL.y;
424
466
            bb.LL.y = bb.UR.y;
425
467
            bb.UR.y = tmp;
426
468
        }
445
487
/* dfs:
446
488
 */
447
489
static void
 
490
#ifndef WITH_CGRAPH
448
491
dfs(node_t * mn, Agraph_t * g, attrsym_t * G_lp, attrsym_t * G_bb)
 
492
#else /* WITH_CGRAPH */
 
493
dfs(Agraph_t * subg, Agraph_t * g, attrsym_t * G_lp, attrsym_t * G_bb)
 
494
#endif /* WITH_CGRAPH */
449
495
{
450
 
    graph_t *subg;
451
496
 
452
 
    subg = agusergraph(mn);
453
 
    if (!strncmp(subg->name, "cluster", 7) && chkBB(subg, G_bb)) {
 
497
#ifndef WITH_CGRAPH
 
498
    graph_t *subg = agusergraph(mn);
 
499
#endif
 
500
    if (!strncmp(agnameof(subg), "cluster", 7) && chkBB(subg, G_bb)) {
454
501
        add_cluster(g, subg);
455
502
        nop_init_graphs(subg, G_lp, G_bb);
456
503
    } else {
 
504
#ifndef WITH_CGRAPH
457
505
        graph_t *mg = g->meta_node->graph;
458
506
        edge_t *me;
459
507
        for (me = agfstout(mg, mn); me; me = agnxtout(mg, me)) {
460
508
            dfs(me->head, g, G_lp, G_bb);
 
509
#else
 
510
        graph_t *mg;
 
511
        for (mg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
 
512
            dfs(mg, g, G_lp, G_bb);
 
513
#endif
461
514
        }
462
515
    }
463
516
}
470
523
static void
471
524
nop_init_graphs(Agraph_t * g, attrsym_t * G_lp, attrsym_t * G_bb)
472
525
{
 
526
#ifndef WITH_CGRAPH
473
527
    graph_t *mg;
474
528
    edge_t *me;
 
529
#else
 
530
    graph_t *subg;
 
531
#endif
475
532
    char *s;
476
 
    point p;
 
533
    double x, y;
477
534
 
478
535
    if (GD_label(g) && G_lp) {
 
536
#ifndef WITH_CGRAPH
479
537
        s = agxget(g, G_lp->index);
480
 
        if (sscanf(s, "%d,%d", &p.x, &p.y) == 2) {
 
538
#else
 
539
        s = agxget(g, G_lp);
 
540
#endif
 
541
        if (sscanf(s, "%lf,%lf", &x, &y) == 2) {
 
542
            GD_label(g)->pos = pointfof(x, y);
481
543
            GD_label(g)->set = TRUE;
482
 
            GD_label(g)->p = p;
483
544
        }
484
545
    }
485
546
 
486
547
    if (!G_bb)
487
548
        return;
 
549
#ifndef WITH_CGRAPH
488
550
    mg = g->meta_node->graph;
489
551
    for (me = agfstout(mg, g->meta_node); me; me = agnxtout(mg, me)) {
490
552
        dfs(me->head, g, G_lp, G_bb);
 
553
#else /* WITH_CGRAPH */
 
554
    for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
 
555
        dfs(subg, g, G_lp, G_bb);
 
556
#endif /* WITH_CGRAPH */
491
557
    }
492
558
}
493
559
 
495
561
 * Translate edge by offset.
496
562
 * Assume ED_spl(e) != NULL
497
563
 */
498
 
static void translateE(edge_t * e, point offset)
 
564
static void translateE(edge_t * e, pointf offset)
499
565
{
500
566
    int i, j;
501
 
    point *pt;
 
567
    pointf *pt;
502
568
    bezier *bez;
503
569
 
504
570
    bez = ED_spl(e)->list;
521
587
    }
522
588
 
523
589
    if (ED_label(e) && ED_label(e)->set) {
524
 
        ED_label(e)->p.x -= offset.x;
525
 
        ED_label(e)->p.y -= offset.y;
 
590
        ED_label(e)->pos.x -= offset.x;
 
591
        ED_label(e)->pos.y -= offset.y;
526
592
    }
527
593
    if (ED_head_label(e) && ED_head_label(e)->set) {
528
 
        ED_head_label(e)->p.x -= offset.x;
529
 
        ED_head_label(e)->p.y -= offset.y;
 
594
        ED_head_label(e)->pos.x -= offset.x;
 
595
        ED_head_label(e)->pos.y -= offset.y;
530
596
    }
531
597
    if (ED_tail_label(e) && ED_tail_label(e)->set) {
532
 
        ED_tail_label(e)->p.x -= offset.x;
533
 
        ED_tail_label(e)->p.y -= offset.y;
 
598
        ED_tail_label(e)->pos.x -= offset.x;
 
599
        ED_tail_label(e)->pos.y -= offset.y;
534
600
    }
535
601
}
536
602
 
537
603
/* translateG:
538
604
 */
539
 
static void translateG(Agraph_t * g, point offset)
 
605
static void translateG(Agraph_t * g, pointf offset)
540
606
{
541
607
    int i;
542
608
 
546
612
    GD_bb(g).LL.y -= offset.y;
547
613
 
548
614
    if (GD_label(g) && GD_label(g)->set) {
549
 
        GD_label(g)->p.x -= offset.x;
550
 
        GD_label(g)->p.y -= offset.y;
 
615
        GD_label(g)->pos.x -= offset.x;
 
616
        GD_label(g)->pos.y -= offset.y;
551
617
    }
552
618
 
553
619
    for (i = 1; i <= GD_n_cluster(g); i++)
561
627
    node_t *n;
562
628
    edge_t *e;
563
629
    pointf offset;
564
 
 
565
 
    offset = cvt2ptf(GD_bb(g).LL);
 
630
    pointf ll;
 
631
 
 
632
    ll = GD_bb(g).LL;
 
633
 
 
634
    offset.x = PS2INCH(ll.x);
 
635
    offset.y = PS2INCH(ll.y);
566
636
    for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
567
637
        ND_pos(n)[0] -= offset.x;
568
638
        ND_pos(n)[1] -= offset.y;
571
641
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
572
642
            for (e = agfstout(g, n); e; e = agnxtout(g, e))
573
643
                if (ED_spl(e))
574
 
                    translateE(e, GD_bb(g).LL);
 
644
                    translateE(e, ll);
575
645
        }
576
646
    }
577
 
    translateG(g, GD_bb(g).LL);
 
647
    translateG(g, ll);
578
648
}
579
649
 
580
650
/* init_nop:
584
654
 * clusters, edges and labels. If certain position information
585
655
 * is missing, init_nop will use a standard neato technique to
586
656
 * supply it.
 
657
 *
 
658
 * If adjust is false, init_nop does nothing but initialize all
 
659
 * of the basic graph information. No tweaking of positions or 
 
660
 * filling in edge splines is done.
 
661
 *
 
662
 * Returns 0 on normal success, 1 if postprocess should be avoided, and -1
 
663
 * on failure.
587
664
 */
588
665
int init_nop(Agraph_t * g, int adjust)
589
666
{
590
667
    int i;
591
668
    node_t *np;
592
669
    pos_edge posEdges;          /* How many edges have spline info */
593
 
    attrsym_t *G_lp = agfindattr(g, "lp");
594
 
    attrsym_t *G_bb = agfindattr(g, "bb");
 
670
    attrsym_t *G_lp = agfindgraphattr(g, "lp");
 
671
    attrsym_t *G_bb = agfindgraphattr(g, "bb");
 
672
    int didAdjust = 0;  /* Have nodes been moved? */
 
673
    int haveBackground;
595
674
 
596
675
    /* If G_bb not defined, define it */
597
676
    if (!G_bb)
 
677
#ifndef WITH_CGRAPH
598
678
        G_bb = agraphattr(g, "bb", "");
 
679
#else /* WITH_CGRAPH */
 
680
        G_bb = agattr(g, AGRAPH, "bb", "");
 
681
#endif /* WITH_CGRAPH */
599
682
 
600
683
    scan_graph(g);              /* mainly to set up GD_neato_nlist */
601
684
    for (i = 0; (np = GD_neato_nlist(g)[i]); i++) {
602
 
        if (!hasPos(np) && strncmp(np->name, "cluster", 7)) {
 
685
        if (!hasPos(np) && strncmp(agnameof(np), "cluster", 7)) {
603
686
            agerr(AGERR, "node %s in graph %s has no position\n",
604
 
                  np->name, g->name);
605
 
            return 1;
 
687
                  agnameof(np), agnameof(g));
 
688
            return -1;
606
689
        }
607
690
    }
608
691
    nop_init_graphs(g, G_lp, G_bb);
609
692
    posEdges = nop_init_edges(g);
610
693
 
611
 
    if (adjust && Nop == 1)
612
 
        adjustNodes(g);
 
694
    if (adjust && (Nop == 1))
 
695
        didAdjust = adjustNodes(g);
 
696
 
 
697
    if (didAdjust) {
 
698
        if (GD_label(g)) GD_label(g)->set = FALSE;
 
699
/* FIX: 
 
700
 *   - if nodes are moved, clusters are no longer valid.
 
701
 */
 
702
    }
613
703
 
614
704
    /* If g does not have a good "bb" attribute or we adjusted the nodes, 
615
705
     * compute it. 
616
706
     */
617
 
    if (!chkBB(g, G_bb) || (adjust && Nop == 1))
 
707
    if (!chkBB(g, G_bb) || didAdjust)
618
708
        compute_bb(g);
619
709
 
 
710
    /* Adjust bounding box for any background */
 
711
    if (GD_drawing(g)->xdots) {
 
712
        haveBackground = 1;
 
713
        GD_bb(g) = xdotBB (g);
 
714
    }
 
715
    else
 
716
        haveBackground = 0;
 
717
 
620
718
    /* At this point, all bounding boxes should be correctly defined.
621
719
     * If necessary, we translate the graph to the origin.
622
720
     */
623
 
    if (adjust && (GD_bb(g).LL.x || GD_bb(g).LL.y))
 
721
    if (adjust && !haveBackground && (ROUND(abs(GD_bb(g).LL.x)) || ROUND(abs(GD_bb(g).LL.y))))
624
722
        translate(g, posEdges);
625
723
 
626
724
    if (!adjust) {
627
725
        node_t *n;
628
726
        State = GVSPLINES;
629
727
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
630
 
            ND_coord_i(n).x = POINTS(ND_pos(n)[0]);
631
 
            ND_coord_i(n).y = POINTS(ND_pos(n)[1]);
 
728
            ND_coord(n).x = POINTS_PER_INCH * (ND_pos(n)[0]);
 
729
            ND_coord(n).y = POINTS_PER_INCH * (ND_pos(n)[1]);
632
730
        }
633
731
    }
634
732
    else if (posEdges != AllEdges)
637
735
        State = GVSPLINES;
638
736
        neato_set_aspect(g);
639
737
    }
640
 
    return 0;
 
738
    return haveBackground;
641
739
}
642
740
 
643
 
static void neato_init_graphn(Agraph_t * g, int dfltdim)
 
741
static void neato_init_graph (Agraph_t * g)
644
742
{
 
743
    int outdim;
 
744
 
645
745
    setEdgeType (g, ET_LINE);
646
 
    GD_ndim(g->root) = late_int(g, agfindattr(g, "dim"), dfltdim, 2);
 
746
    outdim = late_int(g, agfindgraphattr(g, "dimen"), 2, 2);
 
747
    GD_ndim(agroot(g)) = late_int(g, agfindgraphattr(g, "dim"), outdim, 2);
647
748
    Ndim = GD_ndim(g->root) = MIN(GD_ndim(g->root), MAXDIM);
 
749
    GD_odim(g->root) = MIN(outdim, Ndim);
648
750
    neato_init_node_edge(g);
649
751
}
650
752
 
651
 
static void neato_init_graph(Agraph_t * g)
652
 
{
653
 
    neato_init_graphn(g, 2);
654
 
}
655
 
 
656
753
static int neatoModel(graph_t * g)
657
754
{
658
755
    char *p = agget(g, "model");
659
756
    char c;
660
757
 
661
 
    if (!p || (!(c = *p)))
 
758
    if (!p || (!(c = *p)))    /* if p is NULL or "" */
662
759
        return MODEL_SHORTPATH;
663
760
    if ((c == 'c') && streq(p, "circuit"))
664
761
        return MODEL_CIRCUIT;
668
765
        else if (streq(p, "shortpath"))
669
766
            return MODEL_SHORTPATH;
670
767
    }
 
768
    if ((c == 'm') && streq(p, "mds")) {
 
769
#ifndef WITH_CGRAPH
 
770
        if (agindex(g->root->proto->e, "len") >= 0)
 
771
#else /* WITH_CGRAPH */
 
772
        if (agattr(g, AGEDGE, "len", 0))
 
773
#endif /* WITH_CGRAPH */
 
774
            return MODEL_MDS;
 
775
        else {
 
776
            agerr(AGWARN,
 
777
                "edges in graph %s have no len attribute. Hence, the mds model\n", agnameof(g));
 
778
            agerr(AGPREV, "is inappropriate. Reverting to the shortest path model.\n");
 
779
            return MODEL_SHORTPATH;
 
780
        }
 
781
    }
671
782
    agerr(AGWARN,
672
783
          "Unknown value %s for attribute \"model\" in graph %s - ignored\n",
673
 
          p, g->name);
 
784
          p, agnameof(g));
674
785
    return MODEL_SHORTPATH;
675
786
}
676
787
 
698
809
        else
699
810
            agerr(AGWARN,
700
811
                  "Illegal value %s for attribute \"mode\" in graph %s - ignored\n",
701
 
                  str, g->name);
 
812
                  str, agnameof(g));
702
813
    }
703
814
 
704
815
    return mode;
709
820
 */
710
821
static int checkEdge(PointMap * pm, edge_t * ep, int idx)
711
822
{
712
 
    int i = ND_id(ep->tail);
713
 
    int j = ND_id(ep->head);
 
823
    int i = ND_id(agtail(ep));
 
824
    int j = ND_id(aghead(ep));
714
825
    int tmp;
715
826
 
716
827
    if (i > j) {
807
918
#ifdef DIGCOLA
808
919
    float *edists = NULL;
809
920
#endif
 
921
#ifndef WITH_CGRAPH
810
922
    int haveLen;
 
923
#else
 
924
    attrsym_t *haveLen;
 
925
#endif
811
926
    int haveWt;
812
927
    int haveDir;
813
928
    PointMap *ps = newPM();
818
933
        haveLen = FALSE;
819
934
        haveWt = FALSE;
820
935
    } else {
 
936
#ifndef WITH_CGRAPH
821
937
        haveLen = (agindex(g->root->proto->e, "len") >= 0);
 
938
#else /* WITH_CGRAPH */
 
939
        haveLen = agattr(g, AGEDGE, "len", 0) ;
 
940
#endif /* WITH_CGRAPH */
822
941
        haveWt = (E_weight != 0);
823
942
    }
824
943
    if (mode == MODE_HIER || mode == MODE_IPSEP)
864
983
        i_nedges = 1;           /* one for the self */
865
984
 
866
985
        for (ep = agfstedge(g, np); ep; ep = agnxtedge(g, ep, np)) {
867
 
            if (ep->head == ep->tail)
 
986
            if (aghead(ep) == agtail(ep))
868
987
                continue;       /* ignore loops */
869
988
            idx = checkEdge(ps, ep, j);
870
989
            if (idx != j) {     /* seen before */
875
994
                    graph[i].ewgts[idx] = MAX(ED_dist(ep), curlen);
876
995
                }
877
996
            } else {
878
 
                node_t *vp = (((ep->tail) == np) ? ep->head : ep->tail);
 
997
                node_t *vp = (((agtail(ep)) == np) ? aghead(ep) : agtail(ep));
879
998
                ne++;
880
999
                j++;
881
1000
 
892
1011
                    if(s&&!strncmp(s,"none",4)) {
893
1012
                        *edists++ = 0;
894
1013
                    } else {
895
 
                        *edists++ = (np == ep->head ? 1.0 : -1.0);
 
1014
                        *edists++ = (np == aghead(ep) ? 1.0 : -1.0);
896
1015
                    }
897
1016
                }
898
1017
#endif
1008
1127
        long seed;
1009
1128
        /* Check for seed value */
1010
1129
        if (!isdigit(*(unsigned char *)p) || sscanf(p, "%ld", &seed) < 1) {
1011
 
#ifdef MSWIN32
 
1130
#if defined(MSWIN32) || defined(WIN32)
1012
1131
            seed = (unsigned) time(NULL);
1013
1132
#else
1014
1133
            seed = (unsigned) getpid() ^ (unsigned) time(NULL);
1054
1173
 
1055
1174
    fprintf(stderr, "n %d e %d\n", nv, ne);
1056
1175
    for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
1057
 
        fprintf(stderr, "\"%s\" %d\n", v->name, ND_id(v));
 
1176
        fprintf(stderr, "\"%s\" %d\n", agnameof(v), ND_id(v));
1058
1177
    }
1059
1178
    for (i = 0; i < nv; i++) {
1060
1179
        n = gp[i].nedges;
1076
1195
/* majorization:
1077
1196
 * Solve stress using majorization.
1078
1197
 * Old neato attributes to incorporate:
1079
 
 *  weight?
1080
 
 * model will be MODE_MAJOR, MODE_HIER or MODE_IPSEP
 
1198
 *  weight
 
1199
 * mode will be MODE_MAJOR, MODE_HIER or MODE_IPSEP
1081
1200
 */
1082
1201
static void
1083
 
majorization(graph_t *mg, graph_t * g, int nv, int mode, int model, int dim, int steps)
 
1202
majorization(graph_t *mg, graph_t * g, int nv, int mode, int model, int dim, int steps, adjust_data* am)
1084
1203
{
1085
1204
    double **coords;
1086
1205
    int ne;
1088
1207
    node_t *v;
1089
1208
    vtx_data *gp;
1090
1209
    node_t** nodes;
 
1210
#ifdef DIGCOLA
 
1211
#ifdef IPSEPCOLA
1091
1212
    expand_t margin;
 
1213
#endif
 
1214
#endif
1092
1215
 
1093
1216
    int init;
1094
1217
 
1095
1218
    init = checkStart(g, nv, (mode == MODE_HIER ? INIT_SELF : INIT_RANDOM));
 
1219
 
1096
1220
    coords = N_GNEW(dim, double *);
1097
1221
    coords[0] = N_GNEW(nv * dim, double);
1098
1222
    for (i = 1; i < Ndim; i++) {
1103
1227
                model, (init == INIT_SELF), MaxIter, Epsilon);
1104
1228
        fprintf(stderr, "convert graph: ");
1105
1229
        start_timer();
 
1230
#ifdef WITH_CGRAPH
 
1231
        fprintf(stderr, "majorization\n");
 
1232
//      fprintf(stderr, "%i\n", count_nodes(g));
 
1233
 
 
1234
#endif /* WITH_CGRAPH */
1106
1235
    }
1107
1236
    gp = makeGraphData(g, nv, &ne, mode, model, &nodes);
1108
1237
 
1112
1241
 
1113
1242
#ifdef DIGCOLA
1114
1243
    if (mode != MODE_MAJOR) {
1115
 
        double lgap = late_double(g, agfindattr(g, "levelsgap"), 0.0, -MAXDOUBLE);
 
1244
        double lgap = late_double(g, agfindgraphattr(g, "levelsgap"), 0.0, -MAXDOUBLE);
1116
1245
        if (mode == MODE_HIER) {        
1117
1246
            stress_majorization_with_hierarchy(gp, nv, ne, coords, nodes, Ndim,
1118
1247
                       (init == INIT_SELF), model, MaxIter, lgap);
1120
1249
#ifdef IPSEPCOLA
1121
1250
        else {
1122
1251
            char* str;
1123
 
            adjust_data* am;
1124
1252
            ipsep_options opt;
1125
 
            pointf nsize[nv];
 
1253
            pointf* nsize;
1126
1254
            cluster_data *cs = (cluster_data*)cluster_map(mg,g);
 
1255
            nsize = N_GNEW(nv, pointf);
1127
1256
            opt.edge_gap = lgap;
1128
1257
#ifdef MOSEK
1129
1258
            opt.mosek = 0;
1135
1264
                opt.diredges = 1;
1136
1265
                if(Verbose)
1137
1266
                    fprintf(stderr,"Generating Edge Constraints...\n");
1138
 
            } else if (str && !strncasecmp(str,"hier",4)) {
 
1267
            } else if (str && !strncasecmp(str,"hier",4)) {
1139
1268
                opt.diredges = 2;
1140
1269
                if(Verbose)
1141
1270
                    fprintf(stderr,"Generating DiG-CoLa Edge Constraints...\n");
1142
1271
            }
1143
1272
            else opt.diredges = 0;
1144
 
            am = graphAdjustMode (g);
1145
1273
            if (am->mode == AM_IPSEP) {
1146
1274
                opt.noverlap = 1;
1147
1275
                if(Verbose)
1176
1304
 
1177
1305
            stress_majorization_cola(gp, nv, ne, coords, nodes, Ndim, model, MaxIter, &opt);
1178
1306
            freeClusterData(cs);
 
1307
            free (nsize);
1179
1308
        }
1180
1309
#endif
1181
1310
    }
1216
1345
    freeGraphData(gp);
1217
1346
}
1218
1347
 
 
1348
/* mds_model:
 
1349
 * Assume the matrix already contains shortest path values.
 
1350
 * Use the actual lengths provided the input for edges.
 
1351
 */
 
1352
static void mds_model(graph_t * g, int nG)
 
1353
{
 
1354
    long i, j;
 
1355
    node_t *v;
 
1356
    edge_t *e;
 
1357
 
 
1358
    for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
 
1359
        for (e = agfstout(g, v); e; e = agnxtout(g, e)) {
 
1360
            i = AGID(agtail(e));
 
1361
            j = AGID(aghead(e));
 
1362
            if (i == j)
 
1363
                continue;
 
1364
            GD_dist(g)[i][j] = GD_dist(g)[j][i] = ED_dist(e);
 
1365
        }
 
1366
    }
 
1367
}
 
1368
 
1219
1369
/* kkNeato:
1220
1370
 * Solve using gradient descent a la Kamada-Kawai.
1221
1371
 */
1227
1377
        if (!circuit_model(g, nG)) {
1228
1378
            agerr(AGWARN,
1229
1379
                  "graph %s is disconnected. Hence, the circuit model\n",
1230
 
                  g->name);
 
1380
                  agnameof(g));
1231
1381
            agerr(AGPREV,
1232
1382
                  "is undefined. Reverting to the shortest path model.\n");
1233
1383
            agerr(AGPREV,
1235
1385
            agerr(AGPREV, "the graph into connected components.\n");
1236
1386
            shortest_path(g, nG);
1237
1387
        }
 
1388
    } else if (model == MODEL_MDS) {
 
1389
        shortest_path(g, nG);
 
1390
        mds_model(g, nG);
1238
1391
    } else
1239
1392
        shortest_path(g, nG);
1240
1393
    initial_positions(g, nG);
1250
1403
/* neatoLayout:
1251
1404
 * Use stress optimization to layout a single component
1252
1405
 */
1253
 
void neatoLayout(Agraph_t * mg, Agraph_t * g, int layoutMode, int layoutModel)
 
1406
static void 
 
1407
neatoLayout(Agraph_t * mg, Agraph_t * g, int layoutMode, int layoutModel,
 
1408
  adjust_data* am)
1254
1409
{
1255
1410
    int nG;
1256
1411
    char *str;
1266
1421
    if ((nG < 2) || (MaxIter <=0))
1267
1422
        return;
1268
1423
    if (layoutMode)
1269
 
        majorization(mg, g, nG, layoutMode, layoutModel, Ndim, MaxIter);
 
1424
        majorization(mg, g, nG, layoutMode, layoutModel, Ndim, MaxIter, am);
1270
1425
    else
1271
1426
        kkNeato(g, nG, layoutModel);
1272
1427
}
1275
1430
 * If dimension == 3 and z attribute is declared, 
1276
1431
 * attach z value to nodes if not defined.
1277
1432
 */
1278
 
static void
1279
 
addZ (Agraph_t* g)
 
1433
static void addZ (Agraph_t* g)
1280
1434
{
1281
1435
    node_t* n;
1282
1436
    char    buf[BUFSIZ];
1283
1437
 
1284
1438
    if ((Ndim >= 3) && N_z) { 
1285
1439
        for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
1286
 
            sprintf(buf, "%d", POINTS(ND_pos(n)[2]));
 
1440
            sprintf(buf, "%lf", POINTS_PER_INCH * (ND_pos(n)[2]));
 
1441
#ifndef WITH_CGRAPH
1287
1442
            agxset(n, N_z->index, buf);
 
1443
#else /* WITH_CGRAPH */
 
1444
            agxset(n, N_z, buf);
 
1445
#endif /* WITH_CGRAPH */
1288
1446
        }
1289
1447
    }
1290
1448
}
1291
1449
 
 
1450
#ifdef IPSEPCOLA
 
1451
static void
 
1452
addCluster (graph_t* g)
 
1453
{
 
1454
    graph_t *subg;
 
1455
#ifndef WITH_CGRAPH
 
1456
    graph_t *mg;
 
1457
    node_t *mm, *mn;
 
1458
    edge_t *me;
 
1459
    mm = g->meta_node;
 
1460
    mg = agraphof(mm);
 
1461
    for (me = agfstout(mg, mm); me; me = agnxtout(mg, me)) {
 
1462
        mn = aghead(me);
 
1463
        subg = agusergraph(mn);
 
1464
#else
 
1465
    for (subg = agfstsubg(agroot(g)); subg; subg = agnxtsubg(subg)) {
 
1466
#endif
 
1467
        if (!strncmp(agnameof(subg), "cluster", 7)) {
 
1468
            add_cluster(g, subg);
 
1469
            compute_bb(subg);
 
1470
        }
 
1471
   }
 
1472
}
 
1473
#endif
 
1474
 
1292
1475
/* neato_layout:
1293
1476
 */
1294
1477
void neato_layout(Agraph_t * g)
1296
1479
    int layoutMode;
1297
1480
    int model;
1298
1481
    pack_mode mode;
 
1482
    pack_info pinfo;
 
1483
    adjust_data am;
1299
1484
 
1300
1485
    if (Nop) {
1301
1486
        int save = PSinputscale;
1305
1490
        addZ (g);
1306
1491
        ret = init_nop(g, 1);
1307
1492
        PSinputscale = save;
1308
 
        if (ret) {
 
1493
        if (ret < 0) {
1309
1494
            agerr(AGPREV, "as required by the -n flag\n");
1310
 
            exit(1);
 
1495
            return;
1311
1496
        }
 
1497
        else gv_postprocess(g, ret);
1312
1498
    } else {
1313
1499
        neato_init_graph(g);
1314
1500
        layoutMode = neatoMode(g);
 
1501
        graphAdjustMode (g, &am, 0);
1315
1502
        model = neatoModel(g);
1316
 
        mode = getPackMode(g, l_undef);
 
1503
        mode = getPackModeInfo (g, l_undef, &pinfo);
1317
1504
        Pack = getPack(g, -1, CL_OFFSET);
1318
1505
        /* pack if just packmode defined. */
1319
1506
        if (mode == l_undef) {
1322
1509
             */
1323
1510
            if ((Pack < 0) && layoutMode)
1324
1511
                Pack = CL_OFFSET;
1325
 
            mode = l_node;
 
1512
            pinfo.mode = l_node;
1326
1513
        } else if (Pack < 0)
1327
1514
            Pack = CL_OFFSET;
1328
1515
        if (Pack >= 0) {
1330
1517
            graph_t **cc;
1331
1518
            int n_cc;
1332
1519
            int i;
1333
 
            pack_info pinfo;
1334
1520
            boolean pin;
1335
1521
 
1336
1522
            cc = pccomps(g, &n_cc, cc_pfx, &pin);
1338
1524
            for (i = 0; i < n_cc; i++) {
1339
1525
                gc = cc[i];
1340
1526
                nodeInduce(gc);
1341
 
                neatoLayout(g, gc, layoutMode, model);
1342
 
                adjustNodes(gc);
 
1527
                neatoLayout(g, gc, layoutMode, model, &am);
 
1528
                removeOverlapWith(gc, &am);
 
1529
                setEdgeType (gc, ET_LINE);
 
1530
                spline_edges(gc);
1343
1531
            }
1344
1532
            if (n_cc > 1) {
1345
1533
                boolean *bp;
1349
1537
                } else
1350
1538
                    bp = 0;
1351
1539
                pinfo.margin = Pack;
1352
 
                pinfo.doSplines = 0;
1353
 
                pinfo.mode = mode;
1354
1540
                pinfo.fixed = bp;
1355
 
                packGraphs(n_cc, cc, 0, &pinfo);
 
1541
                pinfo.doSplines = 1;
 
1542
                packGraphs(n_cc, cc, g, &pinfo);
1356
1543
                if (bp)
1357
1544
                    free(bp);
1358
1545
            }
1359
1546
            compute_bb(g);
1360
1547
            addZ (g);
1361
 
            spline_edges(g);
1362
1548
 
1363
1549
            /* cleanup and remove component subgraphs */
1364
1550
            for (i = 0; i < n_cc; i++) {
1368
1554
            }
1369
1555
            free (cc);
1370
1556
#ifdef IPSEPCOLA
1371
 
            {
1372
 
                graph_t *mg, *subg;
1373
 
                node_t *mm, *mn;
1374
 
                edge_t *me;
1375
 
                mm = g->meta_node;
1376
 
                mg = mm->graph;
1377
 
                for (me = agfstout(mg, mm); me; me = agnxtout(mg, me)) {
1378
 
                    mn = me->head;
1379
 
                    subg = agusergraph(mn);
1380
 
                    if (!strncmp(subg->name, "cluster", 7)) {
1381
 
                        add_cluster(g,subg);
1382
 
                        compute_bb(subg);
1383
 
                    }
1384
 
                }
1385
 
            }
 
1557
            addCluster (g);
1386
1558
#endif
1387
1559
        } else {
1388
 
            neatoLayout(g, g, layoutMode, model);
1389
 
            adjustNodes(g);
 
1560
            neatoLayout(g, g, layoutMode, model, &am);
 
1561
            removeOverlapWith(g, &am);
1390
1562
            addZ (g);
1391
1563
            spline_edges(g);
1392
1564
        }
 
1565
        dotneato_postprocess(g);
1393
1566
    }
1394
 
    dotneato_postprocess(g);
1395
1567
}