Graph, hashing and map are important data structures and are used in a number of real-life applications. For example, following is a list of applications using graph in real world:
· In a computer network, a vertex can be a computer or a switch and an edge can be the communication link between devices.
· In an airline network, a city can be a vertex and a flight can be an edge. In a transportation network, a location can be a vertex and a road can be an edge.
· In a social network, a person can be a vertex and a friendship between two persons can be an edge.
· The relationship among various websites can also be described by a graph where a website can be a vertex and its link to the other website can be an edge.
· In project management, graph can also be used to describe the relationship between two tasks where a task is a vertex and the dependency of one task on the other is an edge.
In this final project, you and your group have an opportunity to use your creativity to write an application involving graph and one or more other data structures such as hashing or map. The nature of your project will be determined by you and your group. Following is an article which discusses and demonstrates some very basic ideas on “Design data structures for a very large social network like Facebook or Linkedln”.
For social network, we can also apply web scraping tools in our application to collect real-world data and import the scaped data to your application to build a graph, for example, a social network graph, for further analysis. Tools such as Jsoup, HtmlUnit and Selenium are helpful and they support using Java to do web scraping. You may use the following referenced web learning material to get started:
For this project, you and your group can investigate a list of project ideas shown below to see if one of them fits you and your group’s interests. It is also strongly supported and encouraged if you and your group prefer to implement the project with your own ideas instead of the listed ones.
· Using graph to analyze various websites such as Wikipedia to find distances between articles and article with the most incoming edges.
· Using graph for Map and GPS related applications in travel.
· Using graph topological ordering for project scheduling.
· Using graph to find a center of a network
· Using graph to calculate Minimum Cash Flow among a group of people
The project will be graded based on its creativity, complexity and correctness. The more complicated of the project, the more points the project will receive.
Please note, the project that you and your group choose to implement should be your own one and unique one instead of a copy from the Internet or other resources. If the submitted project is found to be a copy from Internet or other resources, our course policy regarding plagiarism will be applied.
For the submission of the project, please prepare a PowerPoint presentation of ten minutes long to present your group’s key take-aways from the project as well as a demo of your project. Please record your group presentation and submit it to the project presentation room. Please also submit the following required documents to the project’s submission dropbox on our course website by the due date:
· A report which describes your project’s ideas, design mechanisms, how graph and other data structures are used, web scraping tools used if applicable, how to run the program and sample running result.
· All Java source code, if a third-party package is used, please include the description how to download it and install it.
· An executable program to run your project.
· The PowerPoint for your project.