Channel Assignment Problem | A Depth First Search based recursive function that returns true if a matching for vertex u is possible ; Try every receiver one by one ; If sender u has packets to send to receiver v and receiver v is not already mapped to any other sender just check if the number of packets is greater than '0' because only one packet can be sent in a time frame anyways ; Mark v as visited ; If receiver ' v ' is not assigned to any sender OR previously assigned sender for receiver v ( which is matchR [ v ] ) has an alternate receiver available . Since v is marked as visited in the above line , matchR [ v ] in the following recursive call will not get receiver ' v ' again ; Returns maximum number of packets that can be sent parallely in 1 time slot from sender to receiver ; Initially all receivers are not mapped to any senders ; Count of receivers assigned to senders ; Mark all receivers as not seen for next sender ; Find if the sender ' u ' can be assigned to the receiver ; Driver Code
def bpm ( table , u , seen , matchR ) : NEW_LINE INDENT global M , N NEW_LINE for v in range ( N ) : NEW_LINE INDENT if ( table [ u ] [ v ] > 0 and not seen [ v ] ) : NEW_LINE INDENT seen [ v ] = True NEW_LINE if ( matchR [ v ] < 0 or bpm ( table , matchR [ v ] , seen , matchR ) ) : NEW_LINE INDENT matchR [ v ] = u NEW_LINE return True NEW_LINE DEDENT DEDENT DEDENT return False NEW_LINE DEDENT def maxBPM ( table ) : NEW_LINE INDENT global M , N NEW_LINE matchR = [ - 1 ] * N NEW_LINE result = 0 NEW_LINE for u in range ( M ) : NEW_LINE INDENT seen = [ 0 ] * N NEW_LINE if ( bpm ( table , u , seen , matchR ) ) : NEW_LINE INDENT result += 1 NEW_LINE DEDENT DEDENT print ( " The ▁ number ▁ of ▁ maximum ▁ packets ▁ sent " , " in ▁ the ▁ time ▁ slot ▁ is " , result ) NEW_LINE for x in range ( N ) : NEW_LINE INDENT if ( matchR [ x ] + 1 != 0 ) : NEW_LINE INDENT print ( " T " , matchR [ x ] + 1 , " - > ▁ R " , x + 1 ) NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT M = 3 NEW_LINE N = 4 NEW_LINE table = [ [ 0 , 2 , 0 ] , [ 3 , 0 , 1 ] , [ 2 , 4 , 0 ] ] NEW_LINE max_flow = maxBPM ( table ) NEW_LINE