There are M transmitter and N receiver stations. Given a matrix that keeps track of the number of packets to be transmitted from a given transmitter to a receiver. If the (i; j)-th entry of the matrix is k, it means at that time the station i has k packets for transmission to station j.
During a time slot, a transmitter can send only one packet and a receiver can receive only one packet. Find the channel assignments so that maximum number of packets are transferred from transmitters to receivers during the next time slot.
Example:
0 2 0 3 0 1 2 4 0
The above is the input format. We call the above matrix M. Each value M[i; j] represents the number of packets Transmitter ‘i’ has to send to Receiver ‘j’. The output should be:
The number of maximum packets sent in the time slot is 3 T1 -> R2 T2 -> R3 T3 -> R1
Note that the maximum number of packets that can be transferred in any slot is min(M, N).
[ad type=”banner”]Algorithm:
The channel assignment problem between sender and receiver can be easily transformed into Maximum Bipartite Matching(MBP) problem that can be solved by converting it into a flow network.
Step 1: Build a Flow Network
There must be a source and sink in a flow network. So we add a dummy source and add edges from source to all senders. Similarly, add edges from all receivers to dummy sink. The capacity of all added edges is marked as 1 unit.
Step 2: Find the maximum flow.
We use Ford-Fulkerson algorithm to find the maximum flow in the flow network built in step 1. The maximum flow is actually the maximum number of packets that can be transmitted without bandwidth interference in a time slot.
Implementation:
Let us first define input and output forms. Input is in the form of Edmonds matrix which is a 2D array ‘table[M][N]‘ with M rows (for M senders) and N columns (for N receivers). The value table[i][j] is the number of packets that has to be sent from transmitter ‘i’ to receiver ‘j’. Output is the maximum number of packets that can be transmitted without bandwidth interference in a time slot.
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.
Extra space can be reduced and code can be simplified using the fact that the graph is bipartite. The idea is to use DFS traversal to find a receiver for a transmitter (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 receiver to the sender. In bpm(), we one by one try all receivers that a sender ‘u’ is interested in until we find a receiver, or all receivers are tried without luck.
For every receiver we try, we do following:
If a receiver is not assigned to anybody, we simply assign it to the sender and return true. If a receiver is assigned to somebody else say x, then we recursively check whether x can be assigned some other receiver. To make sure that x doesn’t get the same receiver again, we mark the receiver ‘v’ as seen before we make recursive call for x. If x can get other receiver, we change the sender for receiver ‘v’ and return true. We use an array maxR[0..N-1] that stores the senders assigned to different receivers.
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().
Time and space complexity analysis:
In case of bipartite matching problem, F ? |V| since there can be only |V| possible edges coming out from source node. So the total running time is O(m’n) = O((m + n)n). The space complexity is also substantially reduces from O ((M+N)*(M+N)) to just a single dimensional array of size M thus storing the mapping between M and N.
C++ Programming:
[pastacode lang=”cpp” manual=”%23include%20%3Ciostream%3E%0A%23include%20%3Cstring.h%3E%0A%23include%20%3Cvector%3E%0A%23define%20M%203%0A%23define%20N%204%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20Depth%20First%20Search%20based%20recursive%20function%20that%20returns%20true%0A%2F%2F%20if%20a%20matching%20for%20vertex%20u%20is%20possible%0Abool%20bpm(int%20table%5BM%5D%5BN%5D%2C%20int%20u%2C%20bool%20seen%5B%5D%2C%20int%20matchR%5B%5D)%0A%7B%0A%20%20%20%20%2F%2F%20Try%20every%20receiver%20one%20by%20one%0A%20%20%20%20for%20(int%20v%20%3D%200%3B%20v%20%3C%20N%3B%20v%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20sender%20u%20has%20packets%20to%20send%20to%20receiver%20v%20and%0A%20%20%20%20%20%20%20%20%2F%2F%20receiver%20v%20is%20not%20already%20mapped%20to%20any%20other%20sender%0A%20%20%20%20%20%20%20%20%2F%2F%20just%20check%20if%20the%20number%20of%20packets%20is%20greater%20than%20’0’%0A%20%20%20%20%20%20%20%20%2F%2F%20because%20only%20one%20packet%20can%20be%20sent%20in%20a%20time%20frame%20anyways%0A%20%20%20%20%20%20%20%20if%20(table%5Bu%5D%5Bv%5D%3E0%20%26%26%20!seen%5Bv%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20seen%5Bv%5D%20%3D%20true%3B%20%2F%2F%20Mark%20v%20as%20visited%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20receiver%20’v’%20is%20not%20assigned%20to%20any%20sender%20OR%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20previously%20assigned%20sender%20for%20receiver%20v%20(which%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20matchR%5Bv%5D)%20has%20an%20alternate%20receiver%20available.%20Since%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20v%20is%20marked%20as%20visited%20in%20the%20above%20line%2C%20matchR%5Bv%5D%20in%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20the%20following%20recursive%20call%20will%20not%20get%20receiver%20’v’%20again%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(matchR%5Bv%5D%20%3C%200%20%7C%7C%20bpm(table%2C%20matchR%5Bv%5D%2C%20seen%2C%20matchR))%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20matchR%5Bv%5D%20%3D%20u%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20maximum%20number%20of%20packets%20that%20can%20be%20sent%20parallely%20in%201%0A%2F%2F%20time%20slot%20from%20sender%20to%20receiver%0Aint%20maxBPM(int%20table%5BM%5D%5BN%5D)%0A%7B%0A%20%20%20%20%2F%2F%20An%20array%20to%20keep%20track%20of%20the%20receivers%20assigned%20to%20the%20senders.%0A%20%20%20%20%2F%2F%20The%20value%20of%20matchR%5Bi%5D%20is%20the%20sender%20ID%20assigned%20to%20receiver%20i.%0A%20%20%20%20%2F%2F%20the%20value%20-1%20indicates%20nobody%20is%20assigned.%0A%20%20%20%20int%20matchR%5BN%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Initially%20all%20receivers%20are%20not%20mapped%20to%20any%20senders%0A%20%20%20%20memset(matchR%2C%20-1%2C%20sizeof(matchR))%3B%0A%20%0A%20%20%20%20int%20result%20%3D%200%3B%20%2F%2F%20Count%20of%20receivers%20assigned%20to%20senders%0A%20%20%20%20for%20(int%20u%20%3D%200%3B%20u%20%3C%20M%3B%20u%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Mark%20all%20receivers%20as%20not%20seen%20for%20next%20sender%0A%20%20%20%20%20%20%20%20bool%20seen%5BN%5D%3B%0A%20%20%20%20%20%20%20%20memset(seen%2C%200%2C%20sizeof(seen))%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20if%20the%20sender%20’u’%20can%20be%20assigned%20to%20the%20receiver%0A%20%20%20%20%20%20%20%20if%20(bpm(table%2C%20u%2C%20seen%2C%20matchR))%0A%20%20%20%20%20%20%20%20%20%20%20%20result%2B%2B%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22The%20number%20of%20maximum%20packets%20sent%20in%20the%20time%20slot%20is%20%22%0A%20%20%20%20%20%20%20%20%20%3C%3C%20result%20%3C%3C%20%22%5Cn%22%3B%0A%20%0A%20%20%20%20for%20(int%20x%3D0%3B%20x%3CN%3B%20x%2B%2B)%0A%20%20%20%20%20%20%20%20if%20(matchR%5Bx%5D%2B1!%3D0)%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22T%22%20%3C%3C%20matchR%5Bx%5D%2B1%20%3C%3C%20%22-%3E%20R%22%20%3C%3C%20x%2B1%20%3C%3C%20%22%5Cn%22%3B%0A%20%20%20%20return%20result%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20table%5BM%5D%5BN%5D%20%3D%20%7B%7B0%2C%202%2C%200%7D%2C%20%7B3%2C%200%2C%201%7D%2C%20%7B2%2C%204%2C%200%7D%7D%3B%0A%20%20%20%20int%20max_flow%20%3D%20maxBPM(table)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]Output:
The number of maximum packets sent in the time slot is 3 T3-> R1 T1-> R2 T2-> R3