0

我正在尝试使用 QuickGraph 在我的二分图中找到最大匹配，但是他们返回给我的 MatchedEdges 集合是空的。我知道有匹配项，因为我用 K7,7（完全二分）图对其进行了测试。所以，我对自己做错了什么感到困惑。

这是我的代码（为了便于阅读，我编写了 Vertex 和 Edge 来代替我的实际类）：

    public void findMatchings(List<Friend> setA, List<Friend> setB, List<Edge> candidateEdges) {
        // we need a graph and two sets of vertices
        IMutableVertexAndEdgeListGraph<Vertex, Edge> graph = new AdjacencyGraph<Vertex, Edge>();

        foreach (Vertex vertex in setA) {
            graph.AddVertex(vertex);
        }

        foreach (Vertex vertex in setB) {
            graph.AddVertex(vertex);
        }

        foreach (Edge candidate in candidatesEdges) {
            graph.AddEdge(candidate);
        }

        // sets a and b must be distinct, and their union must be equal to the set of all vertices in the graph
        // (though they're conceptually the same set, to you or me, I created new instances of everything so they should be practically different.)
        IEnumerable<Vertex> vertexSetA = setA;
        IEnumerable<Vertex> vertexSetB = setB;

        // These functions are used to create new vertices and edges during the execution of the algorithm.  
        // All added objects are removed before the computation returns
        VertexFactory<Vertex> vertexFactory = newVertex; //newVertex() is defined below
        EdgeFactory<Vertex, Edge> edgeFactory = (source, target) => new Edge(source, target);

        // computing the maximum bipartite match
        var maxMatch = new MaximumBipartiteMatchingAlgorithm<Vertex, Edge>(
                graph, vertexSetA, vertexSetB, vertexFactory, edgeFactory);

        Console.WriteLine(maxMatch.MatchedEdges.Count);

    }

    //This is in the same class as the above function:
    static Vertex newVertex() {
        return new Vertex("");
    }

    //This is the constructor in the Edge class:
    public Edge(Vertex source, Vertex target) {
        this.source = source;
        this.target = target;
    }

maxMatch.MatchedEdges.Count 总是返回为 0。这就是问题所在。

我希望有一个简单的解决方案来解决这个问题，比如我不应该使用 new AdjacencyGraph() 或其他东西，但我也愿意接受关于在二分图中找到最大匹配的其他方法的建议。

谢谢！

顺便说一句，这个链接是我用来写东西的： Maximum Bipartite Matching in QuickGraph

4

1 回答 1

1

创建 的实例后MaximumBipartiteMatchingAlgorithm，您需要调用其 Compute 方法以便计算匹配。就您的示例而言，这意味着添加：

maxMatch.Compute();

此外，对该方法的每次调用newVertex()都应返回一个唯一的字符串，该字符串与标识输入中顶点的字符串不同MaximumBipartiteMatchingAlgorithm。

仅供参考：我个人发现有时maxMatch.MatchedEdges包含太多边：一些顶点被覆盖两次。我还看到maxMatch.MatchedEdges包含不在 MaximumBipartiteMatchingAlgorithm 输入中但由算法在内部创建的边缘。

于 2016-07-06T07:51:06.380 回答