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 les 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.

TwitterHandle

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 rst 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/.

4 Commands

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 reexive. 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 command, where is a given node in the graph. The expected behaviour of these two commands for the file c.txt is shown below.

----------------------------------------------------------------------

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 rst 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 expected behaviour of an example command over c.txt is shown below.

----------------------------------------------------------------------

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.