So the goal for the rest of this unit is to modify our search engine code,
to implement the PageRank algorithm.
We have one little problem.
PageRank is a registered trademark of Google, so we're not going to call our algorithm PageRank,
even though we'll do the same thing.
We'll call it URank.
The first thing we need to be able to do to implement this ranking algorithm
is keep track of the link graph.
So our popularity of pages depends on the link structure.
So that means we need to keep track of what pages link to what pages.
So for each link, there's a connection between pages.
And we can think of that as a graph.
Abstractly a graph is just a set of nodes.
We'll draw those as circles with edges between the nodes.
And because our edges go one way, just like links in a page,
we call this a directed graph.
So in order to represent our web link structure, we need to build a directed graph.
The pages in the graph are the nodes.
For each page, we need to keep track of the edges
that connect that node to other nodes.
And so the way we're going to do this is to keep a dictionary.
So, we're going to have a dictionary where the entries in the dictionary are the node, which is the URL.
That's the page.
And for each URL, we'll have a list of all the pages that it links to.
So if this was, say, node A and these were nodes B, C, and D,
our entry for node A would contain the list B, C, D,
and our entry for node B--
Well, there are no edges out of B, so it would be an empty list.
And finishing the example, C has an outlink to one node,
and D has not outlinks.
So that's our goal. We want to build a structure like this that shows the structure of the web pages that we crawl.
And we see that structure because we're following the links in our crawler.
So our goal is to modify the crawlweb procedure that we defined at the end of unit 5
and to modify it so instead of just producing an index, it also produces a graph.
So we're going to modify crawlweb. It's still going to take a seed page as its start.
But what it's going to produce now is both an index and a graph,
and the graph is a structure that gives the mapping from each node to the pages that it links to.
So let's look at the code that we had at the end of unit 5 and see how we need to change that.
So here's the code that we had at the end of unit 5 for crawling the web.
And as a reminder, we're keeping track of the pages left to crawl in the list tocrawl
starting with the seed page.
And we're building up the index as a dictionary.
And as long as there are more pages left to crawl,
we go through the Y loop, which finds a page to crawl, popping fill list pages to crawl.
As long as it's one we haven't crawled before,
it gets the content from that page; it adds it to the index.
It finds all the links using getalllinks, passing in the content on the page
and unions those with tocrawl to update the tocrawl list,
and then it appends this page to the list of pages that have already been crawled.
So to change this to build a graph, we're going to keep most of the code the same.
In addition to producing just the index, we're going to produce a graph,
and the graph is also going to be a dictionary.
And the reason the graph is a dictionary is that the mapping from nodes,
which are URLs, to the list of edges that go out from that node.
So we'll create the graph as an empty dictionary,
and as we find new pages, we're going to add them to the graph.
And we're going to also change the return to return both the index and the graph.
I'm going to make one more change before we give you a quiz,
and the change I'm going to make is instead of calling getalllinks here,
since both the graph building and the tocrawl list depend on knowing all the links,
we're going to create a new variable, and we'll assign the result of getalllinks content
to that variable.
that means we can use those links as the input to content,
but we can also use them to build the graph.
And I'm going to leave the line that we need to build the graph for you to complete.
So we'll make that a quiz, to finish this code.
Write the line that we need to update the graph.