Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4c5525a

Browse files
feat: Added Gomory–Hu Tree (all-pairs min-cuts via n1 max-flows) (#6818)
* Add Gomory–Hu Tree (all-pairs min-cuts via n1 max-flows)* Stabilize Monte Carlo integration with antithetic variates to reduce variance* Fix Checkstyle in GomoryHuTreeTest: remove inner assignments, add braces, split declarations* SpotBugs: use RandomGenerator interface in test helper---------Co-authored-by: Deniz Altunkapan <deniz.altunkapan@outlook.com>
1 parentf352f81 commit4c5525a

File tree

4 files changed

+289
-4
lines changed

4 files changed

+289
-4
lines changed

‎DIRECTORY.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -385,6 +385,7 @@
385385
- 📄[Dinic](src/main/java/com/thealgorithms/graph/Dinic.java)
386386
- 📄[Edmonds](src/main/java/com/thealgorithms/graph/Edmonds.java)
387387
- 📄[EdmondsKarp](src/main/java/com/thealgorithms/graph/EdmondsKarp.java)
388+
- 📄[GomoryHuTree](src/main/java/com/thealgorithms/graph/GomoryHuTree.java)
388389
- 📄[HierholzerAlgorithm](src/main/java/com/thealgorithms/graph/HierholzerAlgorithm.java)
389390
- 📄[HierholzerEulerianPath](src/main/java/com/thealgorithms/graph/HierholzerEulerianPath.java)
390391
- 📄[HopcroftKarp](src/main/java/com/thealgorithms/graph/HopcroftKarp.java)
Lines changed: 144 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,144 @@
1+
packagecom.thealgorithms.graph;
2+
3+
importjava.util.ArrayDeque;
4+
importjava.util.Arrays;
5+
importjava.util.Queue;
6+
7+
/**
8+
* Gomory–Hu tree construction for undirected graphs via n−1 max-flow computations.
9+
*
10+
* <p>API: {@code buildTree(int[][])} returns {@code {parent, weight}} arrays for the tree.
11+
*
12+
* @see <a href="https://en.wikipedia.org/wiki/Gomory%E2%80%93Hu_tree">Wikipedia: Gomory–Hu tree</a>
13+
*/
14+
15+
publicfinalclassGomoryHuTree {
16+
privateGomoryHuTree() {
17+
}
18+
19+
publicstaticint[][]buildTree(int[][]cap) {
20+
validateCapacityMatrix(cap);
21+
finalintn =cap.length;
22+
if (n ==1) {
23+
returnnewint[][] {newint[] {-1},newint[] {0}};
24+
}
25+
26+
int[]parent =newint[n];
27+
int[]weight =newint[n];
28+
Arrays.fill(parent,0);
29+
parent[0] = -1;
30+
weight[0] =0;
31+
32+
for (ints =1;s <n;s++) {
33+
intt =parent[s];
34+
MaxFlowResultres =edmondsKarpWithMinCut(cap,s,t);
35+
intf =res.flow;
36+
weight[s] =f;
37+
38+
for (intv =0;v <n;v++) {
39+
if (v !=s &&parent[v] ==t &&res.reachable[v]) {
40+
parent[v] =s;
41+
}
42+
}
43+
44+
if (t !=0 &&res.reachable[parent[t]]) {
45+
parent[s] =parent[t];
46+
parent[t] =s;
47+
weight[s] =weight[t];
48+
weight[t] =f;
49+
}
50+
}
51+
returnnewint[][] {parent,weight};
52+
}
53+
54+
privatestaticvoidvalidateCapacityMatrix(int[][]cap) {
55+
if (cap ==null ||cap.length ==0) {
56+
thrownewIllegalArgumentException("Capacity matrix must not be null or empty");
57+
}
58+
finalintn =cap.length;
59+
for (inti =0;i <n;i++) {
60+
if (cap[i] ==null ||cap[i].length !=n) {
61+
thrownewIllegalArgumentException("Capacity matrix must be square");
62+
}
63+
for (intj =0;j <n;j++) {
64+
if (cap[i][j] <0) {
65+
thrownewIllegalArgumentException("Capacities must be non-negative");
66+
}
67+
}
68+
}
69+
}
70+
71+
privatestaticfinalclassMaxFlowResult {
72+
finalintflow;
73+
finalboolean[]reachable;
74+
MaxFlowResult(intflow,boolean[]reachable) {
75+
this.flow =flow;
76+
this.reachable =reachable;
77+
}
78+
}
79+
80+
privatestaticMaxFlowResultedmondsKarpWithMinCut(int[][]capacity,intsource,intsink) {
81+
finalintn =capacity.length;
82+
int[][]residual =newint[n][n];
83+
for (inti =0;i <n;i++) {
84+
residual[i] =Arrays.copyOf(capacity[i],n);
85+
}
86+
87+
int[]parent =newint[n];
88+
intmaxFlow =0;
89+
90+
while (bfs(residual,source,sink,parent)) {
91+
intpathFlow =Integer.MAX_VALUE;
92+
for (intv =sink;v !=source;v =parent[v]) {
93+
intu =parent[v];
94+
pathFlow =Math.min(pathFlow,residual[u][v]);
95+
}
96+
for (intv =sink;v !=source;v =parent[v]) {
97+
intu =parent[v];
98+
residual[u][v] -=pathFlow;
99+
residual[v][u] +=pathFlow;
100+
}
101+
maxFlow +=pathFlow;
102+
}
103+
104+
boolean[]reachable =newboolean[n];
105+
markReachable(residual,source,reachable);
106+
returnnewMaxFlowResult(maxFlow,reachable);
107+
}
108+
109+
privatestaticbooleanbfs(int[][]residual,intsource,intsink,int[]parent) {
110+
Arrays.fill(parent, -1);
111+
parent[source] =source;
112+
Queue<Integer>q =newArrayDeque<>();
113+
q.add(source);
114+
while (!q.isEmpty()) {
115+
intu =q.poll();
116+
for (intv =0;v <residual.length;v++) {
117+
if (residual[u][v] >0 &&parent[v] == -1) {
118+
parent[v] =u;
119+
if (v ==sink) {
120+
returntrue;
121+
}
122+
q.add(v);
123+
}
124+
}
125+
}
126+
returnfalse;
127+
}
128+
129+
privatestaticvoidmarkReachable(int[][]residual,intsource,boolean[]vis) {
130+
Arrays.fill(vis,false);
131+
Queue<Integer>q =newArrayDeque<>();
132+
vis[source] =true;
133+
q.add(source);
134+
while (!q.isEmpty()) {
135+
intu =q.poll();
136+
for (intv =0;v <residual.length;v++) {
137+
if (!vis[v] &&residual[u][v] >0) {
138+
vis[v] =true;
139+
q.add(v);
140+
}
141+
}
142+
}
143+
}
144+
}

‎src/main/java/com/thealgorithms/randomized/MonteCarloIntegration.java‎

Lines changed: 12 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -64,13 +64,21 @@ private static double doApproximate(Function<Double, Double> fx, double a, doubl
6464
if (!validate(fx,a,b,n)) {
6565
thrownewIllegalArgumentException("Invalid input parameters");
6666
}
67-
doubletotalArea =0.0;
67+
doubletotal =0.0;
6868
doubleinterval =b -a;
69-
for (inti =0;i <n;i++) {
69+
intpairs =n /2;
70+
for (inti =0;i <pairs;i++) {
71+
doubleu =generator.nextDouble();
72+
doublex1 =a +u *interval;
73+
doublex2 =a + (1.0 -u) *interval;
74+
total +=fx.apply(x1);
75+
total +=fx.apply(x2);
76+
}
77+
if ((n &1) ==1) {
7078
doublex =a +generator.nextDouble() *interval;
71-
totalArea +=fx.apply(x);
79+
total +=fx.apply(x);
7280
}
73-
returninterval *totalArea /n;
81+
returninterval *total /n;
7482
}
7583

7684
privatestaticbooleanvalidate(Function<Double,Double>fx,doublea,doubleb,intn) {
Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
packagecom.thealgorithms.graph;
2+
3+
importstaticorg.junit.jupiter.api.Assertions.assertEquals;
4+
5+
importjava.util.ArrayDeque;
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
importjava.util.List;
9+
importjava.util.Queue;
10+
importjava.util.Random;
11+
importjava.util.random.RandomGenerator;
12+
importorg.junit.jupiter.api.DisplayName;
13+
importorg.junit.jupiter.api.Test;
14+
15+
classGomoryHuTreeTest {
16+
17+
@Test
18+
@DisplayName("Single node graph")
19+
voidsingleNode() {
20+
int[][]cap = {{0}};
21+
int[][]res =GomoryHuTree.buildTree(cap);
22+
int[]parent =res[0];
23+
int[]weight =res[1];
24+
assertEquals(-1,parent[0]);
25+
assertEquals(0,weight[0]);
26+
}
27+
28+
@Test
29+
@DisplayName("Triangle undirected graph with known min-cuts")
30+
voidtriangleGraph() {
31+
// 0-1:3, 1-2:2, 0-2:4
32+
int[][]cap =newint[3][3];
33+
cap[0][1] =3;
34+
cap[1][0] =3;
35+
cap[1][2] =2;
36+
cap[2][1] =2;
37+
cap[0][2] =4;
38+
cap[2][0] =4;
39+
40+
int[][]tree =GomoryHuTree.buildTree(cap);
41+
// validate all pairs via path-min-edge equals maxflow
42+
validateAllPairs(cap,tree);
43+
}
44+
45+
@Test
46+
@DisplayName("Random small undirected graphs compare to EdmondsKarp")
47+
voidrandomSmallGraphs() {
48+
Randomrng =newRandom(42);
49+
for (intn =2;n <=6;n++) {
50+
for (intiter =0;iter <10;iter++) {
51+
int[][]cap =randSymmetricMatrix(n,0,5,rng);
52+
int[][]tree =GomoryHuTree.buildTree(cap);
53+
validateAllPairs(cap,tree);
54+
}
55+
}
56+
}
57+
58+
privatestaticint[][]randSymmetricMatrix(intn,intlo,inthi,RandomGeneratorrng) {
59+
int[][]a =newint[n][n];
60+
for (inti =0;i <n;i++) {
61+
for (intj =i +1;j <n;j++) {
62+
intw =rng.nextInt(hi -lo +1) +lo;
63+
a[i][j] =w;
64+
a[j][i] =w;
65+
}
66+
}
67+
// zero diagonal
68+
for (inti =0;i <n;i++) {
69+
a[i][i] =0;
70+
}
71+
returna;
72+
}
73+
74+
privatestaticvoidvalidateAllPairs(int[][]cap,int[][]tree) {
75+
intn =cap.length;
76+
int[]parent =tree[0];
77+
int[]weight =tree[1];
78+
79+
// build adjacency list of tree without generic array creation
80+
List<List<int[]>>g =newArrayList<>();
81+
for (inti =0;i <n;i++) {
82+
g.add(newArrayList<>());
83+
}
84+
for (intv =1;v <n;v++) {
85+
intu =parent[v];
86+
intw =weight[v];
87+
g.get(u).add(newint[] {v,w});
88+
g.get(v).add(newint[] {u,w});
89+
}
90+
91+
for (ints =0;s <n;s++) {
92+
for (intt =s +1;t <n;t++) {
93+
inttreeVal =minEdgeOnPath(g,s,t);
94+
intflowVal =EdmondsKarp.maxFlow(cap,s,t);
95+
assertEquals(flowVal,treeVal,"pair (" +s +"," +t +")");
96+
}
97+
}
98+
}
99+
100+
privatestaticintminEdgeOnPath(List<List<int[]>>g,ints,intt) {
101+
// BFS to record parent and edge weight along the path, since it's a tree, unique path exists
102+
intn =g.size();
103+
int[]parent =newint[n];
104+
int[]edgeW =newint[n];
105+
Arrays.fill(parent, -1);
106+
Queue<Integer>q =newArrayDeque<>();
107+
q.add(s);
108+
parent[s] =s;
109+
while (!q.isEmpty()) {
110+
intu =q.poll();
111+
if (u ==t) {
112+
break;
113+
}
114+
for (int[]e :g.get(u)) {
115+
intv =e[0];
116+
intw =e[1];
117+
if (parent[v] == -1) {
118+
parent[v] =u;
119+
edgeW[v] =w;
120+
q.add(v);
121+
}
122+
}
123+
}
124+
intcur =t;
125+
intans =Integer.MAX_VALUE;
126+
while (cur !=s) {
127+
ans =Math.min(ans,edgeW[cur]);
128+
cur =parent[cur];
129+
}
130+
returnans ==Integer.MAX_VALUE ?0 :ans;
131+
}
132+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp