-
Notifications
You must be signed in to change notification settings - Fork 35
Project 1 Wordnet Piazza Spring 2016
For the test cases, is it possible the graph contains a circle?
The graph structure you are asked to build is a DAG (Directed, Acyclic Graph) by definition, it is acyclic (meaning that it contains no cycles) so no, it is not possible for the graph to contain a circle unless you are structuring it incorrectly.
What do you mean by a circle? If you mean that there is a cycle, then there won't be as all the test cases use directed acyclic graphs. If you mean a graph that has hypernyms like the following, then this is definitely possible:
1,2 1,3 2,3
I am debugging my code and noticed that the given file has a line with just:
38003
Is this a valid hypernym input?
Yes, for example a root.
Also note that not all roots will be listed like that in the hypernym files. If a synset is a root, it is also possible that the id won't be listed on its own line in the hypernyms file. For example, given a very simple graph with two synsets, where synset (ID: 1) has edge to synset (ID: 2), the hypernyms file may look like the following:
1, 2 2 (this line may be omitted)
This test uses the graph from the project description, the one on the right in Part 2. It tests the pairs (1,5),(2,4),(3,0). The expected result is 1, but if you look at that graph, (1,5) has length 2, (2,4) has length 2 and (3,0) has length 3. What am I missing? or is the test incorrect?
Input 1 2 3 5 4 0 for length, does not mean length between pairs (1,5),(2,4),(3,0). It means the shortest length between the two sets, any id from first set to any id in second set. The length is 1, the length between 1 and 0.
Isn't the length between 3 and 4 also 1? So if ancestor was called on this graph would you return "0 4" because the common ancestors are 0 and 4 with lengths of 1?
- That is correct.