{"action":"created","comment":{"url":"https://api.github.com/repos/pgRouting/pgrouting/pulls/comments/54257513","id":54257513,"diff_hunk":"@@ -0,0 +1,227 @@\n+.. _contraction:\n+\n+Contraction\n+===============================================================================\n+\n+The documentation provides explanation on graph contraction.\n+\n+*level 1* vertices have only one incoming edge.\n+*level 2* vertices have one incoming edge and one outgoing edge.\n+\n+Notations\n+===============================================================================\n+\n+* V: is the set of vertices\n+* E: is the set of edges\n+* G: is the graph\n+* :math:`L1_v`: is the set of *level 1* vertices \n+* :math:`L2_v`: is the set of *level 2* vertices\n+* removed_vertices: is the set of removed vertices\n+\n+The contracted graph will be represented with two parameters, the modified Graph, and the removed_vertices set.\n+\n+\n+removed_vertices = {(v,1):{2}, (e,-1):{3}}.\n+\n+\n+The above notation indicates:\n+vertex 2 is removed, and belongs to vertex 1 subgraph\n+vertex 3 is removed, and belongs to edge -1 subgraph\n+\n+\n+\n+Procedure\n+===============================================================================\n+\n+For contracting, we are going to cycle as follows\n+\n+.. code-block:: none\n+\n+\n+    do N times {\n+\n+    repeat {\n+\n+    < work with level 1 vertices >\n+\n+    until L1_v is empty\n+\n+    }\n+\n+    repeat {\n+\n+    < work with level 2 vertices >\n+\n+    until L2_v is empty\n+\n+    }\n+\n+    }\n+\n+For simplicity all the edges in the examples have unit weight.\n+\n+\n+Examples\n+===============================================================================\n+\n+.. _fig1:","path":"src/contraction/doc/contraction.rst","position":67,"original_position":67,"commit_id":"3634feac1a9b0d43893d33ad3a855006b58de26f","original_commit_id":"3634feac1a9b0d43893d33ad3a855006b58de26f","user":{"login":"cvvergara","id":5035290,"avatar_url":"https://avatars.githubusercontent.com/u/5035290?v=3","gravatar_id":"","url":"https://api.github.com/users/cvvergara","html_url":"https://github.com/cvvergara","followers_url":"https://api.github.com/users/cvvergara/followers","following_url":"https://api.github.com/users/cvvergara/following{/other_user}","gists_url":"https://api.github.com/users/cvvergara/gists{/gist_id}","starred_url":"https://api.github.com/users/cvvergara/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cvvergara/subscriptions","organizations_url":"https://api.github.com/users/cvvergara/orgs","repos_url":"https://api.github.com/users/cvvergara/repos","events_url":"https://api.github.com/users/cvvergara/events{/privacy}","received_events_url":"https://api.github.com/users/cvvergara/received_events","type":"User","site_admin":false},"body":"Example 1: One edge\r\n++++++++++++++++++++","created_at":"2016-02-26T15:31:52Z","updated_at":"2016-02-26T15:31:52Z","html_url":"https://github.com/pgRouting/pgrouting/pull/503#discussion_r54257513","pull_request_url":"https://api.github.com/repos/pgRouting/pgrouting/pulls/503","_links":{"self":{"href":"https://api.github.com/repos/pgRouting/pgrouting/pulls/comments/54257513"},"html":{"href":"https://github.com/pgRouting/pgrouting/pull/503#discussion_r54257513"},"pull_request":{"href":"https://api.github.com/repos/pgRouting/pgrouting/pulls/503"}}},"pull_request":{"url":"https://api.github.com/repos/pgRouting/pgrouting/pulls/503","id":60857508,"html_url":"https://github.com/pgRouting/pgrouting/pull/503","diff_url":"https://github.com/pgRouting/pgrouting/pull/503.diff","patch_url":"https://github.com/pgRouting/pgrouting/pull/503.patch","issue_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/503","number":503,"state":"open","locked":false,"title":"Dev 2.2 contract doc","user":{"login":"sankepallyrohithreddy","id":2110492,"avatar_url":"https://avatars.githubusercontent.com/u/2110492?v=3","gravatar_id":"","url":"https://api.github.com/users/sankepallyrohithreddy","html_url":"https://github.com/sankepallyrohithreddy","followers_url":"https://api.github.com/users/sankepallyrohithreddy/followers","following_url":"https://api.github.com/users/sankepallyrohithreddy/following{/other_user}","gists_url":"https://api.github.com/users/sankepallyrohithreddy/gists{/gist_id}","starred_url":"https://api.github.com/users/sankepallyrohithreddy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sankepallyrohithreddy/subscriptions","organizations_url":"https://api.github.com/users/sankepallyrohithreddy/orgs","repos_url":"https://api.github.com/users/sankepallyrohithreddy/repos","events_url":"https://api.github.com/users/sankepallyrohithreddy/events{/privacy}","received_events_url":"https://api.github.com/users/sankepallyrohithreddy/received_events","type":"User","site_admin":false},"body":"Fixes # .\r\n\r\nChanges proposed in this pull request:\r\n-\r\n-\r\n-\r\n\r\n@pgRouting/admins\r\n","created_at":"2016-02-26T15:26:58Z","updated_at":"2016-02-26T15:31:52Z","closed_at":null,"merged_at":null,"merge_commit_sha":"5890ca42d82c7ee92eae1241a519d816eae9bee4","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/pgRouting/pgrouting/pulls/503/commits","review_comments_url":"https://api.github.com/repos/pgRouting/pgrouting/pulls/503/comments","review_comment_url":"https://api.github.com/repos/pgRouting/pgrouting/pulls/comments{/number}","comments_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/503/comments","statuses_url":"https://api.github.com/repos/pgRouting/pgrouting/statuses/3634feac1a9b0d43893d33ad3a855006b58de26f","head":{"label":"sankepallyrohithreddy:dev-2.2-contract-doc","ref":"dev-2.2-contract-doc","sha":"3634feac1a9b0d43893d33ad3a855006b58de26f","user":{"login":"sankepallyrohithreddy","id":2110492,"avatar_url":"https://avatars.githubusercontent.com/u/2110492?v=3","gravatar_id":"","url":"https://api.github.com/users/sankepallyrohithreddy","html_url":"https://github.com/sankepallyrohithreddy","followers_url":"https://api.github.com/users/sankepallyrohithreddy/followers","following_url":"https://api.github.com/users/sankepallyrohithreddy/following{/other_user}","gists_url":"https://api.github.com/users/sankepallyrohithreddy/gists{/gist_id}","starred_url":"https://api.github.com/users/sankepallyrohithreddy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sankepallyrohithreddy/subscriptions","organizations_url":"https://api.github.com/users/sankepallyrohithreddy/orgs","repos_url":"https://api.github.com/users/sankepallyrohithreddy/repos","events_url":"https://api.github.com/users/sankepallyrohithreddy/events{/privacy}","received_events_url":"https://api.github.com/users/sankepallyrohithreddy/received_events","type":"User","site_admin":false},"repo":{"id":47807821,"name":"pgrouting","full_name":"sankepallyrohithreddy/pgrouting","owner":{"login":"sankepallyrohithreddy","id":2110492,"avatar_url":"https://avatars.githubusercontent.com/u/2110492?v=3","gravatar_id":"","url":"https://api.github.com/users/sankepallyrohithreddy","html_url":"https://github.com/sankepallyrohithreddy","followers_url":"https://api.github.com/users/sankepallyrohithreddy/followers","following_url":"https://api.github.com/users/sankepallyrohithreddy/following{/other_user}","gists_url":"https://api.github.com/users/sankepallyrohithreddy/gists{/gist_id}","starred_url":"https://api.github.com/users/sankepallyrohithreddy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sankepallyrohithreddy/subscriptions","organizations_url":"https://api.github.com/users/sankepallyrohithreddy/orgs","repos_url":"https://api.github.com/users/sankepallyrohithreddy/repos","events_url":"https://api.github.com/users/sankepallyrohithreddy/events{/privacy}","received_events_url":"https://api.github.com/users/sankepallyrohithreddy/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/sankepallyrohithreddy/pgrouting","description":"Repository contains pgRouting library. Development branch is \"develop\", stable branch is \"master\"","fork":true,"url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting","forks_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/forks","keys_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/keys{/key_id}","collaborators_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/teams","hooks_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/hooks","issue_events_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/issues/events{/number}","events_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/events","assignees_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/assignees{/user}","branches_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/branches{/branch}","tags_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/tags","blobs_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/git/refs{/sha}","trees_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/git/trees{/sha}","statuses_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/statuses/{sha}","languages_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/languages","stargazers_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/stargazers","contributors_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/contributors","subscribers_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/subscribers","subscription_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/subscription","commits_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/commits{/sha}","git_commits_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/git/commits{/sha}","comments_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/comments{/number}","issue_comment_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/issues/comments{/number}","contents_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/contents/{+path}","compare_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/compare/{base}...{head}","merges_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/merges","archive_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/downloads","issues_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/issues{/number}","pulls_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/pulls{/number}","milestones_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/milestones{/number}","notifications_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/labels{/name}","releases_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/releases{/id}","deployments_url":"https://api.github.com/repos/sankepallyrohithreddy/pgrouting/deployments","created_at":"2015-12-11T05:47:40Z","updated_at":"2015-12-11T05:47:42Z","pushed_at":"2016-02-26T15:12:50Z","git_url":"git://github.com/sankepallyrohithreddy/pgrouting.git","ssh_url":"git@github.com:sankepallyrohithreddy/pgrouting.git","clone_url":"https://github.com/sankepallyrohithreddy/pgrouting.git","svn_url":"https://github.com/sankepallyrohithreddy/pgrouting","homepage":"http://www.pgrouting.org","size":55501,"stargazers_count":0,"watchers_count":0,"language":"C","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"pgRouting:dev-2.2-contract-doc","ref":"dev-2.2-contract-doc","sha":"ecfdefbd96c9e87c177de4167057cd59a732558a","user":{"login":"pgRouting","id":324933,"avatar_url":"https://avatars.githubusercontent.com/u/324933?v=3","gravatar_id":"","url":"https://api.github.com/users/pgRouting","html_url":"https://github.com/pgRouting","followers_url":"https://api.github.com/users/pgRouting/followers","following_url":"https://api.github.com/users/pgRouting/following{/other_user}","gists_url":"https://api.github.com/users/pgRouting/gists{/gist_id}","starred_url":"https://api.github.com/users/pgRouting/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pgRouting/subscriptions","organizations_url":"https://api.github.com/users/pgRouting/orgs","repos_url":"https://api.github.com/users/pgRouting/repos","events_url":"https://api.github.com/users/pgRouting/events{/privacy}","received_events_url":"https://api.github.com/users/pgRouting/received_events","type":"Organization","site_admin":false},"repo":{"id":1050245,"name":"pgrouting","full_name":"pgRouting/pgrouting","owner":{"login":"pgRouting","id":324933,"avatar_url":"https://avatars.githubusercontent.com/u/324933?v=3","gravatar_id":"","url":"https://api.github.com/users/pgRouting","html_url":"https://github.com/pgRouting","followers_url":"https://api.github.com/users/pgRouting/followers","following_url":"https://api.github.com/users/pgRouting/following{/other_user}","gists_url":"https://api.github.com/users/pgRouting/gists{/gist_id}","starred_url":"https://api.github.com/users/pgRouting/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pgRouting/subscriptions","organizations_url":"https://api.github.com/users/pgRouting/orgs","repos_url":"https://api.github.com/users/pgRouting/repos","events_url":"https://api.github.com/users/pgRouting/events{/privacy}","received_events_url":"https://api.github.com/users/pgRouting/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/pgRouting/pgrouting","description":"Repository contains pgRouting library. Development branch is \"develop\", stable branch is \"master\"","fork":false,"url":"https://api.github.com/repos/pgRouting/pgrouting","forks_url":"https://api.github.com/repos/pgRouting/pgrouting/forks","keys_url":"https://api.github.com/repos/pgRouting/pgrouting/keys{/key_id}","collaborators_url":"https://api.github.com/repos/pgRouting/pgrouting/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/pgRouting/pgrouting/teams","hooks_url":"https://api.github.com/repos/pgRouting/pgrouting/hooks","issue_events_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/events{/number}","events_url":"https://api.github.com/repos/pgRouting/pgrouting/events","assignees_url":"https://api.github.com/repos/pgRouting/pgrouting/assignees{/user}","branches_url":"https://api.github.com/repos/pgRouting/pgrouting/branches{/branch}","tags_url":"https://api.github.com/repos/pgRouting/pgrouting/tags","blobs_url":"https://api.github.com/repos/pgRouting/pgrouting/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/pgRouting/pgrouting/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/pgRouting/pgrouting/git/refs{/sha}","trees_url":"https://api.github.com/repos/pgRouting/pgrouting/git/trees{/sha}","statuses_url":"https://api.github.com/repos/pgRouting/pgrouting/statuses/{sha}","languages_url":"https://api.github.com/repos/pgRouting/pgrouting/languages","stargazers_url":"https://api.github.com/repos/pgRouting/pgrouting/stargazers","contributors_url":"https://api.github.com/repos/pgRouting/pgrouting/contributors","subscribers_url":"https://api.github.com/repos/pgRouting/pgrouting/subscribers","subscription_url":"https://api.github.com/repos/pgRouting/pgrouting/subscription","commits_url":"https://api.github.com/repos/pgRouting/pgrouting/commits{/sha}","git_commits_url":"https://api.github.com/repos/pgRouting/pgrouting/git/commits{/sha}","comments_url":"https://api.github.com/repos/pgRouting/pgrouting/comments{/number}","issue_comment_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/comments{/number}","contents_url":"https://api.github.com/repos/pgRouting/pgrouting/contents/{+path}","compare_url":"https://api.github.com/repos/pgRouting/pgrouting/compare/{base}...{head}","merges_url":"https://api.github.com/repos/pgRouting/pgrouting/merges","archive_url":"https://api.github.com/repos/pgRouting/pgrouting/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/pgRouting/pgrouting/downloads","issues_url":"https://api.github.com/repos/pgRouting/pgrouting/issues{/number}","pulls_url":"https://api.github.com/repos/pgRouting/pgrouting/pulls{/number}","milestones_url":"https://api.github.com/repos/pgRouting/pgrouting/milestones{/number}","notifications_url":"https://api.github.com/repos/pgRouting/pgrouting/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/pgRouting/pgrouting/labels{/name}","releases_url":"https://api.github.com/repos/pgRouting/pgrouting/releases{/id}","deployments_url":"https://api.github.com/repos/pgRouting/pgrouting/deployments","created_at":"2010-11-04T05:31:16Z","updated_at":"2016-02-20T03:57:36Z","pushed_at":"2016-02-26T15:26:58Z","git_url":"git://github.com/pgRouting/pgrouting.git","ssh_url":"git@github.com:pgRouting/pgrouting.git","clone_url":"https://github.com/pgRouting/pgrouting.git","svn_url":"https://github.com/pgRouting/pgrouting","homepage":"http://www.pgrouting.org","size":57943,"stargazers_count":276,"watchers_count":276,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":137,"mirror_url":null,"open_issues_count":90,"forks":137,"open_issues":90,"watchers":276,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/pgRouting/pgrouting/pulls/503"},"html":{"href":"https://github.com/pgRouting/pgrouting/pull/503"},"issue":{"href":"https://api.github.com/repos/pgRouting/pgrouting/issues/503"},"comments":{"href":"https://api.github.com/repos/pgRouting/pgrouting/issues/503/comments"},"review_comments":{"href":"https://api.github.com/repos/pgRouting/pgrouting/pulls/503/comments"},"review_comment":{"href":"https://api.github.com/repos/pgRouting/pgrouting/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/pgRouting/pgrouting/pulls/503/commits"},"statuses":{"href":"https://api.github.com/repos/pgRouting/pgrouting/statuses/3634feac1a9b0d43893d33ad3a855006b58de26f"}}}}