Homework 4

Degrees of Wikipedia

Your goal is to write a program that finds the shortest path between two Wikipedia articles. The shortest path is defined as the minimum number of Wikipedia links you need to click to get from one article to the other article. For instance, the shortest path between John Travolta and Michael Jackson is:

• John Travolta -> 1971 in music -> Michael Jackson.

Here are the steps to follow:

1. Download wiki-titles-small.txt and wiki-links-small.txt data.
2. Download the SPWiki class and rename it to SPWikiLastname.
3. Modify SPWikiLastname to find the shortest paths between 10 pairs of Wikipedia articles of your choice.

Data

• Each line in wiki-titles-small.txt represents a Wikipedia title.

  For_Your_Consideration
  Ford_Star_Jubilee
  Forest_Whitaker
  Forgery
  Formation_(American_football)
  ...
  

• Each line in wiki-links-small.txt consists of the links in the corresponding Wikipedia article. For instance, the first line represents the first Wikipedia article in wiki-titles-small.txt, "For_Your_Consideration", which consists of links to 4 Wikipedia articles, 3735 (Television), 3741 (Television_network), 3857 (The_Hollywood_Reporter), and 4319 (Variety_(magazine)).

  3735 3741 3857 4319
  708 982 2221 2285 2414 2918 3300 4008 4262
  ...
  

Source

• List<String> titles: contains the list of Wikipedia titles.
• int[][] links: contains the link IDs for each Wikipedia article.

Submission

• Write a report including your findings (e.g., shortest paths between 10 Wikipedia articles) as save it to hw4.pdf.
• Compress SPWikiLastname.java and hw4.pdf into hw4.zip and submit it to canvas: https://canvas.emory.edu/courses/32845/assignments/93014

Resources

• Six Degrees of Wikipedia.
• The Wiki Game.
• Wiki links.