Homework 5: Wiki Walkin'

Homework 5: Wiki Walking

Assigned: Tuesday, November 17, 2026

Due: Thursday, December 10, 2026 @ 11:59 PM

Have you heard the trope that clicking the first link in any Wikipedia article will eventually lead you back to the article on “Philosophy?”

These, and other important questions, motivate your final homework in 2120:

• What Wikipedia articles link to what other ones?
• What is the most likely path a user takes between different Wikipedia Articles?
• Is it possible to start on one article and reach another?

Goal: implement a simplified version of some Web Crawler tools that analyze links between a given domain's pages (a la Wikipedia).

Example and Vocabulary

In this assignment, we'll design a simple Site Map consisting of Wikipedia Article Names mapped to the other Articles they link to, as well as the number of times that each link is clicked.

Graphically, this might look like the following:

In the above:

• Our Site Map is essentially a directed graph in which articles are vertices and edges connect A to B if there is a link to article B found on article A.
• Naturally, some articles may reference one another, so cycles are allowed (like between the Java and Object-Oriented articles above).
• When a user clicks on a link from a given Article, we may be interested in logging that, so each edge may have some number of “clickthroughs” recorded for it.
• We’ll define a Trajectory as any path that originates at any vertex in the graph and can be legally reached by clicking some sequence of links on each article’s page. This represents a single user’s path through the site before leaving.
• Thus, the numbers along each edge of the graphical site map are the sum of all trajectories that tread that link.

Choosing Data Structures

To model the above, you’ll use some of the tools we looked at in class, as implemented through the Java Collections Framework! The two main ADTs you’ll need are:

• Maps: Dictionaries that associate unique keys with their mapped values. Two implementations will be of use for us:
  • HashMap: a Hash Table implementation of a map. Useful for quickly checking if keys are stored and for accessing their associated values, though at a cost of memory compared to TreeMaps.
  • TreeMap: a Binary Search Tree implementation of a map. Useful for when obtaining keys in some sorted order is desirable, though at a cost of performance compared to HashMaps.
• Sets: Collections of unique values used for quick lookup of set membership. Two implementations will be of use:
  • HashSet: a Hash Table implementation of a Set, useful for quick lookup of values, though at a cost of memory compared to TreeSets.
  • TreeSet: a Binary Search Tree implementation of a Set, useful for when examining values in some order is required, though at a cost of performance compared to HashSets.

To begin this assignment, you should read the JavaDocs associated with each of the implementations above, learn their interface, and consider how these tools map to the requirements above and below.

HashMap JavaDocs TreeMap JavaDocs HashSet JavaDocs TreeSet JavaDocs

Your goal is not only to ensure your code's functionality, but also that you make intelligent design decisions in regards to what Data Structure (or combination of Data Structures) you use to model your SiteMap!

Solution Skeleton

Start with the solution skeleton in-hand! The following will also serve as your submission mechanism (see submission instructions below).

Homework 5: GitHub Classroom

Included in the skeleton are:

• WikiWalker.java containing the skeleton of all methods you’ll need for the homework. Read on for more specifications of what to do herein.
• WikiWalkerTests.java to validate your solution for the file named above. This time, these are all of the tests you’ll need to achieve full credit for this assignment! Feel free to modify these files to add your own tests.

• junit.jar, a file required to run your tests. Do not touch this!
• .gitignorea set of patterns for git to avoid committing. You may modify this file if your commit attempts to add any project files to the repo (i.e. IntelliJ .idea project files or Java .class files, which should not be submitted)

Specifications

Implement the WikiWalker class that uses whatever ADTs you choose to best provide the behavior described above / below.

Methods

public void addArticle (String articleName, List<String> articleLinks)

Adds an article with the given articleName to the site map and associates the given List of linked article names that are found on that article’s page.

Duplicate links in that list will do nothing and can be ignored, as should an article’s links to itself.

For example, a WikiWalker named ww can add an article named “A” with links to articles named “B” and “C” via:

ww.addArticle("A", Arrays.asList("B", "C"));

public boolean hasPath (String src, String dest)

Determines whether or not, based on the articles and links added in the WikiWalker’s site map, there exists at least one sequence of directed links that could be followed to take the user from the source article to the given destination.

Tautologically returns true if source and destination are the same article.

If either src or dest articles do not exist in the WikiWalker, return false.

In the example above:

ww.hasPath("Programming", "Programming")
    => true
ww.hasPath("Programming", "Java")
    => true
ww.hasPath("Programming", "Collections")
    => true
ww.hasPath("Collections", "Programming")
    => false
ww.hasPath("Philosophy", "Programming")
    => false
ww.hasPath("Programming", "Philosophy")
    => false

public void logTrajectory (List<String> traj)

Increments the click counts of each link along some trajectory as collected from a user’s experience on the site.

For instance, a trajectory of ["A", "B", "C"] indicates that a user started at page “A” before visiting page “B” and then from there “C”. This trajectory will increment the click count of the “B” link on the “A” page, and the count of the “C” link on the “B” page.

For simplicity’s sake, we’ll assume that a provided trajectory is always well-formed, meaning that each step along the trajectory has a preexisting path in the constructed WikiWalker’s site map.

Cycles are perfectly fine to capture in a trajectory.

Each trajectory is expected to be at least 2 items in length; any trajectory that is 1 item or fewer will throw new IllegalArgumentException().

Note: this method is just to simulate how a particular user's trip through a particular website would be logged by some system; its sole purpose in this assignment is to update the number of times that a particular set of links have been "clicked."

public int clickthroughs (String src, String dest)

Returns the number of clickthroughs recorded from the source article to the destination article via the logTrajectory method.

If the destination article is not a link directly reachable from the source, returns -1.

All articles, before any trajectories have been logged, start with 0 clickthroughs.

If the src article is not located in the site map, throw new IllegalArgumentException()

If the src article is in the site map, but the dest article is not within, treat this as a special case of a destination article not being reachable from the source, and thus return -1.

Using the example above:

ww.clickthroughs("Java", "Object-Oriented");
    => 10
ww.clickthroughs("Object-Oriented", "Java");
    => 9
ww.clickthroughs("Data-Structures", "Object-Oriented");
    => -1
ww.clickthroughs("Java", "Philosophy");
    => -1
ww.clickthroughs("Java", "Collections");
    => -1
ww.clickthroughs("Philosophy", "Java");
    => IllegalArgumentException

Note: this method is simply a "getter" for the number of times a link has been clicked, as would have been logged through the logTrajectory method.

public List<String> mostLikelyTrajectory (String src, int k)

Based on the pattern of clickthrough trajectories recorded by this WikiWalker, returns the most likely trajectory consisting of a maximum of k clickthroughs starting at (but not including in the output List) the given src article.

Duplicate site visits and cycles are valid output along a most-likely-trajectory.

In the event that two of the largest article links are equally likely (i.e., have the same number of clickthroughs), ties are broken by ascending alphabetic order of the article names. E.g., if article “A” has 2 links with an equal number of clickthroughs, “B” and “C”, then “B” will be chosen next in the returned trajectory because it alphabetically precedes “C”.

In the event that the most likely trajectory ends at a terminal Article (i.e., an article with no links) that is fewer links than the requested k, this is fine — the trajectory ends there and the remaining number of requested links are ignored.

In the event that the requested trajectory begins at a terminal node, returns an empty List.

In the example above, the following would be expected:

If the src article is not located in the site map, throw new IllegalArgumentException()

ww.mostLikelyTrajectory("Programming", 1)
    => ["Object-Oriented"]
ww.mostLikelyTrajectory("Programming", 2)
    => ["Object-Oriented", "Java"]
ww.mostLikelyTrajectory("Programming", 3)
    => ["Object-Oriented", "Java", "Object-Oriented"]
ww.mostLikelyTrajectory("Collections", 3)
    => []
ww.mostLikelyTrajectory("Philosophy", 3)
    => IllegalArgumentException

Assumptions

To simplify this assignment, we’ll assume the following:

• Don’t worry about an Article adding new links to its page after the addArticle method has already been called with its set of links.
• Articles are case-sensitive — i.e., “philosophy” and “Philosophy” would be considered 2 separate articles. Don’t worry testing for this, I won’t be tricky in the grading, simple equivalence tests will get you full credit here.

Unit Tests

You may use the unit tests included in the following skeleton to check your understanding and correctness of your solution. This is the entire suite of tests I will use to score your solution, so take advantage of them and make sure you pass them all before you submit!

Some edge cases we test, for your own reference:

• Site Maps with cycles.
• Site Maps with a diversity of logged trajectories that might change the output of mostLikelyTrajectory..
• Site Maps with multiple “roots” (i.e., multiple vertexes with no parents) and disconnected articles.

Solution Restrictions

Read the following list of submission restrictions carefully! Violating any restriction will net you a 0 on this homework!

• You MAY use ANY data structure from the Java collections framework in your solution — the shackles are off, feel free to use the tools that will be available to you in the real world!
• However, POOR choice of a data structure may cost you some points in efficiency if you prefer, e.g., an ArrayList to do membership lookup when a Set would be more appropriate and faster.
• You may NOT add any methods or fields to the WikiWalker’s class’ public interface. You may, however, add any private fields or methods that you like.
• Your classes and therefore source files must be named exactly as intimated above (as is in the Solution Skeleton), and your submission should mimic the solution skeleton’s package structure.

Hints

The implementation of this assignment requires you to make some design decisions. However, here are some hints for how you might structure your own.

• Remember: Data Structures can be the values stored in other Data Structures!
• Don’t be afraid to use local data structures to help you accomplish a given task! Declaring a new structure to preserve some part of an operation’s state, although not desirable when in-place algorithms are possible, is often necessary — choose wisely!
• Just because we’re not dealing with trees doesn’t mean recursion is off the table! Consider which methods might lend themselves to a recursive solution.
• Although there are only a few methods for you to implement in this assignment, beware: some of the algorithms may feel non-trivial, especially if you need time to become accustomed to Java’s Sets and Maps. Leave yourself ample time to test, debug, and ask questions!

Submission

You will be submitting your assignments through GitHub Classroom!

What

Complete the source files that accomplishes the specification above in the project structure given in the skeleton.

How

To clone this assignment (if you need a refresher), consult the guide here: GitHub Classroom Tutorial

To submit this assignment:

• Simply push your final, submission copy to the GitHub Classroom repository associated with your GitHub classroom account.
• Make sure that your name is commented as the author at the top of each submitted file AND in the accompanying README.md file.