-
Notifications
You must be signed in to change notification settings - Fork 0
/
GraphClass.java
133 lines (124 loc) · 3.7 KB
/
GraphClass.java
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
class Edge {
Vertex dest;
double cost;
public Edge(Vertex d, double c) {
dest = d;
cost = c;
}
}
class Vertex {
int name,size,dist,decompositionId;
Vertex parent;
boolean visited;
List<Edge> adj;
public Vertex(int n) {
name = n;
adj = new LinkedList<Edge>();
decompositionId = -1;
}
}
class Graph {
private Map<Integer, Vertex> vertexMap = new HashMap<Integer, Vertex>();
//Decomposition ID Map
Map<Integer, Vertex> decIdMap = new HashMap<Integer, Vertex>();
int ID;
public void reset() {
}
public Vertex getVertex(int vName) {
Vertex v = vertexMap.get(vName);
if (v == null) {
v = new Vertex(vName);
vertexMap.put(vName, v);
}
return v;
}
public void addEdge(int begin, int end, double c) {
Vertex v = getVertex(begin);
Vertex w = getVertex(end);
v.adj.add(new Edge(w, c));
//By Directional
w.adj.add(new Edge(v, c));
}
public void saveParantAndSubTreeSize(int n) {
Vertex v = getVertex(n);
Stack<Vertex> s = new Stack<Vertex>(), sp = new Stack<Vertex>();
s.add(v);
boolean isLeaf;
Vertex w;
while(!s.isEmpty()) {
v=s.pop();
isLeaf = true;
for(Edge e : v.adj)
if((w = e.dest) != v.parent) {
isLeaf = false;
w.parent = v;
w.dist = v.dist + 1;
s.add(w);
}
if(isLeaf)
sp.add(v);
}
while(!sp.isEmpty()) {
v=sp.pop();
v.size++;
if(v.parent != null) {
v.parent.size = v.size;
sp.add(v.parent);
}
}
}
public void decompositionBuild(int n) {
Vertex v = getVertex(n);
Stack<Vertex> s = new Stack<Vertex>();
s.add(v);
int max;
Vertex cur, w;
while(!s.isEmpty()) {
v = s.pop();
if(v.decompositionId == -1) {
v.decompositionId = ID;
decIdMap.put(ID++, v);
}
max =-1;
cur = null;
for(Edge e : v.adj)
if((w = e.dest) != v.parent && max < w.size) {
max = w.size;
cur = w;
}
if(max > -1) {
cur.decompositionId = v.decompositionId;
s.add(cur);
}
for(Edge e : v.adj)
if((w = e.dest) != v.parent && w != cur)
s.add(w);
}
}
public long getDecompositionDestonationBetween(int n1, int n2) {
Vertex v = getVertex(n1);
Vertex w = getVertex(n2);
Vertex c = LCA(v, w);
return v.dist + w.dist - 2 * c.dist;
}
public Vertex LCA(int v, int w) {
return LCA(getVertex(v), getVertex(w));
}
public Vertex LCA(Vertex v, Vertex w) {
Vertex nv = null, nw = null;
while(v.decompositionId != w.decompositionId) {
if(decIdMap.get(v.decompositionId) == v)
nv = v.parent;
else nv = decIdMap.get(v.decompositionId);
if(decIdMap.get(w.decompositionId) == w)
nw = w.parent;
else nw = decIdMap.get(w.decompositionId);
if(nv == null || nw != null && nv.dist < nw.dist)
w = nw;
else v = nv;
}
if(v.dist < w.dist)
return v;
return w;
}
}