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.

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.

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.

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).

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.