The Gateway to Computer Science Excellence
0 votes
88 views
10 rooms, numbered 1 to 10, need to be rewired, but there are constraints on the order in
which this can get done.
Rooms 5 and 8 must be rewired before starting on 6
Room 1 must be rewired rewired before starting on 7 and 9
Rooms 4 and 5 must be rewired before starting on 2
Rooms 8 and 10 must be rewired before starting on 5
Room 3 must be rewired rewired before starting on 1 and 4
Rooms 9 and 7 must be rewired before starting on 10
Rooms 9 and 10 must be rewired before starting on 8
Rewiring a room takes one full day. In a day, any number of rooms can be rewired simultaneously
provided the constraints above are met. What is the minimum number of days required to complete the
rewiring?

a)  10

b)   9

c)   8

d)   7

 

In the solution they have drawn a DAG from this and then finded the longest paths.

"Longest paths are 3-1-9-10-8-5-2, 3-1-7-10-8-5-6, 3-1-9-10-8-5-6 and 3-1-7-10-8-5-2 each of length 7." <--quoted from answer

How is it done?How is it connected to DAG?
in Algorithms by Active (1.9k points) | 88 views
0
A different type indeed :P

1 Answer

+1 vote
Best answer

I have done it by topological sorting method..

I am going to explain it by table because drawing diagram might make it dirty. But I will suggest you to draw it on your own following the steps mentioned. Then it will be very easy for you to understand. Refer the table for verification purpose.

1. Create 10 nodes.

2. Draw a directed edge b/w the node u->v if v is dependent on u. For eg: " Rooms 8 and 10 must be rewired before starting on 5 " Here we have to draw an edge directing from 8 and another directed edge from 10 to node 5.

3. After making all the edges note down the in-degree of each node i.e. no. of edges directing to a node.

I got :

in_deg(1) 1 (directed from 3)
in_deg(2) 2 (directed from 4 and 5)
in_deg(3) 0
in_deg(4) 1 (directed from 3)
in_deg(5) 2 (directed from 8 and 10)
in_deg(6) 2 (directed from 5 and 8)
in_deg(7) 1 (directed from 1)
in_deg(8) 2 (directed from 9 and 10)
in_deg(9) 1 (directed from 1)
in_deg(10) 2 (directed from 7 and 9)

 

4. Now you can see that node 3 is the only independent node. It does not depend on any other node (indeg(3) =0). This means that before rewiring room no. 3 no other room needs to be rewired.

So start with 3 and cancel all the edges that originated from node 3. They are 1 and 4. So the indeg of 1 and 4 are reduced by 1.

What does this mean? Room no. 1 and 4 can be rewired only after 3 is done. [Point no. 5 in the list you gave ]

Now update the indeg of node 1 and 4.

in_deg(1) 1-1=0
in_deg(2) 2
in_deg(3) 0
in_deg(4) 1-1=0
in_deg(5) 2
in_deg(6) 2
in_deg(7) 1
in_deg(8) 2
in_deg(9) 1
in_deg(10) 2

 

Now since in degree of 1 and 4 are 0 it means they are now independent of any other node. Both can be processed simultaneously because it is given that :

 In a day, any number of rooms can be rewired simultaneously provided the constraints above are met.

So, till now 3,(1,4) are rewired.

5. Now update the table again and change the in degrees of those that that were dependent on 1 i.e. 9 and 7 and on 4 i.e. 2.

in_deg(1) 0
in_deg(2) 2-1=1
in_deg(3) 0
in_deg(4) 0
in_deg(5) 2
in_deg(6) 2
in_deg(7) 1-1=0
in_deg(8) 2
in_deg(9) 1-1=0
in_deg(10) 2

 

So in deg of 9,7 are 0 now. They can be processed simultaneously.

So, till now 3,(1,4),(7,9) are rewired.

6. Again update the table by decreasing the in degrees of those nodes that were dependent on 2,7,9.

10 is dependent on 7. 8 and 10 are dependent on 9.

Hence in deg of 10 will be reduced by 2.

in_deg(1) 0
in_deg(2) 1
in_deg(3) 0
in_deg(4) 0
in_deg(5) 2
in_deg(6) 2
in_deg(7) 0
in_deg(8) 2-1=1
in_deg(9) 0
in_deg(10) 2-2=0

So now in deg of 10 is 0 and no other node has in degree=0. Hence 10 is the only independent node at this stage.

So, till now 3,(1,4),(7,9),10 are rewired.

After rewiring room 10 we can move to room 5 and 8.

Decrease their in degree by 1.

 

7. Update the table:

in_deg(1) 0
in_deg(2) 1
in_deg(3) 0
in_deg(4) 0
in_deg(5) 2-1=1
in_deg(6) 2
in_deg(7) 0
in_deg(8) 1-1=0
in_deg(9) 0
in_deg(10) 0

 

Only node 8 has in degree 0. So process it and reduce the in degree of nodes dependent on 8 i.e. 6 and 5.

So, till now 3,(1,4),(7,9),10,8 are rewired.

8. Update the table :

in_deg(1) 0
in_deg(2) 0
in_deg(3) 0
in_deg(4) 0
in_deg(5) 1-1=0
in_deg(6) 2-1=1
in_deg(7) 0
in_deg(8) 0
in_deg(9) 0
in_deg(10) 0

 

Now only in degree of 5 is 0. 2 and 6 are dependent on 5. Reduce in degree of 2 and 6 by 1.

So, till now 3,(1,4),(7,9),10,8,5 are rewired.

9. Update the table :

in_deg(1) 0
in_deg(2) 1-1=0
in_deg(3) 0
in_deg(4) 0
in_deg(5) 0
in_deg(6) 1-1=0
in_deg(7) 0
in_deg(8) 0
in_deg(9) 0
in_deg(10) 0

 

Now 2 and 6 can also be processed.

So, till now 3,(1,4),(7,9),10,8,5,(2,6) are rewired.

If you notice the order, 7 days are needed to complete rewiring.

3 on 1st day. (1 and 4) on 2nd day. (7 and 9) on 3rd day and so on...

Longest paths are 3-1-9-10-8-5-2, 3-1-7-10-8-5-6, 3-1-9-10-8-5-6 and 3-1-7-10-8-5-2 each of length 7.

Satisfied :)

End :P

by Boss (23.5k points)
selected by
0
IES level solution :p #the_end i dont think anyone will ever have doubt from this topic now :p
0

arvin hehe :P :P

0
Waao, @minipanda, can you tell total number of topological orders possible?
0
Won't it be 4..that is all those 7 length paths mentioned?
0
You have taken 1 instead if we take 4, there will be more orders

Correct me?
0

Rishav Kumar Singh yes you are right.. I am getting too many orders now >:(  Getting hard to calculate.. how much did you get?

0
I left, by the time I found it so complex.
0
haha :P  I don't think so many nodes will be given during exam for finding topological order..even if there are many nodes, their in degrees shouldn't be too close to each other :p

Here after visiting one node the in degrees of so many other nodes are getting affected opening ways for so many orders!! -_-
0
You are right. I agree

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
198,343 comments
105,035 users