微信客服：xiaoxionga100
微信客服：ITCS521
算法代写-COMP9024
时间：2022-07-27
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 1/6
COMP9024 22T2 Assignment
MyPageRank
Data Structures and Algorithms
Change Log
We may make minor changes to the spec to address/clarify some outstanding issues. These may require minimal changes in your design/code, if at all.
Students are strongly encouraged to check the online forum discussion and the change log regularly.
Version 0.1
(2022-07-11 15:00)
Initial release.
Version 0.2
(2022-07-14 13:00)
Assignment Files: added micro-web link/image.
Version 0.3
(2022-07-14 17:00)
Subset 0: explicitly noted that string.h may be used and memory for list/graph structures should be allocated dynamically.
Assessment: added submission and due date details.
Version 0.4
(2022-07-14 18:15)
Subset 3: in crawler.c code stub replaced fgets and strlen lines with call to scanf.
Version 0.5
(2022-07-21 02:15)
Subset 1: added sample output for micro-web, nothing to ignore.
Subset 2: added sample output for micro-web, nothing to ignore.
Version 0.6
(2022-07-21 04:15)
Subset 1: added testing.
Subset 2: added testing.
Version 0.7
(2022-07-21 13:50)
Subset 3: added sample output for micro-web, nothing to ignore.
Subset 3: added testing.
Version 1.0
(2022-07-21 22:00)
Subsets 1, 2, 3: added sample output and dryrun test cases with ignore lists.
Assignment Files
Download this zip file.
Unzipping the file will create a directory called 'files' with all the assignment start-up files.
You can also make note of the following URLs:
http://www.cse.unsw.edu.au/~cs9024/micro-web
http://www.cse.unsw.edu.au/~cs9024/mini-web
Here is a visual representation of the micro-web:
Once you read the spec, hopefully it will be clear to you what you could use these URLs for! You may also find it useful to construct a similar graph visualisation
for the mini-web.
Background
As we have mentioned in lectures, the Internet can be thought of as a graph (a very large graph). Web pages represent vertices and hyperlinks represent
directed edges.
With over 1.2 Billion unique websites (as of June 2021) and each website having multiple webpages and each webpage having multiple hyperlinks it can
understandably be a very difficult job to remember the URL of every website you want to visit.
In order to make life easier, from the very early days of the internet, there have been search engines that can be used to find websites.
But the job of a search engine is very difficult: First it must index (create a representation of) the entire (or as close to it as possible) internet. Next it must rank
the webpages it finds.
In this assignment we will be implementing algorithms to solve each of these problems.
1. To index the internet we will be creating a web crawling.
2. To rank webpages we will implement the pagerank algorithm.
3. To find the shortest path between two pages we will implement dijkstra's algorithm
The Assignment
Subset 0 - Dependencies
Before we can start crawling we need to be able to store our crawled data. As the internet is a Graph, this means we need a Graph ADT. We will also need a Set
ADT and one of a Queue ADT or a Stack ADT in order to perform web scraping (for a BFS or DFS).
Subset 0a - Implement List (Queue, Stack, Set) ADT
Task
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 2/6
You have been provided with a file list.h. Examine the given list.h file carefully. It provides the interface to an ADT that will provide Queue, Stack, and Set
functionality.
You should create the file list.c to implement this ADT.
Your list ADT should store string (char *) data.
You may use the string.h library and other standard libraries from the weekly exercises.
You are required to dynamically allocate memory in your ADT for full style marks.
You can use whatever internal representation you like for your list ADT.
You can reuse the code previously submitted for weekly assessments in your list ADT.
As a reminder:
Queue - First In, First Out
Stack - First In, Last Out
Set - Only stores unique values.
See list.h for more information about each function that you are required to implement.
Remember that you cannot modify list.h.
You should write programs that use the list ADT to test and debug your code.
Subset 0b - Implement Graph ADT
Task
You have been provided with a file graph.h. Examine the given graph.h file carefully. It provides the interface to an ADT that will provide Graph functionality.
You should create the file graph.c to implement this ADT.
Your graph ADT should store string (char *) data in its vertices.
You may use the string.h library and other standard libraries from the weekly exercises.
You are required to dynamically allocate memory in your ADT for full style marks.
You must use an adjacency list representation for your ADT. But the exact implementation is up to you.
You can reuse the code previously submitted for weekly assessments in your graph ADT.
See graph.h for more information about each function that you are required to implement.
Note that graph.h indicates that each edge has a weight.
Remember that you cannot modify graph.h.
You should write programs that use the graph ADT to test and debug your code.
Subset 1 - Web Crawler
Task
We are now going to use the list and graph ADTs you have created to implement a web scraper.
After compiling with make crawler (using Makefile given), run the executable and check that the output aligns with the navigation of the sample website.
Once you have completed the appropriate list functions, carefully examine the code crawler.c.
Uncomment the block of code that uses 'scanf' to take user inputs for 'ignore list' in the provided implementation, so that users can provide some URLs as input.
The ignore list represents the URLs that we would like to completely ignore when you are calculating page ranks, as if they did not exist in the graph. This
means that any incoming and outgoing edges from these URLs are treated as non-existent. You are required to implement this functionality locally - within the
graph_show() function - and NOT to change the actual graph ADT. For more details see the graph.h file.
crawler.c requires external dependencies (libcurl and libxml2)
The provided Makefile will work on CSE servers (ssh and vlab) but might not work on your home computer.
If you have correctly implemented the ADTs from the previous tasks, this part should be mostly free.
Note: crawler.c is a complete implementation of a web crawler; you do not need to modify the utility functions, only the bottom part of the main function.
However, you should look at the program carefully and understand it well so that you can use it (i.e., modify it appropriately) for later tasks.
Sample Output
Using a modified crawler.c that simply calls graph_show() on the micro-web, and without ignoring any pages, the output should be:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter a page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html 1
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html 1
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html 1
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html 1
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html 1
Now lets add index.html to the ignore list:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter a page to ignore or type 'done': http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter another page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 3/6
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
All traces of index.html have been removed. This means that only the remaining vertices are displayed as there are no longer any edges. Note that the order of
the output matters. It should follow the BFS that is performed by the crawler. If your result does not follow this order, you will be marked as incorrect, even if your
graph is valid.
Testing
We have created a script to automatically test your list and graph ADTs. It expects to find list.c and graph.c in the current working directory. Limited test cases
are provided, so you should always do your own, more thorough, testing.
prompt$ 9024 dryrun assn_crawler
Subset 2 - PageRank
Background
Now that we can crawl a network and build a graph, we need a way to determine what pages in our network (vertices) are important.
We haven't kept page content so the only metric we can use to determine importance of a page is to check how much other pages rely on its existence. That is:
how easy is it to follow a sequence of one or more links (edges) and end up on the page.
In 1998 Larry Page and Sergey Brin created the PageRank algorithm to evaluate this metric.
Google still uses the PageRank algorithm to score every page it indexes on the internet to help order its search results.
Task
In graph.c implement the two new functions graph_pagerank() and graph_viewrank().
First, graph_pagerank() should calculate the PageRank of every page (vertex) in your graph. The algorithm should store and calculate the page rank in the
ADT.
The algorithm must exclude the URLs that are provided in an 'ignore list' to the function. Do not remove the pages from the graph, only skip (i.e., ignore) them
for calcualtion. This means that you will need to understand what parts of the Page Rank algorithm need to be modified.
Using the ignore list, you will be able to see what happens to the page ranks as certain pages are removed. What should happen to the pagerank of a certain
page if you remove all pages pointing to it?
Second, graph_viewrank() should print the PageRank of every page (vertex) in your graph that is NOT in the ignore list.
Pages (vertices) should be printed from highest to lowest rank, if two pages have the same rank then they should be printed alphabetically.
You can add utility functions to graph.c
You can (and most likely will need to) modify your struct definitions in graph.c
You cannot modify the file graph.h
You cannot modify the function prototypes for graph_pagerank() and graph_viewrank()
Algorithm
For :
for :
Where:
is the number of vertices
and are each some vertex
is the "time" (iteration count)
is the PageRank of vertex at some time
is the damping_factor
is the set of vertices that have an outbound edge towards
is the PageRank of vertex at some time
is the degree of vertex , ie. the number of outbound edges of vertex
is the set of sinks, ie. the set of vertices with no outbound edges, ie. where is 0
This is formula is equivalent to the following algorithm:
procedure graph_pagerank(G, damping_factor, epsilon)
N = number of vertices in G
for all V in vertices of G
oldrank of V = 0
pagerank of V = 1 / N
end for
while |pagerank of V - oldrank of V| of any V in vertices of G > epsilon
for all V in vertices of G
oldrank of V = pagerank of V
end for
sink_rank = 0
for all V in vertices of G that have no outbound edges
t = 0
PR(p
i
; t) =
1
N
t > 0
PR(p
i
; t) =
1 − d
N
+ d× (( ∑
p
j
∈M(p
i
)
PR(p
j
; t− 1)
D(p
j
)
) + (∑
p
j
∈S
PR(p
j
; t− 1)
N
))
N
p
i
p
j
t
PR(p
i
; t) p
i
t
d
M(p
i
) M(p
i
)
PR(p
j
; t− 1) p
j
t− 1
D(p
j
) p
j
p
j
S D(p
j
)
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 4/6
sink_rank = sink_rank + (damping_factor * (oldrank of V / N))
end for
for all V in vertices of G
pagerank of V = sink_rank + ((1 - damping_factor) / N)
for all I in vertices of G that have an edge from I to V
pagerank of V = pagerank of V + ((damping_factor * oldrank of I) / number of outbound edges from I)
end for
end for
end while
end procedure
In order to test your pagerank functions, you should modify crawler.c to #include "pagerank.h", and change the last part of the main function to something
like:
...
graph_show(network, stdout, ignore_list);
graph_pagerank(network, damping, delta, ignore_list);
graph_viewrank(network, stdout, ignore_list);
list_destroy(ignore_list);
graph_destroy(network);
where you choose appropriate values for damping and delta (aka epsilon).
Again it is noted that the changes you make to crawler.c are purely for you to test whether your pagerank functions are working. We use a different crawler.c for
testing your pagerank functions.
Sample Output
Here we're using a modified crawler.c that calculates graph_pagerank() and prints graph_viewrank(). Damping has been set to 0.85 and epsilon/delta to
0.00001. For the micro-web, and without ignoring any pages, the output should be:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter a page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html (0.412)
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html (0.196)
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html (0.196)
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html (0.196)
Now lets add index.html to the ignore list:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter a page to ignore or type 'done': http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter another page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html (0.333)
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html (0.333)
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html (0.333)
X.html, Y.html and Z.html have no connections anymore and as such have the same ranks. Note that the sum is still equal to 1, and N, the number of vertices, is
equal to 3 in this case, since there were a total of 4 nodes originally, and 1 of the nodes has been ignored.
Testing
We have created a script to automatically test your PageRank algorithm. It expects to find list.c and graph.c in the current working directory. Limited test cases
are provided, so you should always do your own, more thorough, testing.
prompt$ 9024 dryrun assn_rankings
Subset 3 - Degrees of Separation (Shortest Path)
Task
In graph.c implement the two new functions graph_shortest_path() and graph_view_path().
First, graph_shortest_path() should calculate the shortest path between a source vertex and all other vertices.
graph_shortest_path() should use dijkstra's algorithm to do so.
Note that an ignore list is also passed into graph_shortest_path(). Similar to above, you will need to ensure these URLs are treated as non-existent. For example
if there was a path A->B->C, but B is ignored, then there is no path from A to C.
Unlike a regular implementation of dijkstra's algorithm, your code should minimise the number of edges in the path (not minimise the total weight of the path).
Second, graph_view_path() should print the path from the previously given source vertex to a given destination vertex. With the ignore list, there can be no
path between two vertices. In this case, output nothing.
You can add more utility functions to graph.c
You can (and most likely will need to) extend your struct definitions in graph.c
You cannot modify the file graph.h
You cannot modify the function prototypes for graph_shortest_path() and graph_view_path()
In order to test your dijkstra functions, you should modify crawler.c to add #include "dijkstra.h", and change the last part of the main function to something like:
...
graph_show(network, stdout, ignore_list);
graph_shortest_path(network, argv[1], ignore_list);
char destination[BUFSIZ];
printf("destination: ");
scanf("%s", destination);
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 5/6
graph_view_path(network, destination, ignore_list);
list_destroy(ignore_list);
graph_destroy(network);
The changes you make to crawler.c are purely for you to test whether your dijkstra functions are working. We use a different crawler.c for testing your dijkstra
functions.
Sample Output
Using a modified crawler.c that accepts a source page as a command line argument from which to calculate graph_shortest_path(), and a destination
page to output graph_view_path(), for the micro-web, and without ignoring any pages, the output in tracing a path from X.html to Z.html should be:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/X
destination: http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
Enter a page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
Now let's add index.html to the ignore list:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/X
destination: http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
Enter a page to ignore or type 'done': http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter another page to ignore or type 'done': done
prompt$
Since index.html has been ignored, the path cannot be completed and nothing is returned. Your algorithm should iterate vertices/pages in the same order as the
crawler. This ensures that when your algorithm finds the shortest path, it will return the first path it would encounter from the BFS in the crawler. If your result
does not follow this order, you will be marked as incorrect, even if your path is valid.
Testing
We have created a script to automatically test your shortest path algorithm. It expects to find list.c and graph.c in the current working directory. Limited test cases
are provided, so you should always do your own, more thorough, testing.
prompt$ 9024 dryrun assn_path
Assessment
Submission
Submit your list.c and graph.c files using the following give command:
prompt$ give cs9024 assn list.c graph.c
Make sure you spell the filenames correctly. You can run give multiple times. Only your last submission will be marked.
You can check your latest submission on CSE servers with:
prompt$ 9024 classrun check assn
If you are working at home, you may find it more convenient to upload your work via the "Make Submission" tab at the top of this assignment page on WebCMS,
or via give's web interface.
Due Date
This assignment is due Week 10, Wednesday, 3 August 23:59:59 (i.e. before midnight).
The UNSW standard late penalty for assessment is 5% per day for 5 days - this is implemented hourly for this assignment.
Each hour your assignment is submitted late reduces its mark by 0.2%.
For example, if an assignment worth 60% was submitted 10 hours late, it would be awarded 58.8%.
Beware - submissions more than 5 days late will receive zero marks. This again is the UNSW standard assessment policy.
Assessment Scheme
Total 12 marks allocated for this assignment:
2 marks for quality/correctness of the code to the assignment specification and coding style (readability, comments, etc.) ... manual inspection of the code
by the tutors
6.5 marks for page ranking implementation ... automark/testing
3.5 marks for shortest path implementation ... automark/testing
Important:
Any submission that does not allow us to follow the above mentioned marking procedure "normally" (e.g., missing files, compile errors) will result in your
submission not getting marked in time. Depending on the severity of the errors/problems, we may ask you to resubmit (with max late penalty) or assess
your written code instead (e.g., for some "effort" marks only).
Ensure your submitted code compiles on a CSE machine using dcc with the standard options -Wall -Werror -std=c11.
Plagiarism
Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism detection software will be used to compare all submissions
pairwise (including submissions for similar assignments in previous years, if applicable) and serious penalties will be applied, particularly in the case of repeat
offences.
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 6/6
Do not copy ideas or code from others.
Do not use a publicly accessible repository or allow anyone to see your code.
Please refer to the on-line resources to help you understand what plagiarism is and how it is dealt with at UNSW:
Academic Integrity and Plagiarism
UNSW Plagiarism Policy Statement
UNSW Plagiarism Management Procedure
Copyright
Reproducing, publishing, posting, distributing or translating this assignment is an infringement of copyright and will be referred to UNSW Student Conduct and
Integrity for action.
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 1/6
COMP9024 22T2 Assignment
MyPageRank
Data Structures and Algorithms
Change Log
We may make minor changes to the spec to address/clarify some outstanding issues. These may require minimal changes in your design/code, if at all.
Students are strongly encouraged to check the online forum discussion and the change log regularly.
Version 0.1
(2022-07-11 15:00)
Initial release.
Version 0.2
(2022-07-14 13:00)
Assignment Files: added micro-web link/image.
Version 0.3
(2022-07-14 17:00)
Subset 0: explicitly noted that string.h may be used and memory for list/graph structures should be allocated dynamically.
Assessment: added submission and due date details.
Version 0.4
(2022-07-14 18:15)
Subset 3: in crawler.c code stub replaced fgets and strlen lines with call to scanf.
Version 0.5
(2022-07-21 02:15)
Subset 1: added sample output for micro-web, nothing to ignore.
Subset 2: added sample output for micro-web, nothing to ignore.
Version 0.6
(2022-07-21 04:15)
Subset 1: added testing.
Subset 2: added testing.
Version 0.7
(2022-07-21 13:50)
Subset 3: added sample output for micro-web, nothing to ignore.
Subset 3: added testing.
Version 1.0
(2022-07-21 22:00)
Subsets 1, 2, 3: added sample output and dryrun test cases with ignore lists.
Assignment Files
Download this zip file.
Unzipping the file will create a directory called 'files' with all the assignment start-up files.
You can also make note of the following URLs:
http://www.cse.unsw.edu.au/~cs9024/micro-web
http://www.cse.unsw.edu.au/~cs9024/mini-web
Here is a visual representation of the micro-web:
Once you read the spec, hopefully it will be clear to you what you could use these URLs for! You may also find it useful to construct a similar graph visualisation
for the mini-web.
Background
As we have mentioned in lectures, the Internet can be thought of as a graph (a very large graph). Web pages represent vertices and hyperlinks represent
directed edges.
With over 1.2 Billion unique websites (as of June 2021) and each website having multiple webpages and each webpage having multiple hyperlinks it can
understandably be a very difficult job to remember the URL of every website you want to visit.
In order to make life easier, from the very early days of the internet, there have been search engines that can be used to find websites.
But the job of a search engine is very difficult: First it must index (create a representation of) the entire (or as close to it as possible) internet. Next it must rank
the webpages it finds.
In this assignment we will be implementing algorithms to solve each of these problems.
1. To index the internet we will be creating a web crawling.
2. To rank webpages we will implement the pagerank algorithm.
3. To find the shortest path between two pages we will implement dijkstra's algorithm
The Assignment
Subset 0 - Dependencies
Before we can start crawling we need to be able to store our crawled data. As the internet is a Graph, this means we need a Graph ADT. We will also need a Set
ADT and one of a Queue ADT or a Stack ADT in order to perform web scraping (for a BFS or DFS).
Subset 0a - Implement List (Queue, Stack, Set) ADT
Task
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 2/6
You have been provided with a file list.h. Examine the given list.h file carefully. It provides the interface to an ADT that will provide Queue, Stack, and Set
functionality.
You should create the file list.c to implement this ADT.
Your list ADT should store string (char *) data.
You may use the string.h library and other standard libraries from the weekly exercises.
You are required to dynamically allocate memory in your ADT for full style marks.
You can use whatever internal representation you like for your list ADT.
You can reuse the code previously submitted for weekly assessments in your list ADT.
As a reminder:
Queue - First In, First Out
Stack - First In, Last Out
Set - Only stores unique values.
See list.h for more information about each function that you are required to implement.
Remember that you cannot modify list.h.
You should write programs that use the list ADT to test and debug your code.
Subset 0b - Implement Graph ADT
Task
You have been provided with a file graph.h. Examine the given graph.h file carefully. It provides the interface to an ADT that will provide Graph functionality.
You should create the file graph.c to implement this ADT.
Your graph ADT should store string (char *) data in its vertices.
You may use the string.h library and other standard libraries from the weekly exercises.
You are required to dynamically allocate memory in your ADT for full style marks.
You must use an adjacency list representation for your ADT. But the exact implementation is up to you.
You can reuse the code previously submitted for weekly assessments in your graph ADT.
See graph.h for more information about each function that you are required to implement.
Note that graph.h indicates that each edge has a weight.
Remember that you cannot modify graph.h.
You should write programs that use the graph ADT to test and debug your code.
Subset 1 - Web Crawler
Task
We are now going to use the list and graph ADTs you have created to implement a web scraper.
After compiling with make crawler (using Makefile given), run the executable and check that the output aligns with the navigation of the sample website.
Once you have completed the appropriate list functions, carefully examine the code crawler.c.
Uncomment the block of code that uses 'scanf' to take user inputs for 'ignore list' in the provided implementation, so that users can provide some URLs as input.
The ignore list represents the URLs that we would like to completely ignore when you are calculating page ranks, as if they did not exist in the graph. This
means that any incoming and outgoing edges from these URLs are treated as non-existent. You are required to implement this functionality locally - within the
graph_show() function - and NOT to change the actual graph ADT. For more details see the graph.h file.
crawler.c requires external dependencies (libcurl and libxml2)
The provided Makefile will work on CSE servers (ssh and vlab) but might not work on your home computer.
If you have correctly implemented the ADTs from the previous tasks, this part should be mostly free.
Note: crawler.c is a complete implementation of a web crawler; you do not need to modify the utility functions, only the bottom part of the main function.
However, you should look at the program carefully and understand it well so that you can use it (i.e., modify it appropriately) for later tasks.
Sample Output
Using a modified crawler.c that simply calls graph_show() on the micro-web, and without ignoring any pages, the output should be:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter a page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html 1
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html 1
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html 1
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html 1
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html 1
Now lets add index.html to the ignore list:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter a page to ignore or type 'done': http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter another page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 3/6
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
All traces of index.html have been removed. This means that only the remaining vertices are displayed as there are no longer any edges. Note that the order of
the output matters. It should follow the BFS that is performed by the crawler. If your result does not follow this order, you will be marked as incorrect, even if your
graph is valid.
Testing
We have created a script to automatically test your list and graph ADTs. It expects to find list.c and graph.c in the current working directory. Limited test cases
are provided, so you should always do your own, more thorough, testing.
prompt$ 9024 dryrun assn_crawler
Subset 2 - PageRank
Background
Now that we can crawl a network and build a graph, we need a way to determine what pages in our network (vertices) are important.
We haven't kept page content so the only metric we can use to determine importance of a page is to check how much other pages rely on its existence. That is:
how easy is it to follow a sequence of one or more links (edges) and end up on the page.
In 1998 Larry Page and Sergey Brin created the PageRank algorithm to evaluate this metric.
Google still uses the PageRank algorithm to score every page it indexes on the internet to help order its search results.
Task
In graph.c implement the two new functions graph_pagerank() and graph_viewrank().
First, graph_pagerank() should calculate the PageRank of every page (vertex) in your graph. The algorithm should store and calculate the page rank in the
ADT.
The algorithm must exclude the URLs that are provided in an 'ignore list' to the function. Do not remove the pages from the graph, only skip (i.e., ignore) them
for calcualtion. This means that you will need to understand what parts of the Page Rank algorithm need to be modified.
Using the ignore list, you will be able to see what happens to the page ranks as certain pages are removed. What should happen to the pagerank of a certain
page if you remove all pages pointing to it?
Second, graph_viewrank() should print the PageRank of every page (vertex) in your graph that is NOT in the ignore list.
Pages (vertices) should be printed from highest to lowest rank, if two pages have the same rank then they should be printed alphabetically.
You can add utility functions to graph.c
You can (and most likely will need to) modify your struct definitions in graph.c
You cannot modify the file graph.h
You cannot modify the function prototypes for graph_pagerank() and graph_viewrank()
Algorithm
For :
for :
Where:
is the number of vertices
and are each some vertex
is the "time" (iteration count)
is the PageRank of vertex at some time
is the damping_factor
is the set of vertices that have an outbound edge towards
is the PageRank of vertex at some time
is the degree of vertex , ie. the number of outbound edges of vertex
is the set of sinks, ie. the set of vertices with no outbound edges, ie. where is 0
This is formula is equivalent to the following algorithm:
procedure graph_pagerank(G, damping_factor, epsilon)
N = number of vertices in G
for all V in vertices of G
oldrank of V = 0
pagerank of V = 1 / N
end for
while |pagerank of V - oldrank of V| of any V in vertices of G > epsilon
for all V in vertices of G
oldrank of V = pagerank of V
end for
sink_rank = 0
for all V in vertices of G that have no outbound edges
t = 0
PR(p
i
; t) =
1
N
t > 0
PR(p
i
; t) =
1 − d
N
+ d× (( ∑
p
j
∈M(p
i
)
PR(p
j
; t− 1)
D(p
j
)
) + (∑
p
j
∈S
PR(p
j
; t− 1)
N
))
N
p
i
p
j
t
PR(p
i
; t) p
i
t
d
M(p
i
) M(p
i
)
PR(p
j
; t− 1) p
j
t− 1
D(p
j
) p
j
p
j
S D(p
j
)
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 4/6
sink_rank = sink_rank + (damping_factor * (oldrank of V / N))
end for
for all V in vertices of G
pagerank of V = sink_rank + ((1 - damping_factor) / N)
for all I in vertices of G that have an edge from I to V
pagerank of V = pagerank of V + ((damping_factor * oldrank of I) / number of outbound edges from I)
end for
end for
end while
end procedure
In order to test your pagerank functions, you should modify crawler.c to #include "pagerank.h", and change the last part of the main function to something
like:
...
graph_show(network, stdout, ignore_list);
graph_pagerank(network, damping, delta, ignore_list);
graph_viewrank(network, stdout, ignore_list);
list_destroy(ignore_list);
graph_destroy(network);
where you choose appropriate values for damping and delta (aka epsilon).
Again it is noted that the changes you make to crawler.c are purely for you to test whether your pagerank functions are working. We use a different crawler.c for
testing your pagerank functions.
Sample Output
Here we're using a modified crawler.c that calculates graph_pagerank() and prints graph_viewrank(). Damping has been set to 0.85 and epsilon/delta to
0.00001. For the micro-web, and without ignoring any pages, the output should be:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter a page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html (0.412)
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html (0.196)
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html (0.196)
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html (0.196)
Now lets add index.html to the ignore list:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter a page to ignore or type 'done': http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter another page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html (0.333)
http://www.cse.unsw.edu.au/~cs9024/micro-web/Y.html (0.333)
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html (0.333)
X.html, Y.html and Z.html have no connections anymore and as such have the same ranks. Note that the sum is still equal to 1, and N, the number of vertices, is
equal to 3 in this case, since there were a total of 4 nodes originally, and 1 of the nodes has been ignored.
Testing
We have created a script to automatically test your PageRank algorithm. It expects to find list.c and graph.c in the current working directory. Limited test cases
are provided, so you should always do your own, more thorough, testing.
prompt$ 9024 dryrun assn_rankings
Subset 3 - Degrees of Separation (Shortest Path)
Task
In graph.c implement the two new functions graph_shortest_path() and graph_view_path().
First, graph_shortest_path() should calculate the shortest path between a source vertex and all other vertices.
graph_shortest_path() should use dijkstra's algorithm to do so.
Note that an ignore list is also passed into graph_shortest_path(). Similar to above, you will need to ensure these URLs are treated as non-existent. For example
if there was a path A->B->C, but B is ignored, then there is no path from A to C.
Unlike a regular implementation of dijkstra's algorithm, your code should minimise the number of edges in the path (not minimise the total weight of the path).
Second, graph_view_path() should print the path from the previously given source vertex to a given destination vertex. With the ignore list, there can be no
path between two vertices. In this case, output nothing.
You can add more utility functions to graph.c
You can (and most likely will need to) extend your struct definitions in graph.c
You cannot modify the file graph.h
You cannot modify the function prototypes for graph_shortest_path() and graph_view_path()
In order to test your dijkstra functions, you should modify crawler.c to add #include "dijkstra.h", and change the last part of the main function to something like:
...
graph_show(network, stdout, ignore_list);
graph_shortest_path(network, argv[1], ignore_list);
char destination[BUFSIZ];
printf("destination: ");
scanf("%s", destination);
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 5/6
graph_view_path(network, destination, ignore_list);
list_destroy(ignore_list);
graph_destroy(network);
The changes you make to crawler.c are purely for you to test whether your dijkstra functions are working. We use a different crawler.c for testing your dijkstra
functions.
Sample Output
Using a modified crawler.c that accepts a source page as a command line argument from which to calculate graph_shortest_path(), and a destination
page to output graph_view_path(), for the micro-web, and without ignoring any pages, the output in tracing a path from X.html to Z.html should be:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/X
destination: http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
Enter a page to ignore or type 'done': done
http://www.cse.unsw.edu.au/~cs9024/micro-web/X.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
Now let's add index.html to the ignore list:
prompt$ ./crawler http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html http://www.cse.unsw.edu.au/~cs9024/micro-web/X
destination: http://www.cse.unsw.edu.au/~cs9024/micro-web/Z.html
Enter a page to ignore or type 'done': http://www.cse.unsw.edu.au/~cs9024/micro-web/index.html
Enter another page to ignore or type 'done': done
prompt$
Since index.html has been ignored, the path cannot be completed and nothing is returned. Your algorithm should iterate vertices/pages in the same order as the
crawler. This ensures that when your algorithm finds the shortest path, it will return the first path it would encounter from the BFS in the crawler. If your result
does not follow this order, you will be marked as incorrect, even if your path is valid.
Testing
We have created a script to automatically test your shortest path algorithm. It expects to find list.c and graph.c in the current working directory. Limited test cases
are provided, so you should always do your own, more thorough, testing.
prompt$ 9024 dryrun assn_path
Assessment
Submission
Submit your list.c and graph.c files using the following give command:
prompt$ give cs9024 assn list.c graph.c
Make sure you spell the filenames correctly. You can run give multiple times. Only your last submission will be marked.
You can check your latest submission on CSE servers with:
prompt$ 9024 classrun check assn
If you are working at home, you may find it more convenient to upload your work via the "Make Submission" tab at the top of this assignment page on WebCMS,
or via give's web interface.
Due Date
This assignment is due Week 10, Wednesday, 3 August 23:59:59 (i.e. before midnight).
The UNSW standard late penalty for assessment is 5% per day for 5 days - this is implemented hourly for this assignment.
Each hour your assignment is submitted late reduces its mark by 0.2%.
For example, if an assignment worth 60% was submitted 10 hours late, it would be awarded 58.8%.
Beware - submissions more than 5 days late will receive zero marks. This again is the UNSW standard assessment policy.
Assessment Scheme
Total 12 marks allocated for this assignment:
2 marks for quality/correctness of the code to the assignment specification and coding style (readability, comments, etc.) ... manual inspection of the code
by the tutors
6.5 marks for page ranking implementation ... automark/testing
3.5 marks for shortest path implementation ... automark/testing
Important:
Any submission that does not allow us to follow the above mentioned marking procedure "normally" (e.g., missing files, compile errors) will result in your
submission not getting marked in time. Depending on the severity of the errors/problems, we may ask you to resubmit (with max late penalty) or assess
your written code instead (e.g., for some "effort" marks only).
Ensure your submitted code compiles on a CSE machine using dcc with the standard options -Wall -Werror -std=c11.
Plagiarism
Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism detection software will be used to compare all submissions
pairwise (including submissions for similar assignments in previous years, if applicable) and serious penalties will be applied, particularly in the case of repeat
offences.
2022/7/23 20:55 COMP9024 22T2 - Assignment
https://cgi.cse.unsw.edu.au/~cs9024/22T2/assn/index.php 6/6
Do not copy ideas or code from others.
Do not use a publicly accessible repository or allow anyone to see your code.
Please refer to the on-line resources to help you understand what plagiarism is and how it is dealt with at UNSW:
Academic Integrity and Plagiarism
UNSW Plagiarism Policy Statement
UNSW Plagiarism Management Procedure
Copyright
Reproducing, publishing, posting, distributing or translating this assignment is an infringement of copyright and will be referred to UNSW Student Conduct and
Integrity for action.
