{"action":"created","comment":{"url":"https://api.github.com/repos/rick/CSA/pulls/comments/48762267","id":48762267,"diff_hunk":"@@ -46,19 +50,38 @@ $ wc -l /tmp/flow.txt\n 50000 /tmp/flow.txt\n ```\n \n+### Perfect Matchings\n+\n+CSA presumes that the graph provided contains a perfect matching. If no such matching exists the solver will either not terminate, or can produce a non-optimal matching. (There are notes in the code to the effect that it would be possible to modify the solver to deal with this case, but that work was apparently never undertaken)","path":"README.md","position":30,"original_position":30,"commit_id":"8bfbe9b69751ca304c0e5a615b9084f7443029cf","original_commit_id":"8bfbe9b69751ca304c0e5a615b9084f7443029cf","user":{"login":"rick","id":6259,"avatar_url":"https://avatars.githubusercontent.com/u/6259?v=3","gravatar_id":"","url":"https://api.github.com/users/rick","html_url":"https://github.com/rick","followers_url":"https://api.github.com/users/rick/followers","following_url":"https://api.github.com/users/rick/following{/other_user}","gists_url":"https://api.github.com/users/rick/gists{/gist_id}","starred_url":"https://api.github.com/users/rick/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rick/subscriptions","organizations_url":"https://api.github.com/users/rick/orgs","repos_url":"https://api.github.com/users/rick/repos","events_url":"https://api.github.com/users/rick/events{/privacy}","received_events_url":"https://api.github.com/users/rick/received_events","type":"User","site_admin":false},"body":"Note to self: \".\" at end of sentence.","created_at":"2016-01-04T18:30:22Z","updated_at":"2016-01-04T18:30:22Z","html_url":"https://github.com/rick/CSA/pull/6#discussion_r48762267","pull_request_url":"https://api.github.com/repos/rick/CSA/pulls/6","_links":{"self":{"href":"https://api.github.com/repos/rick/CSA/pulls/comments/48762267"},"html":{"href":"https://github.com/rick/CSA/pull/6#discussion_r48762267"},"pull_request":{"href":"https://api.github.com/repos/rick/CSA/pulls/6"}}},"pull_request":{"url":"https://api.github.com/repos/rick/CSA/pulls/6","id":54916087,"html_url":"https://github.com/rick/CSA/pull/6","diff_url":"https://github.com/rick/CSA/pull/6.diff","patch_url":"https://github.com/rick/CSA/pull/6.patch","issue_url":"https://api.github.com/repos/rick/CSA/issues/6","number":6,"state":"open","locked":false,"title":"Deal with graphs lacking a perfect match","user":{"login":"rick","id":6259,"avatar_url":"https://avatars.githubusercontent.com/u/6259?v=3","gravatar_id":"","url":"https://api.github.com/users/rick","html_url":"https://github.com/rick","followers_url":"https://api.github.com/users/rick/followers","following_url":"https://api.github.com/users/rick/following{/other_user}","gists_url":"https://api.github.com/users/rick/gists{/gist_id}","starred_url":"https://api.github.com/users/rick/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rick/subscriptions","organizations_url":"https://api.github.com/users/rick/orgs","repos_url":"https://api.github.com/users/rick/repos","events_url":"https://api.github.com/users/rick/events{/privacy}","received_events_url":"https://api.github.com/users/rick/received_events","type":"User","site_admin":false},"body":"![](http://www.crucialbrutal.com/site_images/NEWS_pobodysnerfect.jpg)\r\n\r\nThe CSA solver is only guaranteed to work with weighted bipartite graphs which contain a perfect matching. On other graphs the algorithm is not guaranteed to terminate, and/or the optimization may be incorrect.\r\n\r\nAfter consulting with the original author, he provided an efficient algorithm for constructing an augmented weighted bipartite graph with a perfect matching, a solver solution for which can be used to efficiently derive the desired maximum cardinality minimum cost matching we're seeking for instances of the Assignment Problem.\r\n\r\nHere we document the algorithm, and implement tooling to convert a DIMACS-formatted graph description into an augmented graph with a perfect matching, run CSA-Q, and extract the resulting desired flow.\r\n\r\n![](https://raw.githubusercontent.com/rick/CSA/work-with-imperfect-graphs/docs/images/augmented-matching.png)","created_at":"2016-01-03T00:58:56Z","updated_at":"2016-01-04T18:30:22Z","closed_at":null,"merged_at":null,"merge_commit_sha":"c135d55af0fa9d0c6f1e2ca58bb2f00f9ebac1b8","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/rick/CSA/pulls/6/commits","review_comments_url":"https://api.github.com/repos/rick/CSA/pulls/6/comments","review_comment_url":"https://api.github.com/repos/rick/CSA/pulls/comments{/number}","comments_url":"https://api.github.com/repos/rick/CSA/issues/6/comments","statuses_url":"https://api.github.com/repos/rick/CSA/statuses/8bfbe9b69751ca304c0e5a615b9084f7443029cf","head":{"label":"rick:work-with-imperfect-graphs","ref":"work-with-imperfect-graphs","sha":"8bfbe9b69751ca304c0e5a615b9084f7443029cf","user":{"login":"rick","id":6259,"avatar_url":"https://avatars.githubusercontent.com/u/6259?v=3","gravatar_id":"","url":"https://api.github.com/users/rick","html_url":"https://github.com/rick","followers_url":"https://api.github.com/users/rick/followers","following_url":"https://api.github.com/users/rick/following{/other_user}","gists_url":"https://api.github.com/users/rick/gists{/gist_id}","starred_url":"https://api.github.com/users/rick/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rick/subscriptions","organizations_url":"https://api.github.com/users/rick/orgs","repos_url":"https://api.github.com/users/rick/repos","events_url":"https://api.github.com/users/rick/events{/privacy}","received_events_url":"https://api.github.com/users/rick/received_events","type":"User","site_admin":false},"repo":{"id":48858488,"name":"CSA","full_name":"rick/CSA","owner":{"login":"rick","id":6259,"avatar_url":"https://avatars.githubusercontent.com/u/6259?v=3","gravatar_id":"","url":"https://api.github.com/users/rick","html_url":"https://github.com/rick","followers_url":"https://api.github.com/users/rick/followers","following_url":"https://api.github.com/users/rick/following{/other_user}","gists_url":"https://api.github.com/users/rick/gists{/gist_id}","starred_url":"https://api.github.com/users/rick/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rick/subscriptions","organizations_url":"https://api.github.com/users/rick/orgs","repos_url":"https://api.github.com/users/rick/repos","events_url":"https://api.github.com/users/rick/events{/privacy}","received_events_url":"https://api.github.com/users/rick/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/rick/CSA","description":"Mirror of Andrew V. Goldberg's CSA (weighted bipartite matching solver for the Assignment Problem) software; fixes for modern compilers; added tooling","fork":false,"url":"https://api.github.com/repos/rick/CSA","forks_url":"https://api.github.com/repos/rick/CSA/forks","keys_url":"https://api.github.com/repos/rick/CSA/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rick/CSA/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rick/CSA/teams","hooks_url":"https://api.github.com/repos/rick/CSA/hooks","issue_events_url":"https://api.github.com/repos/rick/CSA/issues/events{/number}","events_url":"https://api.github.com/repos/rick/CSA/events","assignees_url":"https://api.github.com/repos/rick/CSA/assignees{/user}","branches_url":"https://api.github.com/repos/rick/CSA/branches{/branch}","tags_url":"https://api.github.com/repos/rick/CSA/tags","blobs_url":"https://api.github.com/repos/rick/CSA/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rick/CSA/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rick/CSA/git/refs{/sha}","trees_url":"https://api.github.com/repos/rick/CSA/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rick/CSA/statuses/{sha}","languages_url":"https://api.github.com/repos/rick/CSA/languages","stargazers_url":"https://api.github.com/repos/rick/CSA/stargazers","contributors_url":"https://api.github.com/repos/rick/CSA/contributors","subscribers_url":"https://api.github.com/repos/rick/CSA/subscribers","subscription_url":"https://api.github.com/repos/rick/CSA/subscription","commits_url":"https://api.github.com/repos/rick/CSA/commits{/sha}","git_commits_url":"https://api.github.com/repos/rick/CSA/git/commits{/sha}","comments_url":"https://api.github.com/repos/rick/CSA/comments{/number}","issue_comment_url":"https://api.github.com/repos/rick/CSA/issues/comments{/number}","contents_url":"https://api.github.com/repos/rick/CSA/contents/{+path}","compare_url":"https://api.github.com/repos/rick/CSA/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rick/CSA/merges","archive_url":"https://api.github.com/repos/rick/CSA/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rick/CSA/downloads","issues_url":"https://api.github.com/repos/rick/CSA/issues{/number}","pulls_url":"https://api.github.com/repos/rick/CSA/pulls{/number}","milestones_url":"https://api.github.com/repos/rick/CSA/milestones{/number}","notifications_url":"https://api.github.com/repos/rick/CSA/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rick/CSA/labels{/name}","releases_url":"https://api.github.com/repos/rick/CSA/releases{/id}","created_at":"2015-12-31T18:19:55Z","updated_at":"2016-01-01T00:29:19Z","pushed_at":"2016-01-03T01:47:41Z","git_url":"git://github.com/rick/CSA.git","ssh_url":"git@github.com:rick/CSA.git","clone_url":"https://github.com/rick/CSA.git","svn_url":"https://github.com/rick/CSA","homepage":"","size":413,"stargazers_count":0,"watchers_count":0,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":1,"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"base":{"label":"rick:master","ref":"master","sha":"bf6c50e95dc78517c09d9c48c71a93e3d32d9b22","user":{"login":"rick","id":6259,"avatar_url":"https://avatars.githubusercontent.com/u/6259?v=3","gravatar_id":"","url":"https://api.github.com/users/rick","html_url":"https://github.com/rick","followers_url":"https://api.github.com/users/rick/followers","following_url":"https://api.github.com/users/rick/following{/other_user}","gists_url":"https://api.github.com/users/rick/gists{/gist_id}","starred_url":"https://api.github.com/users/rick/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rick/subscriptions","organizations_url":"https://api.github.com/users/rick/orgs","repos_url":"https://api.github.com/users/rick/repos","events_url":"https://api.github.com/users/rick/events{/privacy}","received_events_url":"https://api.github.com/users/rick/received_events","type":"User","site_admin":false},"repo":{"id":48858488,"name":"CSA","full_name":"rick/CSA","owner":{"login":"rick","id":6259,"avatar_url":"https://avatars.githubusercontent.com/u/6259?v=3","gravatar_id":"","url":"https://api.github.com/users/rick","html_url":"https://github.com/rick","followers_url":"https://api.github.com/users/rick/followers","following_url":"https://api.github.com/users/rick/following{/other_user}","gists_url":"https://api.github.com/users/rick/gists{/gist_id}","starred_url":"https://api.github.com/users/rick/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rick/subscriptions","organizations_url":"https://api.github.com/users/rick/orgs","repos_url":"https://api.github.com/users/rick/repos","events_url":"https://api.github.com/users/rick/events{/privacy}","received_events_url":"https://api.github.com/users/rick/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/rick/CSA","description":"Mirror of Andrew V. Goldberg's CSA (weighted bipartite matching solver for the Assignment Problem) software; fixes for modern compilers; added tooling","fork":false,"url":"https://api.github.com/repos/rick/CSA","forks_url":"https://api.github.com/repos/rick/CSA/forks","keys_url":"https://api.github.com/repos/rick/CSA/keys{/key_id}","collaborators_url":"https://api.github.com/repos/rick/CSA/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/rick/CSA/teams","hooks_url":"https://api.github.com/repos/rick/CSA/hooks","issue_events_url":"https://api.github.com/repos/rick/CSA/issues/events{/number}","events_url":"https://api.github.com/repos/rick/CSA/events","assignees_url":"https://api.github.com/repos/rick/CSA/assignees{/user}","branches_url":"https://api.github.com/repos/rick/CSA/branches{/branch}","tags_url":"https://api.github.com/repos/rick/CSA/tags","blobs_url":"https://api.github.com/repos/rick/CSA/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/rick/CSA/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/rick/CSA/git/refs{/sha}","trees_url":"https://api.github.com/repos/rick/CSA/git/trees{/sha}","statuses_url":"https://api.github.com/repos/rick/CSA/statuses/{sha}","languages_url":"https://api.github.com/repos/rick/CSA/languages","stargazers_url":"https://api.github.com/repos/rick/CSA/stargazers","contributors_url":"https://api.github.com/repos/rick/CSA/contributors","subscribers_url":"https://api.github.com/repos/rick/CSA/subscribers","subscription_url":"https://api.github.com/repos/rick/CSA/subscription","commits_url":"https://api.github.com/repos/rick/CSA/commits{/sha}","git_commits_url":"https://api.github.com/repos/rick/CSA/git/commits{/sha}","comments_url":"https://api.github.com/repos/rick/CSA/comments{/number}","issue_comment_url":"https://api.github.com/repos/rick/CSA/issues/comments{/number}","contents_url":"https://api.github.com/repos/rick/CSA/contents/{+path}","compare_url":"https://api.github.com/repos/rick/CSA/compare/{base}...{head}","merges_url":"https://api.github.com/repos/rick/CSA/merges","archive_url":"https://api.github.com/repos/rick/CSA/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/rick/CSA/downloads","issues_url":"https://api.github.com/repos/rick/CSA/issues{/number}","pulls_url":"https://api.github.com/repos/rick/CSA/pulls{/number}","milestones_url":"https://api.github.com/repos/rick/CSA/milestones{/number}","notifications_url":"https://api.github.com/repos/rick/CSA/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/rick/CSA/labels{/name}","releases_url":"https://api.github.com/repos/rick/CSA/releases{/id}","created_at":"2015-12-31T18:19:55Z","updated_at":"2016-01-01T00:29:19Z","pushed_at":"2016-01-03T01:47:41Z","git_url":"git://github.com/rick/CSA.git","ssh_url":"git@github.com:rick/CSA.git","clone_url":"https://github.com/rick/CSA.git","svn_url":"https://github.com/rick/CSA","homepage":"","size":413,"stargazers_count":0,"watchers_count":0,"language":"C","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":1,"forks":0,"open_issues":1,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/rick/CSA/pulls/6"},"html":{"href":"https://github.com/rick/CSA/pull/6"},"issue":{"href":"https://api.github.com/repos/rick/CSA/issues/6"},"comments":{"href":"https://api.github.com/repos/rick/CSA/issues/6/comments"},"review_comments":{"href":"https://api.github.com/repos/rick/CSA/pulls/6/comments"},"review_comment":{"href":"https://api.github.com/repos/rick/CSA/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/rick/CSA/pulls/6/commits"},"statuses":{"href":"https://api.github.com/repos/rick/CSA/statuses/8bfbe9b69751ca304c0e5a615b9084f7443029cf"}}}}