SoftEng 281: Object-Oriented Programming Assignment 4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
SoFTENc 281: Object-Oriented Programming
Assignment 4 – Twitter’s Follow Relation as a Graph
2022
1 Introduction to Graphs
Graphs are mathematical objects of the form < V, E > where V denotes a set of vertices (nodes) and E denotes a set of edges. Graphs are used in multitude of applications. One specific example is the follow relation in Twitter, where one user follows another. In addition, there are many other interesting examples in the real world. A very prominent one is GPS navigation, where the destinations in a city, for example, could be represented as the vertices and the edges between them represent the different paths. Google maps uses graphs for building transportation systems, where intersection of two (or more) roads are vertices and the road connecting two vertices is an edge. Google maps calculates the shortest path between two vertices to find the shortest route. Likewise, the friends suggestion algorithm of Facebook uses graph theory, where nodes are users and edges between two users represents a "friendship" relation. In the Web, web pages are considered to be the vertices. There is an edge from a page pl to another page p2 if there is a link of page p2 on page pl . This is the basic idea behind the famous Google Page Ranking Algorithm.
In this assignment we consider Graphs that are directed, fully connected, weighted and rooted, which are defined below. Directed : A graph that is made up of a set of vertices connected by directed edges.
Fully connected : A graph whose nodes have at least one in-comming or one out-going edge. For example, the edge a → b is an out-going edge for node a, and an in-comming edge for node b. Moreover, a fully connected graph is a graph in which it is possible to get from every vertex in the graph to every other vertex through a series of edges, called a path.
Weighted : A graph whose edges have been assigned weights, where a given weight is an integer greater than zero. As such, each edge has a source and a target vertex. For example, a → b, a is the source and b is the target. This edge is an out-going edge for node a.
Rooted: A graph in which one vertex has been distinguished as the root. For simplicity, we assume that the root is the source node of the first edge in the Graph. For example, in the Graph of Figure 1b the root is the node "0" because the first edge is 0 → 0.
(a) Graph visualization.
// 0 , 1 , 2 , 3 , 4 , 5
digraph testgraph {
0 -> 0;
0 -> 1;
1 -> 1;
1 -> 2;
1 -> 3;
2 -> 0;
2 -> 1;
2 -> 2;
2 -> 3;
2 -> 4;
2 -> 5;
3 -> 3;
3 -> 0;
3 -> 1;
3 -> 2;
4 -> 2;
4 -> 3;
4 -> 1;
4 -> 4;
5 -> 5;
5 -> 4;
5 -> 3;
5 -> 2;
}
(b) Textual representation.
Figure 1: An example of rooted, directed graph, which is fully connected
Consider the example graph shown in Figure 1. Note that the set of vertices V can be considered as the set using which a relation may be created. In this example V = {0, 1, 2, 3, 4, 5}. The relation captures the edges of the graph. In this example the adjacency relation between vertices may be captured as a relation
R = {(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4),
(2, 5), (3, 3), (3, 0), (3, 1), (3, 2), (4, 2), (4, 3), (4, 1), (4, 4), (5, 5), (5, 4), (5, 3), (5, 2)}.
Such a relation can be also represented using a specific text format in Figure 1b such as the dot format. Using a popular tool for graphs called Graphviz, a graph is visualised as in Figure 1.
Additionally, in the dot format using the label attribute, we can specify the weight of the edge. We assume that edge weights are positive integers. There is a web application for the Graphviz tool at www.webgraphviz.com. The input file can be visualised for manual validation of the graph. Try to visualize the sample input files in the test-cases folder. One example of a weighted graph is the a.txt file. This can be done simply by copying the entire text in the file to the Graphviz tool.
It is important that the first line in Figure 1b must capture all the nodes in the graph. This is clear because the relations are described only using the existing nodes. However, it is possible that the input file is invalid. For this assignment,
NOTE: (1) In this assignment we will only consider graphs to be NOT weighted. When a graph is weighted, we will ignore the weight attribute; and (2) you can assume that only the correct input files are tested during the marking process.
2 Overview of the assignment
In this assignment, you will be given a set of pre-designed classes, some of which are already implemented and you shouldn’t modify them and others are partially implemented and you are required to complete the methods to perform specific operations on a specific TweetGraph object. More details about the provided classes and your tasks are specified in Section 4. Through this, you will be able to develop new skills by learning about data-structures and algorithms covered in the lectures.
Internally, complex software systems, such as Twitter can be represented as a graph, where the vertices of the graph represent the users and the edges represents the follow relationship. In particular, you will be given a graph represen- tation of some mock Twitter users, who will be represented as nodes of a graph called TweetGraph, which associates a TwitterHandle object with a List of Tweet objects using the Map interface. This class extends another class called Graph, which uses suitable data-structures to represent graphs such as the one shown in Figure 1.
We establish a one-to-one relationship between the Node objects of the graph and a given TwitterHandle object through the unique ID of the user. An example of such a mapping is shown in Table 1.
Name |
Node in Graph |
|
0 |
Natalie Bruen |
0 |
1 |
Delpha Dickinson |
1 |
2 |
Lauretta Crona |
3 |
3 |
Chance Hermann |
3 |
4 |
Yadira Kirlin |
4 |
5 |
Jaylon O’Conner |
5 |
Table 1: Associating Twitter Users with the Vertices of the Graph shown in Figure 1
3 How to start by using Eclipse and Maven
We recommend using Eclipse for doing the assignment (see Section 6), and using the Maven wrapper before submitting to check that everything compiles fine and the test cases pass. Let’s begin!
maven wrapper ( mvnw for Unix/Mac OS and mvnw.cmd for Windows). This file will allow you to build and run this assignment. We will use a Maven wrapper to guarantee that we all have a common configuration to run and test the assignment. You can either build and run the code in your machine with the Maven wrapper via the command line or in Eclipse (https://softeng281.digitaledu.ac.nz/resources/maven-wrapper-eclipse). Ultimately, once you finish your project and before you submit, you will want to ensure that your project compiles without errors and passes the test cases using the Maven wrapper via the command line. This is how your project will be marked. There are four main Maven commands relevant to this assignment:
clean ( ./mvnw clean for Unix/Mac OS and .\mvnw.cmd clean for Windows) Removes the Java binary files (*.class) by clearing the target directory into which Maven normally builds your project. Running clean periodically is useful, for example to remove those .class files referring to deleted or renamed Java source files.
compile ( ./mvnw compile for Unix/Mac OS and .\mvnw.cmd compile for Windows) Compiles the Java classes (will only compile the Java source files that have changed from the previous build). Run this command before starting the assignment to make sure that is compiling correctly. You should see a Build Success:
[ INFO ] - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
[ INFO ] BUILD SUCCESS
[ INFO ] - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
[ INFO ] Total time : 1.007 s
[ INFO ] Finished at : 2022 -02 -13 T16 :06:39+08:00
[ INFO ] - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
test ( ./mvnw test for Unix/Mac OS and .\mvnw.cmd test for Windows) Compiles the Java classes and runs the test cases (will only compile the files that have changed from the previous build).
exec:java ( ./mvnw exec:java for Unix/Mac OS and .\mvnw.cmd exec:java for Windows) Compiles the Java classes and executes the Main class, which will launch the application.
javadoc:javadoc This is to generate the Javadoc API information for all methods and classes which have Javadoc comments. Note that we have provided these comments for the methods given. You need to write these Javadoc comments for all methods you create. The target folder for the Javadoc is on the path: target/site/apidocs.
Note that the first time you run the wrapper might take some time (a couple of minutes) to download the required libraries and dependencies.
You can append commands together. For example, ./mvnw clean test for Unix/Mac OS and .\mvnw.cmd clean test for Windows execute the clean command followed by the test command. For more information about Maven, visit the related page in our course website https://softeng281. digitaledu.ac.nz/topics/development-environment/.
This program uses the architectural design pattern, Model View Controller (MVC). The GraphContrtol is the main controller which has an execute() method that computes Graph operations by passing appropriate commands.
Before proceeding with the tasks, carefully review the code and try to run the application ( ./mvnw exec:java or in Eclipse run the class GraphControl). The console will ask you to insert a command
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The Tweeter Simulator . To know available commands , please type ’ help ’
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The key commands are:
1. check -r / -s / -t / -e, which checks different properties of a graph.
2. eqclass node-id, which computes the equivalence class corresponding to this node, provided the graph is an equivalence relation.
3. tgraph-search BFS/DFS, which searches a the TweetGraph starting from the root(s) in BFS / DFS order.
4. tweet-search node keyword, which searches for a given keyword in a tweet starting from a given node.
NOTE: For the commands which use a given Node / TwitterHandle ID, we assume it to be a valid one i.e. if the graph has nodes from 0 to 10, then for example, the command eq-class can only take a value in the interval [0, 10].
5 Tasks
You may explore the API for this assignment at: https://softeng281.digitaledu.ac.nz/javadocs/a4/index. html.
You are required to convert some of the provided classes in the data-structure package ds so the main data-structures are generic. We have only implemented generics in some classes i.e. the Node, Edge. You have to make the following classes fully generic, based on what has been covered in the lecture Introducing Complexity and Generics using a Linked List: https://softeng281.digitaledu.ac.nz/topics/linked-list/.
● LinkedList.java
● NodesStackAndQueue.java
5.1 Task 1 - A Generic NodeStackAndQueue.java
Implement the methods isEmpty( ), push( ), Node pop( ), Node peek( ), append( ).
The expected behaviour of these methods are provided through the Javadoc.
5.2 Task 2 - A Generic LinkedList.java
Implement the methods prepend(), append(), get( ), insert( ), remove( ), size( ), locateNode( ).
5.3 Task 3 - Graph.java: complete the methods BFS, DFS, isReflexive, isSymmetric, isTransitive, isEquivalent, computeEquivalence
● The isReflexive( ) method checks if the graph is reflexive. This is checked using the check -r command.
● The isSymmetric( ) method checks if the graph is symmetric. This is checked using the check -s command.
● The isTransitive( ) method checks if the graph is transitive. This is checked using the check -t command. The expected behaviour of these three methods over the file a.txt is shown below. When a given command fails, the reason for failure is also printed.
----------------------------------------------------------------------
The Tweeter Simulator. To know available commands, please type !help!
----------------------------------------------------------------------
>>open a.txt
The command is open a.txt
>>list
The command is list
The set elements are: {0,1,2,3,4,5}
The relational elements are:
{(0,0),(0,1),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(3,3),(3,0),(3,1), (3,2),(4,2),(4,3),(4,1),(4,4),(5,5),(5,4),(5,3),(5,2)}
>>check -r
The command is check -r
The graph is reflexive
>>check -s
The command is check -s
For the graph to be symmetric tuple: 1,0 MUST be present
The graph is NOT symmetric
>>check -t
The command is check -t
For the graph to be transitive tuple: 0,2 MUST be present
The graph is NOT transitive
● The isEquivalence( ) method checks if the graph satisfies the properties to be classified as an equivalence relation. This is checked using the check -e command.
● The computeEquivalence( ) method determines the equivalence classes for every node in a graph, which is an equivalence relation. This method is invoked by the eq-class
----------------------------------------------------------------------
The Tweeter Simulator. To know available commands, please type !help!
----------------------------------------------------------------------
>>open c.txt
The command is open c.txt
>>list
The command is list
The set elements are: {0,1,2,3}
The relational elements are: {(0,0),(2,1),(2,2),(2,3),(1,2),(3,1),(1,3),(3,3),(1,1),(3,2)} >>check -e
The command is check -e
The graph represents an equivalence relation
>>eq-class 0
The command is eq-class 0
The eq-class of: [0] = {0}
No of tweets in User: 0= 2500
>>eq-class 1
The command is eq-class 1
The eq-class of: [1] = {2,3,1}
No of tweets in User: 1= 2500
>>eq-class 2
The command is eq-class 2
The eq-class of: [2] = {1,2,3}
No of tweets in User: 2= 2500
>>eq-class 3
The command is eq-class 3
The eq-class of: [3] = {1,3,2}
No of tweets in User: 3= 2500
● The BFS( ) method performs breadth first search of the graph, starting from the root. If the graph has multiple roots, it searches for all such roots.
● The DFS( ) method performs depth first search of the graph, starting from the root. If the graph has multiple roots, it searches for all such roots.
These two methods can be invoked by the command tgraph-search BFS/DFS. The expected behaviour over the file a.txt is shown below.
----------------------------------------------------------------------
The Tweeter Simulator. To know available commands, please type !help!
----------------------------------------------------------------------
>>open a.txt
The command is open a.txt
>>tgraph-search BFS
The command is tgraph-search BFS
The next user visited in BFS order is: [0]
The next user visited in BFS order is: [1]
The next user visited in BFS order is: [2]
The next user visited in BFS order is: [3]
The next user visited in BFS order is: [4]
The next user visited in BFS order is: [5]
>>tgraph-search DFS
The command is tgraph-search DFS
The next user visited in DFS order is: [0]
The next user visited in DFS order is: [1]
The next user visited in DFS order is: [3]
The next user visited in DFS order is: [2]
The next user visited in DFS order is: [5]
The next user visited in DFS order is: [4]
5.4 Task 4 - TweetGraph.java: complete the metod, searchTweet( )
● The method searchTweet( ) searches starting from a TwitterHandle to determine which successor node has a tweet with the specifies tweetKeyword.
This method is invoked using tweet-search
----------------------------------------------------------------------
The Tweeter Simulator. To know available commands, please type !help!
----------------------------------------------------------------------
>>open c.txt
The command is open c.txt
>>list
The command is list
The set elements are: {0,1,2,3}
The relational elements are: {(0,0),(2,1),(2,2),(2,3),(1,2),(3,1),(1,3),(3,3),(1,1),(3,2)} >>tweet-search 0 mother
The command is tweet-search 0 mother
The tweet string found is: The sheep bore for one appendix under a great-grandmother hooked one fortnight. User Miss Natalie Bruen tweeted mother
No of tweets in User: 0 = 2500
The only data structure that you are allowed to use are what has been provided. For example, you are required to use the data-structures given in the ds package. Any additional java.util data-structures are already specified in the appropriate classes. You are required NOT to use any additional ones.
2022-06-08
Twitter’s Follow Relation as a Graph