Assignment 4 – The Follow Relation of Twitter

Learning Outcomes:

You will be able to:
- You will be able to represent Graphs using object-oriented concepts.
- You will be able to implement common data structures like LinkedLists, Stacks and Queues and develop them using Java Generics.
- You will be able to implement search operations on Graphs using algorithms such as Breadth-First Search (BFS) and Depth-First Search (DFS) and understand the difference between BFS and DFS.
- You will be able to understand and verify key mathematical properties of Graphs such as reflexive, symmetric, transitive.
- You will be able to compute the equivalence class of Twitter users from the provided graph, when it represents an equivalence relation.
- You will be able to improve your understanding of unit testing with JUnit. You will be able to practice inheritance, encapsulation, and polymorphism.
- You will be able to read and understand some pre-developed code and extend it, which is a key learning outcome for software developers.

Javadoc for Assignment 4

Please click the following link to explore the application programming interface (API) of this assignment: A4 API

The Assignment Handout

The handout can be obtained as a PDF document by using the following link: The A4 Handout

FAQ

Question: In the method isReflexive(set, relation) what is set, relation?

Answer: set denotes the set of vertices in the graph, where each vertex is represented as a String. Likewise, relation is the set of edges in the graph, where each edge is represented as a string of the form "a,b", where a denotes the source vertex and b denotes the destination vertex. Both the set and the relation are passed as a List<String> by invoking the method tweetGraph.isReflexive(graphUI.getSetElements(), graphUI.getRelationElements()in the controller. This also applies to the parameters of the isEquivalence method.

Likewise, the above applies to the parameter relation used in the methods isSymmetric and isTransitive.
Question: Does the order of the elements in List<String> returned by the isEquivalence method important?

Answer: This is answered in the Piazza handle @585. Specifically, as this represents a Set, the order is unimportant. Test cases will be updated based on this.
Question: Can we import custom classes?

Answer: Yes, as long as you have designed and implemented these classes. These classes also shouldn’t import java.util.*.
Question: Do we have to use adjacencyMap for implementing the methods isReflexive, isSymmetric, isTransitive?

Answer: We have answered this in question 1 above. The answer is NO.
Question: Do we need to check for the correctness of the input files in the dot format i.e. that the graph doesn’t have duplicate vertices / edges etc. Refer to the response to the Piazza post @587.

Answer: For this assignment we will assume that you are always given the correct input file and you don’t need to write extra tests / exceptions for this.
Question: How is the graph represented in the assignment?

Answer: The graph is represented using the adjacencyMap in the class Graph. This map associates every Node<String> in the graph, which is associated with the list of outgoing edges from a specified node. This list of outgoing edges is represented as a LinkedList<Edge<Node<String>>>. NOTE that each Edge object has a source and a destination node. The Edge<Node<String>> is only representing the type of an Edge.
Question: In the method searchTweet() for Task 4 should we use BFS or DFS? Refer to post @580.

Answer: Using BFS and DFS will result in different answers. So, we will require you to only use DFS, for implementing this method.
Question: For the command search-tweet user-id for Task 4, what should we return? Refer to the post @580.

Answer: searchTweet searches for the given keyword starting from a specified user i.e. TwitterHandle object. Note that the answer may be different using BFS or DFS. In our test-cases we use DFS only.

Essentially, you are already given a map that associates a List of Tweets with any given TwitterHandle. You start your search from the specified user and stop when either the user or a successor has a tweet containing the keyword. For determinism, the first occurrence of the user that matches the search criteria is returned.

T4_03_C is incorrect. We will update this.
Question: For the command search-tweet user-id for Task 4, what happens when the user-id given is not connected by any path to a successor user, which contains a Tweet with the given keyword?

Answer: In that case, as the the successor user is unreachable, the result should be No successor of " + user.getName() + "tweeted " + tweetKeyword.
Question: For the command search-tweet user-id for Task 4, what happens when the keyword is a substring of a given word in the Tweet?

Answer: In that case, the Tweet is returned successfully.
Question: Can I use available data-structures from the Collections Framework?

Answer: NO. You are required to implement the data-structures in the package ds.
Question: How do I update the latest files from Canvas to update the new terminal commands, the revised JSON file and the signature change to the depthFirstSearch method?

Answer: Please follow the steps below for these changed files. The overall time taken to incorporate these changes should be less than 15 minutes in total. This is a conservative estimate. Please note that incorporating these changes, including any revisions to your code if you have made significant progress, only affects 1% of the final marks.
1. First open the file to be replaced i.e. say GraphControl.java both the old and the new version. Every one has to replace the following files: GraphControl.java, GraphUI.java, Tweets.json.
2. Go to step 3 if you have cloned but not started. This step is for the students who have cloned and started on the assignment will, in addition, also need to do the following:
  - Copy the method getTweetsText() for TweetGraph.java.
  - Update the method signature for the method depthFirstSearch() in Graph.java.
  - Go to step 4.
3. Open the files TweetGraph.java, Graph.java additionally to step 1.
4. Copy the new version and replace the old version with the new for the files opened in steps 1, 3 ONLY.
5. Delete and replace TestsForMarking.java with StudentsTestForMarking.java.
6. Note that the bestFirstSearch method’s signature has also changed. However, it is optional for you to update this revised method. This is since we only use DFS for the tweetSearch. The outcome of the test cases will be invariant to your decision.
7. If you have any further queries with these steps best to see Aron on the Friday lab session this week or email him if you can’t.