{"id":26653,"date":"2017-12-21T21:12:07","date_gmt":"2017-12-21T15:42:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26653"},"modified":"2017-12-21T21:12:07","modified_gmt":"2017-12-21T15:42:07","slug":"python-algorithm-maximum-bipartite-matching","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-maximum-bipartite-matching\/","title":{"rendered":"Python Algorithm – Maximum Bipartite Matching"},"content":{"rendered":"

A matching in a Bipartite Graph is a set of the edges chosen in such a way that no two edges share an endpoint. A maximum matching is a matching of maximum size (maximum number of edges). <\/span>In a maximum matching, if any edge is added to it, it is no longer a matching. There can be more than one maximum matchings for a given Bipartite Graph.<\/p>\n

Why do we care?<\/strong>
\nThere are many real world problems that can be formed as Bipartite Matching. For example, consider the following problem:
\nThere are M job applicants and N jobs. Each applicant has a subset of jobs that he\/she is interested in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Find an assignment of jobs to applicants in such that as many applicants as possible get jobs.<\/em><\/p>\n

We strongly recommend to read the following post first.<\/p>\n

Ford-Fulkerson Algorithm for Maximum Flow Problem<\/p>\n

Maximum Bipartite Matching and Max Flow Problem<\/strong>
\nM<\/strong>aximum B<\/strong>ipartite M<\/strong>atching (MBP<\/strong>) problem can be solved by converting it into a flow network (See this video to know how did we arrive this conclusion). Following are the steps.<\/p>\n

1) Build a Flow Network<\/strong><\/em>
\nThere must be a source and sink in a flow network. So we add a source and add edges from source to all applicants. Similarly, add edges from all jobs to sink. The capacity of every edge is marked as 1 unit.<\/p>\n

2) Find the maximum flow.
\nWe use Ford-Fulkerson algorithm to find the maximum flow in the flow network built in step 1. The maximum flow is actually the MBP we are looking for.<\/p>\n[ad type=”banner”]\nHow to implement the above approach?<\/strong>
\nLet us first define input and output forms. Input is in the form of Edmonds matrix which is a 2D array \u2018bpGraph[M][N]\u2019 with M rows (for M job applicants) and N columns (for N jobs). The value bpGraph[i][j] is 1 if i\u2019th applicant is interested in j\u2019th job, otherwise 0.
\nOutput is number maximum number of people that can get jobs.<\/p>\n

A simple way to implement this is to create a matrix that represents adjacency matrix representation of a directed graph with M+N+2 vertices. Call the fordFulkerson() for the matrix. This implementation requires O((M+N)*(M+N)) extra space.<\/p>\n

Extra space can be be reduced and code can be simplified using the fact that the graph is bipartite and capacity of every edge is either 0 or 1. The idea is to use DFS traversal to find a job for an applicant (similar to augmenting path in Ford-Fulkerson). We call bpm() for every applicant, bpm() is the DFS based function that tries all possibilities to assign a job to the applicant.<\/p>\n

In bpm(), we one by one try all jobs that an applicant \u2018u\u2019 is interested in until we find a job, or all jobs are tried without luck. For every job we try, we do following.
\nIf a job is not assigned to anybody, we simply assign it to the applicant and return true. If a job is assigned to somebody else say x, then we recursively check whether x can be assigned some other job. To make sure that x doesn\u2019t get the same job again, we mark the job \u2018v\u2019 as seen before we make recursive call for x. If x can get other job, we change the applicant for job \u2018v\u2019 and return true. We use an array maxR[0..N-1] that stores the applicants assigned to different jobs.<\/p>\n

If bmp() returns true, then it means that there is an augmenting path in flow network and 1 unit of flow is added to the result in maxBPM()<\/p>\n[ad type=”banner”]\n

Python Programming:<\/strong><\/p>\n

<\/div> 
# Python program to find maximal Bipartite matching. class Graph:    def __init__(self,graph):        self.graph = graph # residual graph        self.ppl = len(graph)        self.jobs = len(graph[0])     # A DFS based recursive function that returns true if a    # matching for vertex u is possible    def bpm(self, u, matchR, seen):         # Try every job one by one        for v in range(self.jobs):             # If applicant u is interested in job v and v is            # not seen            if self.graph[u][v] and seen[v] == False:                seen[v] = True # Mark v as visited                 '''If job 'v' is not assigned to an applicant OR                previously assigned applicant for job v (which is matchR[v])                 has an alternate job available.                 Since v is marked as visited in the above line, matchR[v]                 in the following recursive call will not get job 'v' again'''                if matchR[v] == -1 or self.bpm(matchR[v], matchR, seen):                    matchR[v] = u                    return True        return False     # Returns maximum number of matching     def maxBPM(self):        '''An array to keep track of the applicants assigned to        jobs. The value of matchR[i] is the applicant number        assigned to job i, the value -1 indicates nobody is        assigned.'''        matchR = [-1] * self.jobs        result = 0 # Count of jobs assigned to applicants        for i in range(self.ppl):            # Mark all jobs as not seen for next applicant.            seen = [False] * self.jobs            # Find if the applicant 'u' can get a job            if self.bpm(i, matchR, seen):                result += 1        return result  bpGraph =[[0, 1, 1, 0, 0, 0],        [1, 0, 0, 1, 0, 0],        [0, 0, 1, 0, 0, 0],        [0, 0, 1, 1, 0, 0],        [0, 0, 0, 0, 0, 0],        [0, 0, 0, 0, 0, 1]] g = Graph(bpGraph) print ("Maximum number of applicants that can get job is %d " % g.maxBPM()) #This code is contributed by Neelam Yadav<\/code><\/pre> <\/div>\n
\n
\n
\n
Output:<\/strong><\/p>\n
Maximum number of applicants that can get job is 5<\/pre>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Python Algorithm – Maximum Bipartite Matching – Graph Algorithm –  A matching in a Bipartite Graph is a set of the edges chosen in such a way<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73906,78429],"tags":[79579,79577,79482,79576,79488,79271,79483,79491,79490,79485,79578,79484],"class_list":["post-26653","post","type-post","status-publish","format-standard","hentry","category-graph-algorithms","category-maximum-flow","tag-bipartite-matching-algorithm-c","tag-bipartite-matching-linear-programming","tag-bipartite-matching-network-flow","tag-bipartite-matching-python","tag-ford-fulkerson-bipartite-matching","tag-hopcroft-karp-algorithm","tag-hopcroft-karp-algorithm-c","tag-maximum-bipartite-matching-java","tag-maximum-matching-algorithm","tag-maximum-matching-in-bipartite-graphs-video","tag-minimum-bipartite-matching","tag-weighted-bipartite-matching"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26653","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26653"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26653\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26653"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26653"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26653"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}