@Test public void notMatchTest() { Map<String, Set<String>> input = new HashMap<>(); input.put("Alice", new HashSet<>(Arrays.asList("Adobe", "Amazon", "Facebook", "Google"))); input.put("Bob", new HashSet<>(Arrays.asList("Amazon", "Yahoo"))); input.put("Carol", new HashSet<>(Arrays.asList("Adobe", "Facebook", "Google"))); input.put("Dave", new HashSet<>(Arrays.asList("Amazon", "Yahoo"))); input.put("Eliza", new HashSet<>(Arrays.asList("Amazon", "Yahoo"))); Map<String, String> test = BipartiteMatching.solve(input); Assert.assertTrue(test.isEmpty()); }
public static Map<String, String> solve(Map<String, Set<String>> student2offer) { Map<String, Integer> company2Idx = fetchCompany(student2offer); int size = company2Idx.size(); if (size != student2offer.size()) return Collections.emptyMap(); String[] id2company = build(company2Idx); int v = 2 * size + 2; FlowNetwork flowNetwork = new FlowNetwork(v); int src = v - 2, tar = v - 1, idx = 0; Map<String, Set<FlowEdge>> student2Edge = new HashMap<>(); for (Map.Entry<String, Set<String>> entry : student2offer.entrySet()) { String studentName = entry.getKey(); student2Edge.put(studentName, new HashSet<>()); flowNetwork.addEdge(new FlowEdge(src, idx, 1)); for (String company : entry.getValue()) { FlowEdge flowEdge = new FlowEdge(idx, company2Idx.get(company), INFINITY); student2Edge.get(studentName).add(flowEdge); flowNetwork.addEdge(flowEdge); } idx++; } for (int i = size; i < src; i++) { flowNetwork.addEdge(new FlowEdge(i, tar, 1)); } FordFulkerson ff = new FordFulkerson(flowNetwork, src, tar); if (Math.abs(ff.value() - size) > EPSILON) return Collections.emptyMap(); Map<String, String> result = new HashMap<>(); for (String student : student2offer.keySet()) { for (FlowEdge edge : student2Edge.get(student)) { if (edge.flow() != 1) continue; result.put(student, id2company[edge.to()]); break; } } return result; }
BipartiteMatching { public static Map<String, String> solve(Map<String, Set<String>> student2offer) { Map<String, Integer> company2Idx = fetchCompany(student2offer); int size = company2Idx.size(); if (size != student2offer.size()) return Collections.emptyMap(); String[] id2company = build(company2Idx); int v = 2 * size + 2; FlowNetwork flowNetwork = new FlowNetwork(v); int src = v - 2, tar = v - 1, idx = 0; Map<String, Set<FlowEdge>> student2Edge = new HashMap<>(); for (Map.Entry<String, Set<String>> entry : student2offer.entrySet()) { String studentName = entry.getKey(); student2Edge.put(studentName, new HashSet<>()); flowNetwork.addEdge(new FlowEdge(src, idx, 1)); for (String company : entry.getValue()) { FlowEdge flowEdge = new FlowEdge(idx, company2Idx.get(company), INFINITY); student2Edge.get(studentName).add(flowEdge); flowNetwork.addEdge(flowEdge); } idx++; } for (int i = size; i < src; i++) { flowNetwork.addEdge(new FlowEdge(i, tar, 1)); } FordFulkerson ff = new FordFulkerson(flowNetwork, src, tar); if (Math.abs(ff.value() - size) > EPSILON) return Collections.emptyMap(); Map<String, String> result = new HashMap<>(); for (String student : student2offer.keySet()) { for (FlowEdge edge : student2Edge.get(student)) { if (edge.flow() != 1) continue; result.put(student, id2company[edge.to()]); break; } } return result; } }
BipartiteMatching { public static Map<String, String> solve(Map<String, Set<String>> student2offer) { Map<String, Integer> company2Idx = fetchCompany(student2offer); int size = company2Idx.size(); if (size != student2offer.size()) return Collections.emptyMap(); String[] id2company = build(company2Idx); int v = 2 * size + 2; FlowNetwork flowNetwork = new FlowNetwork(v); int src = v - 2, tar = v - 1, idx = 0; Map<String, Set<FlowEdge>> student2Edge = new HashMap<>(); for (Map.Entry<String, Set<String>> entry : student2offer.entrySet()) { String studentName = entry.getKey(); student2Edge.put(studentName, new HashSet<>()); flowNetwork.addEdge(new FlowEdge(src, idx, 1)); for (String company : entry.getValue()) { FlowEdge flowEdge = new FlowEdge(idx, company2Idx.get(company), INFINITY); student2Edge.get(studentName).add(flowEdge); flowNetwork.addEdge(flowEdge); } idx++; } for (int i = size; i < src; i++) { flowNetwork.addEdge(new FlowEdge(i, tar, 1)); } FordFulkerson ff = new FordFulkerson(flowNetwork, src, tar); if (Math.abs(ff.value() - size) > EPSILON) return Collections.emptyMap(); Map<String, String> result = new HashMap<>(); for (String student : student2offer.keySet()) { for (FlowEdge edge : student2Edge.get(student)) { if (edge.flow() != 1) continue; result.put(student, id2company[edge.to()]); break; } } return result; }  }
BipartiteMatching { public static Map<String, String> solve(Map<String, Set<String>> student2offer) { Map<String, Integer> company2Idx = fetchCompany(student2offer); int size = company2Idx.size(); if (size != student2offer.size()) return Collections.emptyMap(); String[] id2company = build(company2Idx); int v = 2 * size + 2; FlowNetwork flowNetwork = new FlowNetwork(v); int src = v - 2, tar = v - 1, idx = 0; Map<String, Set<FlowEdge>> student2Edge = new HashMap<>(); for (Map.Entry<String, Set<String>> entry : student2offer.entrySet()) { String studentName = entry.getKey(); student2Edge.put(studentName, new HashSet<>()); flowNetwork.addEdge(new FlowEdge(src, idx, 1)); for (String company : entry.getValue()) { FlowEdge flowEdge = new FlowEdge(idx, company2Idx.get(company), INFINITY); student2Edge.get(studentName).add(flowEdge); flowNetwork.addEdge(flowEdge); } idx++; } for (int i = size; i < src; i++) { flowNetwork.addEdge(new FlowEdge(i, tar, 1)); } FordFulkerson ff = new FordFulkerson(flowNetwork, src, tar); if (Math.abs(ff.value() - size) > EPSILON) return Collections.emptyMap(); Map<String, String> result = new HashMap<>(); for (String student : student2offer.keySet()) { for (FlowEdge edge : student2Edge.get(student)) { if (edge.flow() != 1) continue; result.put(student, id2company[edge.to()]); break; } } return result; }  static Map<String, String> solve(Map<String, Set<String>> student2offer); }
BipartiteMatching { public static Map<String, String> solve(Map<String, Set<String>> student2offer) { Map<String, Integer> company2Idx = fetchCompany(student2offer); int size = company2Idx.size(); if (size != student2offer.size()) return Collections.emptyMap(); String[] id2company = build(company2Idx); int v = 2 * size + 2; FlowNetwork flowNetwork = new FlowNetwork(v); int src = v - 2, tar = v - 1, idx = 0; Map<String, Set<FlowEdge>> student2Edge = new HashMap<>(); for (Map.Entry<String, Set<String>> entry : student2offer.entrySet()) { String studentName = entry.getKey(); student2Edge.put(studentName, new HashSet<>()); flowNetwork.addEdge(new FlowEdge(src, idx, 1)); for (String company : entry.getValue()) { FlowEdge flowEdge = new FlowEdge(idx, company2Idx.get(company), INFINITY); student2Edge.get(studentName).add(flowEdge); flowNetwork.addEdge(flowEdge); } idx++; } for (int i = size; i < src; i++) { flowNetwork.addEdge(new FlowEdge(i, tar, 1)); } FordFulkerson ff = new FordFulkerson(flowNetwork, src, tar); if (Math.abs(ff.value() - size) > EPSILON) return Collections.emptyMap(); Map<String, String> result = new HashMap<>(); for (String student : student2offer.keySet()) { for (FlowEdge edge : student2Edge.get(student)) { if (edge.flow() != 1) continue; result.put(student, id2company[edge.to()]); break; } } return result; }  static Map<String, String> solve(Map<String, Set<String>> student2offer);  }