PageRank -------- Google uses a page ranking algorithm to determine the importance of each web page. The rank of a page is the probability that a particular random web surfer will be looking at the page at any given moment. Suppose we represent the web as a graph with N nodes, each representing a page, and with a directed edge representing each link from one page to another. The random surfer in question behaves as follows. The surfer chooses a first page randomly from among the N pages. To move from a current page to the next page, the surfer does the following. If the current page is the source of zero links, the surfer chooses the next page randomly from among the N pages of the web. Otherwise, with probability 1-ALPHA, the surfer does the same thing (as if the page sourced zero links), and with probability ALPHA, the surfer chooses a link sourced at the current page at random and follows that link. When choosing from among a set of pages or links at ran- dom the surfer gives equal probability to each page or link that might be chosen. So to choose at random from among the N pages of the web, each page has probability 1/N of being chosen. And to choose at random from among Q links sourced at the current page, each link has probability 1/Q of being chosen. You have been asked to compute the probability for each page that that page will be the K'th page visited by the surfer, for a given web graph and value of K. Input ----- For each of several test cases, first a line containing the name of the test case, and then a line containing N ALPHA K where N is the number of pages and K is the number of pages the surfer is to visit. After these two lines are N lines each containing a list of page numbers followed by a 0. Pages are numbered 1, 2, ..., N. The i'th of these lines contains the numbers of the pages targeted by links sourced at page i. So in the sample input below, node 1 has two links to node 2, node 2 has links to nodes 1, 2, and 3, and node 3 has zero links. Note that a node may have several links to the same target node and may have links to itself. 1 <= N <= 100; 0 <= ALPHA <= 1; 1 <= K <= 10,000. Input ends with an end of file. Output ------ For each test case, one line containing the name of the test case (copied exactly from the input), followed by N lines each containing a page number i followed by the probability the K'th page surfed will be page i. The page numbers must be in increasing order. The probabi- lities must be output with exactly 6 decimal places. Sample Input ------ ----- -- SAMPLE 1 -- 3 0.00 2 2 2 0 3 2 1 0 0 -- SAMPLE 2 -- 3 1.00 2 2 2 0 3 2 1 0 0 -- SAMPLE 3 -- 3 0.85 3 2 2 0 3 2 1 0 0 Sample Output ------ ------ -- SAMPLE 1 -- 1 0.333333 2 0.333333 3 0.333333 -- SAMPLE 2 -- 1 0.222222 2 0.555556 3 0.222222 -- SAMPLE 3 -- 1 0.265648 2 0.468704 3 0.265648 Reference: "PageRank: Standing on the Shoulders of Giants", by Massimo Franceschet, Communications of the ACM, Vol 54, No 6, June 2011, pp 92-101. File: pagerank.txt Author: Bob Walton Date: Sat Oct 6 03:26:45 EDT 2012 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2012/10/06 07:28:27 $ $RCSfile: pagerank.txt,v $ $Revision: 1.5 $