@Test public void testMatching() { Set<Edge<Integer, Integer>> edges = new HashSet<>(); edges.add(new Edge<>(1, 6, 0)); edges.add(new Edge<>(1, 7, 0)); edges.add(new Edge<>(1, 8, 0)); edges.add(new Edge<>(1, 9, 0)); edges.add(new Edge<>(1, 10, 0)); edges.add(new Edge<>(2, 6, 0)); edges.add(new Edge<>(2, 9, 0)); edges.add(new Edge<>(3, 7, 0)); edges.add(new Edge<>(3, 9, 0)); edges.add(new Edge<>(4, 7, 0)); edges.add(new Edge<>(4, 9, 0)); edges.add(new Edge<>(4, 10, 0)); edges.add(new Edge<>(5, 6, 0)); Set<Integer> partition1 = new HashSet<>(); partition1.add(1); partition1.add(2); partition1.add(3); partition1.add(4); partition1.add(5); Set<Integer> partition2 = new HashSet<>(); partition2.add(6); partition2.add(7); partition2.add(8); partition2.add(9); partition2.add(10); MaximumCardinalityMatch<Integer, Integer> match = new MaximumCardinalityMatch<>(edges, partition1, partition2); Set<Edge<Integer, Integer>> matching = match.getMatching(); assertEquals(5, matching.size()); assertTrue(matching.contains(new Edge<>(1, 8, 0))); assertTrue(matching.contains(new Edge<>(2, 9, 0))); assertTrue(matching.contains(new Edge<>(3, 7, 0))); assertTrue(matching.contains(new Edge<>(4, 10, 0))); assertTrue(matching.contains(new Edge<>(5, 6, 0))); }
public Set<Edge<V, T>> getMatching() { init(); computeInitialMatching(); while (matchedVertices < partition1.size() && bfs()) { for (int v = 1; v <= partition1.size() && matchedVertices < partition1.size(); v++) { if (matching[v] == nil) { if (dfs(v)) { matchedVertices++; } } } } assert matchedVertices <= partition1.size(); Set<Edge<V, T>> edges = new HashSet<>(); for (int i = 0; i < vertices.size(); i++) { if (matching[i] != nil) { edges.add(edge(vertices.get(i), vertices.get(matching[i]))); } } return edges; }
MaximumCardinalityMatch { public Set<Edge<V, T>> getMatching() { init(); computeInitialMatching(); while (matchedVertices < partition1.size() && bfs()) { for (int v = 1; v <= partition1.size() && matchedVertices < partition1.size(); v++) { if (matching[v] == nil) { if (dfs(v)) { matchedVertices++; } } } } assert matchedVertices <= partition1.size(); Set<Edge<V, T>> edges = new HashSet<>(); for (int i = 0; i < vertices.size(); i++) { if (matching[i] != nil) { edges.add(edge(vertices.get(i), vertices.get(matching[i]))); } } return edges; } }
MaximumCardinalityMatch { public Set<Edge<V, T>> getMatching() { init(); computeInitialMatching(); while (matchedVertices < partition1.size() && bfs()) { for (int v = 1; v <= partition1.size() && matchedVertices < partition1.size(); v++) { if (matching[v] == nil) { if (dfs(v)) { matchedVertices++; } } } } assert matchedVertices <= partition1.size(); Set<Edge<V, T>> edges = new HashSet<>(); for (int i = 0; i < vertices.size(); i++) { if (matching[i] != nil) { edges.add(edge(vertices.get(i), vertices.get(matching[i]))); } } return edges; } MaximumCardinalityMatch(
      Set<Edge<V, T>> edges, Set<V> partition1, Set<V> partition2); }
MaximumCardinalityMatch { public Set<Edge<V, T>> getMatching() { init(); computeInitialMatching(); while (matchedVertices < partition1.size() && bfs()) { for (int v = 1; v <= partition1.size() && matchedVertices < partition1.size(); v++) { if (matching[v] == nil) { if (dfs(v)) { matchedVertices++; } } } } assert matchedVertices <= partition1.size(); Set<Edge<V, T>> edges = new HashSet<>(); for (int i = 0; i < vertices.size(); i++) { if (matching[i] != nil) { edges.add(edge(vertices.get(i), vertices.get(matching[i]))); } } return edges; } MaximumCardinalityMatch(
      Set<Edge<V, T>> edges, Set<V> partition1, Set<V> partition2); Set<Edge<V, T>> getMatching(); }
MaximumCardinalityMatch { public Set<Edge<V, T>> getMatching() { init(); computeInitialMatching(); while (matchedVertices < partition1.size() && bfs()) { for (int v = 1; v <= partition1.size() && matchedVertices < partition1.size(); v++) { if (matching[v] == nil) { if (dfs(v)) { matchedVertices++; } } } } assert matchedVertices <= partition1.size(); Set<Edge<V, T>> edges = new HashSet<>(); for (int i = 0; i < vertices.size(); i++) { if (matching[i] != nil) { edges.add(edge(vertices.get(i), vertices.get(matching[i]))); } } return edges; } MaximumCardinalityMatch(
      Set<Edge<V, T>> edges, Set<V> partition1, Set<V> partition2); Set<Edge<V, T>> getMatching();  }