Java JGrapht 二分图

Question

我看到了 jgraph 和 jgrapht 的示例，很容易理解，但现在确定我将如何使用 CompleteBipartiteGraph？如何使用语法来实例化图表？

http://jgrapht.org/javadoc/

http://jgrapht.org/javadoc/org/jgrapht/generate/CompleteBipartiteGraphGenerator.html

Answer 1

针对评论中的问题“我还能使用这个生成器吗？”:您仍然可以使用它来创建完整的二分图，然后随机删除一些边。

但更直接的方法是简单地生成两组顶点并在它们之间插入一些随机边。事实上，这如此简单，以至于我不得不假设还有一些您到目前为止没有提到的其他约束。我插入了另一种方法，确保二分图不包含孤立的顶点(我的 Crystal 球告诉我要这样做......)

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import org.jgrapht.Graph;
import org.jgrapht.UndirectedGraph;
import org.jgrapht.VertexFactory;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleGraph;

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

        VertexFactory<String> vertexFactory = new VertexFactory<String>()
        {
            int n = 0;
            @Override
            public String createVertex()
            {
                String s = String.valueOf(n);
                n++;
                return s;
            }
        };
        int numVertices0 = 10;
        int numVertices1 = 15;
        int numEdges = 20;
        generateGraph(graph, numVertices0, numVertices1, numEdges, vertexFactory);

        System.out.println(graph);
    }

    // Creates a bipartite graph with the given numbers 
    // of vertices and edges
    public static <V, E> void generateGraph(Graph<V, E> graph,
        int numVertices0, int numVertices1, int numEdges,
        final VertexFactory<V> vertexFactory)
    {
        List<V> vertices0 = new ArrayList<V>();
        for (int i = 0; i < numVertices0; i++)
        {
            V v = vertexFactory.createVertex();
            graph.addVertex(v);
            vertices0.add(v);
        }
        List<V> vertices1 = new ArrayList<V>();
        for (int i = 0; i < numVertices1; i++)
        {
            V v = vertexFactory.createVertex();
            graph.addVertex(v);
            vertices1.add(v);
        }

        // Create edges between random vertices
        Random random = new Random(0);
        while (graph.edgeSet().size() < numEdges)
        {
            int i1 = random.nextInt(vertices1.size());
            V v1 = vertices1.get(i1);
            int i0 = random.nextInt(vertices0.size());
            V v0 = vertices0.get(i0);
            graph.addEdge(v0, v1);
        }

    }

    // Creates a bipartite graph with the given numbers
    // of vertices and edges without isolated vertices
    public static <V, E> void generateGraphNoIsolatedVertices(
        Graph<V, E> graph, int numVertices0, int numVertices1, int numEdges,
        final VertexFactory<V> vertexFactory, 
        List<V> vertices0, List<V> vertices1)
    {
        int minNumEdges = Math.max(numVertices0, numVertices0);
        if (numEdges < minNumEdges)
        {
            System.out.println("At least " + minNumEdges + " are required to " +
                "connect each of the " + numVertices0 + " vertices " +
                "to any of the " + numVertices1 + " vertices");
            numEdges = minNumEdges;
        }

        for (int i = 0; i < numVertices0; i++)
        {
            V v = vertexFactory.createVertex();
            graph.addVertex(v);
            vertices0.add(v);
        }
        for (int i = 0; i < numVertices1; i++)
        {
            V v = vertexFactory.createVertex();
            graph.addVertex(v);
            vertices1.add(v);
        }

        // Connect each vertex of the larger set with
        // a random vertex of the smaller set
        Random random = new Random(0);
        List<V> larger = null;
        List<V> smaller = null;


        if (numVertices0 > numVertices1)
        {
            larger = new ArrayList<V>(vertices0);
            smaller = new ArrayList<V>(vertices1);
        }
        else
        {
            larger = new ArrayList<V>(vertices1);
            smaller = new ArrayList<V>(vertices0);
        }
        List<V> unmatched = new ArrayList<V>(smaller);
        for (V vL : larger)
        {
            int i = random.nextInt(unmatched.size());
            V vS = unmatched.get(i);
            unmatched.remove(i);
            if (unmatched.size() == 0)
            {
                unmatched = new ArrayList<V>(smaller);
            }
            graph.addEdge(vL, vS);
        }

        // Create the remaining edges between random vertices
        while (graph.edgeSet().size() < numEdges)
        {
            int i0 = random.nextInt(vertices0.size());
            V v0 = vertices0.get(i0);
            int i1 = random.nextInt(vertices1.size());
            V v1 = vertices1.get(i1);
            graph.addEdge(v0, v1);
        }

    }


}