Graphs (BFS/DFS/Dijkstras)

For this project you must implement the methods of the Spider,ShortestPath classes.

See:
Description

Packages

cs132.dijkstra	Classes for perfoming Dijkstra's shortest path algorithm to find the shortest path in a weighted graph from a starting vertex to all other vertices.
cs132.testCases
cs132.webPage	Classes for extracting href's embedded in web pages.
cs132.webSpider	Classes for representing WebPages and performing a web crawl.

For this project you must implement the methods of the Spider,ShortestPath classes.

Design

The WebPage class is used to represent a WebPage. For each WebPage, we record the URL of the web page, whether we have visited/crawled the web page, and a Set of crawlable WebPages linked to from this WebPage.

Example

The directory web/in your project contains a set of html files you can try your web crawler on (give it the URL file:web/a.html).

We are going to perform a crawl of 3 web pages, starting at file:web/a.html. After creating the Spider and adding a.html to the crawl list, we have:

We now remove a.html from the crawl list, and crawl it, adding b.html and then d.html to the crawl list.

What happens next depends on whether we are performing a DFS or BFS search crawl.

DFS Crawl

With a DFS crawl, we use a stack or a LIFO queuing order for which web pages to crawl next. So we remove d.html from the stack and crawl it, adding e.html to the crawl list.

Now we remove e.html from the crawl list and crawl it.

Since we have now finished crawling 3 pages, we won't crawl anymore.

BFS crawl

With a BFS crawl, we visit the pages in a queue or FIFO order. So we first remove b.html from the crawl list and crawl it, adding c.html to the crawl list:

Now, since we are using a FIFO crawl order, we remove d.html from the crawl list and crawl it.

Since we have now finished crawling 3 pages, we won't crawl anymore.