b’p1-1-starter.tar.gz’
‘(n1 n2 n4)'(n0 n2 n4)'(n4)'(n1)'(n0 n1 n3)
#!/usr/bin/python3
#####################################################
############# LEAVE CODE BELOW ALONE #############
# Include base directory into path
import os, sys
sys.path.append(os.path.abspath(os.path.join(os.path.dirname( __file__ ), ‘..’, ‘..’)))
# Import tester
from tester import failtest, passtest, assertequals, runcmd, preparefile, runcmdsafe
############# END UNTOUCHABLE CODE #############
#####################################################
###################################
# Write your testing script below #
###################################
python_bin = sys.executable
import pickle
# prepare necessary files
preparefile(‘./test.rkt’)
# run test file
runcmdsafe(‘rm ./output’)
b_stdout, b_stderr, b_exitcode = runcmdsafe(f’racket ./test.rkt’)
# convert stdout bytes to utf-8
stdout = “”
stderr = “”
try:
stdout = b_stdout.decode(‘utf-8’)
stderr = b_stderr.decode(‘utf-8’)
except:
pass
# stdout comparison with expected.txt here
try:
with open(‘answer’, ‘r’) as file1, open(‘output’, ‘r’) as file2:
answer = str(file1.read()).strip()
output = str(file2.read()).strip()
#failtest(answer+”\n\n”+output)
if answer == output:
runcmdsafe(‘rm ./output’)
passtest(”)
else:
runcmdsafe(‘rm ./output’)
failtest(stdout+”\n\n”+stderr)
except FileNotFoundError:
failtest(stdout+”\n\n”+stderr)
#lang racket
(require “../../pagerank.rkt”)
(define g0 ‘((n2 n0)
(n1 n4)
(n4 n0)
(n1 n3)
(n2 n1)
(n0 n1)
(n3 n4)
(n0 n4)
(n4 n1)
(n4 n2)
(n1 n0)))
(define print-set (lambda (s)
(print (sort (set->list s) symbol any? boolean?)
(define (graph? glst)
(and (list? glst)
(andmap
(lambda (element)
(match element
[`(,(? symbol? src) ,(? symbol? dst)) #t]
[else #f]))
glst)))
;; Our implementation takes input graphs and turns them into
;; PageRanks. A PageRank is a Racket hash-map that maps pages (each
;; represented as a Racket symbol) to their corresponding weights,
;; where those weights must sum to 1 (over the whole map).
;; A PageRank encodes a discrete probability distribution over pages.
;;
;; The test graphs for this assignment adhere to several constraints:
;; + There are no “terminal” nodes. All nodes link to at least one
;; other node.
;; + There are no “self-edges,” i.e., there will never be an edge `(n0
;; n0).
;; + To maintain consistenty with the last two facts, each graph will
;; have at least two nodes.
;; + There will be no “repeat” edges. I.e., if `(n0 n1) appears once
;; in the graph, it will not appear a second time.
;;
;; (-> any? boolean?)
(define (pagerank? pr)
(and (hash? pr)
(andmap symbol? (hash-keys pr))
(andmap rational? (hash-values pr))
;; All the values in the PageRank must sum to 1. I.e., the
;; PageRank forms a probability distribution.
(= 1 (foldl + 0 (hash-values pr)))))
;; Takes some input graph and computes the number of pages in the
;; graph. For example, the graph ‘((n0 n1) (n1 n2)) has 3 pages, n0,
;; n1, and n2.
;;
;; (-> graph? nonnegative-integer?)
(define (num-pages graph)
‘todo)
;; Takes some input graph and computes the number of links emanating
;; from page. For example, (num-links ‘((n0 n1) (n1 n0) (n0 n2)) ‘n0)
;; should return 2, as ‘n0 links to ‘n1 and ‘n2.
;;
;; (-> graph? symbol? nonnegative-integer?)
(define (num-links graph page)
‘todo)
;; Calculates a set of pages that link to page within graph. For
;; example, (get-backlinks ‘((n0 n1) (n1 n2) (n0 n2)) n2) should
;; return (set ‘n0 ‘n1).
;;
;; (-> graph? symbol? (set/c symbol?))
(define (get-backlinks graph page)
‘todo)
;; Generate an initial pagerank for the input graph g. The returned
;; PageRank must satisfy pagerank?, and each value of the hash must be
;; equal to (/ 1 N), where N is the number of pages in the given
;; graph.
;; (-> graph? pagerank?)
(define (mk-initial-pagerank graph)
‘todo)
;; Perform one step of PageRank on the specified graph. Return a new
;; PageRank with updated values after running the PageRank
;; calculation. The next iteration’s PageRank is calculated as
;;
;; NextPageRank(page-i) = (1 – d) / N + d * S
;;
;; Where:
;; + d is a specified “dampening factor.” in range [0,1]; e.g., 0.85
;; + N is the number of pages in the graph
;; + S is the sum of P(page-j) for all page-j.
;; + P(page-j) is CurrentPageRank(page-j)/NumLinks(page-j)
;; + NumLinks(page-j) is the number of outbound links of page-j
;; (i.e., the number of pages to which page-j has links).
;;
;; (-> pagerank? rational? graph? pagerank?)
(define (step-pagerank pr d graph)
‘todo)
;; Iterate PageRank until the largest change in any page’s rank is
;; smaller than a specified delta.
;;
;; (-> pagerank? rational? graph? rational? pagerank?)
(define (iterate-pagerank-until pr d graph delta)
‘todo)
;; Given a PageRank, returns the list of pages it contains in ranked
;; order (from least-popular to most-popular) as a list. You may
;; assume that the none of the pages in the pagerank have the same
;; value (i.e., there will be no ambiguity in ranking)
;;
;; (-> pagerank? (listof symbol?))
(define (rank-pages pr)
‘todo)
# Assignment 1: Implementing PageRank
Functions for minimal, satisfactory, and excellent are specified. To
get excellent (/ satisfactory), you must also get satisfactory and
minimal.
PageRank is a popular graph algorithm used for information
retrieval and was first popularized as an algorithm powering
the Google search engine. Details of the PageRank algorithm will be
discussed in class. Here, you will implement several functions that
implement the PageRank algorithm in Racket.
Hints:
– For this assignment, you may assume that no graph will include
any “self-links” (pages that link to themselves) and that each page
will link to at least one other page.
– you can use the code in `testing-facilities.rkt` to help generate
test input graphs for the project. The test suite was generated
using those functions.
– You may want to define “helper functions” to break up complicated
function definitions.
# (graph? g)
(-> any? boolean?)
You do not have to write this function.
This program accepts graphs as input. Graphs are represented as a list
of links, where each link is a list `(,src ,dst) that signals page src
links to page dst. This function checks whether a value is a valid
graph.
# (pagerank? p).
(-> any? boolean?)
You do not have to write this function.
Our implementation takes input graphs and turns them into PageRanks. A
PageRank is a Racket hash-map that maps pages (each represented as a
Racket symbol) to their corresponding weights, where those weights
must sum to 1 (over the whole map). A PageRank encodes a discrete
probability distribution over pages.
The test graphs for this assignment adhere to several constraints:
+ There are no “terminal” nodes. All nodes link to at least one
other node.
+ There are no “self-edges,” i.e., there will never be an edge `(n0
n0).
+ To maintain consistenty with the last two facts, each graph will
have at least two nodes.
+ There will be no “repeat” edges. I.e., if `(n0 n1) appears once
in the graph, it will not appear a second time.
# (num-pages graph)
Required for minimal
(-> graph? nonnegative-integer?)
Takes some input graph and computes the number of pages in the
graph. For example, the graph ‘((n0 n1) (n1 n2)) has 3 pages, n0, n1,
and n2.
# (get-backlinks graph)
(-> graph? symbol? (set/c symbol?))
Required for minimal
Calculates a set of pages that link to page within graph. For
example, (get-backlinks ‘((n0 n1) (n1 n2) (n0 n2)) n2) should
return (set ‘n0 ‘n1).
# (mk-initial-pagerank graph)
(-> graph? pagerank?)
Required for minimal.
Generate an initial pagerank for the input graph g. The returned
PageRank must satisfy pagerank?, and each value of the hash must be
equal to (/ 1 N), where N is the number of pages in the given graph.
# (step-pagerank pr d graph)
(-> pagerank? rational? graph? pagerank?)
Please watch the upcoming video about this one, it is hard to
understand and you may need examples to make sense of it.
Required for satisfactory.
Perform one step of PageRank on the specified graph. Return a new
PageRank with updated values after running the PageRank
calculation. The next iteration’s PageRank is calculated as:
NextPageRank(page-i) = (1 – d) / N + d * SumOfWeightedLinks
Where:
+ d is a specified “dampening factor.” in range [0,1]; e.g., 0.85
+ N is the number of pages in the graph
+ SumOfWeightedLinks is the sum of P(page-j) for all page-j.
+ P(page-j) is CurrentPageRank(page-j)/NumLinks(page-j)
+ NumLinks(page-j) is the number of outbound links of page-j
(i.e., the number of pages to which page-j has links).
# (iterate-pagerank-until pr d graph delta)
(-> pagerank? rational? graph? rational? pagerank?)
Required for excellent.
Iterate PageRank until the largest change in any page’s rank is
smaller than a specified delta.
# (rank-pages pr)
(-> pagerank? (listof symbol?))
Required for excellent.
Given a PageRank, returns the list of pages it contains in ranked
order (from least-popular to most-popular) as a list. You may assume
that the none of the pages in the pagerank have the same value (i.e.,
there will be no ambiguity in ranking).
# Assignment 1: Implementing PageRank
PageRank is a popular graph algorithm used for information
retrieval and was first popularized as an algorithm powering
the Google search engine. Details of the PageRank algorithm will be
discussed in class. Here, you will implement several functions that
implement the PageRank algorithm in Racket.
Hints:
– For this assignment, you may assume that no graph will include
any “self-links” (pages that link to themselves) and that each page
will link to at least one other page.
– you can use the code in `testing-facilities.rkt` to help generate
test input graphs for the project. The test suite was generated
using those functions.
– You may want to define “helper functions” to break up complicated
function definitions.
# (graph? g)
This program accepts graphs as input. Graphs are represented as a list
of links, where each link is a list `(,src ,dst) that signals page src
links to page dst. This function checks whether a value is a valid
graph (-> any? boolean?).
# (pagerank? p).
#lang racket
;; Assignment 1: Implementing PageRank
;;
;; PageRank is a popular graph algorithm used for information
;; retrieval and was first popularized as an algorithm powering
;; the Google search engine. Details of the PageRank algorithm will be
;; discussed in class. Here, you will implement several functions that
;; implement the PageRank algorithm in Racket.
;;
;; Hints:
;;
;; – For this assignment, you may assume that no graph will include
;; any “self-links” (pages that link to themselves) and that each page
;; will link to at least one other page.
;;
;; – you can use the code in `testing-facilities.rkt` to help generate
;; test input graphs for the project. The test suite was generated
;; using those functions.
;;
;; – You may want to define “helper functions” to break up complicated
;; function definitions.
(provide graph?
pagerank?
num-pages
num-links
get-backlinks
mk-initial-pagerank
step-pagerank
iterate-pagerank-until
rank-pages)
;; This program accepts graphs as input. Graphs are represented as a
;; list of links, where each link is a list `(,src ,dst) that signals
;; page src links to page dst.
;; (-> any? boolean?)
(define (graph? glst)
(and (list? glst)
(andmap
(lambda (element)
(match element
[`(,(? symbol? src) ,(? symbol? dst)) #t]
[else #f]))
glst)))
;; Our implementation takes input graphs and turns them into
;; PageRanks. A PageRank is a Racket hash-map that maps pages (each
;; represented as a Racket symbol) to their corresponding weights,
;; where those weights must sum to 1 (over the whole map).
;; A PageRank encodes a discrete probability distribution over pages.
;;
;; The test graphs for this assignment adhere to several constraints:
;; + There are no “terminal” nodes. All nodes link to at least one
;; other node.
;; + There are no “self-edges,” i.e., there will never be an edge `(n0
;; n0).
;; + To maintain consistenty with the last two facts, each graph will
;; have at least two nodes.
;; + There will be no “repeat” edges. I.e., if `(n0 n1) appears once
;; in the graph, it will not appear a second time.
;;
;; (-> any? boolean?)
(define (pagerank? pr)
(and (hash? pr)
(andmap symbol? (hash-keys pr))
(andmap rational? (hash-values pr))
;; All the values in the PageRank must sum to 1. I.e., the
;; PageRank forms a probability distribution.
(= 1 (foldl + 0 (hash-values pr)))))
;; Takes some input graph and computes the number of pages in the
;; graph. For example, the graph ‘((n0 n1) (n1 n2)) has 3 pages, n0,
;; n1, and n2.
;;
;; (-> graph? nonnegative-integer?)
(define (num-pages graph)
‘todo)
;; Takes some input graph and computes the number of links emanating
;; from page. For example, (num-links ‘((n0 n1) (n1 n0) (n0 n2)) ‘n0)
;; should return 2, as ‘n0 links to ‘n1 and ‘n2.
;;
;; (-> graph? symbol? nonnegative-integer?)
(define (num-links graph page)
‘todo)
;; Calculates a set of pages that link to page within graph. For
;; example, (get-backlinks ‘((n0 n1) (n1 n2) (n0 n2)) n2) should
;; return (set ‘n0 ‘n1).
;;
;; (-> graph? symbol? (set/c symbol?))
(define (get-backlinks graph page)
‘todo)
;; Generate an initial pagerank for the input graph g. The returned
;; PageRank must satisfy pagerank?, and each value of the hash must be
;; equal to (/ 1 N), where N is the number of pages in the given
;; graph.
;; (-> graph? pagerank?)
(define (mk-initial-pagerank graph)
‘todo)
;; Perform one step of PageRank on the specified graph. Return a new
;; PageRank with updated values after running the PageRank
;; calculation. The next iteration’s PageRank is calculated as
;;
;; NextPageRank(page-i) = (1 – d) / N + d * S
;;
;; Where:
;; + d is a specified “dampening factor.” in range [0,1]; e.g., 0.85
;; + N is the number of pages in the graph
;; + S is the sum of P(page-j) for all page-j.
;; + P(page-j) is CurrentPageRank(page-j)/NumLinks(page-j)
;; + NumLinks(page-j) is the number of outbound links of page-j
;; (i.e., the number of pages to which page-j has links).
;;
;; (-> pagerank? rational? graph? pagerank?)
(define (step-pagerank pr d graph)
‘todo)
;; Iterate PageRank until the largest change in any page’s rank is
;; smaller than a specified delta.
;;
;; (-> pagerank? rational? graph? rational? pagerank?)
(define (iterate-pagerank-until pr d graph delta)
‘todo)
;; Given a PageRank, returns the list of pages it contains in ranked
;; order (from least-popular to most-popular) as a list. You may
;; assume that the none of the pages in the pagerank have the same
;; value (i.e., there will be no ambiguity in ranking)
;;
;; (-> pagerank? (listof symbol?))
(define (rank-pages pr)
‘todo)
#!/usr/bin/python3
# #######################
#
# This file runs tests for this coding assignment.
# Read the file but do not modify.
#
# #######################
#
# Autograde test.py runner
# Some code taken from test.py from submit
#
import os, sys, subprocess, json, argparse, signal
from subprocess import Popen, PIPE, STDOUT, TimeoutExpired
#####################
# Start Test Utilities
#####################
def preparefile(file):
pass
def runcmdsafe(binfile):
b_stdout, b_stderr, b_exitcode = runcmd(binfile)
return b_stdout, b_stderr, b_exitcode
def runcmd(cmd):
stdout, stderr, process = None, None, None
if os.name != ‘nt’:
cmd = “exec ” + cmd
with Popen(cmd, shell=True, stdin=PIPE, stdout=PIPE, stderr=STDOUT) as process:
try:
stdout, stderr = process.communicate(timeout=15)
except TimeoutExpired:
if os.name == ‘nt’:
Popen(“TASKKILL /F /PID {pid} /T”.format(pid=process.pid))
else:
process.kill()
exit()
return stdout, stderr, process.returncode
def assertequals(expected, actual):
if expected == actual:
passtest(”)
else:
failtest(f’Expected {expected} got {actual}’)
def failtest(message):
testmsg(‘failed’, message)
def passtest(message):
testmsg(‘passed’, message)
def testmsg(status, message):
x = {
“status”: status,
“message”: message
}
print(json.dumps(x))
sys.exit()
#####################
# End Test Utilities
#####################
verbose = False
def runtest(name):
global verbose
print(‘———————‘)
print(f’\nRunning test: {name}’)
try:
python_bin = sys.executable
output = subprocess.check_output(f'”{python_bin}” driver.py’, cwd=f’test/{name}’, shell=True)
y = json.loads(output)
status = y[“status”]
message = y[“message”]
stdout = output
if verbose and len(message) > 0:
print(“\nExpected:\n”)
try:
with open(f’test/{name}/answer’, ‘r’) as file1:
print(str(file1.read()))
except:
print(“Couldn’t read file”)
try:
print(“\n\nSTDOUT:\n”)
print(message)
except:
print(“No output”)
if status == “failed”:
print(‘ FAILED’)
return False
if status == “passed”:
print(‘ PASSED’)
return True
except:
print(sys.exc_info()[0])
print(‘ TIMED OUT’)
return False
def runtests():
tests = listtests()
num_passed = 0
for test in tests:
if runtest(test):
num_passed += 1
print(‘\n===========================’)
print(f’Summary: {num_passed} / {len(tests)} tests passed’)
print(‘===========================’)
def listtests():
tests = [test for test in os.listdir(“test/”)]
tests.sort()
return tests
def main():
global verbose
parser = argparse.ArgumentParser()
parser.add_argument(‘–list’, ‘-l’, help=’List available tests’, action=’store_true’)
parser.add_argument(“–all”, “-a”, help=’Perform all tests’, action=’store_true’)
parser.add_argument(‘–verbose’, ‘-v’, help=’View test stdout, verbose output’, action=’store_true’)
parser.add_argument(‘–test’, ‘-t’, help=’Perform a specific testname (case sensitive)’)
args = parser.parse_args()
if args.verbose:
verbose = True
if args.all:
runtests()
return
if args.test:
if not os.path.exists(f’test/{args.test}’):
print(f’Test “{args.test}” not found’)
return
runtest(args.test)
return
if args.list:
print(“Available tests: “)
print(*listtests(), sep=’\n’)
return
parser.print_help()
if __name__ == “__main__”: main()
;; testing-facilities
;;
;; Facilites for testing assignment 1.
;;
;; The tests were partially generated using:
;;
;; (generate-random-graph N) (for various values of N)
;; (generate-random-pagerank n) (for various values of N)
;;
;; You can generate random graphs by loading Racket and requiring this file:
;; > (require “testing-facilities.rkt”)
;; > (generate-random-graph 5)
#lang racket
;; generate a random graph of a certain size. Our graph has several
;; properties necessary for PageRank to work out nicely:
;;
;; – graphs will never include any “self-edges” (pages that link to themselves)
;; – graphs will not have any nodes which link to no other nodes
;;
;; These two properties simplify the definition of the PageRank
;; algorithm, which implicitly assumes graphs have been normalized to
;; this format.
(define (generate-random-graph n)
(define nodes (map (lambda (x) (string->symbol (format “n~a” x))) (range 0 n)))
;; Generate a random number between 0 and n-1 that excludes k
(define (random-to-n-excluding n k)
(let ([guess (random 0 n)])
(if (= guess k) (random-to-n-excluding n k) guess)))
;; Calculuate a list of edges. Remove duplicates via list->set->list
(set->list
(list->set
(foldl
;; For each node, next-node, in [0,..,n-1]
(lambda (next-node acc)
;; Generate some random number of edges of form `(,next-node ,o)
(append acc (map (lambda (_) `(,(string->symbol (format “n~a” next-node))
;; Take care to ensure we don’t include self-edges
,(string->symbol (format “n~a” (random-to-n-excluding n next-node)))))
;; Take care to ensure that each node links to one thing
(range (random 1 n)))))
‘()
(range n)))))
;; generate a random pagerank of a certain size
;; ensures that no two pagerank nodes have the same value
;; (useful for testing rank-pages)
(define (generate-random-pagerank n)
(define divisor 1000000)
(define expected-value (inexact->exact (round (* divisor (/ 1 n)))))
(define bottom (inexact->exact (round (/ expected-value 2))))
(define top (inexact->exact (round (+ expected-value (/ expected-value 2)))))
(define (iter sum lst)
(define next (/ (random bottom top) divisor))
;; Make sure not to repeat a number
(if (member next lst)
(iter sum lst)
(if (> (+ sum next) 1)
(cons (- 1 sum) lst)
(iter (+ next sum) (cons next lst)))))
(define l (iter 0 ‘()))
(foldl (lambda (i v acc) (hash-set acc (string->symbol (format “node~a” i)) v)) (hash) (range 0 (length l)) l))
test/public-backlinks/answer
test/public-backlinks/driver.py
test/public-backlinks/test.rkt
test/public-iteruntil/answer
test/public-iteruntil/driver.py
test/public-iteruntil/test.rkt
test/public-mkinit/answer
test/public-mkinit/driver.py
test/public-mkinit/test.rkt
test/public-numlinks/answer
test/public-numlinks/driver.py
test/public-numlinks/test.rkt
test/public-numpages/answer
test/public-numpages/driver.py
test/public-numpages/test.rkt
test/public-rankpages/answer
test/public-rankpages/driver.py
test/public-rankpages/test.rkt
test/public-step/answer
test/public-step/driver.py
test/public-step/test.rkt
test/public-sumtoone/answer
test/public-sumtoone/driver.py
test/public-sumtoone/test.rkt
#pagerank.rkt#
README.md
README.md~
pagerank.rkt
tester.py
testing-facilities.rkt