代写 graph COMP9024 (19T0)

COMP9024 (19T0)
• Ass2 : How to Implement? Notes:
• The document offers some suggestions only, with incomplete pseudo code
• The pseudo code is easy to read, but may not be efficient. You need to improve it!
• You can use code from labs/lecture material, however, must acknowledge it and provide a reference. For example you can use graph ADT implementation from one of the labs, and adapt it for this assignment.
• You can build a graph structure using Adjacency Matrix or List Representation.
1

graph.h
graph.c
• See lectures and labs on Graph ADT
readData.h
readData.c (see next page)
invertedIndex.h
invertedIndex.c
Possible implementations
• List of list OR
• BST where key is a string and value is a list (can use strcmp to compare key strings)
2

List of List
mars
*
url21
url32
…
*
…
…
…
venus
*
url56
3

Binary Search Tree (BST) Binary Search Tree where key is a string and value is a list
(can use strcmp to compare key strings).
We will discuss BST in Week 07.
You can work on Part-A in Week-06 and Part-B in Week-07.
mars
url21
url32
*
char *word; // key
ListNode *urlList;
Tree *left; Tree *right
4

readData.c
List_of_UrlsßGetCollection( )
Create a set (list) of urls to process by reading data from file “collection.txt”
Graph gßGetGraph(List_of_Urls )
Create empty graph (use graph ADT in say graph.h and graph.c) For each url in the above list
• read .txt file, and update graph by adding a node and outgoing links
InvertedList ß GetInvertedList(List_of_Urls )
Create empty inverted list (use say List of lists, BST where values are lists, etc)
For each url in List_of_Urls
• read .txt file, and update inverted index
5

pagerank.h
pagerank.c
pagerank.c
Get args : d, diffPR, maxIterations List_of_UrlsßGetCollection( )
Graph gßGetGraph(List_of_Urls)
List_Urls_PageRanks = calculatePageRank(g, d, diffPR, maxIterations );
Ordered_List_Urls_PageRanks = order (List_Urls_PageRanks ) Output Ordered_List_Urls_PageRanks to “pagerankList.txt”
6

invertedIndex.h
invertedIndex.c
invertedIndex.c
List_of_UrlsßGetCollection( )
InvertedIndex invertedIdx ß GetInvertedList (List_of_Urls)
Output invertedIdx to “invertedIndex.txt”
7

searchPagerank.h
searchPagerank.c
searchPagerank.c
Get query words from arguments matched_Url_listßfindMatchedUrls(“invertedIndex.txt”, queryWords)
matched_Urls_with_PRßfindPagerank(“pagerankList.txt”, matched_Url_list) Output ordered urls on stdout
8