Task
back to topIntroduction
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.
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 fileindex.txtstores the names of the people in the network – you may assume that we only store the given names and these names are unique; andfriend.txtstores who knows whom. The program must read these two files. The following section describes the format of these two files.
Thefriend.txttakes 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 offriend.txt:
5
0 3
1 3
0 1
2 4
1 5
Theindex.txtwhich 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 usesfriend.txtto build the vertices and edges of the social network, and useindex.txtto 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 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 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: Wallace, 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 3 - 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 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 or when 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 and friends of the friends (task 2).
3.Prompt users for a name and list all 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 which checks for the validity of the names.
3. If your program fails to read input files (task 1), other tasks will not be assessed and will be awarded 0 marks
Design, Presentation and Conventions
You need to think about the design of your program to allow code reuse. The Social Network Class should make use of the Graph class from Interact2 site under Resources. This graph class is directed, so you need to extend it by making use of inheritance so it becomes an undirected graph. You should also consider the number of lines in each method; Avoid writing long methods; Consider refactoring when the method exceeds 25 lines of code.
Presentation is mainly formatting for aesthetic, while conventions cover issues like naming of classes, methods and variables as well as coding standards. We will use Google’s Java Style Guide as described inhttps://google.github.io/styleguide/javaguide.html.
Rationale
back to topThis assessment task will assess the following learning outcome/s:
- be able to apply a variety of abstract data structures to the solution of welldefined problems.
- be able to implement selected data structures in the Java language.
- be able to design wellstructured solutions to programming problems and implement these solutions in the Java language.
This assignment requires you to use the Java programming language to:
•Read input from text files.
•Use a non-directed graph to build a social network.
•Traverse a graph using depth first search.
•Print error messages to System.err
•Write a simple text based user interface.
•Document Java programs using Javadoc.
Marking criteria and standards
back to top
Criteria |
HD (85-100%) |
DI (75-84%) |
CR (65-74%) |
PS (50-64%) |
FL (0-49%) |
---|
Funtionality [85 marks] |
Demonstrates highly developed capability to implement program specification by correctly implementing all tasks specified; with a program is robust and correctly handles exceptions and errors. Error messages are easy to understand and printed to System.err.
Applies required data structure and produce correct results; explicit evidence of appropriate choice of data structure.
Program reads friend.txt and index.txt by default.
|
Demonstrates a well-developed capability to implement program specification by implementing all tasks; with a program that correctly handles most exceptions and errors. Error messages are generally easy to understand.
Applies required data structure to complete all tasks but produce partially correct results.
|
Demonstrates moderate ability to implement program specification by implementing more than half of the tasks specified. The program has some exception and error handling. The error messages provided are clear but require further explanation.
Applies required data structure to build most tasks but produce partially correct results.
|
Demonstrates minimal ability to implement program specification. Identifies required data structure but can only build a few of the required tasks.
Very little or no exception and error handling.
|
Demonstrates very little or almost no understanding of implementing the program specification. Identifies required data structure but does not know how to apply it correctly.
No error messages or cryptic error messages.
|
Design [15 marks] |
Shows in-depth understanding of software maintainability by implementing best practices of object-oriented design including information hiding and reusable classes (see Section 3 above).
Use inheritance or other appropriate object-oriented concepts to extend Graph.java to be an undirected graph.
The names of the default files (friend.txt and index.txt) must be stored as constants.
|
Shows good understanding of software maintainability by implementing most good practices of object-oriented design including information hiding and reusable classes. |
Shows moderate understanding of software maintainability by implementing some good practices of object-oriented design including information hiding and reusable classes. |
Shows minimal understanding of software maintainability. Some classes and methods are poorly designed. |
Shows little or no understanding of software maintainability. Many classes and methods are poorly designed. |
Presentation and Conventions [5 marks] |
The code is extremely well organised, aesthetically pleasing and easy to follow. Uses JavaDoc to document each class and method. Comments each variable and blocks of code, and comments for the code are meaningful (focus on why rather than what). May skip a few variables that are obvious (such as those used in loops).
Names of all the classes, modules and variables are meaningful.
Subscribes to all good coding conventions as described in Section 3 above.
|
The code is fairly easy to read and mostly aesthetically pleasing. One to two names of the classes, modules and variables may be inappropriate. Uses Javadoc to comment most classes and methods. Comments most variables and blocks of code.
Subscribes to most good coding conventions as described in the style guide above.
|
The code is somewhat readable. Three to four names of the classes, modules and variables maybe inappropriate. Uses Javadoc style to comment many of the classes and methods. Comments many variables and blocks of code.
Subscribes to some coding conventions as described in the style guide above.
|
The code is partially organized and somewhat difficult to read. More than four names of the classes, modules and variables maybe appropriate. Uses Javadoc style to comment some of the classes and methods. Comments some variables and blocks of code.
Subscribes to a few coding conventions as described in the style guide above.
|
Code is disorganized (such as poorly indented). Poor choice of names for many of the classes, modules and variables. Little or no internal documentation (comments) and Javadoc.
Subscribes to little or no coding conventions as described in the style guide above.
|
**Assignment will be marked out of 100 but will be scaled to assignment weight 20%
Presentation
back to top• please submit all *.java files in the correct directory structure (as dictated by the package structures).
•Documentation (Word file preferable) describing how to compile and run your program and any assumptions you have made (not more than 200 words).