2 部グラフとは、すべてのグラフの頂点を 2 つの集合に分割でき、各辺に対応する 2 つの頂点がそれぞれ 2 つの集合に属することを意味します。 2 部グラフ G において、M はそのサブグラフの 1 つです。 M の辺集合のいずれかの 2 つの辺が 同じ頂点に隣接されていない場合、M はマッチングと呼ばれます。 通常、2 部グラフマッチングは、需給関係が明確なシナリオでの情報マッチングに使用されます。

アルゴリズムの基本概念は以下のとおりです。
  • 左側の最初の頂点からマッチングしていない頂点を選択して、増加道を検索します。
  • マッチングしていない頂点が見つかった場合、検索は成功です。
  • 道の情報は更新されます。 マッチングする辺の数が 1 つ増えた場合、検索は停止します。
  • 増加道が見つからない場合、検索はこの頂点から開始されなくなります。

サンプルコード

2 部マッチング アルゴリズムのコードは以下のとおりです。
import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.util.Random;
import com.aliyun.odps.data.TableInfo;
import com.aliyun.odps.graph.ComputeContext;
import com.aliyun.odps.graph.GraphJob;
import com.aliyun.odps.graph.MutationContext;
import com.aliyun.odps.graph.WorkerContext;
import com.aliyun.odps.graph.Vertex;
import com.aliyun.odps.graph.GraphLoader;
import com.aliyun.odps.io.LongWritable;
import com.aliyun.odps.io.NullWritable;
import com.aliyun.odps.io.Text;
import com.aliyun.odps.io.Writable;
import com.aliyun.odps.io.WritableRecord;
public class BipartiteMatching {
  private static final Text UNMATCHED = new Text("UNMATCHED");
  public static class TextPair implements Writable {
    public Text first;
    public Text second;
    public TextPair() {
      first = new Text();
      second = new Text();
    
    public TextPair(Text first, Text second) {
      this.first = new Text(first);
      this.second = new Text(second);
    
    @ Override
    public void write(DataOutput out) throws IOException {
      first.write(out);
      second.write(out);
    
    @ Override
    public void readFields(DataInput in) throws IOException {
      first = new Text();
      first.readFields(in);
      second = new Text();
      second.readFields(in);
    
    @ Override
    public String toString（）{
      return first + ": " + second;
    
  
  public static class BipartiteMatchingVertexReader extends
      GraphLoader<Text, TextPair, NullWritable, Text> {
    @ Override
    public void load(LongWritable recordNum, WritableRecord record,
        MutationContext<Text, TextPair, NullWritable, Text> context)
        throws IOException {
      BipartiteMatchingVertex vertex = new BipartiteMatchingVertex();
      vertex.setId((Text) record.get(0));
      vertex.setValue(new TextPair(UNMATCHED, (Text) record.get(1)));
      String[] adjs = record.get(2).toString().split(",");
      for (String adj : adjs) {
        vertex.addEdge(new Text(adj), null);
      
      context.addVertexRequest(vertex);
    
  
  public static class BipartiteMatchingVertex extends
  Vertex <Text, TextPair, NullWritable, Text> {
    private static final Text LEFT = new Text("LEFT");
    private static final Text RIGHT = new Text("RIGHT");
    private static Random rand = new Random();
    @ Override
    public void compute (
    ComputeContext<Text, TextPair, NullWritable, Text> context,
        Iterable messages) throws ioexception {
      if (isMatched()) {
        voteToHalt();
        return;
      
      switch ((int) context.getSuperstep() % 4) {
      case 0:
        if (isLeft()) {
          context.sendMessageToNeighbors(this, getId());
        
        break;
      case 1:
        if (isRight()) {
          Text luckyLeft = null;
          for (Text message : messages) {
            if (luckyLeft == null) {
              luckyLeft = new Text(message);
            } else{
              if (rand.nextInt(1) == 0) {
                luckyLeft.set(message);
              
            
          
          if (luckyLeft ! = null) {
            context.sendMessage(luckyLeft, getId());
          
        
        break;
      case 2:
        if (isLeft()) {
          Text luckyRight = null;
          for (Text msg : messages) {
            if (luckyRight == null) {
              luckyRight = new Text(msg);
            } else{
              if (rand.nextInt(1) == 0) {
                luckyRight.set(msg);
              
            
          
          if (luckyRight ! = null) {
            setMatchVertex(luckyRight);
            context.sendMessage(luckyRight, getId());
          
        
        break;
      case 3:
        if (isRight()) {
          for (Text msg : messages) {
            setMatchVertex(msg);
          
        
        break;
      
    
    @ Override
    public void cleanup(
    WorkerContext<Text, TextPair, NullWritable, Text> context)
        throws IOException {
      context.write(getId(), getValue().first);
    
    private boolean isMatched() {
      return ! getValue().first.equals(UNMATCHED);
    
    private boolean isLeft() {
      return getValue().second.equals(LEFT);
    
    private boolean isRight() {
      return getValue().second.equals(RIGHT);
    
    private void setMatchVertex(Text matchVertex) {
      getValue().first.set(matchVertex);
    
  
  private static void printUsage() {
    System.err.println("BipartiteMatching <input> <output> [maxIteration]");
  
  public static void main（final String [] args）throws IOException{
    if (args.length < 2) {
      printUsage();
    
    GraphJob job = new GraphJob();
    job.setGraphLoaderClass(BipartiteMatchingVertexReader.class);
    job.setVertexClass(BipartiteMatchingVertex.class);
    job.addInput(TableInfo.builder().tableName(args[0]).build());
    job.addOutput(TableInfo.builder().tableName(args[1]).build());
    int maxIteration = 30;
    if (args.length > 2) {
      maxIteration = Integer.parseInt(args[2]);
    
    job.setMaxIteration(maxIteration);
    job.run();