Graphviz 13.1.1~dev.20250701.1401
Loading...
Searching...
No Matches
class1.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11
12/*
13 * Classify edges for rank assignment phase to
14 * create temporary edges.
15 */
16
17#include <dotgen/dot.h>
18#include <stdbool.h>
19
21 char *constr;
22
23 if (E_constr && (constr = agxget(e, E_constr))) {
24 if (constr[0] && !mapbool(constr))
25 return true;
26 }
27 return false;
28}
29
30static void
32{
33 node_t *v, *t0, *h0;
34 int offset, t_len, h_len, t_rank, h_rank;
35
36 if (ND_clust(agtail(e)))
37 t_rank = ND_rank(agtail(e)) - ND_rank(GD_leader(ND_clust(agtail(e))));
38 else
39 t_rank = 0;
40 if (ND_clust(aghead(e)))
41 h_rank = ND_rank(aghead(e)) - ND_rank(GD_leader(ND_clust(aghead(e))));
42 else
43 h_rank = 0;
44 offset = ED_minlen(e) + t_rank - h_rank;
45 if (offset > 0) {
46 t_len = 0;
47 h_len = offset;
48 } else {
49 t_len = -offset;
50 h_len = 0;
51 }
52
53 v = virtual_node(g);
55 t0 = UF_find(t);
56 h0 = UF_find(h);
57 edge_t *const rt = make_aux_edge(v, t0, t_len, CL_BACK * ED_weight(e));
58 edge_t *const rh = make_aux_edge(v, h0, h_len, ED_weight(e));
59 ED_to_orig(rt) = ED_to_orig(rh) = e;
60}
61void class1(graph_t * g)
62{
63 node_t *n, *t, *h;
64 edge_t *e, *rep;
65
67 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
68 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
69
70 /* skip edges already processed */
71 if (ED_to_virt(e))
72 continue;
73
74 /* skip edges that we want to ignore in this phase */
75 if (nonconstraint_edge(e))
76 continue;
77
78 t = UF_find(agtail(e));
79 h = UF_find(aghead(e));
80
81 /* skip self, flat, and intra-cluster edges */
82 if (t == h)
83 continue;
84
85
86 /* inter-cluster edges require special treatment */
87 if (ND_clust(t) || ND_clust(h)) {
88 interclust1(g, agtail(e), aghead(e), e);
89 continue;
90 }
91
92 if ((rep = find_fast_edge(t, h)))
93 merge_oneway(e, rep);
94 else
95 virtual_edge(t, h, e);
96 }
97 }
98}
99
void class1(graph_t *g)
Definition class1.c:61
static void interclust1(graph_t *g, node_t *t, node_t *h, edge_t *e)
Definition class1.c:31
bool nonconstraint_edge(edge_t *e)
Definition class1.c:20
bool mapbool(const char *p)
Definition utils.c:337
node_t * UF_find(node_t *n)
Definition utils.c:100
#define SLACKNODE
Definition const.h:26
#define CL_BACK
Definition const.h:150
static Dtdisc_t constr
Definition constraint.c:52
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition fastgr.c:168
void merge_oneway(Agedge_t *, Agedge_t *)
Definition fastgr.c:287
Agedge_t * make_aux_edge(Agnode_t *, Agnode_t *, double, int)
Definition position.c:176
Agedge_t * find_fast_edge(Agnode_t *, Agnode_t *)
Definition fastgr.c:41
Agnode_t * virtual_node(Agraph_t *)
Definition fastgr.c:198
Agsym_t * E_constr
Definition globals.h:85
char * agxget(void *obj, Agsym_t *sym)
Definition attr.c:472
#define ED_to_orig(e)
Definition types.h:598
#define ED_minlen(e)
Definition types.h:592
Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition edge.c:26
#define agtail(e)
Definition cgraph.h:988
#define ED_weight(e)
Definition types.h:603
#define aghead(e)
Definition cgraph.h:989
Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition edge.c:41
#define ED_to_virt(e)
Definition types.h:599
#define GD_leader(g)
Definition types.h:375
#define ND_rank(n)
Definition types.h:523
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
#define ND_clust(n)
Definition types.h:489
#define ND_node_type(n)
Definition types.h:511
void mark_clusters(graph_t *g)
Definition cluster.c:299
graph or subgraph
Definition cgraph.h:424