Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Channel Assignment Problem
2.1.
Example
2.1.1.
Input 
2.1.2.
Output
2.1.3.
Explanation
3.
Algorithm
4.
Explanation
5.
Implementation in C
5.1.
Input
5.2.
Output
6.
Time Complexity
7.
Space Complexity
8.
Frequently Asked Questions
8.1.
What is the channel assignment problem?
8.2.
Which algorithm is used to solve assignment problems?
8.3.
What is a graph in data structures?
8.4.
What are the advantages of graphs?
8.5.
What do you mean by static channel allocation?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Channel Assignment Problem

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A group of nodes with data and connections to other nodes makes up a graph data structure. Let's use an illustration to try to comprehend this. Everything on Instagram is a node. Everything with data is a node, including Account, Photo, Event, Group, Page, Comment, Story, Video, Link, and Note. 

Every connection between two nodes is an edge. If you share a photo, join a group, "like" a page, etc., that relationship gains a new edge.

Introduction

In this problem, we will discuss a graph data structure problem in detail including its time and space complexity.

Channel Assignment Problem

There are N receiver stations and M transmitter stations. From the graph, count the number of packets that are sent from sender to receiver.

  • If the ( i, j)-th entry in the matrix has a value of k, the station “i” is now transmitting “k” packets to station “j”.
     
  • A transmitter and a receiver are each only allowed to send and receive one packet per time slot. 

In order to send the most packets from transmitters to receivers within the next window of time, identify the channel assignments that will allow this.

Example

Input 

Number of Sender = 3
Number of reciever  = 2
Values of Graph
4 5 2
1 3 2

Output

1-->2
2-->1

Explanation

Keep in mind that each slot has a maximum amount of packets that can be sent, which is min (m, n). In the about example the minimum number from sender and receiver is 2 so that, two packets can be sent in the time window at most.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

The Maximum Bipartite Matching (MBM) problem, which can be addressed by changing it into a flow network, can be simply transformed from the channel assignment problem between sender and receiver.

Maximum Bipartite Matching (MBM)
  • Create a Flow Network

We add a fake source and add source edges to all senders. Add edges from each receiver to the dummy sink in a similar manner. All additional edges' combined capacity is indicated as 1 unit.

  • Calculate the maximum flow

To determine the maximum flow in the flow network constructed in step 1, we apply the Ford-Fulkerson algorithm. The amount of packets that can be transmitted in a time slot without incurring bandwidth issues is the maximum flow.

Explanation

Edmonds matrix input takes the form of a graph, where m is the number of senders and n is the number of receivers.

  • The graph shows how many packets must be transmitted from transmitter i to receiver "j".
     
  • Output is the maximum amount of packets that can be transferred within a time period without incurring bandwidth interference.
     
  • Making a matrix that depicts the adjacency matrix representation of a directed graph with m+n+2 vertices is an easy approach to putting this into practice.
     
  • For the matrix, use the ford_Fulkerson() method. The extra space needed for this implementation is O((m+n)*(m+n)).
     
  • The graph's bipartite nature allows for the reduction of extra space and the simplification of the code. 
     
  • The plan is to locate a receiver for a transmitter using DFS traversal.
     
  • Every applicant receives a call, a DFS Algorithm-based function that attempts every possible option to match the sender and receiver.
     
  • All of the receivers that a sender is interested in are tested one by one until a match is made or all receivers have been tested in vain.

Implementation in C


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int ** enter_M_N(int m, int n);
void compute(int ** g, int m, int n);

bool dfs_util(int ** res, int m, int n, int unknown, int des, bool *vis);
void matrix(int ** g, int n);

//passing m and n as parameters.
int ** enter_M_N(int m, int n){

     int ** g;
     int ** temp;
     int i;
     int j;
     
     //allocating malloc size of m into temp.
     temp = malloc(sizeof(int *) *m);
     
     // Malloc for m.
     for (i = 0; i < m; i++)
           temp[i] = malloc(sizeof i *n);
     for (i = 0; i < m; i++)
           for (j = 0; j < n; j++)
                 scanf("%d", &temp[i][j]);
     g = malloc(sizeof(int *) *(m + n + 2));
     
     // matrix representation of a directed graph with m+n+2 vertices
     for (i = 0; i < m + n + 2; i++)
           g[i] = malloc(sizeof i *(m + n + 2));
           
     for (i = 0; i < m + n + 2; i++)
           for (j = 0; j < m + n + 2; j++)
                 g[i][j] = 0;

     for (i = 1; i < m + 1; i++)
           g[0][i] = 1;

     matrix representation of a directed graph with m + n + 1 vertices
     
     for (i = m + 1; i < m + n + 1; i++)
           g[i][m + n + 1] = 1;
           
     for (i = 0; i < m; i++)
           for (j = 0; j < n; j++)
                 g[i + 1][m + j + 1] = temp[i][j];
     matrix(temp, m);
     
     return g;
}

//Main function. 
int main(void)
{
     int m;
     int n;
     int ** g;
     
     //We are taking input from the user m.
     printf("Enter m\t");
     scanf("%d", &m);
     
     //We are taking input from the user n.
     printf("\n");
     printf("Enter n\t");
     scanf("%d", &n);
     printf("\n");
     
     //We are taking input from the user graph value.
     printf("Input the graph\n");
     g = enter_M_N(m, n);
     compute(g, m, n);
     matrix(g, m + n + 2);
     return 0;
}

// computing the number of packets can be transferred.
void compute(int ** g, int m, int n)
{
     int i;
     int j;
     int result;
     int ** res;
     bool *vis;
     
     //allocating size
     res = malloc(sizeof(int *) *(m + n + 2));
     for (i = 0; i < m + n + 2; i++)
           res[i] = malloc(sizeof i *(m + n + 2));
     for (i = 0; i < m + n + 2; i++)
           for (j = 0; j < m + n + 2; j++)
                 res[i][j] = g[i][j];
                 
     //storing bool size of m+n+2
     vis = malloc(sizeof(bool) *(m + n + 2));
     for (i = 0; i < m + n + 2; i++)
           vis[i] = 0;
     result = 0;
     
     for (i = 1; i < m + 1; i++)
           if (dfs_util(res, m, n, i, m + n + 1, vis))
           {
                 res[0][i]--;
                 res[i][0]++;
                 result++;
           }
           
     //Printing total maximum transfer packets.
     printf("Maximum transfer is %d packets\n", result);
     
     for (i = 1; i < m + 1; i++)
           for (j = m + 1; j < m + n + 1; j++)
                 if (g[i][j] > res[i][j])
                       // Printing transfer packets.
                       printf("%d-->%d\n", i, j - m);
     free(vis);
     matrix(res, m + n + 2);
}

// dfs transverse.
bool dfs_util(int ** res, int m, int n, int unknown, int des, bool *vis)
{
     int i;
     if (unknown == des)
           return 1;
     vis[unknown] = 1;
     for (i = 1; i < m + n + 2; i++)
           if (res[unknown][i] && !vis[i] && dfs_util(res, m, n, i, des, vis))
           {
                 res[unknown][i]--;
                 res[i][unknown]++;
                 vis[unknown] = 0;
                 return 1;
           }
     vis[unknown] = 0;
     return 0;
}

// Matrix function defining.
void matrix(int ** g, int n)
{
     int i;
     for (i = 0; i < n; i++)
           free(g[i]);
     free(g);
}

Input

Enter m     3
Enter n 2
Input the graph
4
5
2
1
3
4

Output

Maximum transfer is 2 packets
1-->2
2-->1

Time Complexity

O((M + N) * N): Where m is the number of senders and n is the number of receivers. 

Reason: Because only edges can exit the source node. O((M + N) * N) is the total running time complexity.

Time Complexity

Read More - Time Complexity of Sorting Algorithms

Space Complexity

O(M): Where m is the number of senders and n is the number of receivers. 

Reason: By storing the mapping between M and N in a single-dimensional array of size M, the space complexity is also significantly decreased from O((M + N)^2).

Check out this problem - Smallest Distinct Window.

Frequently Asked Questions

What is the channel assignment problem?

A channel assignment problem is a triple (V, E, w), where V is a collection of vertex elements, E is a set of pairings of those elements (referred to as edges), and w is a function that gives the edges of E positive integer weights.

Which algorithm is used to solve assignment problems?

This illustrates a homework issue that the Hungarian Algorithm can resolve. When assigning people to activities based on cost, the Hungarian Algorithm determines the minimum price; each activity must be assigned to a distinct person.

What is a graph in data structures?

A graph is a non-linear data structure consisting of a finite number of nodes or vertices connected by edges. In data structures, graphs are used to handle problems in the actual world by simulating the problem area as a network, such as social networks, telephone networks, and circuit networks.

What are the advantages of graphs?

Better Problem-Solving Performance with Object-Oriented Thinking Update Data in Real-Time and Support Queries Flexible Online Schema Environment.

What do you mean by static channel allocation?

It is defined as the amount of the frequency channel allocated to each user under the old technique of channel allocation known as static channel allocation. Users might be base stations, access points, or terminal devices.

Conclusion

That concludes the Channel Assignment Problem. To better understand, check out the various examples and run the code in your Compiler.

Check out these questions. It will help you in exploring path-finding algorithms similar to Channel Assignment Problem.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow. 

Comment here with any questions or concerns you may have about the post.

Happy Learning Ninja! 🥷

Previous article
What is the Sieve Method?
Next article
Travelling Salesman Problem | Part 2
Live masterclass