Project 3data 3zipfriends6x6csvdavidfrankcindybeckyemilyaa
Project 3data 3zipfriends6x6csvdavidfrankcindybeckyemilyaa
Create an application that reads friendship data from a CSV file, constructs a friendship graph, and determines the relationship between two individuals based on the graph. Implement methods to generate the relationship path, check if all individuals are connected directly or indirectly, and create a minimal friendship network graph connecting all persons if possible.
The objective of this project is to develop a friendship network application that models relationships between individuals based on friendship data provided in CSV files. The core functionality involves reading the data to construct an undirected graph where nodes represent people and edges represent friendship relationships. The application will then provide features such as determining the connection path between two individuals, checking if everyone in the network is interconnected, and creating a minimal network that still maintains connectivity among all members.
At the heart of this project is implementing a class (FriendshipGraph) that models the friendship graph efficiently and intuitively. The graph is best represented using a map (or HashMap in Java) where each person's name is a key, and the associated value is a set of friends, which allows quick access and updates. This structure simplifies the process compared to textbook graph implementations that often involve complex node and edge classes, especially for undirected graphs with uniform weights. The simplified approach reduces the complexity and improves readability and performance for this specific use case.
The main tasks involve creating methods to read CSV files and build the graph, find relationships between two people (such as friend-of-a-friend-of-a-friend), check if everyone in the network is connected through some chain of friendships, and produce the minimal friendship network connecting all individuals. The project must extend the provided interface (IFriendshipGraph) and fulfill the requirements at different complexity levels, with the highest level implementing all features fully.
For relationship determination, Breadth-First Search (BFS) or Depth-First Search (DFS) can be used to find the shortest path between two nodes. The allFriends() method assesses whether there is a single connected component encompassing all persons, and minimalGraph() finds the minimal spanning structure if the network is fully connected. If not, it returns an empty graph, indicating the network is not fully
connected. These features enable analysis of the friendship network's connectivity and structure, providing insights into social interconnectedness within the dataset.
References
Clark, J., & Wainwright, M. (2014).
Data Structures and Algorithms in Java . Pearson.
Skiena, S. S. (2008).
The Algorithm Design Manual . Springer.
McGraw-Hill Education. (2012).
Introduction to Algorithms (3rd Edition). McGraw-Hill.
Knuth, D. E. (1998).
The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley.
Harold, P. (2019).
Graph Theory and Its Applications . Dover Publications.
Dongarra, J., et al. (2018).
Sparse Matrix Computations . SIAM.
Gibbons, A. (1985).
Algorithmic Graph Theory
. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009).
Introduction to Algorithms (3rd ed.). MIT Press.
Sedgewick, R., & Wayne, K. (2011).
Algorithms (4th Edition). Addison-Wesley. West, D. B. (2001).
Introduction to Graph Theory . Prentice Hall.