Graph::bipartiteMatching

Function

vector<Edge<T> > bipartiteMatching(vector <T> m, vector<T> m1);
vector<Edge<T> > bipartiteMatching(vector <Vertex<T> > v, vector<Vertex<T> > v1);

Get the edges of the maximum bipartite matching by given the vertices of two independent sets.

Parameters

m, m1
vector of label of vertices of two independent sets in the bipartite graph.

v, v1
vector of vertices of two independent sets in the bipartite graph.

Return value

Return vector of edges of the bipartite graph maximum matching.

Example

#include "HKUAL_graph.h"
#include <iostream>
#include <vector>
using namespace std;
using namespace HKUAL;

int main(){
    Graph<string> g;
    g.addVertex("A");
    g.addVertex("B");
    g.addVertex("C");
    g.addEdge("A", "B");
    g.addEdge("A", "C");
 
    vector<string> v1, v2;
    v1.push_back("A");
    v1.push_back("B");
    v1.push_back("C");
    v2.push_back("D");
    v2.push_back("E");
    v2.push_back("F");
	
    vector <Edge<string> > result;
    result = g.bipartitemMatching(v1, v2);
    for (int i = 0; i < result.size(); i++){
        cout << result[i].X << ' ' << result[i].Y << endl;
    }
    return 0;
}

Output

Time Complexity

, for is number of edges and is total number of vertices.