Graphviz  2.35.20130930.0449
class1.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  * Classify edges for rank assignment phase to
17  * create temporary edges.
18  */
19 
20 #include "dot.h"
21 
22 
24 {
25  char *constr;
26 
27 #ifndef WITH_CGRAPH
28  if (E_constr && (constr = agxget(e, E_constr->index))) {
29 #else /* WITH_CGRAPH */
30  if (E_constr && (constr = agxget(e, E_constr))) {
31 #endif /* WITH_CGRAPH */
32  if (constr[0] && mapbool(constr) == FALSE)
33  return TRUE;
34  }
35  return FALSE;
36 }
37 
38 static void
39 interclust1(graph_t * g, node_t * t, node_t * h, edge_t * e)
40 {
41  node_t *v, *t0, *h0;
42  int offset, t_len, h_len, t_rank, h_rank;
43  edge_t *rt, *rh;
44 
45  if (ND_clust(agtail(e)))
46  t_rank = ND_rank(agtail(e)) - ND_rank(GD_leader(ND_clust(agtail(e))));
47  else
48  t_rank = 0;
49  if (ND_clust(aghead(e)))
50  h_rank = ND_rank(aghead(e)) - ND_rank(GD_leader(ND_clust(aghead(e))));
51  else
52  h_rank = 0;
53  offset = ED_minlen(e) + t_rank - h_rank;
54  if (offset > 0) {
55  t_len = 0;
56  h_len = offset;
57  } else {
58  t_len = -offset;
59  h_len = 0;
60  }
61 
62  v = virtual_node(g);
64  t0 = UF_find(t);
65  h0 = UF_find(h);
66  rt = make_aux_edge(v, t0, t_len, CL_BACK * ED_weight(e));
67  rh = make_aux_edge(v, h0, h_len, ED_weight(e));
68  ED_to_orig(rt) = ED_to_orig(rh) = e;
69 }
70 void class1(graph_t * g)
71 {
72  node_t *n, *t, *h;
73  edge_t *e, *rep;
74 
75  mark_clusters(g);
76  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
77  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
78 
79  /* skip edges already processed */
80  if (ED_to_virt(e))
81  continue;
82 
83  /* skip edges that we want to ignore in this phase */
84  if (nonconstraint_edge(e))
85  continue;
86 
87  t = UF_find(agtail(e));
88  h = UF_find(aghead(e));
89 
90  /* skip self, flat, and intra-cluster edges */
91  if (t == h)
92  continue;
93 
94 
95  /* inter-cluster edges require special treatment */
96  if (ND_clust(t) || ND_clust(h)) {
97  interclust1(g, agtail(e), aghead(e), e);
98  continue;
99  }
100 
101  if ((rep = find_fast_edge(t, h)))
102  merge_oneway(e, rep);
103  else
104  virtual_edge(t, h, e);
105 
106 #ifdef NOTDEF
107  if ((t == agtail(e)) && (h == aghead(e))) {
108  if (rep = find_fast_edge(t, h))
109  merge_oneway(e, rep);
110  else
111  virtual_edge(t, h, e);
112  } else {
113  f = agfindedge(g, t, h);
114  if (f && (ED_to_virt(f) == NULL))
115  rep = virtual_edge(t, h, f);
116  else
117  rep = find_fast_edge(t, h);
118  if (rep)
119  merge_oneway(e, rep);
120  else
121  virtual_edge(t, h, e);
122  }
123 #endif
124  }
125  }
126 }
127