Graphviz  2.41.20170921.2350
circular.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 
15 #include "circular.h"
16 #include "blocktree.h"
17 #include "circpos.h"
18 #include <string.h>
19 
20 #define MINDIST 1.0
21 
22 /* initGraphAttrs:
23  * Set attributes based on original root graph.
24  * This is obtained by taking a node of g, finding its node
25  * in the original graph, and finding that node's graph.
26  */
27 static void initGraphAttrs(Agraph_t * g, circ_state * state)
28 {
29  static Agraph_t *rootg;
30  static attrsym_t *N_artpos;
31  static attrsym_t *N_root;
32  static attrsym_t *G_mindist;
33  static char *rootname;
34  Agraph_t *rg;
35  node_t *n = agfstnode(g);
36 
37  rg = agraphof(ORIGN(n));
38  if (rg != rootg) { /* new root graph */
39  state->blockCount = 0;
40  rootg = rg;
41  G_mindist = agattr(rootg,AGRAPH, "mindist", NULL);
42  N_artpos = agattr(rootg,AGNODE, "articulation_pos", NULL);
43  N_root = agattr(rootg,AGNODE, "root", NULL);
44  }
45  rootname = agget(rootg, "root");
46  initBlocklist(&state->bl);
47  state->orderCount = 1;
48  state->min_dist = late_double(rootg, G_mindist, MINDIST, 0.0);
49  state->N_artpos = N_artpos;
50  state->N_root = N_root;
51  state->rootname = rootname;
52 }
53 
54 /* cleanup:
55  * We need to cleanup objects created in initGraphAttrs
56  * and all blocks. All graph objects are components of the
57  * initial derived graph and will be freed when it is closed.
58  */
59 static void cleanup(block_t * root, circ_state * sp)
60 {
61  freeBlocktree(root);
62 }
63 
64 static block_t*
65 createOneBlock(Agraph_t * g, circ_state * state)
66 {
67  Agraph_t *subg;
68  char name[SMALLBUF];
69  block_t *bp;
70  Agnode_t* n;
71 
72  sprintf(name, "_block_%d", state->blockCount++);
73  subg = agsubg(g, name, 1);
74  bp = mkBlock(subg);
75 
76  for (n = agfstnode(g); n; n = agnxtnode(g,n)) {
77  agsubnode(bp->sub_graph, n, 1);
78  BLOCK(n) = bp;
79  }
80 
81  return bp;
82 }
83 
84 /* circularLayout:
85  * Do circular layout of g.
86  * Assume g is strict.
87  * g is a "connected" component of the derived graph of the
88  * original graph.
89  * We make state static so that it keeps a record of block numbers used
90  * in a graph; it gets reset when a new root graph is used.
91  */
92 void circularLayout(Agraph_t * g, Agraph_t* realg)
93 {
94  block_t *root;
95  static circ_state state;
96 
97  if (agnnodes(g) == 1) {
98  Agnode_t *n = agfstnode(g);
99  ND_pos(n)[0] = 0;
100  ND_pos(n)[1] = 0;
101  return;
102  }
103 
104  initGraphAttrs(g, &state);
105 
106  if (mapbool(agget(realg, "oneblock")))
107  root = createOneBlock(g, &state);
108  else
109  root = createBlocktree(g, &state);
110  circPos(g, root, &state);
111 
112  cleanup(root, &state);
113 }
114 
115 #ifdef DEBUG
116 void prGraph(Agraph_t * g)
117 {
118  Agnode_t *n;
119  Agedge_t *e;
120 
121  fprintf(stderr, "%s\n", agnameof(g));
122  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
123  fprintf(stderr, "%s (%x)\n", agnameof(n), (unsigned int) n);
124  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
125  fprintf(stderr, "%s", agnameof(n));
126  fprintf(stderr, " -- %s (%x)\n", agnameof(aghead(e)),
127  (unsigned int) e);
128  }
129  }
130 }
131 
132 cdata *cvt(Agnode_t * n)
133 {
134  return DATA(n);
135 }
136 
137 void prData(Agnode_t * n, int pass)
138 {
139  char *pname;
140  char *bname;
141  char *tname;
142  char *name1;
143  char *name2;
144  int dist1, dist2;
145 
146  if (PARENT(n))
147  pname = agnameof(PARENT(n));
148  else
149  pname = "<P0>";
150  if (BLOCK(n))
151  bname = agnameof(BLOCK(n)->sub_graph);
152  else {
153  pname = "<B0>";
154  bname = "";
155  }
156  fprintf(stderr, "%s: %x %s %s ", agnameof(n), FLAGS(n), pname, bname);
157  switch (pass) {
158  case 0:
159  fprintf(stderr, "%d %d\n", VAL(n), LOWVAL(n));
160  break;
161  case 1:
162  if (TPARENT(n))
163  tname = agnameof(TPARENT(n));
164  else
165  tname = "<ROOT>";
166  dist1 = DISTONE(n);
167  if (dist1 > 0)
168  name1 = agnameof(LEAFONE(n));
169  else
170  name1 = "<null>";
171  dist2 = DISTTWO(n);
172  if (dist2 > 0)
173  name2 = agnameof(LEAFTWO(n));
174  else
175  name2 = "<null>";
176  fprintf(stderr, "%s %s %d %s %d\n", tname, name1, dist1, name2,
177  dist2);
178  break;
179  default:
180  fprintf(stderr, "%d\n", POSITION(n));
181  break;
182  }
183 }
184 #endif
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
void circPos(Agraph_t *g, block_t *sn, circ_state *state)
Definition: circpos.c:475
void circularLayout(Agraph_t *g, Agraph_t *realg)
Definition: circular.c:92
#define LOWVAL(n)
Definition: circular.h:93
#define SMALLBUF
Definition: const.h:17
attrsym_t * N_root
Definition: circular.h:25
void initBlocklist(blocklist_t *bl)
Definition: block.c:20
#define ND_pos(n)
Definition: types.h:526
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
int blockCount
Definition: circular.h:23
#define TPARENT(n)
Definition: circular.h:95
block_t * createBlocktree(Agraph_t *g, circ_state *state)
Definition: blocktree.c:181
#define PARENT(n)
Definition: circular.h:89
Definition: circular.h:44
#define DISTTWO(n)
Definition: circular.h:99
int orderCount
Definition: circular.h:22
char * agget(void *obj, char *name)
Definition: attr.c:428
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
#define LEAFONE(n)
Definition: circular.h:96
CGRAPH_API Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition: subg.c:52
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
double min_dist
Definition: circular.h:27
Agraph_t * sub_graph
Definition: block.h:33
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
char * rootname
Definition: circular.h:26
#define MINDIST
Definition: circular.c:20
block_t * mkBlock(Agraph_t *g)
Definition: block.c:41
attrsym_t * N_artpos
Definition: circular.h:24
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define BLOCK(n)
Definition: circular.h:90
Definition: block.h:30
#define AGNODE
Definition: cgraph.h:101
#define FLAGS(n)
Definition: circular.h:88
COORD dist2(Ppoint_t, Ppoint_t)
Definition: visibility.c:213
blocklist_t bl
Definition: circular.h:21
#define NULL
Definition: logic.h:39
void freeBlocktree(block_t *bp)
Definition: blocktree.c:224
double late_double(void *obj, attrsym_t *attr, double def, double low)
Definition: utils.c:87
#define VAL(n)
Definition: circular.h:92
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
boolean mapbool(char *p)
Definition: utils.c:472
#define ORIGN(n)
Definition: circular.h:87
#define LEAFTWO(n)
Definition: circular.h:97
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define POSITION(n)
Definition: circular.h:100
#define DATA(n)
Definition: circular.h:85
#define DISTONE(n)
Definition: circular.h:98
CGRAPH_API Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
#define AGRAPH
Definition: cgraph.h:100