JAVA Jgrapht Hopcroft Karp Bipartite匹配

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); 
    } 
}