Graphviz  2.41.20170921.2350
sameport.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 /* vladimir@cs.ualberta.ca, 9-Dec-1997
16  * merge edges with specified samehead/sametail onto the same port
17  */
18 
19 #include "dot.h"
20 
21 
22 #define MAXSAME 5 /* max no of same{head,tail} groups on a node */
23 
24 typedef struct same_t {
25  char *id; /* group id */
26  elist l; /* edges in the group */
27  int n_arr; /* number of edges with arrows */
28  double arr_len; /* arrow length of an edge in the group */
29 } same_t;
30 
31 static int sameedge(same_t * same, int n_same, node_t * n, edge_t * e, char *id);
32 static void sameport(node_t * u, elist * l, double arr_len);
33 
35 /* merge edge ports in G */
36 {
37  node_t *n;
38  edge_t *e;
39  char *id;
40  same_t samehead[MAXSAME];
41  same_t sametail[MAXSAME];
42  int n_samehead; /* number of same_t groups on current node */
43  int n_sametail; /* number of same_t groups on current node */
44  int i;
45 
46  E_samehead = agattr(g, AGEDGE, "samehead",(char*)0);
47  E_sametail = agattr(g, AGEDGE, "sametail",(char*)0);
48  if (!(E_samehead || E_sametail))
49  return;
50  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
51  n_samehead = n_sametail = 0;
52  for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
53  if (aghead(e) == agtail(e)) continue; /* Don't support same* for loops */
54  if (aghead(e) == n && E_samehead &&
55  (id = agxget(e, E_samehead))[0])
56  n_samehead = sameedge(samehead, n_samehead, n, e, id);
57  else if (agtail(e) == n && E_sametail &&
58  (id = agxget(e, E_sametail))[0])
59  n_sametail = sameedge(sametail, n_sametail, n, e, id);
60  }
61  for (i = 0; i < n_samehead; i++) {
62  if (samehead[i].l.size > 1)
63  sameport(n, &samehead[i].l, samehead[i].arr_len);
64  free_list(samehead[i].l);
65  /* I sure hope I don't need to free the char* id */
66  }
67  for (i = 0; i < n_sametail; i++) {
68  if (sametail[i].l.size > 1)
69  sameport(n, &sametail[i].l, sametail[i].arr_len);
70  free_list(sametail[i].l);
71  /* I sure hope I don't need to free the char* id */
72  }
73  }
74 }
75 
76 static int sameedge(same_t * same, int n_same, node_t * n, edge_t * e, char *id)
77 /* register E in the SAME structure of N under ID. Uses static int N_SAME */
78 {
79  int i, sflag, eflag, flag;
80 
81  for (i = 0; i < n_same; i++)
82  if (streq(same[i].id, id)) {
83  elist_append(e, same[i].l);
84  goto set_arrow;
85  }
86  if (++n_same > MAXSAME) {
87  n_same--;
88  agerr(AGERR, "too many (> %d) same{head,tail} groups for node %s\n",
89  MAXSAME, agnameof(n));
90  return n_same;
91  }
92  alloc_elist(1, same[i].l);
93  elist_fastapp(e, same[i].l);
94  same[i].id = id;
95  same[i].n_arr = 0;
96  same[i].arr_len = 0;
97  set_arrow:
98  arrow_flags(e, &sflag, &eflag);
99  if ((flag = aghead(e) == n ? eflag : sflag))
100  same[i].arr_len =
101  /* only consider arrows if there's exactly one arrow */
102  (++same[i].n_arr == 1) ? arrow_length(e, flag) : 0;
103  return n_same;
104 }
105 
106 static void sameport(node_t * u, elist * l, double arr_len)
107 /* make all edges in L share the same port on U. The port is placed on the
108  node boundary and the average angle between the edges. FIXME: this assumes
109  naively that the edges are straight lines, which is wrong if they are long.
110  In that case something like concentration could be done.
111 
112  An arr_port is also computed that's ARR_LEN away from the node boundary.
113  It's used for edges that don't themselves have an arrow.
114 */
115 {
116  node_t *v;
117  edge_t *e, *f;
118  int i;
119  double x = 0, y = 0, x1, y1, x2, y2, r;
120  port prt;
121  int sflag, eflag;
122 #ifdef OLD
123  int ht;
124  port arr_prt;
125 #endif
126 
127  /* Compute the direction vector (x,y) of the average direction. We compute
128  with direction vectors instead of angles because else we have to first
129  bring the angles within PI of each other. av(a,b)!=av(a,b+2*PI) */
130  for (i = 0; i < l->size; i++) {
131  e = l->list[i];
132  if (aghead(e) == u)
133  v = agtail(e);
134  else
135  v = aghead(e);
136  x1 = ND_coord(v).x - ND_coord(u).x;
137  y1 = ND_coord(v).y - ND_coord(u).y;
138  r = hypot(x1, y1);
139  x += x1 / r;
140  y += y1 / r;
141  }
142  r = hypot(x, y);
143  x /= r;
144  y /= r;
145 
146  /* (x1,y1),(x2,y2) is a segment that must cross the node boundary */
147  x1 = ND_coord(u).x;
148  y1 = ND_coord(u).y; /* center of node */
149  r = MAX(ND_lw(u) + ND_rw(u), ND_ht(u) + GD_ranksep(agraphof(u))); /* far away */
150  x2 = x * r + ND_coord(u).x;
151  y2 = y * r + ND_coord(u).y;
152  { /* now move (x1,y1) to the node boundary */
153  pointf curve[4]; /* bezier control points for a straight line */
154  curve[0].x = x1;
155  curve[0].y = y1;
156  curve[1].x = (2 * x1 + x2) / 3;
157  curve[1].y = (2 * y1 + y2) / 3;
158  curve[2].x = (2 * x2 + x1) / 3;
159  curve[2].y = (2 * y2 + y1) / 3;
160  curve[3].x = x2;
161  curve[3].y = y2;
162 
163  shape_clip(u, curve);
164  x1 = curve[0].x - ND_coord(u).x;
165  y1 = curve[0].y - ND_coord(u).y;
166  }
167 
168  /* compute PORT on the boundary */
169  prt.p.x = ROUND(x1);
170  prt.p.y = ROUND(y1);
171  prt.bp = 0;
172  prt.order =
173  (MC_SCALE * (ND_lw(u) + prt.p.x)) / (ND_lw(u) + ND_rw(u));
174  prt.constrained = FALSE;
175  prt.defined = TRUE;
176  prt.clip = FALSE;
177  prt.dyna = FALSE;
178  prt.theta = 0;
179  prt.side = 0;
180  prt.name = NULL;
181 
182 #ifdef OBSOLETE
183 /* This is commented because a version of gcc cannot handle it otherwise.
184 This code appears obsolete and wrong. First, we don't use arr_prt
185 anymore, as we have previously ifdef'ed out the code below where it
186 is used. In addition, it resets the rank height. But we've already
187 positioned the nodes, so it can cause the new ht2, when added to a
188 node's y coordinate to give a value in the middle of the rank above.
189 This causes havoc when constructing box for spline routing.
190 See bug 419.
191 If we really want to make room for arrowheads, this should be done in
192 the general case that the user sets a small ranksep, and requires repositioning
193 nodes and maintaining equal separation when specified
194 */
195  /* compute ARR_PORT at a distance ARR_LEN away from the boundary */
196  if ((arr_prt.defined = arr_len && TRUE)) {
197  arr_prt.p.x = ROUND(x1 + x * arr_len);
198  arr_prt.p.y = ROUND(y1 + y * arr_len);
199  arr_prt.bp = 0;
200  arr_prt.side = 0;
201  arr_prt.constrained = FALSE;
202  arr_prt.order =
203  (MC_SCALE * (ND_lw_i(u) + arr_prt.p.x)) / (ND_lw_i(u) +
204  ND_rw_i(u));
205  /* adjust ht so that splines.c uses feasible boxes.
206  FIXME: I guess this adds an extra box for all edges in the rank */
207  if (u == l->list[0]->head) {
208  if (GD_rank(u->graph)[ND_rank(u)].ht2 <
209  (ht = ABS(arr_prt.p.y)))
210  GD_rank(u->graph)[ND_rank(u)].ht2 = ht;
211  } else {
212  if (GD_rank(u->graph)[ND_rank(u)].ht1 <
213  (ht = ABS(arr_prt.p.y)))
214  GD_rank(u->graph)[ND_rank(u)].ht1 = ht;
215  }
216  }
217 #endif
218 
219  /* assign one of the ports to every edge */
220  for (i = 0; i < l->size; i++) {
221  e = l->list[i];
222  arrow_flags(e, &sflag, &eflag);
223 #ifndef OBSOLETE
224  for (; e; e = ED_to_virt(e)) { /* assign to all virt edges of e */
225  for (f = e; f;
226  f = ED_edge_type(f) == VIRTUAL &&
227  ND_node_type(aghead(f)) == VIRTUAL &&
228  ND_out(aghead(f)).size == 1 ?
229  ND_out(aghead(f)).list[0] : NULL) {
230  if (aghead(f) == u)
231  ED_head_port(f) = prt;
232  if (agtail(f) == u)
233  ED_tail_port(f) = prt;
234  }
235  for (f = e; f;
236  f = ED_edge_type(f) == VIRTUAL &&
237  ND_node_type(agtail(f)) == VIRTUAL &&
238  ND_in(agtail(f)).size == 1 ?
239  ND_in(agtail(f)).list[0] : NULL) {
240  if (aghead(f) == u)
241  ED_head_port(f) = prt;
242  if (agtail(f) == u)
243  ED_tail_port(f) = prt;
244  }
245  }
246 #else
247  for (; e; e = ED_to_virt(e)) { /* assign to all virt edges of e */
248  if (aghead(e) == u)
249  ED_head_port(e) =
250  arr_port.defined && !eflag ? arr_prt : prt;
251  if (agtail(e) == u)
252  ED_tail_port(e) =
253  arr_port.defined && !sflag ? arr_prt : prt;
254  }
255 #endif
256  }
257 
258  ND_has_port(u) = TRUE; /* kinda pointless, because mincross is already done */
259 }
#define MAX(a, b)
Definition: agerror.c:17
#define ND_rank(n)
Definition: types.h:529
Definition: cgraph.h:388
#define ABS(a)
Definition: arith.h:45
Definition: types.h:67
Agsym_t * agattr(Agraph_t *g, int kind, char *name, char *value)
Definition: attr.c:324
#define elist_append(item, L)
Definition: types.h:272
char * id
Definition: sameport.c:25
boolean clip
Definition: types.h:75
#define ND_node_type(n)
Definition: types.h:518
#define ED_head_port(e)
Definition: types.h:591
#define ROUND(f)
Definition: arith.h:84
void dot_sameports(Agraph_t *)
Definition: sameport.c:34
Definition: geom.h:28
boxf * bp
Definition: types.h:70
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
unsigned char side
Definition: types.h:78
#define alloc_elist(n, L)
Definition: types.h:273
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
boolean constrained
Definition: types.h:74
void arrow_flags(Agedge_t *e, int *sflag, int *eflag)
Definition: arrows.c:198
double arrow_length(edge_t *e, int flag)
Definition: arrows.c:229
EXTERN Agsym_t * E_sametail
Definition: globals.h:107
#define GD_ranksep(g)
Definition: types.h:406
CGRAPH_API Agraph_t * agraphof(void *obj)
Definition: obj.c:185
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
double arr_len
Definition: sameport.c:28
unsigned char order
Definition: types.h:77
#define ED_tail_port(e)
Definition: types.h:600
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
Definition: types.h:261
#define ND_ht(n)
Definition: types.h:506
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
double y
Definition: geom.h:28
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define VIRTUAL
Definition: const.h:28
#define MAXSAME
Definition: sameport.c:22
#define ND_has_port(n)
Definition: types.h:501
#define ND_rw(n)
Definition: types.h:531
edge_t ** list
Definition: types.h:262
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define elist_fastapp(item, L)
Definition: types.h:271
double theta
Definition: types.h:69
struct same_t same_t
#define ED_to_virt(e)
Definition: types.h:602
#define ND_lw(n)
Definition: types.h:513
#define NULL
Definition: logic.h:39
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
#define ND_in(n)
Definition: types.h:507
double x
Definition: geom.h:28
#define ND_coord(n)
Definition: types.h:496
#define streq(s, t)
Definition: cghdr.h:52
void shape_clip(node_t *n, pointf curve[4])
Definition: splines.c:195
pointf p
Definition: types.h:68
char * name
Definition: types.h:82
#define ND_out(n)
Definition: types.h:522
#define MC_SCALE
Definition: const.h:100
int size
Definition: types.h:263
EXTERN Agsym_t * E_samehead
Definition: globals.h:107
elist l
Definition: sameport.c:26
int n_arr
Definition: sameport.c:27
#define GD_rank(g)
Definition: types.h:404
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
#define AGEDGE
Definition: cgraph.h:104
#define ED_edge_type(e)
Definition: types.h:585
#define FALSE
Definition: cgraph.h:35
#define free_list(L)
Definition: types.h:274
boolean dyna
Definition: types.h:76
boolean defined
Definition: types.h:73
#define TRUE
Definition: cgraph.h:38