{"action":"created","comment":{"url":"https://api.github.com/repos/networkx/networkx/pulls/comments/31135750","id":31135750,"diff_hunk":"@@ -0,0 +1,299 @@\n+\"\"\"\n+================================\n+Travelling Salesman Problem (TSP)\n+================================\n+\n+Implementation of heuristic and metaheuristic algorithms\n+for solving and approximating the TSP problem.\n+\n+Categories of algorithms which are implemented:\n+- Greedy\n+- Simulated Annealing (SA)\n+\n+Travelling Salesman Problem tries to find, given the weight\n+(distance) between all points where salesman has to visit, the\n+route so that:\n+- Total distance (cost) which salesman travels to be minimized.\n+- Salesman has to return to the point where he stated.\n+- Salesman has to visit each point only once apart fom source\n+point.\n+\n+It is an NP-hard problem in combinatorial optimization,\n+important in operations research and theoretical computer science.\n+\n+http://en.wikipedia.org/wiki/Travelling_salesman_problem\n+\"\"\"\n+from __future__ import division\n+import math\n+from random import choice, randint, random\n+import networkx as nx\n+import itertools\n+\n+__all__ = ['greedy_tsp', 'simulated_annealing_tsp']\n+\n+\n+def greedy_tsp(G, source, weight='weight'):","path":"networkx/algorithms/tsp.py","position":35,"original_position":35,"commit_id":"562cd359ad429d6321ee8837cdfd6890e80d0799","original_commit_id":"562cd359ad429d6321ee8837cdfd6890e80d0799","user":{"login":"jfinkels","id":121755,"avatar_url":"https://avatars.githubusercontent.com/u/121755?v=3","gravatar_id":"","url":"https://api.github.com/users/jfinkels","html_url":"https://github.com/jfinkels","followers_url":"https://api.github.com/users/jfinkels/followers","following_url":"https://api.github.com/users/jfinkels/following{/other_user}","gists_url":"https://api.github.com/users/jfinkels/gists{/gist_id}","starred_url":"https://api.github.com/users/jfinkels/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jfinkels/subscriptions","organizations_url":"https://api.github.com/users/jfinkels/orgs","repos_url":"https://api.github.com/users/jfinkels/repos","events_url":"https://api.github.com/users/jfinkels/events{/privacy}","received_events_url":"https://api.github.com/users/jfinkels/received_events","type":"User","site_admin":false},"body":"Algorithms like this should have their worst-case time complexity documented.","created_at":"2015-05-27T14:01:27Z","updated_at":"2015-05-27T14:01:27Z","html_url":"https://github.com/networkx/networkx/pull/1508#discussion_r31135750","pull_request_url":"https://api.github.com/repos/networkx/networkx/pulls/1508","_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments/31135750"},"html":{"href":"https://github.com/networkx/networkx/pull/1508#discussion_r31135750"},"pull_request":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1508"}}},"pull_request":{"url":"https://api.github.com/repos/networkx/networkx/pulls/1508","id":34804001,"html_url":"https://github.com/networkx/networkx/pull/1508","diff_url":"https://github.com/networkx/networkx/pull/1508.diff","patch_url":"https://github.com/networkx/networkx/pull/1508.patch","issue_url":"https://api.github.com/repos/networkx/networkx/issues/1508","number":1508,"state":"open","locked":false,"title":"Algorithms for solving Travelling Salesman Problem (TSP)","user":{"login":"theosotr","id":6434138,"avatar_url":"https://avatars.githubusercontent.com/u/6434138?v=3","gravatar_id":"","url":"https://api.github.com/users/theosotr","html_url":"https://github.com/theosotr","followers_url":"https://api.github.com/users/theosotr/followers","following_url":"https://api.github.com/users/theosotr/following{/other_user}","gists_url":"https://api.github.com/users/theosotr/gists{/gist_id}","starred_url":"https://api.github.com/users/theosotr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/theosotr/subscriptions","organizations_url":"https://api.github.com/users/theosotr/orgs","repos_url":"https://api.github.com/users/theosotr/repos","events_url":"https://api.github.com/users/theosotr/events{/privacy}","received_events_url":"https://api.github.com/users/theosotr/received_events","type":"User","site_admin":false},"body":"This pull request implements some algorithms for solving a Combinatorial Optimization Problem.\r\nFor more information see: [(https://github.com/networkx/networkx/issues/1507)]\r\nOne of the most famous Combinatorial Optimization Problem is Travelling Salesman Problem\r\n\r\nTravelling Salesman Problem tries to find, given the weight (distance) between all points where salesman has to visit, the route so that:\r\n- Total distance (cost) which salesman travels to be minimized.\r\n- Salesman has to return to the point where he started.\r\n- Salesman has to visit each point only once apart fom source point.\r\n\r\nIn terms of graph, solution of TSP is the Hamiltonian circuit with the minimum cost.\r\nThere are a lot of heuristic, metahuristic, artificial intelligence algorithms for solving TSP. This pull request implements a simple greedy algorithm for constructing a initial solution of TSP, and Simulated Annealing; an iteration improvement algorithm which tries to improve a current solution in each iteration.\r\n\r\nWe intend to implement more algorithms for that purpose, but we would like to get some feedback about our code.","created_at":"2015-05-06T10:15:24Z","updated_at":"2015-05-27T14:01:27Z","closed_at":null,"merged_at":null,"merge_commit_sha":"e0efca8f357641aaca42feeee4c3eff520bf68a8","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/networkx/networkx/pulls/1508/commits","review_comments_url":"https://api.github.com/repos/networkx/networkx/pulls/1508/comments","review_comment_url":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}","comments_url":"https://api.github.com/repos/networkx/networkx/issues/1508/comments","statuses_url":"https://api.github.com/repos/networkx/networkx/statuses/562cd359ad429d6321ee8837cdfd6890e80d0799","head":{"label":"Overriders:TSP","ref":"TSP","sha":"562cd359ad429d6321ee8837cdfd6890e80d0799","user":{"login":"Overriders","id":11508766,"avatar_url":"https://avatars.githubusercontent.com/u/11508766?v=3","gravatar_id":"","url":"https://api.github.com/users/Overriders","html_url":"https://github.com/Overriders","followers_url":"https://api.github.com/users/Overriders/followers","following_url":"https://api.github.com/users/Overriders/following{/other_user}","gists_url":"https://api.github.com/users/Overriders/gists{/gist_id}","starred_url":"https://api.github.com/users/Overriders/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Overriders/subscriptions","organizations_url":"https://api.github.com/users/Overriders/orgs","repos_url":"https://api.github.com/users/Overriders/repos","events_url":"https://api.github.com/users/Overriders/events{/privacy}","received_events_url":"https://api.github.com/users/Overriders/received_events","type":"Organization","site_admin":false},"repo":{"id":32471655,"name":"networkx","full_name":"Overriders/networkx","owner":{"login":"Overriders","id":11508766,"avatar_url":"https://avatars.githubusercontent.com/u/11508766?v=3","gravatar_id":"","url":"https://api.github.com/users/Overriders","html_url":"https://github.com/Overriders","followers_url":"https://api.github.com/users/Overriders/followers","following_url":"https://api.github.com/users/Overriders/following{/other_user}","gists_url":"https://api.github.com/users/Overriders/gists{/gist_id}","starred_url":"https://api.github.com/users/Overriders/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Overriders/subscriptions","organizations_url":"https://api.github.com/users/Overriders/orgs","repos_url":"https://api.github.com/users/Overriders/repos","events_url":"https://api.github.com/users/Overriders/events{/privacy}","received_events_url":"https://api.github.com/users/Overriders/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/Overriders/networkx","description":"Official NetworkX source code repository.  ","fork":true,"url":"https://api.github.com/repos/Overriders/networkx","forks_url":"https://api.github.com/repos/Overriders/networkx/forks","keys_url":"https://api.github.com/repos/Overriders/networkx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/Overriders/networkx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/Overriders/networkx/teams","hooks_url":"https://api.github.com/repos/Overriders/networkx/hooks","issue_events_url":"https://api.github.com/repos/Overriders/networkx/issues/events{/number}","events_url":"https://api.github.com/repos/Overriders/networkx/events","assignees_url":"https://api.github.com/repos/Overriders/networkx/assignees{/user}","branches_url":"https://api.github.com/repos/Overriders/networkx/branches{/branch}","tags_url":"https://api.github.com/repos/Overriders/networkx/tags","blobs_url":"https://api.github.com/repos/Overriders/networkx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/Overriders/networkx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/Overriders/networkx/git/refs{/sha}","trees_url":"https://api.github.com/repos/Overriders/networkx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/Overriders/networkx/statuses/{sha}","languages_url":"https://api.github.com/repos/Overriders/networkx/languages","stargazers_url":"https://api.github.com/repos/Overriders/networkx/stargazers","contributors_url":"https://api.github.com/repos/Overriders/networkx/contributors","subscribers_url":"https://api.github.com/repos/Overriders/networkx/subscribers","subscription_url":"https://api.github.com/repos/Overriders/networkx/subscription","commits_url":"https://api.github.com/repos/Overriders/networkx/commits{/sha}","git_commits_url":"https://api.github.com/repos/Overriders/networkx/git/commits{/sha}","comments_url":"https://api.github.com/repos/Overriders/networkx/comments{/number}","issue_comment_url":"https://api.github.com/repos/Overriders/networkx/issues/comments{/number}","contents_url":"https://api.github.com/repos/Overriders/networkx/contents/{+path}","compare_url":"https://api.github.com/repos/Overriders/networkx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/Overriders/networkx/merges","archive_url":"https://api.github.com/repos/Overriders/networkx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/Overriders/networkx/downloads","issues_url":"https://api.github.com/repos/Overriders/networkx/issues{/number}","pulls_url":"https://api.github.com/repos/Overriders/networkx/pulls{/number}","milestones_url":"https://api.github.com/repos/Overriders/networkx/milestones{/number}","notifications_url":"https://api.github.com/repos/Overriders/networkx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/Overriders/networkx/labels{/name}","releases_url":"https://api.github.com/repos/Overriders/networkx/releases{/id}","created_at":"2015-03-18T16:49:38Z","updated_at":"2015-05-07T17:08:34Z","pushed_at":"2015-05-22T23:06:53Z","git_url":"git://github.com/Overriders/networkx.git","ssh_url":"git@github.com:Overriders/networkx.git","clone_url":"https://github.com/Overriders/networkx.git","svn_url":"https://github.com/Overriders/networkx","homepage":"http://networkx.github.io","size":13247,"stargazers_count":0,"watchers_count":0,"language":"Python","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":"networkx:master","ref":"master","sha":"248d3f260717b28d88eddb84e1de581634c02e4c","user":{"login":"networkx","id":388785,"avatar_url":"https://avatars.githubusercontent.com/u/388785?v=3","gravatar_id":"","url":"https://api.github.com/users/networkx","html_url":"https://github.com/networkx","followers_url":"https://api.github.com/users/networkx/followers","following_url":"https://api.github.com/users/networkx/following{/other_user}","gists_url":"https://api.github.com/users/networkx/gists{/gist_id}","starred_url":"https://api.github.com/users/networkx/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/networkx/subscriptions","organizations_url":"https://api.github.com/users/networkx/orgs","repos_url":"https://api.github.com/users/networkx/repos","events_url":"https://api.github.com/users/networkx/events{/privacy}","received_events_url":"https://api.github.com/users/networkx/received_events","type":"Organization","site_admin":false},"repo":{"id":890377,"name":"networkx","full_name":"networkx/networkx","owner":{"login":"networkx","id":388785,"avatar_url":"https://avatars.githubusercontent.com/u/388785?v=3","gravatar_id":"","url":"https://api.github.com/users/networkx","html_url":"https://github.com/networkx","followers_url":"https://api.github.com/users/networkx/followers","following_url":"https://api.github.com/users/networkx/following{/other_user}","gists_url":"https://api.github.com/users/networkx/gists{/gist_id}","starred_url":"https://api.github.com/users/networkx/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/networkx/subscriptions","organizations_url":"https://api.github.com/users/networkx/orgs","repos_url":"https://api.github.com/users/networkx/repos","events_url":"https://api.github.com/users/networkx/events{/privacy}","received_events_url":"https://api.github.com/users/networkx/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/networkx/networkx","description":"Official NetworkX source code repository.  ","fork":false,"url":"https://api.github.com/repos/networkx/networkx","forks_url":"https://api.github.com/repos/networkx/networkx/forks","keys_url":"https://api.github.com/repos/networkx/networkx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/networkx/networkx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/networkx/networkx/teams","hooks_url":"https://api.github.com/repos/networkx/networkx/hooks","issue_events_url":"https://api.github.com/repos/networkx/networkx/issues/events{/number}","events_url":"https://api.github.com/repos/networkx/networkx/events","assignees_url":"https://api.github.com/repos/networkx/networkx/assignees{/user}","branches_url":"https://api.github.com/repos/networkx/networkx/branches{/branch}","tags_url":"https://api.github.com/repos/networkx/networkx/tags","blobs_url":"https://api.github.com/repos/networkx/networkx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/networkx/networkx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/networkx/networkx/git/refs{/sha}","trees_url":"https://api.github.com/repos/networkx/networkx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/networkx/networkx/statuses/{sha}","languages_url":"https://api.github.com/repos/networkx/networkx/languages","stargazers_url":"https://api.github.com/repos/networkx/networkx/stargazers","contributors_url":"https://api.github.com/repos/networkx/networkx/contributors","subscribers_url":"https://api.github.com/repos/networkx/networkx/subscribers","subscription_url":"https://api.github.com/repos/networkx/networkx/subscription","commits_url":"https://api.github.com/repos/networkx/networkx/commits{/sha}","git_commits_url":"https://api.github.com/repos/networkx/networkx/git/commits{/sha}","comments_url":"https://api.github.com/repos/networkx/networkx/comments{/number}","issue_comment_url":"https://api.github.com/repos/networkx/networkx/issues/comments{/number}","contents_url":"https://api.github.com/repos/networkx/networkx/contents/{+path}","compare_url":"https://api.github.com/repos/networkx/networkx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/networkx/networkx/merges","archive_url":"https://api.github.com/repos/networkx/networkx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/networkx/networkx/downloads","issues_url":"https://api.github.com/repos/networkx/networkx/issues{/number}","pulls_url":"https://api.github.com/repos/networkx/networkx/pulls{/number}","milestones_url":"https://api.github.com/repos/networkx/networkx/milestones{/number}","notifications_url":"https://api.github.com/repos/networkx/networkx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/networkx/networkx/labels{/name}","releases_url":"https://api.github.com/repos/networkx/networkx/releases{/id}","created_at":"2010-09-06T00:53:44Z","updated_at":"2015-05-27T02:05:41Z","pushed_at":"2015-05-27T13:57:24Z","git_url":"git://github.com/networkx/networkx.git","ssh_url":"git@github.com:networkx/networkx.git","clone_url":"https://github.com/networkx/networkx.git","svn_url":"https://github.com/networkx/networkx","homepage":"http://networkx.github.io","size":23943,"stargazers_count":1419,"watchers_count":1419,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":451,"mirror_url":null,"open_issues_count":204,"forks":451,"open_issues":204,"watchers":1419,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1508"},"html":{"href":"https://github.com/networkx/networkx/pull/1508"},"issue":{"href":"https://api.github.com/repos/networkx/networkx/issues/1508"},"comments":{"href":"https://api.github.com/repos/networkx/networkx/issues/1508/comments"},"review_comments":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1508/comments"},"review_comment":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1508/commits"},"statuses":{"href":"https://api.github.com/repos/networkx/networkx/statuses/562cd359ad429d6321ee8837cdfd6890e80d0799"}}}}