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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
/* vim: set expandtab tabstop=4 shiftwidth=4 : */
public class SAP
{
// data type use space proportional to E + V
// all methods take time at most proportional to E + V in the worst case
private static class SAPResult {
private int ancestor;
private int length;
public SAPResult(int a, int l) {
ancestor = a;
length = l;
}
public int length() { return length; }
public int ancestor() { return ancestor; }
};
private Digraph g;
// constructor takes a digraph (not necessarily a DAG)
public SAP(Digraph G)
{
g = new Digraph(G);
}
// length of shortest ancestral path between v and w
// -1 if no such path
public int length(int v, int w)
{
return ancestorAndLength(v, w).length();
}
// a common ancestor of v and w that participates in a shortest ancestral path
// -1 if no such path
public int ancestor(int v, int w)
{
return ancestorAndLength(v, w).ancestor();
}
// length of shortest ancestral path between any vertex in v and any vertex in w
// -1 if no such path
public int length(Iterable<Integer> v, Iterable<Integer> w)
{
return ancestorAndLength(v, w).length();
}
// a common ancestor that participates in shortest ancestral path
// -1 if no such path
public int ancestor(Iterable<Integer> v, Iterable<Integer> w)
{
return ancestorAndLength(v, w).ancestor();
}
private SAPResult ancestorAndLength(int v, int w)
{
if ((Math.max(v, w) >= g.V()) || (Math.min(v, w) < 0))
throw new IndexOutOfBoundsException("out of index");
// the smallest index shall have the smallest components count
int a, b;
if (v < w) {
a = v;
b = w;
} else {
a = w;
b = v;
}
int sol = -1;
int len = Integer.MAX_VALUE;
if (a == b) {
sol = a;
len = 0;
} else {
ResizingArrayQueue<Integer> c = new ResizingArrayQueue<Integer>();
SpecializedBFS aBFS = new SpecializedBFS(g, a, c);
SpecializedBFS bBFS = new SpecializedBFS(g, b, null);
for (int x : c) {
if (!bBFS.hasPathTo(x)) continue;
int l = aBFS.distTo(x) + bBFS.distTo(x);
if (len > l) {
len = l;
sol = x;
}
}
}
if (sol == -1) len = -1;
return new SAPResult(sol, len);
}
private SAPResult ancestorAndLength(Iterable<Integer> vv, Iterable<Integer> ww)
{
for (int v : vv) {
if (v < 0 || v >= g.V())
throw new IndexOutOfBoundsException("out of index");
}
for (int w : ww) {
if (w < 0 || w >= g.V())
throw new IndexOutOfBoundsException("out of index");
}
int sol = -1;
int len = Integer.MAX_VALUE;
ResizingArrayQueue<Integer> c = new ResizingArrayQueue<Integer>();
SpecializedBFS aBFS = new SpecializedBFS(g, vv, c);
SpecializedBFS bBFS = new SpecializedBFS(g, ww, null);
for (int x : c) {
if (!bBFS.hasPathTo(x)) continue;
int l = aBFS.distTo(x) + bBFS.distTo(x);
if (len > l) {
len = l;
sol = x;
}
}
if (sol == -1) len = -1;
SAPResult res = new SAPResult(sol, len);
return res;
}
// for unit testing of this class (such as the one below)
public static void main(String[] args)
{
int length, ancestor;
In in;
Digraph G;
SAP sap;
in = new In("./data/digraph1.txt");
G = new Digraph(in);
sap = new SAP(G);
length = sap.length(3, 11);
ancestor = sap.ancestor(3, 11);
StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
length = sap.length(9, 12);
ancestor = sap.ancestor(9, 12);
StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
length = sap.length(7, 2);
ancestor = sap.ancestor(7, 2);
StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
length = sap.length(1, 6);
ancestor = sap.ancestor(1, 6);
StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
Stopwatch w1 = new Stopwatch();
for (int i = 1; i < 7; i++) {
String g = "./data/digraph"+i+".txt";
in = new In(g);
G = new Digraph(in);
sap = new SAP(G);
for (int v = 0; v < G.V(); v++) {
for (int w = 0; w < G.V(); w++) {
int a = sap.ancestor(v, w);
int l = sap.length(v, w);
// StdOut.printf("%s %d->%d : a:%d l:%d\n", g, v, w, a, l);
}
}
}
double a1 = w1.elapsedTime();
StdOut.printf("all solved in : %g \n", a1);
}
}
|
