[Tutor] Fwd: Graph question was: Re: (no subject)

[dn]

On 16/03/2021 13.34, Alan Gauld via Tutor wrote:
> On 15/03/2021 23:56, Alan Gauld wrote:
> 
>> I have written it in a more readable format.
>> In this problem, you need to create a program for managing Graphs. The
>> input to the program will be as described next: The first line will
>> contain a positive integer NN. NNdenotes the number of nodes in the
>> graph. Nodes themselves are numbered from 0 to N−1N−1.
> 
> I'm probably just being dense but I still don't understand this.
> 
> It says the number is NN which denotes the number of nodes.
> I'd read that as a two digit number.
> 
> Then it says it ranges from 0 to N-1
> That suggests to me that the number of nodes should really
> read the index of the highest node? Maybe? Except...
> 
> It says "numbered from 0 to N-1N-1" which suggests that if
> N is, say, 5 the numbering could be up to 44?
> Which makes no sense to me at all!
> 
>>  The second line will contain a non-negative integer MM(M≥0M≥0). This
>> will be the number of edges in the graph (However, some of these could
>> be invalid/duplicate). 
> 
> This has a similar issue in that how is a single number of edges
> represented using a double digit?
> 
> And when we look at the sample data below the first
> two "lines" are both single digits...
> 
>> The next MMlines each will contain a pair of
>> integers i,ji,jrepresenting a directed edge i→ji→j. Self edges (i→ii→i)
>> are allowed. However, multi-edges (two or more instances of i→ji→j) have
>> to be stored only once. Last line will contain an integer kk. 
> 
> And what is kk supposed to be? There is no explanation.
> 
>>  If kkrepresents a valid node, print all the nodes
>> sssuch that s→ks→kis a (directed) edge in the graph. 
> 
> OK, Now we have a sort of explanation for kk - it might be a node.
> but we introduce a new term s. What is s?
> 
>> ___________________________________ INPUT: 3 4 0,1 1,2 2,0 0,2 2 OUTPUT:
>> 0,1 
> 
> I assume this should be written:
> 
> 3
> 4
> 0,1
> 1,2
> 2,0
> 0,2
> 2
> 
> ie 3 nodes, 4 edges and the mystery node is 2.
> The solution is apparently 0,1 but I'm not sure why?
> 
> As I say, it's probably me missing something (and my
> graph theory days are long behind me so that's very
> likely!)
> 
> But unless we understand what the data represents
> and how the output should be calculated we can't
> begin to discuss what the Python code might look
> like.


+1


The first confusion, eg "NN", is likely caused by a failed transition
from the original format of the assignment into email. It makes sense
when one ignores the duplication, instead reading "N" or "N−1"...

Your re-formatting of the graph-data makes tremendous sense - because it
is so much easier to read!

It is a case where I'd be recommending the use of JSON/YAML (even XML)
to avoid errors through self-documentation, eg

nodes_count: 3
edges_count: 4
edge: 0,1
...

NB don't quote me - I can't remember the exact purposes of each of those
numbers. Also, I fail to see why the second is necessary if there are
that number of pairs of edge information. As you say, what are we missing?


Sadly, there are still tutors who seem to feel that assignments should
hinge on understanding arcane aspects, instead of testing the trainee's
understanding of Python and/or Graph Theory. My sympathy to the students...


As it happens, I've just dusted-off my Graph Theory as part of
evaluating AWS' Neptune (graph database). So, IMHO the assignment does
make sense. Although the trivial nature and paucity of sample-data is
not unduly helpful (perhaps less critical if the course is in Graph
Theory cf Python Coding!). (I think) I can see what is required. Hence
the earlier response asking the OP for his progress and ideas towards
solution...
-- 
Regards,
=dn