graph generator problem 83
Back to Problem Solutions forum
My code was successful on the example input but not the test. For test input:
input = '13 784'
My output: 26 28 24 6 20 26 28 45 41 32 27 20 3 Expected output: 31 25 12 36 18 11 35 40 31 37 37 13 22
My randomizer gives the same first 8 random numbers as per the example.
I am not 100% sure how to interpret:
'Do not create edges connecting Vi with itself. Also do not create an edge from Vi to V1 or V2 if another edge already exists between them. Just skip them in both cases.'
The first part is clear (I think). Example if Vi is 2 and V1 is 2 do not create edge 2-2 of weight D1. Similarly if V2 is 2 do not create an edge 2-2 of weight D2. But say if V1 is 2 and V2 is 3 do I create an one edge 2-3 of weight D2?
The way I am interpreting the second part is example: Vi is 2 and V1 is 4 and V2 is 7. If there is not edge 2-4 or 4-2 or 2-7 or 7-2 it is OK to create and edge 2-4 of weight D1 and 2-7 of weight D2. If there is an edge 2-4 or 4-2 but not an edge 2-7 or 7-2 then do not create and edge 2-4 but OK to create an edge 2-7. Is this correct?
What Vi is say 2 and V1 equals V2 but neither of V1 nor V2 equals 2, say V1 == V2 == 8? Do you create one edge from Vi to 8?
The specification says: 'All edges should be undirected (i.e. two-way).' I interpret this to mean that if yo create an edge from 1 to 2 of length 1 and an edge from 1 to 10 of length 3 then immediately create an edge from 2 to 1 of length 1 and an edge from 10 to 1 of length 3. Is this correct?
Hi and thanks for your question!
...but OK to create an edge 2-7. Is this correct?
Yep, seems correct. The whole idea is that we do not want to have duplicate edges.
...Do you create one edge from Vi to 8?
Should be so, according to idea stated above. If not, then it is a bug... just tell...
All edges should be undirected
I think your understanding is correct. Creating two directed edges to represent one undirected is a common approach.
What puzzles me is that your answer seem to differ significantly from the expected one. Either for some reason there was a glitch (like page opened in two tabs and resetting data) - or there may be something more than just misinterpretation of duplicate edges, probably...
P.S. looking at the code you submitted:
if ((vertex, V1) not in edges or (vertex, V2) not in edges):
edge1, edge2 = (vertex, V1), (vertex, V2)
if vertex != V1:
edges.add(edge1)
graph[vertex].append((V1, D1))
I'm not sure, but probably here is a logic flaw. If (vertex,v1) is in edges and (vertex,v2) not you are
adding (vertex,v1) anyway. I think you can work both edges independently and the first long if is misleading.
Hi and thanks for prompt response.
I have changed my code to 'work both edges independently' as per your suggestion.
Again this gives the correct output on the example but not on the test.
I am still not sure my interpretation is correct.
The instructions say:
'for current vertex Vi (you will have a loop for i = 1 ... N) generate two pairs of random values V1 D1 V2 D2 and then connect Vi to V1 with an edge of weight D1 and to V2 with an edge of weight D2.'
If one of the conditions is not met, that is: 1) Vi == V1 or Vi == V2 in other words do not connect a vertex with itself; 2) Another edge already exists between Vi and V1 or Vi and V2
Do I not use any of the pairs of random values, that is do not create any edges for the current vertex Vi ?
or
Do I use one of the pairs of random values provided of course for that particular pair conditions 1 and 2 do not apply?
Your initial reply makes me think it is the latter but this does not seem to work for my code.
Hi again and sorry for delay...
If one of the conditions is not met
If one of two edges should not be added, nevertheless add another. I.e. treat them independently.
The idea is to be sure that any vertex has at least two neighbors.
Thanks again.
The age old trick of leaving the problem for a day and returning too it worked. My mistake was simple. Solved it.