{"action":"created","comment":{"url":"https://api.github.com/repos/nitlang/nit/pulls/comments/40134573","id":40134573,"diff_hunk":"@@ -0,0 +1,84 @@\n+# This file is part of NIT (http://www.nitlanguage.org).\n+#\n+# Licensed under the Apache License, Version 2.0 (the \"License\");\n+# you may not use this file except in compliance with the License.\n+# You may obtain a copy of the License at\n+#\n+#     http://www.apache.org/licenses/LICENSE-2.0\n+#\n+# Unless required by applicable law or agreed to in writing, software\n+# distributed under the License is distributed on an \"AS IS\" BASIS,\n+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+# See the License for the specific language governing permissions and\n+# limitations under the License.\n+\n+# Add PageRank computation for vertices in Digraph.\n+module pagerank\n+\n+import graphs::digraph\n+\n+redef class Digraph[V]\n+\n+\t# Compute PageRank for each vertex\n+\t#\n+\t# Details of the algorithm can be found in:\n+\t# > L. Page, S. Brin, R. Motwani, and T.Winograd.\n+\t# > **The pagerank citation ranking: Bringing order to the web.**\n+\t# > *Technical report, Stanford Digital Library Technologies Project, 1998*\n+\t#\n+\t# Example:\n+\t# ~~~\n+\t# var g = new HashDigraph[String]\n+\t# g.add_arc(\"A\", \"B\")\n+\t# g.add_arc(\"A\", \"C\")\n+\t# g.add_arc(\"B\", \"C\")\n+\t# g.add_arc(\"C\", \"A\")\n+\t# g.add_arc(\"D\", \"C\")\n+\t#\n+\t# assert g.pagerank.join(\", \", \":\") == \"A:1.488, B:0.782, C:1.575, D:0.15\"\n+\t# ~~~\n+\tfun pagerank: PRMap[V] do\n+\t\t# `d` constant such as `initial_pagerank(node) == (1 - d) != 0`\n+\t\tvar d = 0.85 # commonly-choosen value\n+\t\t# Init each node page rank with an initial_value\n+\t\tvar values = new PRMap[V]\n+\t\tvar vertices = self.vertices\n+\t\tfor v in vertices do values[v] = 1.0 - d\n+\t\t# Compute page rank until convergence\n+\t\tvar prev = new PRMap[V]\n+\t\twhile values != prev do\n+\t\t\tprev = new PRMap[V].from(values)\n+\t\t\tfor v in vertices do\n+\t\t\t\tvar in_pr = 0.0\n+\t\t\t\tfor o in predecessors(v) do\n+\t\t\t\t\tin_pr += values[o] / out_degree(o).to_f\n+\t\t\t\tend\n+\t\t\t\tvalues[v] = (1.0 - d) + d * in_pr\n+\t\t\tend\n+\t\tend\n+\t\treturn values\n+\tend\n+end\n+\n+# Map each Vertice of a Digraph to it's PageRank.\n+#\n+# See: `Digraph::pagerank`.\n+class PRMap[V]\n+\tsuper HashMap[V, Float]\n+\n+\t# Init `self` by copying `other` values.\n+\tinit from(other: PRMap[V]) do\n+\t\tinit\n+\t\tfor k, v in other do self[k] = v\n+\tend\n+\n+\t# Equality is based on `Float::is_approx` with precision `0.001`.\n+\tredef fun ==(o) do\n+\t\tif not o isa SELF then return false\n+\t\tfor k1, v1 in self do\n+\t\t\tif not o.has_key(k1) then return false\n+\t\t\tif not 0.001.is_approx(v1, o[k1]) then return false","path":"lib/graphs/pagerank.nit","position":80,"original_position":80,"commit_id":"182cf091ed4df64eb9d60324be578a7bf41c911d","original_commit_id":"182cf091ed4df64eb9d60324be578a7bf41c911d","user":{"login":"privat","id":135828,"avatar_url":"https://avatars.githubusercontent.com/u/135828?v=3","gravatar_id":"","url":"https://api.github.com/users/privat","html_url":"https://github.com/privat","followers_url":"https://api.github.com/users/privat/followers","following_url":"https://api.github.com/users/privat/following{/other_user}","gists_url":"https://api.github.com/users/privat/gists{/gist_id}","starred_url":"https://api.github.com/users/privat/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/privat/subscriptions","organizations_url":"https://api.github.com/users/privat/orgs","repos_url":"https://api.github.com/users/privat/repos","events_url":"https://api.github.com/users/privat/events{/privacy}","received_events_url":"https://api.github.com/users/privat/received_events","type":"User","site_admin":false},"body":"If I remember correctly, the correct way is `v1.is_approx(o[k1], 0.001)` the precision is the last parameter. http://nitlanguage.org/doc/stdlib/class_core__kernel__Float.html#core__kernel__Float__is_approx.definition","created_at":"2015-09-22T19:46:58Z","updated_at":"2015-09-22T19:46:58Z","html_url":"https://github.com/nitlang/nit/pull/1706#discussion_r40134573","pull_request_url":"https://api.github.com/repos/nitlang/nit/pulls/1706","_links":{"self":{"href":"https://api.github.com/repos/nitlang/nit/pulls/comments/40134573"},"html":{"href":"https://github.com/nitlang/nit/pull/1706#discussion_r40134573"},"pull_request":{"href":"https://api.github.com/repos/nitlang/nit/pulls/1706"}}},"pull_request":{"url":"https://api.github.com/repos/nitlang/nit/pulls/1706","id":44804345,"html_url":"https://github.com/nitlang/nit/pull/1706","diff_url":"https://github.com/nitlang/nit/pull/1706.diff","patch_url":"https://github.com/nitlang/nit/pull/1706.patch","issue_url":"https://api.github.com/repos/nitlang/nit/issues/1706","number":1706,"state":"open","locked":false,"title":"lib/graphs: introduce PageRank computation on digraphs","user":{"login":"Morriar","id":583144,"avatar_url":"https://avatars.githubusercontent.com/u/583144?v=3","gravatar_id":"","url":"https://api.github.com/users/Morriar","html_url":"https://github.com/Morriar","followers_url":"https://api.github.com/users/Morriar/followers","following_url":"https://api.github.com/users/Morriar/following{/other_user}","gists_url":"https://api.github.com/users/Morriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Morriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Morriar/subscriptions","organizations_url":"https://api.github.com/users/Morriar/orgs","repos_url":"https://api.github.com/users/Morriar/repos","events_url":"https://api.github.com/users/Morriar/events{/privacy}","received_events_url":"https://api.github.com/users/Morriar/received_events","type":"User","site_admin":false},"body":"Implement famous Google's `PageRank` algorithm for directed graphs.\r\n\r\nPing @ablondin ","created_at":"2015-09-11T16:50:53Z","updated_at":"2015-09-22T19:46:58Z","closed_at":null,"merged_at":null,"merge_commit_sha":"6be2acfaf81edce16d6adf69adb94035cfdca4df","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/nitlang/nit/pulls/1706/commits","review_comments_url":"https://api.github.com/repos/nitlang/nit/pulls/1706/comments","review_comment_url":"https://api.github.com/repos/nitlang/nit/pulls/comments{/number}","comments_url":"https://api.github.com/repos/nitlang/nit/issues/1706/comments","statuses_url":"https://api.github.com/repos/nitlang/nit/statuses/182cf091ed4df64eb9d60324be578a7bf41c911d","head":{"label":"Morriar:pagerank","ref":"pagerank","sha":"182cf091ed4df64eb9d60324be578a7bf41c911d","user":{"login":"Morriar","id":583144,"avatar_url":"https://avatars.githubusercontent.com/u/583144?v=3","gravatar_id":"","url":"https://api.github.com/users/Morriar","html_url":"https://github.com/Morriar","followers_url":"https://api.github.com/users/Morriar/followers","following_url":"https://api.github.com/users/Morriar/following{/other_user}","gists_url":"https://api.github.com/users/Morriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Morriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Morriar/subscriptions","organizations_url":"https://api.github.com/users/Morriar/orgs","repos_url":"https://api.github.com/users/Morriar/repos","events_url":"https://api.github.com/users/Morriar/events{/privacy}","received_events_url":"https://api.github.com/users/Morriar/received_events","type":"User","site_admin":false},"repo":{"id":1456691,"name":"nit","full_name":"Morriar/nit","owner":{"login":"Morriar","id":583144,"avatar_url":"https://avatars.githubusercontent.com/u/583144?v=3","gravatar_id":"","url":"https://api.github.com/users/Morriar","html_url":"https://github.com/Morriar","followers_url":"https://api.github.com/users/Morriar/followers","following_url":"https://api.github.com/users/Morriar/following{/other_user}","gists_url":"https://api.github.com/users/Morriar/gists{/gist_id}","starred_url":"https://api.github.com/users/Morriar/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Morriar/subscriptions","organizations_url":"https://api.github.com/users/Morriar/orgs","repos_url":"https://api.github.com/users/Morriar/repos","events_url":"https://api.github.com/users/Morriar/events{/privacy}","received_events_url":"https://api.github.com/users/Morriar/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/Morriar/nit","description":"Nit language","fork":true,"url":"https://api.github.com/repos/Morriar/nit","forks_url":"https://api.github.com/repos/Morriar/nit/forks","keys_url":"https://api.github.com/repos/Morriar/nit/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Morriar/nit/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Morriar/nit/teams","hooks_url":"https://api.github.com/repos/Morriar/nit/hooks","issue_events_url":"https://api.github.com/repos/Morriar/nit/issues/events{/number}","events_url":"https://api.github.com/repos/Morriar/nit/events","assignees_url":"https://api.github.com/repos/Morriar/nit/assignees{/user}","branches_url":"https://api.github.com/repos/Morriar/nit/branches{/branch}","tags_url":"https://api.github.com/repos/Morriar/nit/tags","blobs_url":"https://api.github.com/repos/Morriar/nit/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Morriar/nit/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Morriar/nit/git/refs{/sha}","trees_url":"https://api.github.com/repos/Morriar/nit/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Morriar/nit/statuses/{sha}","languages_url":"https://api.github.com/repos/Morriar/nit/languages","stargazers_url":"https://api.github.com/repos/Morriar/nit/stargazers","contributors_url":"https://api.github.com/repos/Morriar/nit/contributors","subscribers_url":"https://api.github.com/repos/Morriar/nit/subscribers","subscription_url":"https://api.github.com/repos/Morriar/nit/subscription","commits_url":"https://api.github.com/repos/Morriar/nit/commits{/sha}","git_commits_url":"https://api.github.com/repos/Morriar/nit/git/commits{/sha}","comments_url":"https://api.github.com/repos/Morriar/nit/comments{/number}","issue_comment_url":"https://api.github.com/repos/Morriar/nit/issues/comments{/number}","contents_url":"https://api.github.com/repos/Morriar/nit/contents/{+path}","compare_url":"https://api.github.com/repos/Morriar/nit/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Morriar/nit/merges","archive_url":"https://api.github.com/repos/Morriar/nit/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Morriar/nit/downloads","issues_url":"https://api.github.com/repos/Morriar/nit/issues{/number}","pulls_url":"https://api.github.com/repos/Morriar/nit/pulls{/number}","milestones_url":"https://api.github.com/repos/Morriar/nit/milestones{/number}","notifications_url":"https://api.github.com/repos/Morriar/nit/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Morriar/nit/labels{/name}","releases_url":"https://api.github.com/repos/Morriar/nit/releases{/id}","created_at":"2011-03-08T22:16:33Z","updated_at":"2015-06-06T03:02:03Z","pushed_at":"2015-09-11T16:52:08Z","git_url":"git://github.com/Morriar/nit.git","ssh_url":"git@github.com:Morriar/nit.git","clone_url":"https://github.com/Morriar/nit.git","svn_url":"https://github.com/Morriar/nit","homepage":"http://nitlanguage.org","size":72689,"stargazers_count":3,"watchers_count":3,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":2,"mirror_url":null,"open_issues_count":16,"forks":2,"open_issues":16,"watchers":3,"default_branch":"master"}},"base":{"label":"nitlang:master","ref":"master","sha":"feea1e8bcb1e0f48b0c838569b6eed9a9d97c255","user":{"login":"nitlang","id":5420298,"avatar_url":"https://avatars.githubusercontent.com/u/5420298?v=3","gravatar_id":"","url":"https://api.github.com/users/nitlang","html_url":"https://github.com/nitlang","followers_url":"https://api.github.com/users/nitlang/followers","following_url":"https://api.github.com/users/nitlang/following{/other_user}","gists_url":"https://api.github.com/users/nitlang/gists{/gist_id}","starred_url":"https://api.github.com/users/nitlang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nitlang/subscriptions","organizations_url":"https://api.github.com/users/nitlang/orgs","repos_url":"https://api.github.com/users/nitlang/repos","events_url":"https://api.github.com/users/nitlang/events{/privacy}","received_events_url":"https://api.github.com/users/nitlang/received_events","type":"Organization","site_admin":false},"repo":{"id":328597,"name":"nit","full_name":"nitlang/nit","owner":{"login":"nitlang","id":5420298,"avatar_url":"https://avatars.githubusercontent.com/u/5420298?v=3","gravatar_id":"","url":"https://api.github.com/users/nitlang","html_url":"https://github.com/nitlang","followers_url":"https://api.github.com/users/nitlang/followers","following_url":"https://api.github.com/users/nitlang/following{/other_user}","gists_url":"https://api.github.com/users/nitlang/gists{/gist_id}","starred_url":"https://api.github.com/users/nitlang/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nitlang/subscriptions","organizations_url":"https://api.github.com/users/nitlang/orgs","repos_url":"https://api.github.com/users/nitlang/repos","events_url":"https://api.github.com/users/nitlang/events{/privacy}","received_events_url":"https://api.github.com/users/nitlang/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/nitlang/nit","description":"Nit language","fork":false,"url":"https://api.github.com/repos/nitlang/nit","forks_url":"https://api.github.com/repos/nitlang/nit/forks","keys_url":"https://api.github.com/repos/nitlang/nit/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nitlang/nit/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nitlang/nit/teams","hooks_url":"https://api.github.com/repos/nitlang/nit/hooks","issue_events_url":"https://api.github.com/repos/nitlang/nit/issues/events{/number}","events_url":"https://api.github.com/repos/nitlang/nit/events","assignees_url":"https://api.github.com/repos/nitlang/nit/assignees{/user}","branches_url":"https://api.github.com/repos/nitlang/nit/branches{/branch}","tags_url":"https://api.github.com/repos/nitlang/nit/tags","blobs_url":"https://api.github.com/repos/nitlang/nit/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nitlang/nit/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nitlang/nit/git/refs{/sha}","trees_url":"https://api.github.com/repos/nitlang/nit/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nitlang/nit/statuses/{sha}","languages_url":"https://api.github.com/repos/nitlang/nit/languages","stargazers_url":"https://api.github.com/repos/nitlang/nit/stargazers","contributors_url":"https://api.github.com/repos/nitlang/nit/contributors","subscribers_url":"https://api.github.com/repos/nitlang/nit/subscribers","subscription_url":"https://api.github.com/repos/nitlang/nit/subscription","commits_url":"https://api.github.com/repos/nitlang/nit/commits{/sha}","git_commits_url":"https://api.github.com/repos/nitlang/nit/git/commits{/sha}","comments_url":"https://api.github.com/repos/nitlang/nit/comments{/number}","issue_comment_url":"https://api.github.com/repos/nitlang/nit/issues/comments{/number}","contents_url":"https://api.github.com/repos/nitlang/nit/contents/{+path}","compare_url":"https://api.github.com/repos/nitlang/nit/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nitlang/nit/merges","archive_url":"https://api.github.com/repos/nitlang/nit/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nitlang/nit/downloads","issues_url":"https://api.github.com/repos/nitlang/nit/issues{/number}","pulls_url":"https://api.github.com/repos/nitlang/nit/pulls{/number}","milestones_url":"https://api.github.com/repos/nitlang/nit/milestones{/number}","notifications_url":"https://api.github.com/repos/nitlang/nit/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nitlang/nit/labels{/name}","releases_url":"https://api.github.com/repos/nitlang/nit/releases{/id}","created_at":"2009-10-06T15:03:00Z","updated_at":"2015-09-10T13:33:12Z","pushed_at":"2015-09-22T19:42:14Z","git_url":"git://github.com/nitlang/nit.git","ssh_url":"git@github.com:nitlang/nit.git","clone_url":"https://github.com/nitlang/nit.git","svn_url":"https://github.com/nitlang/nit","homepage":"http://nitlanguage.org","size":99645,"stargazers_count":78,"watchers_count":78,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":44,"mirror_url":null,"open_issues_count":120,"forks":44,"open_issues":120,"watchers":78,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/nitlang/nit/pulls/1706"},"html":{"href":"https://github.com/nitlang/nit/pull/1706"},"issue":{"href":"https://api.github.com/repos/nitlang/nit/issues/1706"},"comments":{"href":"https://api.github.com/repos/nitlang/nit/issues/1706/comments"},"review_comments":{"href":"https://api.github.com/repos/nitlang/nit/pulls/1706/comments"},"review_comment":{"href":"https://api.github.com/repos/nitlang/nit/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/nitlang/nit/pulls/1706/commits"},"statuses":{"href":"https://api.github.com/repos/nitlang/nit/statuses/182cf091ed4df64eb9d60324be578a7bf41c911d"}}}}