Graphviz  2.39.20141218.0545
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  if (E_constr && (constr = agxget(e, E_constr))) {
28  if (constr[0] && mapbool(constr) == FALSE)
29  return TRUE;
30  }
31  return FALSE;
32 }
33 
34 static void
35 interclust1(graph_t * g, node_t * t, node_t * h, edge_t * e)
36 {
37  node_t *v, *t0, *h0;
38  int offset, t_len, h_len, t_rank, h_rank;
39  edge_t *rt, *rh;
40 
41  if (ND_clust(agtail(e)))
42  t_rank = ND_rank(agtail(e)) - ND_rank(GD_leader(ND_clust(agtail(e))));
43  else
44  t_rank = 0;
45  if (ND_clust(aghead(e)))
46  h_rank = ND_rank(aghead(e)) - ND_rank(GD_leader(ND_clust(aghead(e))));
47  else
48  h_rank = 0;
49  offset = ED_minlen(e) + t_rank - h_rank;
50  if (offset > 0) {
51  t_len = 0;
52  h_len = offset;
53  } else {
54  t_len = -offset;
55  h_len = 0;
56  }
57 
58  v = virtual_node(g);
60  t0 = UF_find(t);
61  h0 = UF_find(h);
62  rt = make_aux_edge(v, t0, t_len, CL_BACK * ED_weight(e));
63  rh = make_aux_edge(v, h0, h_len, ED_weight(e));
64  ED_to_orig(rt) = ED_to_orig(rh) = e;
65 }
66 void class1(graph_t * g)
67 {
68  node_t *n, *t, *h;
69  edge_t *e, *rep;
70 
71  mark_clusters(g);
72  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
73  for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
74 
75  /* skip edges already processed */
76  if (ED_to_virt(e))
77  continue;
78 
79  /* skip edges that we want to ignore in this phase */
80  if (nonconstraint_edge(e))
81  continue;
82 
83  t = UF_find(agtail(e));
84  h = UF_find(aghead(e));
85 
86  /* skip self, flat, and intra-cluster edges */
87  if (t == h)
88  continue;
89 
90 
91  /* inter-cluster edges require special treatment */
92  if (ND_clust(t) || ND_clust(h)) {
93  interclust1(g, agtail(e), aghead(e), e);
94  continue;
95  }
96 
97  if ((rep = find_fast_edge(t, h)))
98  merge_oneway(e, rep);
99  else
100  virtual_edge(t, h, e);
101 
102 #ifdef NOTDEF
103  if ((t == agtail(e)) && (h == aghead(e))) {
104  if (rep = find_fast_edge(t, h))
105  merge_oneway(e, rep);
106  else
107  virtual_edge(t, h, e);
108  } else {
109  f = agfindedge(g, t, h);
110  if (f && (ED_to_virt(f) == NULL))
111  rep = virtual_edge(t, h, f);
112  else
113  rep = find_fast_edge(t, h);
114  if (rep)
115  merge_oneway(e, rep);
116  else
117  virtual_edge(t, h, e);
118  }
119 #endif
120  }
121  }
122 }
123 
#define ND_rank(n)
Definition: types.h:490
Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:494
Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:502
#define GD_leader(g)
Definition: types.h:362
void class1(graph_t *g)
Definition: class1.c:66
Agedge_t * find_fast_edge(Agnode_t *, Agnode_t *)
Definition: fastgr.c:42
#define ND_node_type(n)
Definition: types.h:479
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
Agnode_t * virtual_node(Agraph_t *)
Definition: fastgr.c:240
#define ED_to_orig(e)
Definition: types.h:555
#define ED_weight(e)
Definition: types.h:560
EXTERN Agsym_t * E_constr
Definition: globals.h:116
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition: fastgr.c:199
#define ND_clust(n)
Definition: types.h:456
node_t * UF_find(node_t *n)
Definition: utils.c:144
#define SLACKNODE
Definition: const.h:29
#define CL_BACK
Definition: const.h:154
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
void merge_oneway(Agedge_t *, Agedge_t *)
Definition: fastgr.c:334
Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
#define ED_to_virt(e)
Definition: types.h:556
#define NULL
Definition: logic.h:50
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
boolean mapbool(char *p)
Definition: utils.c:470
#define agfindedge(g, t, h)
Definition: types.h:564
Agedge_t * make_aux_edge(Agnode_t *, Agnode_t *, double, int)
Definition: position.c:172
char * agxget(void *obj, Agsym_t *sym)
Definition: attr.c:444
#define FALSE
Definition: cgraph.h:24
void mark_clusters(graph_t *g)
Definition: cluster.c:298
#define ED_minlen(e)
Definition: types.h:549
int nonconstraint_edge(edge_t *e)
Definition: class1.c:23
#define TRUE
Definition: cgraph.h:27