{"action":"opened","number":191,"pull_request":{"url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/191","id":66380570,"html_url":"https://github.com/jgrapht/jgrapht/pull/191","diff_url":"https://github.com/jgrapht/jgrapht/pull/191.diff","patch_url":"https://github.com/jgrapht/jgrapht/pull/191.patch","issue_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/191","number":191,"state":"open","locked":false,"title":"Extension of Max Flow algorithms: undirected graphs are now supported","user":{"login":"jkinable","id":2742474,"avatar_url":"https://avatars.githubusercontent.com/u/2742474?v=3","gravatar_id":"","url":"https://api.github.com/users/jkinable","html_url":"https://github.com/jkinable","followers_url":"https://api.github.com/users/jkinable/followers","following_url":"https://api.github.com/users/jkinable/following{/other_user}","gists_url":"https://api.github.com/users/jkinable/gists{/gist_id}","starred_url":"https://api.github.com/users/jkinable/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jkinable/subscriptions","organizations_url":"https://api.github.com/users/jkinable/orgs","repos_url":"https://api.github.com/users/jkinable/repos","events_url":"https://api.github.com/users/jkinable/events{/privacy}","received_events_url":"https://api.github.com/users/jkinable/received_events","type":"User","site_admin":false},"body":"@jsichi : For some reason, this pull request seems to contain a lot of changes I didn't make? E.g. I didn't touch .travis.yml or HISTORY.md? As a result an automatic merge ain't possible. Did I mess something up?\r\n\r\nThis pull request extends both EdmondsKarpMaximumFlow and PushRelabelMaximumFlow, thereby adding the option to run both algorithms on undirected graphs.\r\n\r\nChangelog:\r\n-EdmondsKarpMaximumFlow and PushRelabelMaximimumFlow algorithms now also work on undirected graphs\r\n-Added test for both directed and undirected graphs\r\n-Rewrote & documented significant parts of the old implementation. \r\n-Deleted RandomizedTest from Max flow tests: this test did not serve any purpose. The results were never verified. The only way the test could fail is if the algorithm throw some internal exception.\r\n-Deleted the Legacy implementation of EdmondsKarpMaximumFlow and corresponding test\r\n-Documented public (!) functions of Extension class. Added some questions wrt revisions.\r\n-Separated flow calculation from actually generating a map representing the flow on each edge individually. The latter often is expensive and unnecessary.\r\n\r\nNote: in the previous release of jgrapht, significant changes to the MaxFlow algorithms were introduced. Unfortunately, this code was overly complex, messy, and very poorly documented, especially when you consider the simplicity of the algorithm. It took a considerable amount of time to reverse engineer what was going on. A simple 1 hour task of adding support for undirected graphs turned out to be a 2-day endeavor. Let's try to avoid this in the future. Algorithms should be implemented (and documented) as clear as possible such that other people can extend the code, fix potential bugs, etc. In addition, the runtime complexity of an implementation should be clear.\r\n\r\nNote 2: I left several comments in the Extension.java class. Please review those.","created_at":"2016-04-13T19:50:32Z","updated_at":"2016-04-13T19:50:32Z","closed_at":null,"merged_at":null,"merge_commit_sha":null,"assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/191/commits","review_comments_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/191/comments","review_comment_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}","comments_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/191/comments","statuses_url":"https://api.github.com/repos/jgrapht/jgrapht/statuses/f5697081b6ccc0c1cbb63568e3defbd3ced37630","head":{"label":"jkinable:EdmondKarpUndirGraph_releaseCandidate","ref":"EdmondKarpUndirGraph_releaseCandidate","sha":"f5697081b6ccc0c1cbb63568e3defbd3ced37630","user":{"login":"jkinable","id":2742474,"avatar_url":"https://avatars.githubusercontent.com/u/2742474?v=3","gravatar_id":"","url":"https://api.github.com/users/jkinable","html_url":"https://github.com/jkinable","followers_url":"https://api.github.com/users/jkinable/followers","following_url":"https://api.github.com/users/jkinable/following{/other_user}","gists_url":"https://api.github.com/users/jkinable/gists{/gist_id}","starred_url":"https://api.github.com/users/jkinable/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jkinable/subscriptions","organizations_url":"https://api.github.com/users/jkinable/orgs","repos_url":"https://api.github.com/users/jkinable/repos","events_url":"https://api.github.com/users/jkinable/events{/privacy}","received_events_url":"https://api.github.com/users/jkinable/received_events","type":"User","site_admin":false},"repo":{"id":6578121,"name":"jgrapht","full_name":"jkinable/jgrapht","owner":{"login":"jkinable","id":2742474,"avatar_url":"https://avatars.githubusercontent.com/u/2742474?v=3","gravatar_id":"","url":"https://api.github.com/users/jkinable","html_url":"https://github.com/jkinable","followers_url":"https://api.github.com/users/jkinable/followers","following_url":"https://api.github.com/users/jkinable/following{/other_user}","gists_url":"https://api.github.com/users/jkinable/gists{/gist_id}","starred_url":"https://api.github.com/users/jkinable/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jkinable/subscriptions","organizations_url":"https://api.github.com/users/jkinable/orgs","repos_url":"https://api.github.com/users/jkinable/repos","events_url":"https://api.github.com/users/jkinable/events{/privacy}","received_events_url":"https://api.github.com/users/jkinable/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jkinable/jgrapht","description":"Master repository for the JGraphT project","fork":true,"url":"https://api.github.com/repos/jkinable/jgrapht","forks_url":"https://api.github.com/repos/jkinable/jgrapht/forks","keys_url":"https://api.github.com/repos/jkinable/jgrapht/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jkinable/jgrapht/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jkinable/jgrapht/teams","hooks_url":"https://api.github.com/repos/jkinable/jgrapht/hooks","issue_events_url":"https://api.github.com/repos/jkinable/jgrapht/issues/events{/number}","events_url":"https://api.github.com/repos/jkinable/jgrapht/events","assignees_url":"https://api.github.com/repos/jkinable/jgrapht/assignees{/user}","branches_url":"https://api.github.com/repos/jkinable/jgrapht/branches{/branch}","tags_url":"https://api.github.com/repos/jkinable/jgrapht/tags","blobs_url":"https://api.github.com/repos/jkinable/jgrapht/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jkinable/jgrapht/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jkinable/jgrapht/git/refs{/sha}","trees_url":"https://api.github.com/repos/jkinable/jgrapht/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jkinable/jgrapht/statuses/{sha}","languages_url":"https://api.github.com/repos/jkinable/jgrapht/languages","stargazers_url":"https://api.github.com/repos/jkinable/jgrapht/stargazers","contributors_url":"https://api.github.com/repos/jkinable/jgrapht/contributors","subscribers_url":"https://api.github.com/repos/jkinable/jgrapht/subscribers","subscription_url":"https://api.github.com/repos/jkinable/jgrapht/subscription","commits_url":"https://api.github.com/repos/jkinable/jgrapht/commits{/sha}","git_commits_url":"https://api.github.com/repos/jkinable/jgrapht/git/commits{/sha}","comments_url":"https://api.github.com/repos/jkinable/jgrapht/comments{/number}","issue_comment_url":"https://api.github.com/repos/jkinable/jgrapht/issues/comments{/number}","contents_url":"https://api.github.com/repos/jkinable/jgrapht/contents/{+path}","compare_url":"https://api.github.com/repos/jkinable/jgrapht/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jkinable/jgrapht/merges","archive_url":"https://api.github.com/repos/jkinable/jgrapht/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jkinable/jgrapht/downloads","issues_url":"https://api.github.com/repos/jkinable/jgrapht/issues{/number}","pulls_url":"https://api.github.com/repos/jkinable/jgrapht/pulls{/number}","milestones_url":"https://api.github.com/repos/jkinable/jgrapht/milestones{/number}","notifications_url":"https://api.github.com/repos/jkinable/jgrapht/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jkinable/jgrapht/labels{/name}","releases_url":"https://api.github.com/repos/jkinable/jgrapht/releases{/id}","deployments_url":"https://api.github.com/repos/jkinable/jgrapht/deployments","created_at":"2012-11-07T11:18:31Z","updated_at":"2016-02-17T12:50:12Z","pushed_at":"2016-04-13T19:20:46Z","git_url":"git://github.com/jkinable/jgrapht.git","ssh_url":"git@github.com:jkinable/jgrapht.git","clone_url":"https://github.com/jkinable/jgrapht.git","svn_url":"https://github.com/jkinable/jgrapht","homepage":"http://www.jgrapht.org","size":5818,"stargazers_count":1,"watchers_count":1,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":0,"forks":1,"open_issues":0,"watchers":1,"default_branch":"master"}},"base":{"label":"jgrapht:master","ref":"master","sha":"8575334f4c04c56093712aee148088753007fe34","user":{"login":"jgrapht","id":1624681,"avatar_url":"https://avatars.githubusercontent.com/u/1624681?v=3","gravatar_id":"","url":"https://api.github.com/users/jgrapht","html_url":"https://github.com/jgrapht","followers_url":"https://api.github.com/users/jgrapht/followers","following_url":"https://api.github.com/users/jgrapht/following{/other_user}","gists_url":"https://api.github.com/users/jgrapht/gists{/gist_id}","starred_url":"https://api.github.com/users/jgrapht/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jgrapht/subscriptions","organizations_url":"https://api.github.com/users/jgrapht/orgs","repos_url":"https://api.github.com/users/jgrapht/repos","events_url":"https://api.github.com/users/jgrapht/events{/privacy}","received_events_url":"https://api.github.com/users/jgrapht/received_events","type":"Organization","site_admin":false},"repo":{"id":3969325,"name":"jgrapht","full_name":"jgrapht/jgrapht","owner":{"login":"jgrapht","id":1624681,"avatar_url":"https://avatars.githubusercontent.com/u/1624681?v=3","gravatar_id":"","url":"https://api.github.com/users/jgrapht","html_url":"https://github.com/jgrapht","followers_url":"https://api.github.com/users/jgrapht/followers","following_url":"https://api.github.com/users/jgrapht/following{/other_user}","gists_url":"https://api.github.com/users/jgrapht/gists{/gist_id}","starred_url":"https://api.github.com/users/jgrapht/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jgrapht/subscriptions","organizations_url":"https://api.github.com/users/jgrapht/orgs","repos_url":"https://api.github.com/users/jgrapht/repos","events_url":"https://api.github.com/users/jgrapht/events{/privacy}","received_events_url":"https://api.github.com/users/jgrapht/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/jgrapht/jgrapht","description":"Master repository for the JGraphT project","fork":true,"url":"https://api.github.com/repos/jgrapht/jgrapht","forks_url":"https://api.github.com/repos/jgrapht/jgrapht/forks","keys_url":"https://api.github.com/repos/jgrapht/jgrapht/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jgrapht/jgrapht/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jgrapht/jgrapht/teams","hooks_url":"https://api.github.com/repos/jgrapht/jgrapht/hooks","issue_events_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/events{/number}","events_url":"https://api.github.com/repos/jgrapht/jgrapht/events","assignees_url":"https://api.github.com/repos/jgrapht/jgrapht/assignees{/user}","branches_url":"https://api.github.com/repos/jgrapht/jgrapht/branches{/branch}","tags_url":"https://api.github.com/repos/jgrapht/jgrapht/tags","blobs_url":"https://api.github.com/repos/jgrapht/jgrapht/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jgrapht/jgrapht/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jgrapht/jgrapht/git/refs{/sha}","trees_url":"https://api.github.com/repos/jgrapht/jgrapht/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jgrapht/jgrapht/statuses/{sha}","languages_url":"https://api.github.com/repos/jgrapht/jgrapht/languages","stargazers_url":"https://api.github.com/repos/jgrapht/jgrapht/stargazers","contributors_url":"https://api.github.com/repos/jgrapht/jgrapht/contributors","subscribers_url":"https://api.github.com/repos/jgrapht/jgrapht/subscribers","subscription_url":"https://api.github.com/repos/jgrapht/jgrapht/subscription","commits_url":"https://api.github.com/repos/jgrapht/jgrapht/commits{/sha}","git_commits_url":"https://api.github.com/repos/jgrapht/jgrapht/git/commits{/sha}","comments_url":"https://api.github.com/repos/jgrapht/jgrapht/comments{/number}","issue_comment_url":"https://api.github.com/repos/jgrapht/jgrapht/issues/comments{/number}","contents_url":"https://api.github.com/repos/jgrapht/jgrapht/contents/{+path}","compare_url":"https://api.github.com/repos/jgrapht/jgrapht/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jgrapht/jgrapht/merges","archive_url":"https://api.github.com/repos/jgrapht/jgrapht/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jgrapht/jgrapht/downloads","issues_url":"https://api.github.com/repos/jgrapht/jgrapht/issues{/number}","pulls_url":"https://api.github.com/repos/jgrapht/jgrapht/pulls{/number}","milestones_url":"https://api.github.com/repos/jgrapht/jgrapht/milestones{/number}","notifications_url":"https://api.github.com/repos/jgrapht/jgrapht/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jgrapht/jgrapht/labels{/name}","releases_url":"https://api.github.com/repos/jgrapht/jgrapht/releases{/id}","deployments_url":"https://api.github.com/repos/jgrapht/jgrapht/deployments","created_at":"2012-04-09T05:30:23Z","updated_at":"2016-04-13T18:03:49Z","pushed_at":"2016-04-13T02:46:28Z","git_url":"git://github.com/jgrapht/jgrapht.git","ssh_url":"git@github.com:jgrapht/jgrapht.git","clone_url":"https://github.com/jgrapht/jgrapht.git","svn_url":"https://github.com/jgrapht/jgrapht","homepage":"http://www.jgrapht.org","size":7350,"stargazers_count":645,"watchers_count":645,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":268,"mirror_url":null,"open_issues_count":54,"forks":268,"open_issues":54,"watchers":645,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/191"},"html":{"href":"https://github.com/jgrapht/jgrapht/pull/191"},"issue":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/191"},"comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/issues/191/comments"},"review_comments":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/191/comments"},"review_comment":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/jgrapht/jgrapht/pulls/191/commits"},"statuses":{"href":"https://api.github.com/repos/jgrapht/jgrapht/statuses/f5697081b6ccc0c1cbb63568e3defbd3ced37630"}},"merged":false,"mergeable":null,"mergeable_state":"unknown","merged_by":null,"comments":0,"review_comments":0,"commits":9,"additions":2102,"deletions":2764,"changed_files":319}}