Algorithm GRCOV
G (bipartite graph example to be used in this code):
G = np.array([
[1, 0, 1, 0, 0], # c1 connected to b1 and b3
[0, 1, 0, 0, 1], # c2 connected to b2 and b5
[0, 0, 0, 1, 1], # c3 connected to b4 and b5
[0, 0, 0, 0, 1] # c4 connected to b5
])
Initialization:
G = 4x5 matrix above
N (clients) =4
M (messages) =5
t=1 (number of edge needed to satisfy a client)
C = {} (empty code set)
B = {} (empty message set)
CNT[1] = t (Here CNT[1] means counter for client 1 which is equal to t)
CNT[2] = t
CNT[3] = t
CNT[4] = t
The main thing is we are trying to find is a maximal set of message by greedily adding messages to the
clients and seeing which clients are satisfied. One client will be satisfied with only one message (because
we know t = 1). For example in the graph G, we can see the |w1(b)| values by trying different
combinations, and we start by sending one message to the 4 clients:
w1(b) |w1(b)|
b1 1 (1 because b1 is connected to c1 with only 1 edge, so we keep b1)
b1,b2 2 (2 because b1 is connected to c1, b2 is connected to c2, and value of |w1(b)|
increased from 1, so we take this)
b1,b2,b3 1 (since it decreased from 2, we don't take b3 and check combination again
from b4)
b1,b2,b4 3 (increased from 2, so we take this)
b1,b2,b4,b5 2 (value decreased, so we ignore)
Note that we don’t stop the loop here! At this point, we don’t have any b6 or b7 to send, so we do one
last sweep to check if |w1(b)| value increases or decreases. By last sweep, it means to check any other
possible bit combination, for example – b1,b2,b4,b3 (we didn’t test this earlier). If |w1(b)| value
increases, we keep the combination and continue until |w1(b)| value decreases. Then we do another
last sweep to check if |w1(b)| value increases or decreases. The loop finally stops until it checks every
single bit combination possible for all remaining bits.
To find the maximal set for example, after the loop stops, we can say b1,b2,b4 whose value of
|w1(b)|=3 is the maximal set and we need to add b1,b2,b4 to message set B (B was previously initialized
as empty set).
Then the C set is updated to be b1+b2+b4 which is represented by matrix in the code = [1, 1, 0, 1, 0 ]
The edges responsible for the maximal set of messages above are removed from G, and CNT values of
the clients satisfied which in this case is C1,C2 and C3 becomes 0 from 1.
CNT[1] = 0
CNT[2] = 0
CNT[3] = 0
CNT[4] = 1
Then we repeat the same process. For example, now the graph G (after removing edges) will have c1
connecting to b3, then c2 connecting to b5, then c3 connecting to b5 and then c4 connecting to b5.
G after removing the edges corresponding to the maximal set of messages:
w1(b) |w1(b)|
b1 0 (ignore because it's not 1)
b2 0 (ignore) b3 1 (we keep this)
b3,b4 1 (didn't increase, so we ignore)
b3,b5 4 (value increased from 1, so we keep)
We say b3,b5 whose value of |w1(b)|=4 is the maximal set and we add b3,b5 to message set B in a
separate row (previously filled with b1,b2,b4). Satisfied edges are removed and CNT is updated. We can
see all 4 clients are satisfied and all edges have been removed from the graph. So we end the while loop.
CNT[1] = 0
CNT[2] = 0
CNT[3] = 0
CNT[4] = 0
Finally output C which is b1+b2+b4 and b3+b5 which is represented by matrix in the code = [1, 1, 0, 1, 0
], [0, 0, 1, 0, 1 ]
Code length = 2 (print it)
Please print out all steps to find exactly what’s happening at each step.
NOTE: In the example above, the final output can be different as I didn’t check every single bit
combination, but the algorithm needs to check every single bit combination.
implement by python.