GitHub PullRequestEvent at 2014-04-09 20:19:22
Repository: networkx
Actor: hagberg
Payload: {"action":"closed","number":1099,"pull_request":{"url":"https://api.github.com/repos/networkx/networkx/pulls/1099","id":14509806,"html_url":"https://github.com/networkx/networkx/pull/1099","diff_url":"https://github.com/networkx/networkx/pull/1099.diff","patch_url":"https://github.com/networkx/networkx/pull/1099.patch","issue_url":"https://api.github.com/repos/networkx/networkx/issues/1099","number":1099,"state":"closed","title":"Add shortest augmenting path maximum flow algorithm","user":{"login":"ysitu","id":7018196,"avatar_url":"https://avatars.githubusercontent.com/u/7018196?","gravatar_id":"3fa62d3aa068923a03b0b57ea07f734f","url":"https://api.github.com/users/ysitu","html_url":"https://github.com/ysitu","followers_url":"https://api.github.com/users/ysitu/followers","following_url":"https://api.github.com/users/ysitu/following{/other_user}","gists_url":"https://api.github.com/users/ysitu/gists{/gist_id}","starred_url":"https://api.github.com/users/ysitu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ysitu/subscriptions","organizations_url":"https://api.github.com/users/ysitu/orgs","repos_url":"https://api.github.com/users/ysitu/repos","events_url":"https://api.github.com/users/ysitu/events{/privacy}","received_events_url":"https://api.github.com/users/ysitu/received_events","type":"User","site_admin":false},"body":"This is Ahuja & Orlin's shortest augmenting path algorithm briefly touched on in #1095. See [1] for detailed description. The two-phase method tailored for unit-capacity networks in [1] is also provided through an optional parameter.\r\n\r\n##### Timing tests\r\n###### Cases from #1082\r\nFor general problems, SAP is no doubt an improvement over Edmonds–Karp, but highest-label preflow-push is a better idea.\r\n\r\n| Case | `ford_fulkerson` | `shortest_augmenting_path` | `preflow_push` |\r\n|:-----|-----------------:|---------------------------:|---------------:|\r\n| GL1  |           1.36 s |                     0.68 s |         0.12 s |\r\n| GL2  |           4.05 s |                     1.27 s |         0.20 s |\r\n| GL3  |          17.50 s |                     5.30 s |         0.80 s |\r\n| GL4  |          65.67 s |                    11.74 s |         1.25 s |\r\n| GL5  |         308.97 s |                    39.69 s |         2.88 s |\r\n| GL6  |        1508.11 s |                   170.58 s |         6.65 s |\r\n| GW1  |           0.52 s |                     0.49 s |         0.33 s |\r\n| GW2  |           2.50 s |                     1.68 s |         0.70 s |\r\n| GW3  |           7.80 s |                     4.22 s |         1.79 s |\r\n| GW4  |          34.07 s |                    12.46 s |         4.05 s |\r\n| GW5  |         165.34 s |                    40.50 s |        10.94 s |\r\n| GW6  |         844.14 s |                   117.70 s |        28.95 s |\r\n| WLM1 |           0.09 s |                     0.04 s |         0.02 s |\r\n| WLM2 |           0.42 s |                     0.10 s |         0.06 s |\r\n| WLM3 |           1.38 s |                     0.24 s |         0.12 s |\r\n| WLM4 |           7.80 s |                     0.83 s |         0.32 s |\r\n| WLM5 |          42.75 s |                     2.56 s |         1.06 s |\r\n| WLM6 |         188.53 s |                     6.06 s |         3.01 s |\r\n\r\n###### 3000 vs 3000 random bipartite matching\r\nEdmonds–Karp is good when the graph is very dense (*m*/*n*² > 0.1) or very sparse (*m*/*n*² < 0.00001). In the more sensible range, SAP is the king.\r\n\r\nThe two-phase method seems to make a difference only when the gap heuristic is disabled. When enabled, the heuristic always terminates the algorithm before the criterion for switching to phase 2 is met. So there is no reason to disable it.\r\n\r\n| #edges  | `ford_fulkerson` | `shortest_augmenting_path` | `preflow_push` |\r\n|--------:|-----------------:|---------------------------:|---------------:|\r\n| 9000000 |         52.570 s |                   96.890 s |      189.640 s |\r\n|  901033 |          8.100 s |                    9.930 s |       11.290 s |\r\n|   89714 |          3.290 s |                    1.250 s |        1.610 s |\r\n|    8832 |          3.750 s |                    0.700 s |        0.750 s |\r\n|     882 |          1.380 s |                    0.150 s |        0.260 s |\r\n|      90 |          0.250 s |                    0.120 s |        0.210 s |\r\n|      11 |          0.070 s |                    0.110 s |        0.210 s |\r\n\r\n* 6000 extra edges needed for reducing bipartite matching to maximum flow are not counted.\r\n\r\n##### Reference\r\n1. Ahuja, R. K.; Orlin, J. B. (1991). \"[Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems](http://onlinelibrary.wiley.com/doi/10.1002/1520-6750%28199106%2938:3%3C413::AID-NAV3220380310%3E3.0.CO;2-J/abstract)\". *Naval Research Logistics*, **38** (3): 413–430.","created_at":"2014-04-08T16:43:32Z","updated_at":"2014-04-09T20:19:21Z","closed_at":"2014-04-09T20:19:21Z","merged_at":"2014-04-09T20:19:21Z","merge_commit_sha":"45090736e0ecba519aec227113bbbe2aae8b7f98","assignee":{"login":"hagberg","id":187875,"avatar_url":"https://avatars.githubusercontent.com/u/187875?","gravatar_id":"cf2fa0c08e61c5568e451b7c03579229","url":"https://api.github.com/users/hagberg","html_url":"https://github.com/hagberg","followers_url":"https://api.github.com/users/hagberg/followers","following_url":"https://api.github.com/users/hagberg/following{/other_user}","gists_url":"https://api.github.com/users/hagberg/gists{/gist_id}","starred_url":"https://api.github.com/users/hagberg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hagberg/subscriptions","organizations_url":"https://api.github.com/users/hagberg/orgs","repos_url":"https://api.github.com/users/hagberg/repos","events_url":"https://api.github.com/users/hagberg/events{/privacy}","received_events_url":"https://api.github.com/users/hagberg/received_events","type":"User","site_admin":false},"milestone":{"url":"https://api.github.com/repos/networkx/networkx/milestones/2","labels_url":"https://api.github.com/repos/networkx/networkx/milestones/2/labels","id":236123,"number":2,"title":"networkx-1.9","description":"","creator":{"login":"hagberg","id":187875,"avatar_url":"https://avatars.githubusercontent.com/u/187875?","gravatar_id":"cf2fa0c08e61c5568e451b7c03579229","url":"https://api.github.com/users/hagberg","html_url":"https://github.com/hagberg","followers_url":"https://api.github.com/users/hagberg/followers","following_url":"https://api.github.com/users/hagberg/following{/other_user}","gists_url":"https://api.github.com/users/hagberg/gists{/gist_id}","starred_url":"https://api.github.com/users/hagberg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hagberg/subscriptions","organizations_url":"https://api.github.com/users/hagberg/orgs","repos_url":"https://api.github.com/users/hagberg/repos","events_url":"https://api.github.com/users/hagberg/events{/privacy}","received_events_url":"https://api.github.com/users/hagberg/received_events","type":"User","site_admin":false},"open_issues":10,"closed_issues":110,"state":"open","created_at":"2012-12-29T15:42:26Z","updated_at":"2014-04-09T20:19:21Z","due_on":"2013-12-28T08:00:00Z"},"commits_url":"https://api.github.com/repos/networkx/networkx/pulls/1099/commits","review_comments_url":"https://api.github.com/repos/networkx/networkx/pulls/1099/comments","review_comment_url":"https://api.github.com/repos/networkx/networkx/pulls/comments/{number}","comments_url":"https://api.github.com/repos/networkx/networkx/issues/1099/comments","statuses_url":"https://api.github.com/repos/networkx/networkx/statuses/ae4519a26e372f8a27a7e460fc08d409c5bafe55","head":{"label":"ysitu:sap","ref":"sap","sha":"ae4519a26e372f8a27a7e460fc08d409c5bafe55","user":{"login":"ysitu","id":7018196,"avatar_url":"https://avatars.githubusercontent.com/u/7018196?","gravatar_id":"3fa62d3aa068923a03b0b57ea07f734f","url":"https://api.github.com/users/ysitu","html_url":"https://github.com/ysitu","followers_url":"https://api.github.com/users/ysitu/followers","following_url":"https://api.github.com/users/ysitu/following{/other_user}","gists_url":"https://api.github.com/users/ysitu/gists{/gist_id}","starred_url":"https://api.github.com/users/ysitu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ysitu/subscriptions","organizations_url":"https://api.github.com/users/ysitu/orgs","repos_url":"https://api.github.com/users/ysitu/repos","events_url":"https://api.github.com/users/ysitu/events{/privacy}","received_events_url":"https://api.github.com/users/ysitu/received_events","type":"User","site_admin":false},"repo":{"id":17967846,"name":"networkx","full_name":"ysitu/networkx","owner":{"login":"ysitu","id":7018196,"avatar_url":"https://avatars.githubusercontent.com/u/7018196?","gravatar_id":"3fa62d3aa068923a03b0b57ea07f734f","url":"https://api.github.com/users/ysitu","html_url":"https://github.com/ysitu","followers_url":"https://api.github.com/users/ysitu/followers","following_url":"https://api.github.com/users/ysitu/following{/other_user}","gists_url":"https://api.github.com/users/ysitu/gists{/gist_id}","starred_url":"https://api.github.com/users/ysitu/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ysitu/subscriptions","organizations_url":"https://api.github.com/users/ysitu/orgs","repos_url":"https://api.github.com/users/ysitu/repos","events_url":"https://api.github.com/users/ysitu/events{/privacy}","received_events_url":"https://api.github.com/users/ysitu/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/ysitu/networkx","description":"Official NetworkX source code repository.  ","fork":true,"url":"https://api.github.com/repos/ysitu/networkx","forks_url":"https://api.github.com/repos/ysitu/networkx/forks","keys_url":"https://api.github.com/repos/ysitu/networkx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/ysitu/networkx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/ysitu/networkx/teams","hooks_url":"https://api.github.com/repos/ysitu/networkx/hooks","issue_events_url":"https://api.github.com/repos/ysitu/networkx/issues/events{/number}","events_url":"https://api.github.com/repos/ysitu/networkx/events","assignees_url":"https://api.github.com/repos/ysitu/networkx/assignees{/user}","branches_url":"https://api.github.com/repos/ysitu/networkx/branches{/branch}","tags_url":"https://api.github.com/repos/ysitu/networkx/tags","blobs_url":"https://api.github.com/repos/ysitu/networkx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/ysitu/networkx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/ysitu/networkx/git/refs{/sha}","trees_url":"https://api.github.com/repos/ysitu/networkx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/ysitu/networkx/statuses/{sha}","languages_url":"https://api.github.com/repos/ysitu/networkx/languages","stargazers_url":"https://api.github.com/repos/ysitu/networkx/stargazers","contributors_url":"https://api.github.com/repos/ysitu/networkx/contributors","subscribers_url":"https://api.github.com/repos/ysitu/networkx/subscribers","subscription_url":"https://api.github.com/repos/ysitu/networkx/subscription","commits_url":"https://api.github.com/repos/ysitu/networkx/commits{/sha}","git_commits_url":"https://api.github.com/repos/ysitu/networkx/git/commits{/sha}","comments_url":"https://api.github.com/repos/ysitu/networkx/comments{/number}","issue_comment_url":"https://api.github.com/repos/ysitu/networkx/issues/comments/{number}","contents_url":"https://api.github.com/repos/ysitu/networkx/contents/{+path}","compare_url":"https://api.github.com/repos/ysitu/networkx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/ysitu/networkx/merges","archive_url":"https://api.github.com/repos/ysitu/networkx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/ysitu/networkx/downloads","issues_url":"https://api.github.com/repos/ysitu/networkx/issues{/number}","pulls_url":"https://api.github.com/repos/ysitu/networkx/pulls{/number}","milestones_url":"https://api.github.com/repos/ysitu/networkx/milestones{/number}","notifications_url":"https://api.github.com/repos/ysitu/networkx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/ysitu/networkx/labels{/name}","releases_url":"https://api.github.com/repos/ysitu/networkx/releases{/id}","created_at":"2014-03-21T04:05:26Z","updated_at":"2014-04-09T20:19:21Z","pushed_at":"2014-04-09T09:33:23Z","git_url":"git://github.com/ysitu/networkx.git","ssh_url":"git@github.com:ysitu/networkx.git","clone_url":"https://github.com/ysitu/networkx.git","svn_url":"https://github.com/ysitu/networkx","homepage":"http:/networkx.lanl.gov/","size":11805,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":false,"has_downloads":true,"has_wiki":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master","master_branch":"master"}},"base":{"label":"networkx:master","ref":"master","sha":"3ff0a3d00e1896da21721013e9e727f893c311c2","user":{"login":"networkx","id":388785,"avatar_url":"https://avatars.githubusercontent.com/u/388785?","gravatar_id":"839f97e174de34ac9e485680f0c5113c","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?","gravatar_id":"839f97e174de34ac9e485680f0c5113c","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":"2014-04-09T20:19:21Z","pushed_at":"2014-04-09T20:19:22Z","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.lanl.gov/","size":17537,"stargazers_count":795,"watchers_count":795,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":false,"forks_count":253,"mirror_url":null,"open_issues_count":122,"forks":253,"open_issues":122,"watchers":795,"default_branch":"master","master_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1099"},"html":{"href":"https://github.com/networkx/networkx/pull/1099"},"issue":{"href":"https://api.github.com/repos/networkx/networkx/issues/1099"},"comments":{"href":"https://api.github.com/repos/networkx/networkx/issues/1099/comments"},"review_comments":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1099/comments"},"review_comment":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1099/commits"},"statuses":{"href":"https://api.github.com/repos/networkx/networkx/statuses/ae4519a26e372f8a27a7e460fc08d409c5bafe55"}},"merged":true,"mergeable":null,"mergeable_state":"unknown","merged_by":{"login":"hagberg","id":187875,"avatar_url":"https://avatars.githubusercontent.com/u/187875?","gravatar_id":"cf2fa0c08e61c5568e451b7c03579229","url":"https://api.github.com/users/hagberg","html_url":"https://github.com/hagberg","followers_url":"https://api.github.com/users/hagberg/followers","following_url":"https://api.github.com/users/hagberg/following{/other_user}","gists_url":"https://api.github.com/users/hagberg/gists{/gist_id}","starred_url":"https://api.github.com/users/hagberg/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hagberg/subscriptions","organizations_url":"https://api.github.com/users/hagberg/orgs","repos_url":"https://api.github.com/users/hagberg/repos","events_url":"https://api.github.com/users/hagberg/events{/privacy}","received_events_url":"https://api.github.com/users/hagberg/received_events","type":"User","site_admin":false},"comments":11,"review_comments":0,"commits":6,"additions":603,"deletions":145,"changed_files":7}}