FlowBipartiteMatchingFinder implements BipartiteMatchingFinder<E, V> { @Override public Graph<E, V> find(Graph<E, V> bipartiteGraph) { final Graph<E, V> copy = GraphUtils.copy(bipartiteGraph); final Graph<FlowEdgeDetails, V> network = createFlowNetwork(bipartiteGraph); final Graph<FlowEdgeDetails, V> maximumFlow = finder.find(network, network.size() - 2, network.size() - 1); for (Vertex<V> vertex : network) { if (((Integer) 0).equals(vertex.getProperty("part"))) { final List<Vertex<V>> neighbors = network.getNeighbors(vertex); for (Vertex<V> neighbor : neighbors) { final boolean selected = maximumFlow.edge(vertex.getIndex(), neighbor.getIndex()).getDetails().getFlow() > 0; copy.edge(vertex.getIndex(), neighbor.getIndex()).setProperty("selected", selected); copy.edge(neighbor.getIndex(), vertex.getIndex()).setProperty("selected", selected); } } } return copy; }  @Override Graph<E, V> find(Graph<E, V> bipartiteGraph);  }
@Test public void testMatching() throws Exception { final BipartiteMatchingFinder<EdgeDetails, VertexDetails> finder = new FlowBipartiteMatchingFinder<>(); final Graph<EdgeDetails, VertexDetails> graph = GraphSamples.sampleBipartiteGraph(); final Graph<EdgeDetails, VertexDetails> result = finder.find(graph); assertThat(result, is(notNullValue())); assertThat(result.size(), is(graph.size())); final Matrix<Boolean> selection = new ArrayMatrix<>(graph.size(), graph.size()); for (MatrixRow<Boolean> row : selection) { for (MatrixCell<Boolean> cell : row) { selection.set(cell.getRowNumber(), cell.getColumnNumber(), false); } } selection.set(0, 5, true); selection.set(2, 6, true); selection.set(1, 7, true); selection.set(5, 0, true); selection.set(6, 2, true); selection.set(7, 1, true); for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result.size(); j++) { final Edge<EdgeDetails, VertexDetails> edge = result.edge(i, j); if (edge == null) { assertThat(selection.get(i, j), is(false)); } else { assertThat(edge.getProperty("selected", Boolean.class), is(selection.get(i, j))); } } } }