Introduction

A graph data structure is useful for representing networks, such as social networks, and a non-directed graph is particularly useful for this purpose. Social networks are non-directed because it is assumed that if A knows B, then B knows A too. In this assignment, you are required to design and implement a simple social network program in Java. You should use an adjacency matrix data structure in your implementation.

What to Implement (Tasks)

Task 1 (15 marks)

Write a social network program in Java. The default information for this network is stored in two files: index.txt and friend.txt. The file index.txt stores the names of the people in the network - you may assume that we only store the given names and these names are unique; and friend.txt stores who knows whom. The program must read these two files. The following section describes the format of these two files.

The friend.txt takes the following format. The first line is the number of pairs of friends. Each subsequent line has two integer numbers. The first two numbers are the indices of the names. The following is an example of friend.txt: 5 0 3 1 3 0 1 2 4 1 5

The index.txt stores the names of the people in the network. The first line is the number of people in the file; for example: 6 0 Gromit 1 Gwendolyn 2 Le-Spiderman 3 Wallace 4 Batman 5 Superman The second line "Gromit" is the label for vertex 0, the third line "Gwendolyn" is for vertex 1. For this system, we will only record the given names (without spaces). By looking at the content of these two files, we know that Gromit is a friend of Wallace and Wallace is a friend of Gromit. We also know that Gwendolyn knows Wallace and Wallace knows Gwendolyn, and so on. Unknown to Wallace and Gromit, Gwendolyn is a friend of Superman!

To build the social network, the program reads both files. It uses friend.txt to build the vertices and edges of the social network, and useindex.txt to label the vertices. If it fails to read the files (such as file not found), then it must also print appropriate error messages using System.err.

The program must also check that the number of relations or indices read is the same as the number of relations or indices specified at the start of each file. The two files above are kept short to simplify the explanation and can be used when you first start developing the program. Eventually, the program will be tested with larger datasets of about 20 friends and 30 pairs of friends.

Task 2 - friends list (5 marks)

Prompt users for a name, say Wallace, and list all the people that Wallace knows. In the example above, Wallace has two friends and they are Gromit and Gwendolyn. The program should print appropriate messages when the given name does not exist or when the network is empty.

Task 3 - friends and friends' of friends list (10 marks)

Prompt users for a name, say Wallace and list all the friends that Wallace knows and all the friends that Wallace's friends know. In this case, this list should be Gromit, Gwendolyn and Superman. This is a good way of checking that the program has built the network correctly.

Please be mindful that users of this social network have low computer literacy, so the error messages have to be very easy to understand. If the given name does not exist in the network, the program should display an error message. If the network is completely empty, then the program should inform users that the network is empty as soon as they choose this option. Task 4 (15 marks)

Prompt users for two names, say Wallace and Gromit, and list all the people that they both know. In this case, there is only one, and it is Gwendolyn. The program should print appropriate messages when the given name does not exist or when the network is empty. Task 5 (15 marks)

Prompt users for a name to delete from the social network. When a member of the social network (vertex) is deleted from the network, all its edges must be deleted too. The program should print appropriate messages when the given name does not exist orwhen the network is empty.

Note that friends of this social network are extremely hostile to those who have withdrawn themselves, so please seek confirmation before deleting anyone. Task 6 (15 marks)

List all members sorted by popularity with the most popular members (having the highest number of friends) listed first, then within popularity sorted by name. The program must display the name and the number of friends (including a report title and column names). Task 7 (10 marks)

Write a driver program to test all the functionality that you have implemented. The driver program should have a simple menu to allow users to: 1. Prompt users for a friend filename and an index file name. Note that the information read from these two files represents a new network. All information from the default or previous network will be replaced by this new network. 2. Prompt users for a name and list all the friends (task 2). 3. Prompt users for a name and list all the friends and friends of the friends (task 3). 4. Prompt users for two names, and list all the friends known to these two people (task 4). 5. Delete a member from the network (task 5). 6. List all members sorted by popularity, then by names (task 6). 7. Exit.

Important Notes

1. Social networks are undirected graphs, so the program must add an edge from A to B and from B to A.

2. For tasks 2 to 5, if users enter a name that does not exist, then the program should inform users. Since this validation is required for several tasks, you might like to write a method that checks for the validity of the names (you can assume that names are not case sensitive).

3. If your program fails to read input files (task 1), other tasks will not be assessed and will be awarded 0 marks

4. The index.txt and friend.txt files should be placed in a default directory of the project so that one doesn't need to change the path of those input files to run your program. In other words, DO NOT use any file path structure to read files, e.g., "c:/my project/index.txt", rater should use File myFile = new File("index.txt");