algorithm_part2/SAP.java at master · honorwu/algorithm_part2 · GitHub

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
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.TreeSet;

public class SAP {
	private Digraph g;
	// constructor takes a digraph (not necessarily a DAG)
	public SAP(Digraph G) {
		g = new Digraph(G.V());
		for (int i=0; i<G.V(); i++) {
			for (int j : G.adj(i)) {
				g.addEdge(i,j);
			}
		}
	}

	// length of shortest ancestral path between v and w; -1 if no such path
	public int length(int v, int w) {
		DeluxeBFS bfs1 = new DeluxeBFS(g, v);
		DeluxeBFS bfs2 = new DeluxeBFS(g, w);

		TreeSet<Integer> visit1 = bfs1.getVisit();
		TreeSet<Integer> visit2 = bfs2.getVisit();

		visit1.retainAll(visit2);

		int min = -1;

		for (Integer x : visit1) {
			if (min == -1 || bfs1.distTo(x) + bfs2.distTo(x) < min) {
				min = bfs1.distTo(x) + bfs2.distTo(x);
			}
		}

		return min;
	}

	// 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) {
		DeluxeBFS bfs1 = new DeluxeBFS(g, v);
		DeluxeBFS bfs2 = new DeluxeBFS(g, w);

		TreeSet<Integer> visit1 = bfs1.getVisit();
		TreeSet<Integer> visit2 = bfs2.getVisit();

		visit1.retainAll(visit2);

		int min = 2147483647;
		int minId = -1;

		for (Integer x : visit1) {
			if (bfs1.distTo(x) + bfs2.distTo(x) < min) {
				min = bfs1.distTo(x) + bfs2.distTo(x);
				minId = x;
			}
		}

		return minId;
	}

	// 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) {
		if (v == null || w == null) {
			throw new java.lang.IllegalArgumentException();
		}

		for (Integer vv : v) {
			if (vv == null) {
				throw new java.lang.IllegalArgumentException();
			}
		}

		for (Integer ww : w) {
			if (ww == null) {
				throw new java.lang.IllegalArgumentException();
			}
		}

		DeluxeBFS bfs1 = new DeluxeBFS(g, v);
		DeluxeBFS bfs2 = new DeluxeBFS(g, w);

		TreeSet<Integer> visit1 = bfs1.getVisit();
		TreeSet<Integer> visit2 = bfs2.getVisit();

		visit1.retainAll(visit2);

		int min = -1;

		for (Integer x : visit1) {
			if (min == -1 || bfs1.distTo(x) + bfs2.distTo(x) < min) {
				min = bfs1.distTo(x) + bfs2.distTo(x);
			}
		}

		return min;
	}

	// a common ancestor that participates in shortest ancestral path; -1 if no such path
	public int ancestor(Iterable<Integer> v, Iterable<Integer> w) {
		if (v == null || w == null) {
			throw new java.lang.IllegalArgumentException();
		}

		for (Integer vv : v) {
			if (vv == null) {
				throw new java.lang.IllegalArgumentException();
			}
		}

		for (Integer ww : w) {
			if (ww == null) {
				throw new java.lang.IllegalArgumentException();
			}
		}

		DeluxeBFS bfs1 = new DeluxeBFS(g, v);
		DeluxeBFS bfs2 = new DeluxeBFS(g, w);

		TreeSet<Integer> visit1 = bfs1.getVisit();
		TreeSet<Integer> visit2 = bfs2.getVisit();

		visit1.retainAll(visit2);

		int min = 2147483647;
		int minId = -1;

		for (Integer x : visit1) {
			if (bfs1.distTo(x) + bfs2.distTo(x) < min) {
				min = bfs1.distTo(x) + bfs2.distTo(x);
				minId = x;
			}
		}

		return minId;
	}

	// do unit testing of this class
	public static void main(String[] args) {
		In in = new In("a.txt");
		Digraph G = new Digraph(in);
		SAP sap = new SAP(G);
		while (!StdIn.isEmpty()) {
			int v = StdIn.readInt();
			int w = StdIn.readInt();
			int length   = sap.length(v, w);
			int ancestor = sap.ancestor(v, w);
			StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
		}
	}
}