JAVA Jgrapht Hopcroft Karp 二分匹配

Question

我正在尝试制作 HopcroftKarpBipartiteMatching，但没有演示，或者我找不到其他任何东西来帮助我使用该库。我无法从文档中弄清楚实例化 HopcroftKarpBipartiteMatching 类的方式和需要什么？我有一组代表顶点的字符串。它是来自顶点的每条路径的列表。举个例子:

Array{(V1,V7), (V1,V8), (V1,V6)]
Array{(V2,V8), (V2,V5), (V2, V6)]
Array{(V3, V4),(V3, V8)}

使用 JApplet 的可能解决方案

public class GraphDemo  extends JApplet{

     private static final long serialVersionUID = 2202072534703043194L;
        private static final Dimension DEFAULT_SIZE = new Dimension(530, 320);



        private JGraphXAdapter<String, DefaultEdge> jgxAdapter;

    public static void main(String[] args) {



                JGraphAdapterDemo applet = new JGraphAdapterDemo();
                applet.init();

                JFrame frame = new JFrame();
                frame.getContentPane().add(applet);
                frame.setTitle("JGraphT Adapter to JGraph Demo");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.pack();
                frame.setVisible(true);
            }

    public void init()
    { 
        UndirectedGraph<String, DefaultEdge> g = 
                new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

        jgxAdapter = new JGraphXAdapter<String, DefaultEdge>(g);

        getContentPane().add(new mxGraphComponent(jgxAdapter));
        resize(DEFAULT_SIZE);

        String x1 = "x1";
        String x2 = "x2";
        String x3 = "x3";

        String y1 = "y1";
        String y2 = "y2";
        String y3 = "y3";
        String y4 = "y5";

        g.addVertex(x1);
        g.addVertex(x2);
        g.addVertex(x3);

        g.addVertex(y1);
        g.addVertex(y2);
        g.addVertex(y3);
        g.addVertex(y4);

        g.addEdge(x1, y1);
        g.addEdge(x1, y2);

        g.addEdge(x2, y1);
        g.addEdge(x2, y4);

        g.addEdge(x3, y2);
        g.addEdge(x3, y3);

        Set<String> p1 = new HashSet<String>(Arrays.asList(x1, x2, x3));
        Set<String> p2 = new HashSet<String>(Arrays.asList(y1, y2, y3, y4));

        HopcroftKarpBipartiteMatching<String, DefaultEdge> alg = 
            new HopcroftKarpBipartiteMatching<String, DefaultEdge>(g, p1, p2);

        Set<DefaultEdge> match = alg.getMatching();

        mxCircleLayout layout = new mxCircleLayout(jgxAdapter);
        layout.execute(jgxAdapter.getDefaultParent());

        System.out.println(g.toString());
        System.out.println(match);
    }
}

Answer 1

HopcroftKarpBipartiteMatching构造函数需要一个图和两个分区集，即:

UndirectedGraph<String, DefaultEdge> g = ...
Set<String> part1 = ...
Set<String> part2 = ...
new HopcroftKarpBipartiteMatching<String, DefaultEdge>(g, part1, part2);

这是一个简单的例子:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

import org.jgrapht.UndirectedGraph;
import org.jgrapht.alg.HopcroftKarpBipartiteMatching;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

public class GraphDemo {

    public static void main(String[] args) {
        UndirectedGraph<String, DefaultEdge> g = 
                new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

        String x1 = "x1";
        String x2 = "x2";
        String x3 = "x3";

        String y1 = "y1";
        String y2 = "y2";
        String y3 = "y3";
        String y4 = "y5";

        g.addVertex(x1);
        g.addVertex(x2);
        g.addVertex(x3);

        g.addVertex(y1);
        g.addVertex(y2);
        g.addVertex(y3);
        g.addVertex(y4);

        g.addEdge(x1, y1);
        g.addEdge(x1, y2);

        g.addEdge(x2, y1);
        g.addEdge(x2, y4);

        g.addEdge(x3, y2);
        g.addEdge(x3, y3);

        Set<String> p1 = new HashSet<String>(Arrays.asList(x1, x2, x3));
        Set<String> p2 = new HashSet<String>(Arrays.asList(y1, y2, y3, y4));

        HopcroftKarpBipartiteMatching<String, DefaultEdge> alg = 
            new HopcroftKarpBipartiteMatching<String, DefaultEdge>(g, p1, p2);

        Set<DefaultEdge> match = alg.getMatching();

        System.out.println(g.toString());
        System.out.println(match);
    }
}