Algorithms in a Nutshell

Bipartite Matching | 241

Network Flow

Algorithms

// convert pairs into appropriate input for FlowNetwork. All edges

// will have capacity of 1.

for (int i = 0; i < pairs.length; i++) {

Integer src = map.get(pairs[i][0]);

Integer tgt = map.get(pairs[i][1]);

if (src == null) {

map.put(pairs[i][0], src = ++ctr);

reverse.put(src, pairs[i][0]);

}

if (tgt == null) {

map.put(pairs[i][1], tgt = ++ctr);

reverse.put(tgt, pairs[i][1]);

}

edges.add(new EdgeInfo(src, tgt, 1));

}

// add extra "source" and extra "target" vertices

srcIndex = 0;

tgtIndex = setS.length + setT.length+1;

numVertices = tgtIndex+1;

for (Object o : setS) {

edges.add(new EdgeInfo(0, map.get(o), 1));

}

for (Object o : setT) {

edges.add(new EdgeInfo(map.get(o), ctr+1, 1));

}

}

public Iterator<Pair> compute( ) {

FlowNetworkArray network = new FlowNetworkArray(numVertices,

srcIndex, tgtIndex, edges.iterator( ));

FordFulkerson solver = new FordFulkerson (network,

new DFS_SearchArray(network));

solver.compute( );

// retrieve from original edgeInfo set; ignore created edges to the

// added 'source' and 'target'. Only include in solution if flow == 1

ArrayList<Pair> pairs = new ArrayList<Pair>( );

for (EdgeInfo ei : edges) {

if (ei.start != srcIndex && ei.end != tgtIndex) {

if (ei.getFlow( ) == 1) {

pairs.add(new Pair(reverse.get(ei.start), reverse.get(ei.end)));

}

}

}

return pairs.iterator( );

}

}

Example 8-5. Bipartite Matching using Ford-Fulkerson (continued)

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use