全部产品
存储与CDN 数据库 安全 应用服务 数加·人工智能 数加·大数据基础服务 互联网中间件 视频服务 开发者工具 解决方案 物联网
MaxCompute

BiPartiteMatchiing

更新时间:2017-10-22 14:27:23

二分图是指图的所有顶点可分为两个集合,每条边对应的两个顶点分别属于这两个集合。对于一个二分图 G,M 是它的一个子图,如果 M 的边集中任意两条边都不依附于同一个顶点,则称 M 为一个匹配。二分图匹配常用于有明确供需关系场景(如交友网站等)下的信息匹配行为。

算法描述,如下所示:

  • 从左边第 1 个顶点开始,挑选未匹配点进行搜索,寻找增广路。

  • 如果经过一个未匹配点,说明寻找成功。

  • 更新路径信息,匹配边数 +1,停止搜索。

  • 如果一直没有找到增广路,则不再从这个点开始搜索。

代码示例

BiPartiteMatchiing 算法的代码,如下所示:

  1. import java.io.DataInput;
  2. import java.io.DataOutput;
  3. import java.io.IOException;
  4. import java.util.Random;
  5. import com.aliyun.odps.data.TableInfo;
  6. import com.aliyun.odps.graph.ComputeContext;
  7. import com.aliyun.odps.graph.GraphJob;
  8. import com.aliyun.odps.graph.MutationContext;
  9. import com.aliyun.odps.graph.WorkerContext;
  10. import com.aliyun.odps.graph.Vertex;
  11. import com.aliyun.odps.graph.GraphLoader;
  12. import com.aliyun.odps.io.LongWritable;
  13. import com.aliyun.odps.io.NullWritable;
  14. import com.aliyun.odps.io.Text;
  15. import com.aliyun.odps.io.Writable;
  16. import com.aliyun.odps.io.WritableRecord;
  17. public class BipartiteMatching {
  18. private static final Text UNMATCHED = new Text("UNMATCHED");
  19. public static class TextPair implements Writable {
  20. public Text first;
  21. public Text second;
  22. public TextPair() {
  23. first = new Text();
  24. second = new Text();
  25. }
  26. public TextPair(Text first, Text second) {
  27. this.first = new Text(first);
  28. this.second = new Text(second);
  29. }
  30. @Override
  31. public void write(DataOutput out) throws IOException {
  32. first.write(out);
  33. second.write(out);
  34. }
  35. @Override
  36. public void readFields(DataInput in) throws IOException {
  37. first = new Text();
  38. first.readFields(in);
  39. second = new Text();
  40. second.readFields(in);
  41. }
  42. @Override
  43. public String toString() {
  44. return first + ": " + second;
  45. }
  46. }
  47. public static class BipartiteMatchingVertexReader extends
  48. GraphLoader<Text, TextPair, NullWritable, Text> {
  49. @Override
  50. public void load(LongWritable recordNum, WritableRecord record,
  51. MutationContext<Text, TextPair, NullWritable, Text> context)
  52. throws IOException {
  53. BipartiteMatchingVertex vertex = new BipartiteMatchingVertex();
  54. vertex.setId((Text) record.get(0));
  55. vertex.setValue(new TextPair(UNMATCHED, (Text) record.get(1)));
  56. String[] adjs = record.get(2).toString().split(",");
  57. for (String adj : adjs) {
  58. vertex.addEdge(new Text(adj), null);
  59. }
  60. context.addVertexRequest(vertex);
  61. }
  62. }
  63. public static class BipartiteMatchingVertex extends
  64. Vertex<Text, TextPair, NullWritable, Text> {
  65. private static final Text LEFT = new Text("LEFT");
  66. private static final Text RIGHT = new Text("RIGHT");
  67. private static Random rand = new Random();
  68. @Override
  69. public void compute(
  70. ComputeContext<Text, TextPair, NullWritable, Text> context,
  71. Iterable<Text> messages) throws IOException {
  72. if (isMatched()) {
  73. voteToHalt();
  74. return;
  75. }
  76. switch ((int) context.getSuperstep() % 4) {
  77. case 0:
  78. if (isLeft()) {
  79. context.sendMessageToNeighbors(this, getId());
  80. }
  81. break;
  82. case 1:
  83. if (isRight()) {
  84. Text luckyLeft = null;
  85. for (Text message : messages) {
  86. if (luckyLeft == null) {
  87. luckyLeft = new Text(message);
  88. } else {
  89. if (rand.nextInt(1) == 0) {
  90. luckyLeft.set(message);
  91. }
  92. }
  93. }
  94. if (luckyLeft != null) {
  95. context.sendMessage(luckyLeft, getId());
  96. }
  97. }
  98. break;
  99. case 2:
  100. if (isLeft()) {
  101. Text luckyRight = null;
  102. for (Text msg : messages) {
  103. if (luckyRight == null) {
  104. luckyRight = new Text(msg);
  105. } else {
  106. if (rand.nextInt(1) == 0) {
  107. luckyRight.set(msg);
  108. }
  109. }
  110. }
  111. if (luckyRight != null) {
  112. setMatchVertex(luckyRight);
  113. context.sendMessage(luckyRight, getId());
  114. }
  115. }
  116. break;
  117. case 3:
  118. if (isRight()) {
  119. for (Text msg : messages) {
  120. setMatchVertex(msg);
  121. }
  122. }
  123. break;
  124. }
  125. }
  126. @Override
  127. public void cleanup(
  128. WorkerContext<Text, TextPair, NullWritable, Text> context)
  129. throws IOException {
  130. context.write(getId(), getValue().first);
  131. }
  132. private boolean isMatched() {
  133. return !getValue().first.equals(UNMATCHED);
  134. }
  135. private boolean isLeft() {
  136. return getValue().second.equals(LEFT);
  137. }
  138. private boolean isRight() {
  139. return getValue().second.equals(RIGHT);
  140. }
  141. private void setMatchVertex(Text matchVertex) {
  142. getValue().first.set(matchVertex);
  143. }
  144. }
  145. private static void printUsage() {
  146. System.err.println("BipartiteMatching <input> <output> [maxIteration]");
  147. }
  148. public static void main(String[] args) throws IOException {
  149. if (args.length < 2) {
  150. printUsage();
  151. }
  152. GraphJob job = new GraphJob();
  153. job.setGraphLoaderClass(BipartiteMatchingVertexReader.class);
  154. job.setVertexClass(BipartiteMatchingVertex.class);
  155. job.addInput(TableInfo.builder().tableName(args[0]).build());
  156. job.addOutput(TableInfo.builder().tableName(args[1]).build());
  157. int maxIteration = 30;
  158. if (args.length > 2) {
  159. maxIteration = Integer.parseInt(args[2]);
  160. }
  161. job.setMaxIteration(maxIteration);
  162. job.run();
  163. }
  164. }
本文导读目录