Skip to content

Commit bfa050f

Browse files
kongbombkongbomb
committed
add hopcroft-karp algorithm
1 parent 16eeb6c commit bfa050f

File tree

5 files changed

+252
-2
lines changed

5 files changed

+252
-2
lines changed

‎TODO‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,3 @@
1-
respect categiry in http://en.wikipedia.org/wiki/List_of_algorithms
2-
move trivial division for primality test.
31
solve a hopcroftkarp problem TAXI, move it.
42
add stack example, problem
53
change vertex to String type in tests
@@ -16,6 +14,7 @@ Shortest Path Faster Algorithm
1614
dinic'S ALGORITHM
1715
study sieves - http://en.wikipedia.org/wiki/Sieve_of_Atkin, http://en.wikipedia.org/wiki/Wheel_factorization
1816
update site for primality test. problem is SPOJ PPATH
17+
move trivial division for primality test.
1918

2019
- after release
2120
update site for seiveoferatosthenes. problem is SPOJ PPATH, example is exist.

‎src/main/java/org/psjava/algo/graph/matching/HopcroftKarpAlgorithm.java‎

Lines changed: 205 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,205 @@
1+
package org.psjava.algo.graph.matching;
2+
3+
import org.psjava.algo.graph.bfs.BFS;
4+
import org.psjava.algo.graph.bfs.BFSStopper;
5+
import org.psjava.algo.graph.bfs.BFSVisitor;
6+
import org.psjava.algo.graph.dfs.DFSVisitorBase;
7+
import org.psjava.algo.graph.dfs.MultiSourceDFS;
8+
import org.psjava.ds.Collection;
9+
import org.psjava.ds.array.DynamicArray;
10+
import org.psjava.ds.array.FirstInArray;
11+
import org.psjava.ds.array.LastInArray;
12+
import org.psjava.ds.graph.AdjacencyList;
13+
import org.psjava.ds.graph.AdjacencyListFromGraph;
14+
import org.psjava.ds.graph.BipartiteGraph;
15+
import org.psjava.ds.graph.BipartiteGraphEdge;
16+
import org.psjava.ds.graph.DirectedEdge;
17+
import org.psjava.ds.graph.EdgeFilteredSubAdjacencyList;
18+
import org.psjava.ds.graph.MutableGraph;
19+
import org.psjava.ds.map.MutableMap;
20+
import org.psjava.goods.GoodMutableMapFactory;
21+
import org.psjava.util.DataFilter;
22+
import org.psjava.util.FilteredIterable;
23+
import org.psjava.util.ZeroTo;
24+
25+
/**
26+
* Implementation of Hopcroft–Karp algorithm
27+
*
28+
* http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
29+
*
30+
* O(V*root(E))
31+
*/
32+
33+
public class HopcroftKarpAlgorithm implements MaximumBipartiteMatching {
34+
35+
private enum Side {
36+
LEFT, RIGHT
37+
}
38+
39+
private static class Vertex<V> {
40+
V original;
41+
Side side;
42+
boolean free = true;
43+
44+
Vertex(V original, Side side) {
45+
this.original = original;
46+
this.side = side;
47+
}
48+
}
49+
50+
private static class EdgeStatus {
51+
boolean inMatch = false;
52+
Object bfsMark = null;
53+
}
54+
55+
private static class Edge<V> implements DirectedEdge<Vertex<V>> {
56+
final Vertex<V> from, to;
57+
final EdgeStatus status;
58+
59+
Edge(Vertex<V> from, Vertex<V> to, EdgeStatus status) {
60+
this.from = from;
61+
this.to = to;
62+
this.status = status;
63+
}
64+
65+
@Override
66+
public Vertex<V> from() {
67+
return from;
68+
}
69+
70+
@Override
71+
public Vertex<V> to() {
72+
return to;
73+
}
74+
75+
}
76+
77+
@Override
78+
public <V> MaximumBipartiteMatchingResult<V> calc(BipartiteGraph<V> bg) {
79+
AdjacencyList<Vertex<V>, Edge<V>> adj = wrapAsGraph(bg);
80+
while (true) {
81+
Object bfsMark = new Object();
82+
Collection<Vertex<V>> bfsFinishes = bfs(adj, bfsMark);
83+
if (bfsFinishes.isEmpty())
84+
break;
85+
dfs(adj, bfsFinishes, bfsMark);
86+
}
87+
return createResult(adj);
88+
}
89+
90+
private <V> AdjacencyList<Vertex<V>, Edge<V>> wrapAsGraph(BipartiteGraph<V> bg) {
91+
MutableMap<V, Vertex<V>> vertex = GoodMutableMapFactory.getInstance().create();
92+
for (V v : bg.getLeftVertices())
93+
vertex.put(v, new Vertex<V>(v, Side.LEFT));
94+
for (V v : bg.getRightVertices())
95+
vertex.put(v, new Vertex<V>(v, Side.RIGHT));
96+
MutableGraph<Vertex<V>, Edge<V>> graph = MutableGraph.create();
97+
for (Vertex<V> v : vertex.values())
98+
graph.insertVertex(v);
99+
for (BipartiteGraphEdge<V> e : bg.getEdges()) {
100+
EdgeStatus status = new EdgeStatus();
101+
graph.addEdge(new Edge<V>(vertex.get(e.left()), vertex.get(e.right()), status));
102+
graph.addEdge(new Edge<V>(vertex.get(e.right()), vertex.get(e.left()), status));
103+
}
104+
return AdjacencyListFromGraph.create(graph);
105+
}
106+
107+
private <V> Collection<Vertex<V>> bfs(final AdjacencyList<Vertex<V>, Edge<V>> adj, final Object mark) {
108+
final DynamicArray<Vertex<V>> finishes = DynamicArray.create();
109+
110+
BFS.traverse(EdgeFilteredSubAdjacencyList.wrap(adj, new DataFilter<Edge<V>>() {
111+
@Override
112+
public boolean isAccepted(Edge<V> edge) {
113+
// to alternate matched and non-matched edges.
114+
if (edge.from.side == Side.LEFT)
115+
return !edge.status.inMatch;
116+
else
117+
return edge.status.inMatch;
118+
}
119+
}), FilteredIterable.create(adj.getVertices(), new DataFilter<Vertex<V>>() {
120+
@Override
121+
public boolean isAccepted(Vertex<V> v) {
122+
return (v.side == Side.LEFT) && v.free;
123+
}
124+
}), new BFSVisitor<Vertex<V>, Edge<V>>() {
125+
int finishDepth = -1;
126+
127+
@Override
128+
public void onDiscover(Vertex<V> vertex, int depth, BFSStopper stopper) {
129+
if (finishDepth == -1 || depth <= finishDepth) {
130+
if (vertex.side == Side.RIGHT && vertex.free) {
131+
finishDepth = depth;
132+
finishes.addToLast(vertex);
133+
}
134+
} else {
135+
stopper.stop();
136+
}
137+
}
138+
139+
@Override
140+
public void onWalk(Edge<V> e) {
141+
e.status.bfsMark = mark;
142+
}
143+
144+
});
145+
return finishes;
146+
}
147+
148+
private <V> void dfs(final AdjacencyList<Vertex<V>, Edge<V>> adj, final Collection<Vertex<V>> bfsFinishes, final Object bfsMark) {
149+
MultiSourceDFS.traverse(EdgeFilteredSubAdjacencyList.wrap(adj, new DataFilter<Edge<V>>() {
150+
@Override
151+
public boolean isAccepted(Edge<V> edge) {
152+
return edge.status.bfsMark == bfsMark; // uses only edges discovered in bfs step.
153+
}
154+
}), bfsFinishes, new DFSVisitorBase<Vertex<V>, Edge<V>>() {
155+
DynamicArray<Edge<V>> path = DynamicArray.create();
156+
157+
@Override
158+
public void onWalkDown(Edge<V> edge) {
159+
path.addToLast(edge);
160+
}
161+
162+
@Override
163+
public void onWalkUp(Edge<V> downedEdge) {
164+
path.removeLast();
165+
}
166+
167+
@Override
168+
public void onDiscovered(Vertex<V> v, int depth) {
169+
if (wasBfsStart(v)) {
170+
for (int index : ZeroTo.get(path.size()))
171+
path.get(index).status.inMatch = (index % 2 == 0);
172+
FirstInArray.getFirst(path).from.free = false;
173+
LastInArray.getLast(path).to.free = false;
174+
}
175+
}
176+
177+
private boolean wasBfsStart(Vertex<V> v) {
178+
return v.side == Side.LEFT && v.free;
179+
}
180+
181+
});
182+
}
183+
184+
private <V> MaximumBipartiteMatchingResult<V> createResult(AdjacencyList<Vertex<V>, Edge<V>> adj) {
185+
final MutableMap<V, V> match = GoodMutableMapFactory.getInstance().create();
186+
for (Vertex<V> v : adj.getVertices())
187+
for (Edge<V> e : adj.getEdges(v))
188+
if (e.status.inMatch)
189+
match.put(e.from().original, e.to().original);
190+
191+
return new MaximumBipartiteMatchingResult<V>() {
192+
public V getMatchedVertex(V v) {
193+
return match.get(v);
194+
}
195+
196+
public int getMaxMatchCount() {
197+
return match.size() / 2;
198+
}
199+
200+
public boolean hasMatch(V v) {
201+
return match.containsKey(v);
202+
}
203+
};
204+
}
205+
}

‎src/main/java/org/psjava/algo/graph/matching/MaximumBipartiteMatching.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package org.psjava.algo.graph.matching;
2+
3+
import org.psjava.ds.graph.BipartiteGraph;
4+
5+
public interface MaximumBipartiteMatching {
6+
<V> MaximumBipartiteMatchingResult<V> calc(BipartiteGraph<V> graph);
7+
}

‎src/main/java/org/psjava/algo/graph/matching/MaximumBipartiteMatchingResult.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package org.psjava.algo.graph.matching;
2+
3+
public interface MaximumBipartiteMatchingResult<V> {
4+
int getMaxMatchCount();
5+
boolean hasMatch(V v);
6+
V getMatchedVertex(V v);
7+
}

‎src/test/java/org/psjava/algo/graph/matching/HopcroftKarpAlgorithmTest.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package org.psjava.algo.graph.matching;
2+
3+
import java.util.Set;
4+
import java.util.TreeSet;
5+
6+
import org.junit.Assert;
7+
import org.junit.Test;
8+
import org.psjava.ds.graph.MutableBipartiteGraph;
9+
10+
public class HopcroftKarpAlgorithmTest {
11+
12+
@Test
13+
public void testCLRS() {
14+
MutableBipartiteGraph<Integer> g = MutableBipartiteGraph.create();
15+
int[][] d = { { 0, 5 }, { 1, 5 }, { 1, 7 }, { 2, 6 }, { 2, 7 }, { 2, 8 }, { 3, 7 }, { 4, 7 } };
16+
for (int[] subd : d) {
17+
g.insertLeftVertex(subd[0]);
18+
g.insertRightVertex(subd[1]);
19+
g.addEdge(subd[0], subd[1]);
20+
}
21+
22+
MaximumBipartiteMatchingResult<Integer> r = new HopcroftKarpAlgorithm().calc(g);
23+
Assert.assertEquals(3, r.getMaxMatchCount());
24+
25+
Set<Integer> rightSet = new TreeSet<Integer>();
26+
for (int left : g.getLeftVertices())
27+
if(r.hasMatch(left))
28+
rightSet.add(r.getMatchedVertex(left));
29+
Assert.assertEquals(3, rightSet.size());
30+
}
31+
32+
}

0 commit comments

Comments
 (0)