Graphviz  2.41.20170921.2350
conc.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 /*
16  * build edge_t concentrators for parallel edges with a common endpoint
17  */
18 
19 #include "dot.h"
20 #include <setjmp.h>
21 
22 #define UP 0
23 #define DOWN 1
24 
25 static jmp_buf jbuf;
26 
27 static boolean samedir(edge_t * e, edge_t * f)
28 {
29  edge_t *e0, *f0;
30 
31  for (e0 = e; ED_edge_type(e0) != NORMAL; e0 = ED_to_orig(e0));
32  for (f0 = f; ED_edge_type(f0) != NORMAL; f0 = ED_to_orig(f0));
33  if (ED_conc_opp_flag(e0))
34  return FALSE;
35  if (ED_conc_opp_flag(f0))
36  return FALSE;
37  return ((ND_rank(agtail(f0)) - ND_rank(aghead(f0)))
38  * (ND_rank(agtail(e0)) - ND_rank(aghead(e0))) > 0);
39 }
40 
41 static boolean downcandidate(node_t * v)
42 {
43  return ((ND_node_type(v) == VIRTUAL) && (ND_in(v).size == 1)
44  && (ND_out(v).size == 1) && (ND_label(v) == NULL));
45 }
46 
47 static boolean bothdowncandidates(node_t * u, node_t * v)
48 {
49  edge_t *e, *f;
50  e = ND_in(u).list[0];
51  f = ND_in(v).list[0];
52  if (downcandidate(v) && (agtail(e) == agtail(f))) {
53  return samedir(e, f)
54  && (portcmp(ED_tail_port(e), ED_tail_port(f)) == 0);
55  }
56  return FALSE;
57 }
58 
59 static boolean upcandidate(node_t * v)
60 {
61  return ((ND_node_type(v) == VIRTUAL) && (ND_out(v).size == 1)
62  && (ND_in(v).size == 1) && (ND_label(v) == NULL));
63 }
64 
65 static boolean bothupcandidates(node_t * u, node_t * v)
66 {
67  edge_t *e, *f;
68  e = ND_out(u).list[0];
69  f = ND_out(v).list[0];
70  if (upcandidate(v) && (aghead(e) == aghead(f))) {
71  return samedir(e, f)
72  && (portcmp(ED_head_port(e), ED_head_port(f)) == 0);
73  }
74  return FALSE;
75 }
76 
77 static void mergevirtual(graph_t * g, int r, int lpos, int rpos, int dir)
78 {
79  int i, k;
80  node_t *left, *right;
81  edge_t *e, *f, *e0;
82 
83  left = GD_rank(g)[r].v[lpos];
84  /* merge all right nodes into the leftmost one */
85  for (i = lpos + 1; i <= rpos; i++) {
86  right = GD_rank(g)[r].v[i];
87  if (dir == DOWN) {
88  while ((e = ND_out(right).list[0])) {
89  for (k = 0; (f = ND_out(left).list[k]); k++)
90  if (aghead(f) == aghead(e))
91  break;
92  if (f == NULL)
93  f = virtual_edge(left, aghead(e), e);
94  while ((e0 = ND_in(right).list[0])) {
95  merge_oneway(e0, f);
96  /*ED_weight(f) += ED_weight(e0); */
97  delete_fast_edge(e0);
98  }
100  }
101  } else {
102  while ((e = ND_in(right).list[0])) {
103  for (k = 0; (f = ND_in(left).list[k]); k++)
104  if (agtail(f) == agtail(e))
105  break;
106  if (f == NULL)
107  f = virtual_edge(agtail(e), left, e);
108  while ((e0 = ND_out(right).list[0])) {
109  merge_oneway(e0, f);
110  delete_fast_edge(e0);
111  }
112  delete_fast_edge(e);
113  }
114  }
115  assert(ND_in(right).size + ND_out(right).size == 0);
116  delete_fast_node(g, right);
117  }
118  k = lpos + 1;
119  i = rpos + 1;
120  while (i < GD_rank(g)[r].n) {
121  node_t *n;
122  n = GD_rank(g)[r].v[k] = GD_rank(g)[r].v[i];
123  ND_order(n) = k;
124  k++;
125  i++;
126  }
127  GD_rank(g)[r].n = k;
128  GD_rank(g)[r].v[k] = NULL;
129 }
130 
131 static void infuse(graph_t * g, node_t * n)
132 {
133  node_t *lead;
134 
135  lead = GD_rankleader(g)[ND_rank(n)];
136  if ((lead == NULL) || (ND_order(lead) > ND_order(n)))
137  GD_rankleader(g)[ND_rank(n)] = n;
138 }
139 
140 static void rebuild_vlists(graph_t * g)
141 {
142  int c, i, r, maxi;
143  node_t *n, *lead;
144  edge_t *e, *rep;
145 
146  for (r = GD_minrank(g); r <= GD_maxrank(g); r++)
147  GD_rankleader(g)[r] = NULL;
148  dot_scan_ranks(g);
149  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
150  infuse(g, n);
151  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
152  for (rep = e; ED_to_virt(rep); rep = ED_to_virt(rep));
153  while (ND_rank(aghead(rep)) < ND_rank(aghead(e))) {
154  infuse(g, aghead(rep));
155  rep = ND_out(aghead(rep)).list[0];
156  }
157  }
158  }
159 
160  for (r = GD_minrank(g); r <= GD_maxrank(g); r++) {
161  lead = GD_rankleader(g)[r];
162  if (GD_rank(dot_root(g))[r].v[ND_order(lead)] != lead) {
163  agerr(AGERR, "rebuiltd_vlists: rank lead %s not in order %d of rank %d\n",
164  agnameof(lead), ND_order(lead), r);
165  longjmp(jbuf, 1);
166  }
167  GD_rank(g)[r].v =
168  GD_rank(dot_root(g))[r].v + ND_order((GD_rankleader(g)[r]));
169  maxi = -1;
170  for (i = 0; i < GD_rank(g)[r].n; i++) {
171  if ((n = GD_rank(g)[r].v[i]) == NULL)
172  break;
173  if (ND_node_type(n) == NORMAL) {
174  if (agcontains(g, n))
175  maxi = i;
176  else
177  break;
178  } else {
179  edge_t *e;
180  for (e = ND_in(n).list[0]; e && ED_to_orig(e);
181  e = ED_to_orig(e));
182  if (e && (agcontains(g, agtail(e)))
183  && agcontains(g, aghead(e)))
184  maxi = i;
185  }
186  }
187  if (maxi == -1)
188  agerr(AGWARN, "degenerate concentrated rank %s,%d\n", agnameof(g),
189  r);
190  GD_rank(g)[r].n = maxi + 1;
191  }
192 
193  for (c = 1; c <= GD_n_cluster(g); c++)
194  rebuild_vlists(GD_clust(g)[c]);
195 }
196 
198 {
199  int c, r, leftpos, rightpos;
200  node_t *left, *right;
201 
202  if (GD_maxrank(g) - GD_minrank(g) <= 1)
203  return;
204  /* this is the downward looking pass. r is a candidate rank. */
205  for (r = 1; GD_rank(g)[r + 1].n; r++) {
206  for (leftpos = 0; leftpos < GD_rank(g)[r].n; leftpos++) {
207  left = GD_rank(g)[r].v[leftpos];
208  if (downcandidate(left) == FALSE)
209  continue;
210  for (rightpos = leftpos + 1; rightpos < GD_rank(g)[r].n;
211  rightpos++) {
212  right = GD_rank(g)[r].v[rightpos];
213  if (bothdowncandidates(left, right) == FALSE)
214  break;
215  }
216  if (rightpos - leftpos > 1)
217  mergevirtual(g, r, leftpos, rightpos - 1, DOWN);
218  }
219  }
220  /* this is the corresponding upward pass */
221  while (r > 0) {
222  for (leftpos = 0; leftpos < GD_rank(g)[r].n; leftpos++) {
223  left = GD_rank(g)[r].v[leftpos];
224  if (upcandidate(left) == FALSE)
225  continue;
226  for (rightpos = leftpos + 1; rightpos < GD_rank(g)[r].n;
227  rightpos++) {
228  right = GD_rank(g)[r].v[rightpos];
229  if (bothupcandidates(left, right) == FALSE)
230  break;
231  }
232  if (rightpos - leftpos > 1)
233  mergevirtual(g, r, leftpos, rightpos - 1, UP);
234  }
235  r--;
236  }
237  if (setjmp(jbuf)) {
238  agerr(AGPREV, "concentrate=true may not work correctly.\n");
239  return;
240  }
241  for (c = 1; c <= GD_n_cluster(g); c++)
242  rebuild_vlists(GD_clust(g)[c]);
243 }
int portcmp(port p0, port p1)
Definition: dotsplines.c:116
#define ND_rank(n)
Definition: types.h:529
Definition: cgraph.h:388
void delete_fast_node(Agraph_t *, Agnode_t *)
Definition: fastgr.c:229
#define GD_rankleader(g)
Definition: types.h:405
#define GD_n_cluster(g)
Definition: types.h:396
#define ND_node_type(n)
Definition: types.h:518
#define ED_head_port(e)
Definition: types.h:591
void dot_scan_ranks(graph_t *g)
Definition: rank.c:204
#define assert(x)
Definition: cghdr.h:47
#define ED_to_orig(e)
Definition: types.h:601
#define UP
Definition: conc.c:22
#define DOWN
Definition: conc.c:23
int agerr(agerrlevel_t level, const char *fmt,...)
Definition: agerror.c:141
void delete_fast_edge(Agedge_t *)
Definition: fastgr.c:115
CGRAPH_API int agcontains(Agraph_t *, void *)
Definition: obj.c:245
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
void dot_concentrate(graph_t *g)
Definition: conc.c:197
#define ND_label(n)
Definition: types.h:509
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition: fastgr.c:199
#define ED_conc_opp_flag(e)
Definition: types.h:582
Definition: cgraph.h:388
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
#define ED_tail_port(e)
Definition: types.h:600
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
#define ND_order(n)
Definition: types.h:520
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define VIRTUAL
Definition: const.h:28
#define GD_maxrank(g)
Definition: types.h:389
void merge_oneway(Agedge_t *, Agedge_t *)
Definition: fastgr.c:334
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define GD_clust(g)
Definition: types.h:364
Agraph_t * dot_root(void *p)
Definition: dotinit.c:513
#define ED_to_virt(e)
Definition: types.h:602
#define NULL
Definition: logic.h:39
#define ND_in(n)
Definition: types.h:507
#define right(i)
Definition: closest.c:87
#define ND_out(n)
Definition: types.h:522
#define left
Definition: dthdr.h:16
#define GD_minrank(g)
Definition: types.h:391
#define GD_rank(g)
Definition: types.h:404
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define NORMAL
Definition: const.h:27
Definition: cgraph.h:388
#define ED_edge_type(e)
Definition: types.h:585
#define FALSE
Definition: cgraph.h:35