{"action":"created","issue":{"url":"https://api.github.com/repos/math1um/objects-invariants-properties/issues/401","repository_url":"https://api.github.com/repos/math1um/objects-invariants-properties","labels_url":"https://api.github.com/repos/math1um/objects-invariants-properties/issues/401/labels{/name}","comments_url":"https://api.github.com/repos/math1um/objects-invariants-properties/issues/401/comments","events_url":"https://api.github.com/repos/math1um/objects-invariants-properties/issues/401/events","html_url":"https://github.com/math1um/objects-invariants-properties/issues/401","id":248055586,"node_id":"MDU6SXNzdWUyNDgwNTU1ODY=","number":401,"title":"Add utility: bipartite set","user":{"login":"cjoshea9","id":29434683,"node_id":"MDQ6VXNlcjI5NDM0Njgz","avatar_url":"https://avatars0.githubusercontent.com/u/29434683?v=4","gravatar_id":"","url":"https://api.github.com/users/cjoshea9","html_url":"https://github.com/cjoshea9","followers_url":"https://api.github.com/users/cjoshea9/followers","following_url":"https://api.github.com/users/cjoshea9/following{/other_user}","gists_url":"https://api.github.com/users/cjoshea9/gists{/gist_id}","starred_url":"https://api.github.com/users/cjoshea9/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cjoshea9/subscriptions","organizations_url":"https://api.github.com/users/cjoshea9/orgs","repos_url":"https://api.github.com/users/cjoshea9/repos","events_url":"https://api.github.com/users/cjoshea9/events{/privacy}","received_events_url":"https://api.github.com/users/cjoshea9/received_events","type":"User","site_admin":false},"labels":[{"id":126912183,"node_id":"MDU6TGFiZWwxMjY5MTIxODM=","url":"https://api.github.com/repos/math1um/objects-invariants-properties/labels/enhancement","name":"enhancement","color":"84b6eb","default":true}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2017-08-04T16:30:24Z","updated_at":"2018-06-08T22:46:36Z","closed_at":null,"author_association":"NONE","body":"```python\r\ndef bs(g,s,c):\r\n    #print \"s is {}\".format(s)\r\n    #print \"c is {}\".format(c)\r\n    if len(c) == 0:\r\n        return s\r\n    \r\n    v = c[0]\r\n    #print \"v is {}\".format(v)\r\n    SCopy = copy(s)\r\n    SCopy.append(v)\r\n    Gprime = g.subgraph(SCopy)\r\n    \r\n    CCopy = copy(c)\r\n    CCopy.remove(v) #CCopy is C with v removed\r\n    if not(Gprime.is_bipartite()):\r\n        #print \"{} is not bipartite\".format(SCopy)\r\n        return bs(g, s, CCopy)\r\n    \r\n    \r\n    temp1 = bs(g, SCopy, CCopy)\r\n    temp2 = bs(g, s, CCopy)\r\n    \r\n    if len(temp1) > len(temp2):\r\n        return temp1\r\n    else:\r\n        return temp2\r\n```"},"comment":{"url":"https://api.github.com/repos/math1um/objects-invariants-properties/issues/comments/395912435","html_url":"https://github.com/math1um/objects-invariants-properties/issues/401#issuecomment-395912435","issue_url":"https://api.github.com/repos/math1um/objects-invariants-properties/issues/401","id":395912435,"node_id":"MDEyOklzc3VlQ29tbWVudDM5NTkxMjQzNQ==","user":{"login":"math1um","id":2118748,"node_id":"MDQ6VXNlcjIxMTg3NDg=","avatar_url":"https://avatars3.githubusercontent.com/u/2118748?v=4","gravatar_id":"","url":"https://api.github.com/users/math1um","html_url":"https://github.com/math1um","followers_url":"https://api.github.com/users/math1um/followers","following_url":"https://api.github.com/users/math1um/following{/other_user}","gists_url":"https://api.github.com/users/math1um/gists{/gist_id}","starred_url":"https://api.github.com/users/math1um/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/math1um/subscriptions","organizations_url":"https://api.github.com/users/math1um/orgs","repos_url":"https://api.github.com/users/math1um/repos","events_url":"https://api.github.com/users/math1um/events{/privacy}","received_events_url":"https://api.github.com/users/math1um/received_events","type":"User","site_admin":false},"created_at":"2018-06-08T22:46:36Z","updated_at":"2018-06-08T22:46:36Z","author_association":"OWNER","body":"It looks like this is an auxilliary function for computing the *bipartite number* of a graph: that is, the size of a maximum set of vertices that induces a bipartite subgraph.\r\n\r\nThis number comes up, for instance, in investigations of the independence number of a graph (alpha >= 0.5*bipartite number).\r\n\r\nThe function above looks like maybe it is trying to use the idea of the Tarjan-Trojanowski maximum independent set algorithm to find a maximum bipartite subgraph. The basic idea here would be: either a vertex v is in a maximum bipartite subgraph or it is not.\r\n\r\nIn an case, a properly written function should return a 2-element set if the input is a complete graph (with order at least 2) and bipartite_number(Kn)=2."}}
{"actor":{"display_login":"math1um"}}