Extra Lab Exercise

• To implement a web crawler
• To see how directed graphs might be used with real-world data

This lab is not marked and there is no submission for it.

We can view the World Wide Web as a massive directed graph, where pages (identified by URLs) are the vertices and hyperlinks are the directed edges. Unlike the graphs we have studied in lectures, there is not a single central representation (e.g. adjacency matrix) for all the edges in the graph of the web; such a data structure would clearly be way too large to store. Instead, the "edges" are embedded in the "vertices". Despite the unusual representation, the Web is clearly a graph, so the aim of this lab exercise is to build an in-memory graph structure for a very, very small subset of the Web.

Web crawlers are programs that navigate the Web automatically, moving from page to page, processing each page they visit. Crawlers typically use a standard graph traversal algorithm to:

• maintain a list of pages to visit (a ToDo list)
• "visit" the next page by grabbing its HTML content
• scan the HTML to extract whatever features they are interested in
• collect hyperlinks from the visited page, and add these to the ToDo list
• repeat the above steps (until there are no more pages to visit :-)

You need to implement such a crawler, using a collection of supplied ADTs and a partially complete main program. Your crawler processes each page by finding any hyperlinks and inserting the implied edges into a directed Graph ADT based on an adjacency matrix. One difference between this Graph ADT and the ones we have looked at in lectures is that you dynamically add information about vertices, as well as edges. The following diagram shows what an instance of the Graph ADT might look like:

The Graph data structure allows for maxV vertices (URLs), where maxV is supplied when graph is created. Initially, there are no vertices or edges, but as the crawler examines the web, it adds the URLs of any pages that it visits and records the hyperlinks between them. This diagram shows what a web crawler might have discovered had it started crawling from the URL http://x.com/index.html, and so far examined four web pages.

If we number the four pages from 0..3, with

• page (vertex) 0 being http://x.com/index.html
• page (vertex) 1 being http://x.com/category/index.html
• page (vertex) 2 being http://x.com/products.html
• page (vertex) 3 being http://x.com/products/abc.html

The vertices array holds the actual URL strings and also, effectively, provides the mapping between URLs and vertex numbers. The edges array is a standard adjacency matrix. The top row tells us that page 0 has hyperlinks to pages 1 and 2. The second row tells us that page 1 has a hyperlink back to page 0. The third row similarly shows a hyperlink from page 2 back to page 0, but also a hyperlink to page 3.

Set up a directory for this lab, change into that directory, and run the following command:

unzip /web/cs2521/24T1/labs/week15/downloads/files.zip

If you're working at home, download files.zip by clicking on the above link and then run the unzip command on the downloaded file.

If you've done the above correctly, you should now have the following files:

Makefile

a set of dependencies used to control compilation

crawl.c

a main program that implements a web crawler (incomplete)

url_file.h, url_file.c

provides a file-like interface to webpages

html.h, html.c

provides functions for extracting URLs from HTML

Graph.h, Graph.c

a Graph ADT interface and implementation

Queue.h, Queue.c

a Queue ADT interface and implementation

Stack.h, Stack.c

a Stack ADT interface and implementation

Set.h, Set.c

a Set ADT interface and implementation

The only file you need to modify is crawl.c, but you need to understand at least the interfaces to the functions in the various ADTs. This is described in comments in the .h files. You can also see examples of using the ADT functions in the t?.c files. Note that there's no test file for the HTML parsing and URL-extracting code, because the supplied version of crawl.c effectively provides this.

Note that HTML parsing code was borrowed from Dartmouth College. If you looks at the code, it has quite a different style to the rest of the code. This provides an interesting comparison with our code.

The crawl program is used as follows:

./crawl StartingURL MaxURLsInGraph

The StartingURL tells you which URL to start the crawl from, and should be of the form http://x.y.z/. The crawler uses this URL as both the starting point and uses a normalised version as the base against which to interpret other URLs.

The MaxURLsInGraph specifies the maximum number of URLs that can be stored in the Graph. Once this many URLs have been scanned, the crawling will stop, or will stop earlier if there are no more URLs left in the ToDo list.

If you compile then run the supplied crawler on the UNSW handbook, you would see something like:

./crawl http://www.handbook.unsw.edu.au/2017/ 100
Found: 'http://www.unsw.edu.au'
Found: 'https://my.unsw.edu.au/'
Found: 'https://student.unsw.edu.au/'
Found: 'http://www.futurestudents.unsw.edu.au/'
Found: 'http://timetable.unsw.edu.au/'
Found: 'https://student.unsw.edu.au/node/62'
Found: 'http://www.library.unsw.edu.au/'
Found: 'http://www.handbook.unsw.edu.au/2017/'
Found: 'http://www.unsw.edu.au/faculties'
Found: 'https://student.unsw.edu.au/node/4431'
Found: 'https://student.unsw.edu.au/node/128'
Found: 'http://www.unsw.edu.au/contacts'
Found: 'http://www.handbook.unsw.edu.au/general/current/SSAPO/previousEditions.html'
Found: 'http://www.handbook.unsw.edu.au/undergraduate/2017/'
Found: 'http://www.handbook.unsw.edu.au/postgraduate/2017/'
Found: 'http://www.handbook.unsw.edu.au/research/2017/'
Found: 'http://www.handbook.unsw.edu.au/nonaward/2017/'
Found: 'http://www.unsw.edu.au/future-students/domestic-undergraduate'
Found: 'http://www.unsw.edu.au/future-students/postgraduate-coursework'
Found: 'http://research.unsw.edu.au/future-students'
Found: 'http://www.international.unsw.edu.au/#1'
Found: 'https://student.unsw.edu.au/node/1334'
Found: 'https://moodle.telt.unsw.edu.au/login/index.php'
Found: 'https://student.unsw.edu.au/node/943'
Found: 'https://apply.unsw.edu.au/'
Found: 'https://student.unsw.edu.au/node/5450'
Found: 'http://cgi.cse.unsw.edu.au/~nss/feest/'
Found: 'http://www.unsw.edu.au/privacy'
Found: 'http://www.unsw.edu.au/copyright-disclaimer'
Found: 'http://www.unsw.edu.au/accessibility'

The supplied crawler simply scans the URL given on the command line, prints out any URLs that it finds, and then stops. It does not attempt to traverse any further than the supplied page. The second command-line argument, which limits the size of the Graph, is effectively ignored here, since the supplied code does not build a Graph; you need to add the code to do this.

If you run the supplied "crawler" on http://www.cse.unsw.edu.au, you don't get very much, because the CSE website recently moved under the Engineering Faculty system and the above URL is just a redirection page to the new site. Copying/pasting the redirection URL gives you more interesting results. Before you go running the "crawler" on other websites ... DON'T! See the comments below.

HTML is a language which is difficult to parse given the way it is frequently used, and the GetNextURL() make some approximations which, while they wouldn't be acceptable in a real Web crawler, are OK for this lab.