This project is a simulation of a social network in which users search for friends in the network. The users are identified by a unique ID. At initialization, each user is given a target ID which he/she will use to find the first friend. The user then will use this friend to connect to other people and it goes on like that.
Explanation of solution
I used QuickSort in this method. In class Dale gave us an implementation of QuickSort. I just made a few changes to this implementation. Among that the most important one is the compareTo() method to compare two objects.
I used Binary search in this project because the list is kept sorted by QuickSort so Binary search will be very efficient with time complexity of O(log n)
Move Closer method
One interesting part of the narrative of this project is moving a user closer to its target. I had fun using math (specifically geometry) to find a way to do this. The formula that I used in my code:
results from some geometry between two similar triangles:
which leads to the following:
The image above is the case when there are 20 users and 60x60 landscape. The users gradually move to one cluser.
The same case happen when there are 2000 users:
However, I don't know how to explicitly explain why the users move to one cluster.
For all the tries I did, the number of clusters stayed as one.
If a user is randomly placed after visiting someone, there is still a part in the landscape where there are more users but the users are scattered quite randomly in other parts:
I use saturation to change the color of the users. Initially the users are grey. When it has enough friends it turns green, then yellow. I make a public static MAX_FRIENDS in NetworkSimulation so any user can get access to this. Because the number of friends of a user increases slowly so I change the way saturate is calculated a bit:
I used QuickSort in this project for efficiency.
In the draw method for each user, I loop through the friend list and draw a line to represent the connect between the user and his/her friends. Only 10% of the users have their connections drawn.
I implement the removing a user from the simulation by adding a new part to the narrative. Each user carries a field called "lonelyState". Whenever an user fails to find a new friend in his friend's friendlist, lonelyState will increase by one. If lonelyState goes beyond 10, the user dies. Removing the user from the implementation consists of:
- Removing the user from his/her friends' friend lists
- Removing the user from the scape's agent list
- Updating the SORTED_USERS list
Before the SORTED_USERS list contains all the IDs from 0 to SORTED_USERS.size() so to find an user with id i I can just call SORTED_USERS.get(i) but now I have to use the search method to find it. So in the User class, method UpdateState I have to change: this.targetUser = SORTED_USERS.get(this.targetId) to this.targetUser = search(SORTED_USERS, this.targetId). .... I just realized that I didn't make this change in this file I submitted!
I collect the data of average number of friends and time and the graph is above. From the graph we can see that the average number of friends increase exponentially. This can be explained by the nature of how a user finds new friends: a user find new friends by looking into the friend list of another user.
What I learned
I learned more about static field and static method in this project. Also I learned more about BinarySearch and QuickSort.