De La Salle University - Manila
College of Computer Studies
Department of Software Technology
In Partial Fulfillment of the Course
Data Structures and algorithms
Term 3, A.Y. 2022 - 2023
Major Course Output 2: Graphs
Submitted by: Group 10
Arca, Althea Denisse G.
Del Mundo, Rahmon Khayle U.
Madrinan, Raico Luis C.
Submitted to:
Mr. Romualdo Jr. M. Bautista
I. Introduction
A. This program gets the friend list of a specific input based on the text file provided,
for example if the user inputs “0” which is for example stated in the text file that 0
on the right is the person for example then the one on the left are his/her friends.
Then there will be some options where the user will be asked if the user wants to
get the friend list, get connection, or exit the program. If the user picks the get
friend list then the program will show its friend list. Then if the user picks the get
connection it will show if the input has other same friends with other input then it
will show their connection with each other having the same friends. Then lastly if
the user selects the exit option then the program will just stop.
B. The contents of this report would cover the following:
● Description of the Data structure
● Description of the Algorithms
● Algorithmic Analysis of the Algorithms in Terms of Time
Complexity.
● Summary of Findings
II. Data Structure
The data structure used to represent the social graph in our code is an Undirected Graph
implemented on a HashMap in Java.
public Network(String filePath) throws IOException {
graph = new HashMap<>();
loadGraph(filePath);
}
This is a data structure that maps keys to values wherein the keys are the
account IDs and the values are the sets of friends for each of the accounts. The use of
HashMap has allowed us to represent the social graph data and access the relationships
between the accounts.
In the sense of being an Undirected Graph, it is also accompanied by the data
structure of adjacency lists which represents the set of friends of a selected person. The
undirected graph represents the connections of people whose mutual friends are also
connected to each other. The vertices of the graph represent the people respectively.
The program utilized the use of HashMap and ArrayLists to store and represent the data
given by the files which would be converted into an undirected graph by adding edges
which represents the friendship of two people. The edges are then stored in a HashSet
to create an Adjacency list or Friend list for the person.
graph.putIfAbsent(person, new LinkedHashSet<>());
graph.get(person).add(friend);
graph.putIfAbsent(friend, new LinkedHashSet<>());
graph.get(friend).add(person);
The “Get connection” feature would be referenced to the undirected graph by
performing traversals within the graph that searches if person A is in the same graph as
person B. With queueing and Breadth-First-Search algorithm, the network of people in
the graph is explored and finds the shortest path in terms of mutual connections
between the two people being compared. If the traversal is performed and person B is
found to be in the same graph, the program traces and returns the path it took to travel
to vertex of person B.
if (current == person2) {
int tracePerson = current;
while (tracePerson != person1) {
path.add(tracePerson);
tracePerson = parentMap.get(tracePerson);
}
path.add(person1);
Collections.reverse(path);
return path;
}
If the traversal is performed and person B is not found in the same graph, then there is
no connection between person A and person B.
return null; // No connection found
III. Algorithms
These algorithms were used in this project in order to display the friend list as
well as to display the connection between two persons.
A. getFriendList() - The graph map has already stored the person-friend pairs data
in a HashSet while loading and reading the file. In this method, it would only need
to take an account ID as an input and it will return the set of friends from the
graph map in a HashSet. Empty set if the account ID is not in the map.
B. getConnectionPath() - Creates a map that stores the parent of each account in
the path. This map is used to track the path from the first person to the second
person. This algorithm then starts at the first person and adds it to the queue. It
then iterates through the queue, one account at a time implementing the
breadth-first search algorithm. For each account, the algorithm checks if the
account is the second person and it returns the path from the first person to the
second person if it is. Otherwise, it adds all the friends of the account to the
queue. This continues until it finds the second person or the queue is empty. If it
is empty, then there is no connection between the 2 persons.
IV. Algorithmic Analysis of the Algorithms in Terms of Time Complexity
A. getFriendList() - the time complexity of this algorithm is O(1) as it simply gets
the set of friends for the account ID from the graph map and returns an empty set
if the accountID is not in the map.
B. getConnectionPath() - The time complexity of this algorithm is O(V+E). This
method uses BFS in order to find the shortest connection path between two
people. In the worst-case scenario, BFS visits all the V or vertices which
represent the Persons in the graph and explores all of the E or edges which
represent the friendships.
C. loadGraph() - The time complexity of this algorithm is O(E), because this method
reads the data from the file and iterates over each friendship connection (edge) in
the graph. Since there are E friendships in the network.
V. Summary of Findings
In conclusion, the program basically shows the friend list of the input that
the user typed and then it also shows the connections to other people. This
depends on what the user wants to do but those are just the options of this
program.
The program represents an adjacency list to store the pairings on the
social network graph. The undirected graph is then represented using a Map with
a LinkedHashSet whereas each account has a set of friends.
The program then implements 3 main algorithms:
1. Load Graph - reads the data from a file then constructs the undirected
graph by creating the edges between pairings or friends.
2. Get Friend Lists - retrieves the friend list of a specific person from the
graph
3. Get Connection Path - traverses to find the connection path between
two people in the graph
VI. Contributions
Name Contributions
Arca, Althea Denisse G. ● Coding
● Documentation
Del Mundo, Rahmon Khayle U. ● Coding
● Documentation
Madrinan, Raico Luis C. ● Coding
● Documentation
VII. References
Adjacency list (With code in C, C++, Java and Python). (n.d.). Programiz: Learn to Code
for Free. https://www.programiz.com/dsa/graph-adjacency-list
Data Structure and Algorithms - Hash table. (n.d.). Tutorialspoint.
https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.h
tm
Dotnet-Bot. (n.d.). Hashtable Class (System.Collections). Microsoft Learn.
https://learn.microsoft.com/en-us/dotnet/api/system.collections.hashtable?view=n
et-7.0
HashTable (Java Platform SE 8 ). (2023, June 14).
https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html
Hashtable in Java. (2023, February 15). GeeksforGeeks.
https://www.geeksforgeeks.org/hashtable-in-java/
Hashtable in java. (2022). W3schools.
https://www.w3schools.blog/hashtable-in-java
Java HashMap (With examples). (n.d.). Programiz: Learn to Code for Free.
https://www.programiz.com/java-programming/hashmap
Java HashSet. (n.d.). W3Schools Online Web Tutorials.
https://www.w3schools.com/java/java_hashset.asp
