Introduction

The Internet can be viewed from both physical and logical perspectives. From a physical point of view, the Internet is a collection of web servers connected together with fibre optic cables. From a logical point of view, the Internet is a collection of webpages connected together with hyperlinks. For this assignment, both perspectives are modeled as graphs in the following ways.

Server Graph

The collection of servers, on one hand, is represented

by an undirected, unweighted server graph S $=($V$,$ E$)$

where:

$1.$ each vertex s E V represents a web server and $2.$

each undirected edge $($s$,$ t$)$ E represents the physical connection between servers and server t$.$

Each server has a unique name and a list of the webpages that it hosts. Also, there is no hard limit on the number of servers.

Web Graph

The collection of webpages, on the other hand, is represented by a directed, unweighted web graph W $=($V$,$ E$)$ where:

$1.$ each vertex u $$ V is a webpage and $2.$

each directed edge $($u$,$ v$)$ E is a hyperlink from webpage u to webpage v$.$ To simplify our discussion, there is at most one hyperlink from u to v$.$

Each webpage has a unique name as well as the name of the server that hosts it$.$

Task $2$: Web Graph $(36$ marks$)$

Using the partial definitions below, implement and test the web graph as an expandable adjacency list.

$//5$ marks

public class WebPage

$\{$

public string Name $\{$get; set;$\}$ public string Server $\{$get; set;$\}$ public List E $\{$get; set;$\}$

public WebPage$($string name, string host$)...$ public int FindLink$($string name$)...$

$\}$

$\{$

public class WebGraph

private List P;

$1|2$ marks

I$/$ Create an empty WebGraph public WebGraph$()...$

$//2$ marks

$//$ Return the index of the webpage with the given

name; otherwise return $-1$ private int FindPage$($string name$)...$

$//4$ marks

Il Add a webpage with the given name and store it on the host server

$//$ Return true if successful; otherwise return false

public bool AddPage$($string name, string host, ServerGraph S$)...$

$//8$ marks

$//$ Remove the webpage with the given name,

including the hyperlinks

$//$ from and to the webpage

$//$ Return true if successful; otherwise return false

public bool RemovePage $($string name, Server Graph S$)...$

$//3$ marks

$/$I Add a hyperlink from one webpage to another

$//$ Return true if successful; otherwise return false

public bool AddLink $($string from, string to$)...$

$//3$ marks

$//$ Remove a hyperlink from one webpage to another

$//$ Return true if successful; otherwise return false

public bool RemoveLink $($string from, string to$)...$

$//6$ marks

$//$ Return the average length of the shortest paths from

the webpage with

Il given name to each of its hyperlinks

$//$ Hint: Use the method ShortestPath in the class

ServerGraph

public float AvgShortestPaths$($string name, ServerGraph S$)...$

$//3$ marks

$//$ Print the name and hyperlinks of each webpage

public void PrintGraph$()...$

$\}$

Task $3$: The Main $(16$ marks$)$

The server and web graphs define the physical and logical models of the Internet and work in tandem to reflect the same reality. In the main program, an instance of each graph is instantiated and the following steps are carried out to exercise your program. Ensure that both successful and unsuccessful cases are tested.

$1.$ Instantiate a server graph and a web graph.

$2.$ Add a number of servers.

$3.$ Add additional connections between servers.

$4.$ Add a number of webpages to various servers.

$5.$ Add and remove hyperlinks between the webpages.

$6.$ Remove both webpages and servers.

$7.$ Determine the critical servers of the remaining Internet.

$8.$ Calculate the average shortest distance to the hyperlinks of a given webpage.

Testing and Documentation $(20$ marks$)$

In a separate document, illustrate your test cases and compare them with the results of your program.