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