{"action":"opened","number":1415,"pull_request":{"url":"https://api.github.com/repos/networkx/networkx/pulls/1415","id":31426196,"html_url":"https://github.com/networkx/networkx/pull/1415","diff_url":"https://github.com/networkx/networkx/pull/1415.diff","patch_url":"https://github.com/networkx/networkx/pull/1415.patch","issue_url":"https://api.github.com/repos/networkx/networkx/issues/1415","number":1415,"state":"open","locked":false,"title":"Add fast approximation for k-(node)-components.","user":{"login":"jtorrents","id":1184374,"avatar_url":"https://avatars.githubusercontent.com/u/1184374?v=3","gravatar_id":"","url":"https://api.github.com/users/jtorrents","html_url":"https://github.com/jtorrents","followers_url":"https://api.github.com/users/jtorrents/followers","following_url":"https://api.github.com/users/jtorrents/following{/other_user}","gists_url":"https://api.github.com/users/jtorrents/gists{/gist_id}","starred_url":"https://api.github.com/users/jtorrents/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jtorrents/subscriptions","organizations_url":"https://api.github.com/users/jtorrents/orgs","repos_url":"https://api.github.com/users/jtorrents/repos","events_url":"https://api.github.com/users/jtorrents/events{/privacy}","received_events_url":"https://api.github.com/users/jtorrents/received_events","type":"User","site_admin":false},"body":"This is an approximation approach to compute the k-component structure\r\nof a graph (#1414 is the exact, and slow, version of this). I wrote a\r\npaper to explore this approach in detail, see http://arxiv.org/abs/1503.04476\r\n\r\nThe logic of the approximation algorithm for computing the `k`-component\r\nstructure is based on repeatedly applying simple and fast algorithms\r\nfor `k`-cores and biconnected components in order to narrow down the\r\nnumber of pairs of nodes over which we have to compute White and Newman's\r\napproximation algorithm for finding node independent paths (implemented at #1405).\r\nMore formally, this algorithm is based on Whitney's theorem, which states\r\nan inclusion relation among node connectivity, edge connectivity, and\r\nminimum degree for any graph G. This theorem implies that every\r\n`k`-component is nested inside a `k`-edge-component, which in turn,\r\nis contained in a `k`-core. Thus, this algorithm computes node independent\r\npaths among pairs of nodes in each biconnected part of each `k`-core,\r\nand repeats this procedure for each `k` from 3 to the maximal core number\r\nof a node in the input graph.\r\n\r\nBecause, in practice, many nodes of the core of level `k` inside a\r\nbicomponent actually are part of a component of level k, the auxiliary\r\ngraph needed for the algorithm it's likely to be very dense. Thus, we use\r\na complement graph data structure to save memory (`_AntiGraph` see #599\r\nfor an earlier dicussion about this). AntiGraph only stores information\r\nof the edges that are *not* present in the actual auxiliary graph.\r\nHowever, when applying algorithms to this complement graph data structure,\r\nit behaves as if it were the dense version. So it can be used directly\r\nin several NetworkX algorithms, this version is only tested for the\r\nalgorithms needed here: `connected_components`, `k-cores`, and\r\n`biconnected_components`. I used a `ThinGraph` for building the `AntiGraph`\r\nand the memory consumption is quite small compared with a regular `Graph`.\r\n\r\nI think `AntiGraph` is not useful enough to be a top level class in NetworkX,\r\nbut it could be a good example of a `Graph` subclass. I'll add to the\r\nexamples folder.\r\n\r\nThis PR supersedes and closes #580.","created_at":"2015-03-18T13:02:15Z","updated_at":"2015-03-18T13:02:15Z","closed_at":null,"merged_at":null,"merge_commit_sha":null,"assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/networkx/networkx/pulls/1415/commits","review_comments_url":"https://api.github.com/repos/networkx/networkx/pulls/1415/comments","review_comment_url":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}","comments_url":"https://api.github.com/repos/networkx/networkx/issues/1415/comments","statuses_url":"https://api.github.com/repos/networkx/networkx/statuses/c7076ac2a301c8d303a27e19fc674e6d269358c1","head":{"label":"jtorrents:k-components-approx","ref":"k-components-approx","sha":"c7076ac2a301c8d303a27e19fc674e6d269358c1","user":{"login":"jtorrents","id":1184374,"avatar_url":"https://avatars.githubusercontent.com/u/1184374?v=3","gravatar_id":"","url":"https://api.github.com/users/jtorrents","html_url":"https://github.com/jtorrents","followers_url":"https://api.github.com/users/jtorrents/followers","following_url":"https://api.github.com/users/jtorrents/following{/other_user}","gists_url":"https://api.github.com/users/jtorrents/gists{/gist_id}","starred_url":"https://api.github.com/users/jtorrents/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jtorrents/subscriptions","organizations_url":"https://api.github.com/users/jtorrents/orgs","repos_url":"https://api.github.com/users/jtorrents/repos","events_url":"https://api.github.com/users/jtorrents/events{/privacy}","received_events_url":"https://api.github.com/users/jtorrents/received_events","type":"User","site_admin":false},"repo":{"id":4785563,"name":"networkx","full_name":"jtorrents/networkx","owner":{"login":"jtorrents","id":1184374,"avatar_url":"https://avatars.githubusercontent.com/u/1184374?v=3","gravatar_id":"","url":"https://api.github.com/users/jtorrents","html_url":"https://github.com/jtorrents","followers_url":"https://api.github.com/users/jtorrents/followers","following_url":"https://api.github.com/users/jtorrents/following{/other_user}","gists_url":"https://api.github.com/users/jtorrents/gists{/gist_id}","starred_url":"https://api.github.com/users/jtorrents/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jtorrents/subscriptions","organizations_url":"https://api.github.com/users/jtorrents/orgs","repos_url":"https://api.github.com/users/jtorrents/repos","events_url":"https://api.github.com/users/jtorrents/events{/privacy}","received_events_url":"https://api.github.com/users/jtorrents/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jtorrents/networkx","description":"my development fork of NetworkX","fork":true,"url":"https://api.github.com/repos/jtorrents/networkx","forks_url":"https://api.github.com/repos/jtorrents/networkx/forks","keys_url":"https://api.github.com/repos/jtorrents/networkx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jtorrents/networkx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jtorrents/networkx/teams","hooks_url":"https://api.github.com/repos/jtorrents/networkx/hooks","issue_events_url":"https://api.github.com/repos/jtorrents/networkx/issues/events{/number}","events_url":"https://api.github.com/repos/jtorrents/networkx/events","assignees_url":"https://api.github.com/repos/jtorrents/networkx/assignees{/user}","branches_url":"https://api.github.com/repos/jtorrents/networkx/branches{/branch}","tags_url":"https://api.github.com/repos/jtorrents/networkx/tags","blobs_url":"https://api.github.com/repos/jtorrents/networkx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jtorrents/networkx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jtorrents/networkx/git/refs{/sha}","trees_url":"https://api.github.com/repos/jtorrents/networkx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jtorrents/networkx/statuses/{sha}","languages_url":"https://api.github.com/repos/jtorrents/networkx/languages","stargazers_url":"https://api.github.com/repos/jtorrents/networkx/stargazers","contributors_url":"https://api.github.com/repos/jtorrents/networkx/contributors","subscribers_url":"https://api.github.com/repos/jtorrents/networkx/subscribers","subscription_url":"https://api.github.com/repos/jtorrents/networkx/subscription","commits_url":"https://api.github.com/repos/jtorrents/networkx/commits{/sha}","git_commits_url":"https://api.github.com/repos/jtorrents/networkx/git/commits{/sha}","comments_url":"https://api.github.com/repos/jtorrents/networkx/comments{/number}","issue_comment_url":"https://api.github.com/repos/jtorrents/networkx/issues/comments{/number}","contents_url":"https://api.github.com/repos/jtorrents/networkx/contents/{+path}","compare_url":"https://api.github.com/repos/jtorrents/networkx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jtorrents/networkx/merges","archive_url":"https://api.github.com/repos/jtorrents/networkx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jtorrents/networkx/downloads","issues_url":"https://api.github.com/repos/jtorrents/networkx/issues{/number}","pulls_url":"https://api.github.com/repos/jtorrents/networkx/pulls{/number}","milestones_url":"https://api.github.com/repos/jtorrents/networkx/milestones{/number}","notifications_url":"https://api.github.com/repos/jtorrents/networkx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jtorrents/networkx/labels{/name}","releases_url":"https://api.github.com/repos/jtorrents/networkx/releases{/id}","created_at":"2012-06-25T18:30:17Z","updated_at":"2014-05-31T15:59:34Z","pushed_at":"2015-03-18T13:00:45Z","git_url":"git://github.com/jtorrents/networkx.git","ssh_url":"git@github.com:jtorrents/networkx.git","clone_url":"https://github.com/jtorrents/networkx.git","svn_url":"https://github.com/jtorrents/networkx","homepage":"","size":12809,"stargazers_count":1,"watchers_count":1,"language":"Python","has_issues":false,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":1,"default_branch":"master"}},"base":{"label":"networkx:master","ref":"master","sha":"ee6d96c1fecf44f03a8e56cbf8d44f0e5214fc7b","user":{"login":"networkx","id":388785,"avatar_url":"https://avatars.githubusercontent.com/u/388785?v=3","gravatar_id":"","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?v=3","gravatar_id":"","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":"2015-03-17T22:11:07Z","pushed_at":"2015-03-17T22:11:07Z","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.github.io","size":21402,"stargazers_count":1274,"watchers_count":1274,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":405,"mirror_url":null,"open_issues_count":167,"forks":405,"open_issues":167,"watchers":1274,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1415"},"html":{"href":"https://github.com/networkx/networkx/pull/1415"},"issue":{"href":"https://api.github.com/repos/networkx/networkx/issues/1415"},"comments":{"href":"https://api.github.com/repos/networkx/networkx/issues/1415/comments"},"review_comments":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1415/comments"},"review_comment":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1415/commits"},"statuses":{"href":"https://api.github.com/repos/networkx/networkx/statuses/c7076ac2a301c8d303a27e19fc674e6d269358c1"}},"merged":false,"mergeable":null,"mergeable_state":"unknown","merged_by":null,"comments":0,"review_comments":0,"commits":1,"additions":694,"deletions":0,"changed_files":3}}