{"action":"created","comment":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/comments/43877490","id":43877490,"diff_hunk":"@@ -263,14 +263,32 @@ end\n \"\"\"Will return `true` if graph `g` is\n [bipartite](https://en.wikipedia.org/wiki/Bipartite_graph).\n \"\"\"\n-function is_bipartite(g::SimpleGraph, s::Int)\n+is_bipartite(g::SimpleGraph, s::Int) = bipartite_internal(g, s).is_bipartite\n+\n+function is_bipartite(g::SimpleGraph)\n+    cc = filter(x->length(x)>2, connected_components(g))\n+    return all(x->is_bipartite(g,x[1]), cc)\n+end\n+\n+function bipartite_internal(g::SimpleGraph, s::Int)","path":"src/traversals/bfs.jl","position":12,"original_position":12,"commit_id":"907800a0cb933a3d7184ad53fa39ae8daa991cb5","original_commit_id":"907800a0cb933a3d7184ad53fa39ae8daa991cb5","user":{"login":"CarloLucibello","id":7014210,"avatar_url":"https://avatars.githubusercontent.com/u/7014210?v=3","gravatar_id":"","url":"https://api.github.com/users/CarloLucibello","html_url":"https://github.com/CarloLucibello","followers_url":"https://api.github.com/users/CarloLucibello/followers","following_url":"https://api.github.com/users/CarloLucibello/following{/other_user}","gists_url":"https://api.github.com/users/CarloLucibello/gists{/gist_id}","starred_url":"https://api.github.com/users/CarloLucibello/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CarloLucibello/subscriptions","organizations_url":"https://api.github.com/users/CarloLucibello/orgs","repos_url":"https://api.github.com/users/CarloLucibello/repos","events_url":"https://api.github.com/users/CarloLucibello/events{/privacy}","received_events_url":"https://api.github.com/users/CarloLucibello/received_events","type":"User","site_admin":false},"body":"ok","created_at":"2015-11-04T13:03:53Z","updated_at":"2015-11-04T13:03:53Z","html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/207#discussion_r43877490","pull_request_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/207","_links":{"self":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/comments/43877490"},"html":{"href":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/207#discussion_r43877490"},"pull_request":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/207"}}},"pull_request":{"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/207","id":49339953,"html_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/207","diff_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/207.diff","patch_url":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/207.patch","issue_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/207","number":207,"state":"open","locked":false,"title":"matching algorithm for bipartite graphs (linear programming)","user":{"login":"CarloLucibello","id":7014210,"avatar_url":"https://avatars.githubusercontent.com/u/7014210?v=3","gravatar_id":"","url":"https://api.github.com/users/CarloLucibello","html_url":"https://github.com/CarloLucibello","followers_url":"https://api.github.com/users/CarloLucibello/followers","following_url":"https://api.github.com/users/CarloLucibello/following{/other_user}","gists_url":"https://api.github.com/users/CarloLucibello/gists{/gist_id}","starred_url":"https://api.github.com/users/CarloLucibello/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CarloLucibello/subscriptions","organizations_url":"https://api.github.com/users/CarloLucibello/orgs","repos_url":"https://api.github.com/users/CarloLucibello/repos","events_url":"https://api.github.com/users/CarloLucibello/events{/privacy}","received_events_url":"https://api.github.com/users/CarloLucibello/received_events","type":"User","site_admin":false},"body":"partially fixes #194\r\n\r\nThis is meant to be a temporary solution, exploiting the fact that for bipartite graphs matching can be relaxed to linear programming, untill someone finds the courage and the will to implement a more effcient matching algorithm.\r\n\r\nFor the time being I added JuMP to REQUIRE, I don't know how to set them as optional dependences.","created_at":"2015-10-31T02:45:14Z","updated_at":"2015-11-04T13:03:53Z","closed_at":null,"merged_at":null,"merge_commit_sha":"f9851e387dc7b42c08d32735da6ba27c750ee4fb","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/207/commits","review_comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/207/comments","review_comment_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/comments{/number}","comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/207/comments","statuses_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/statuses/907800a0cb933a3d7184ad53fa39ae8daa991cb5","head":{"label":"CarloLucibello:matching2","ref":"matching2","sha":"907800a0cb933a3d7184ad53fa39ae8daa991cb5","user":{"login":"CarloLucibello","id":7014210,"avatar_url":"https://avatars.githubusercontent.com/u/7014210?v=3","gravatar_id":"","url":"https://api.github.com/users/CarloLucibello","html_url":"https://github.com/CarloLucibello","followers_url":"https://api.github.com/users/CarloLucibello/followers","following_url":"https://api.github.com/users/CarloLucibello/following{/other_user}","gists_url":"https://api.github.com/users/CarloLucibello/gists{/gist_id}","starred_url":"https://api.github.com/users/CarloLucibello/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CarloLucibello/subscriptions","organizations_url":"https://api.github.com/users/CarloLucibello/orgs","repos_url":"https://api.github.com/users/CarloLucibello/repos","events_url":"https://api.github.com/users/CarloLucibello/events{/privacy}","received_events_url":"https://api.github.com/users/CarloLucibello/received_events","type":"User","site_admin":false},"repo":{"id":42853831,"name":"LightGraphs.jl","full_name":"CarloLucibello/LightGraphs.jl","owner":{"login":"CarloLucibello","id":7014210,"avatar_url":"https://avatars.githubusercontent.com/u/7014210?v=3","gravatar_id":"","url":"https://api.github.com/users/CarloLucibello","html_url":"https://github.com/CarloLucibello","followers_url":"https://api.github.com/users/CarloLucibello/followers","following_url":"https://api.github.com/users/CarloLucibello/following{/other_user}","gists_url":"https://api.github.com/users/CarloLucibello/gists{/gist_id}","starred_url":"https://api.github.com/users/CarloLucibello/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/CarloLucibello/subscriptions","organizations_url":"https://api.github.com/users/CarloLucibello/orgs","repos_url":"https://api.github.com/users/CarloLucibello/repos","events_url":"https://api.github.com/users/CarloLucibello/events{/privacy}","received_events_url":"https://api.github.com/users/CarloLucibello/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/CarloLucibello/LightGraphs.jl","description":"An optimized graphs package for Julia","fork":true,"url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl","forks_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/forks","keys_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/keys{/key_id}","collaborators_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/teams","hooks_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/hooks","issue_events_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/issues/events{/number}","events_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/events","assignees_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/assignees{/user}","branches_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/branches{/branch}","tags_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/tags","blobs_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/git/refs{/sha}","trees_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/git/trees{/sha}","statuses_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/statuses/{sha}","languages_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/languages","stargazers_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/stargazers","contributors_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/contributors","subscribers_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/subscribers","subscription_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/subscription","commits_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/commits{/sha}","git_commits_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/git/commits{/sha}","comments_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/comments{/number}","issue_comment_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/issues/comments{/number}","contents_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/contents/{+path}","compare_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/compare/{base}...{head}","merges_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/merges","archive_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/downloads","issues_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/issues{/number}","pulls_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/pulls{/number}","milestones_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/milestones{/number}","notifications_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/labels{/name}","releases_url":"https://api.github.com/repos/CarloLucibello/LightGraphs.jl/releases{/id}","created_at":"2015-09-21T08:32:37Z","updated_at":"2015-09-21T08:32:38Z","pushed_at":"2015-11-03T14:53:03Z","git_url":"git://github.com/CarloLucibello/LightGraphs.jl.git","ssh_url":"git@github.com:CarloLucibello/LightGraphs.jl.git","clone_url":"https://github.com/CarloLucibello/LightGraphs.jl.git","svn_url":"https://github.com/CarloLucibello/LightGraphs.jl","homepage":"","size":4086,"stargazers_count":0,"watchers_count":0,"language":"Julia","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":"JuliaGraphs:master","ref":"master","sha":"1f66906d7f4c5a51d17ce4417256e5d7da4230f9","user":{"login":"JuliaGraphs","id":10791402,"avatar_url":"https://avatars.githubusercontent.com/u/10791402?v=3","gravatar_id":"","url":"https://api.github.com/users/JuliaGraphs","html_url":"https://github.com/JuliaGraphs","followers_url":"https://api.github.com/users/JuliaGraphs/followers","following_url":"https://api.github.com/users/JuliaGraphs/following{/other_user}","gists_url":"https://api.github.com/users/JuliaGraphs/gists{/gist_id}","starred_url":"https://api.github.com/users/JuliaGraphs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JuliaGraphs/subscriptions","organizations_url":"https://api.github.com/users/JuliaGraphs/orgs","repos_url":"https://api.github.com/users/JuliaGraphs/repos","events_url":"https://api.github.com/users/JuliaGraphs/events{/privacy}","received_events_url":"https://api.github.com/users/JuliaGraphs/received_events","type":"Organization","site_admin":false},"repo":{"id":29314835,"name":"LightGraphs.jl","full_name":"JuliaGraphs/LightGraphs.jl","owner":{"login":"JuliaGraphs","id":10791402,"avatar_url":"https://avatars.githubusercontent.com/u/10791402?v=3","gravatar_id":"","url":"https://api.github.com/users/JuliaGraphs","html_url":"https://github.com/JuliaGraphs","followers_url":"https://api.github.com/users/JuliaGraphs/followers","following_url":"https://api.github.com/users/JuliaGraphs/following{/other_user}","gists_url":"https://api.github.com/users/JuliaGraphs/gists{/gist_id}","starred_url":"https://api.github.com/users/JuliaGraphs/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JuliaGraphs/subscriptions","organizations_url":"https://api.github.com/users/JuliaGraphs/orgs","repos_url":"https://api.github.com/users/JuliaGraphs/repos","events_url":"https://api.github.com/users/JuliaGraphs/events{/privacy}","received_events_url":"https://api.github.com/users/JuliaGraphs/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/JuliaGraphs/LightGraphs.jl","description":"An optimized graphs package for Julia","fork":false,"url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl","forks_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/forks","keys_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/keys{/key_id}","collaborators_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/teams","hooks_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/hooks","issue_events_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/events{/number}","events_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/events","assignees_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/assignees{/user}","branches_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/branches{/branch}","tags_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/tags","blobs_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/refs{/sha}","trees_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/trees{/sha}","statuses_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/statuses/{sha}","languages_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/languages","stargazers_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/stargazers","contributors_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/contributors","subscribers_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/subscribers","subscription_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/subscription","commits_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/commits{/sha}","git_commits_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/git/commits{/sha}","comments_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/comments{/number}","issue_comment_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/comments{/number}","contents_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/contents/{+path}","compare_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/compare/{base}...{head}","merges_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/merges","archive_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/downloads","issues_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues{/number}","pulls_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls{/number}","milestones_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/milestones{/number}","notifications_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/labels{/name}","releases_url":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/releases{/id}","created_at":"2015-01-15T19:44:43Z","updated_at":"2015-11-01T06:56:10Z","pushed_at":"2015-11-03T23:19:03Z","git_url":"git://github.com/JuliaGraphs/LightGraphs.jl.git","ssh_url":"git@github.com:JuliaGraphs/LightGraphs.jl.git","clone_url":"https://github.com/JuliaGraphs/LightGraphs.jl.git","svn_url":"https://github.com/JuliaGraphs/LightGraphs.jl","homepage":"","size":5877,"stargazers_count":30,"watchers_count":30,"language":"Julia","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":15,"mirror_url":null,"open_issues_count":12,"forks":15,"open_issues":12,"watchers":30,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/207"},"html":{"href":"https://github.com/JuliaGraphs/LightGraphs.jl/pull/207"},"issue":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/207"},"comments":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/issues/207/comments"},"review_comments":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/207/comments"},"review_comment":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/pulls/207/commits"},"statuses":{"href":"https://api.github.com/repos/JuliaGraphs/LightGraphs.jl/statuses/907800a0cb933a3d7184ad53fa39ae8daa991cb5"}}}}