{"action":"created","comment":{"url":"https://api.github.com/repos/networkx/networkx/pulls/comments/36988452","id":36988452,"diff_hunk":"@@ -463,3 +466,146 @@ def find_cycle(G, source=None, orientation='original'):\n \n     return cycle[i:]\n \n+\n+@not_implemented_for('directed')\n+@not_implemented_for('multigraph')\n+def minimum_cycle_basis(G, weight=None):\n+    \"\"\"\n+    Returns a minimum weight cycle basis for G\n+    It is defined as a cycle basis for which the total weight (length \n+    for unweighted graphs) of all the cycles is minimum. \n+\n+    Parameters\n+    ----------\n+    G : NetworkX Graph\n+    weight: edge attribute to use\n+\n+    Returns\n+    -------\n+    A list of cycle lists.  Each cycle list is a list of nodes\n+    which forms a cycle (loop) in G. Note that the nodes are not\n+    necessarily returned in a order by which they appear in the cycle\n+\n+    Examples\n+    --------\n+    >>> G=nx.Graph()\n+    >>> G.add_cycle([0,1,2,3])\n+    >>> G.add_cycle([0,3,4,5])\n+    >>> print(nx.minimum_cycle_basis(G))\n+    [[0, 1, 2, 3], [0, 3, 4, 5]]\n+\n+    References:    \n+        [1] Kavitha, Telikepalli, et al. \"An O(m^2n) Algorithm for Minimum Cycle Basis of Graphs.\"\n+        http://link.springer.com/article/10.1007/s00453-007-9064-z\n+        [2] de Pina, J. 1995. Applications of shortest path methods. Ph.D. thesis, University of Amsterdam, Netherlands \n+\n+    See Also\n+    --------\n+    simple_cycles, cycle_basis\n+\n+    \"\"\"\n+\n+    # We first split the graph in commected subgraphs\n+    return sum((_min_cycle_basis(c, weight) for c in\n+                nx.connected_component_subgraphs(G)), [])\n+\n+def _min_cycle_basis(comp, weight):\n+    cb = []\n+    # We  extract the edges not in a spanning tree. We do not really need a \n+    # *minimum* spanning tree. That is why we call the next function with \n+    # weight=None. Depending on implementation, it may be faster as well. \n+    spanning_tree_edges = list(\n+        nx.minimum_spanning_edges(comp, weight=None, data=False))\n+    edges_excl = [\n+        frozenset(e) for e in comp.edges() if e not in spanning_tree_edges]\n+    N = len(edges_excl)\n+\n+    # We maintain a set of vectors orthogonal to sofar found cycles\n+    set_orth = [set([edge]) for edge in edges_excl]\n+    for k in range(N):\n+        # kth cycle is \"parallel\" to kth vector in set_orth\n+        new_cycle = _min_cycle(comp, set_orth[k], weight=weight)\n+        cb.append(list(set().union(*new_cycle)))\n+        # now update set_orth so that k+1,k+2... th elements are\n+        # orthogonal to the newly found cycle, as per [p. 336, 1]\n+        base = set_orth[k]\n+        set_orth[k + 1:] = [orth ^ base if len(orth & new_cycle) % 2\n+                            else orth for orth in set_orth[k + 1:]]\n+\n+    return cb\n+\n+\n+def _min_cycle(G, orth, weight=None):\n+    \"\"\"\n+    Computes the minimum weight cycle in G, orthogonal to the vector orth\n+    as per [p. 338, 1]\n+    \"\"\"\n+    T = nx.Graph()\n+\n+    nodes_idx = {node: idx for idx, node in enumerate(G.nodes())}\n+    idx_nodes = {idx: node for node, idx in nodes_idx.items()}\n+\n+    nnodes = len(nodes_idx)\n+\n+    # Add 2 copies of each edge in G to T. If edge is in orth, add cross edge;\n+    # otherwise in-plane edge\n+    if weight is not None:\n+        for u, v in G.edges():\n+            uidx, vidx = nodes_idx[u], nodes_idx[v]\n+            edge_w = G[u][v][weight]\n+            if frozenset((u, v)) in orth:\n+                T.add_edges_from(\n+                    [(uidx, nnodes + vidx), (nnodes + uidx, vidx)], weight=edge_w)\n+\n+            else:\n+                T.add_edges_from(\n+                    [(uidx, vidx), (nnodes + uidx, nnodes + vidx)], weight=edge_w)\n+\n+        all_shortest_pathlens = nx.shortest_path_length(T, weight='weight')","path":"networkx/algorithms/cycles.py","position":null,"original_position":123,"commit_id":"88c3f21c565de7fadd16af532d5cfc553f5bba9c","original_commit_id":"29d182653109dfc1fc8ad26e61627c1417c455a2","user":{"login":"debsankha","id":313429,"avatar_url":"https://avatars.githubusercontent.com/u/313429?v=3","gravatar_id":"","url":"https://api.github.com/users/debsankha","html_url":"https://github.com/debsankha","followers_url":"https://api.github.com/users/debsankha/followers","following_url":"https://api.github.com/users/debsankha/following{/other_user}","gists_url":"https://api.github.com/users/debsankha/gists{/gist_id}","starred_url":"https://api.github.com/users/debsankha/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debsankha/subscriptions","organizations_url":"https://api.github.com/users/debsankha/orgs","repos_url":"https://api.github.com/users/debsankha/repos","events_url":"https://api.github.com/users/debsankha/events{/privacy}","received_events_url":"https://api.github.com/users/debsankha/received_events","type":"User","site_admin":false},"body":"Thanks! I have implemented it. ","created_at":"2015-08-13T15:34:17Z","updated_at":"2015-08-13T15:34:17Z","html_url":"https://github.com/networkx/networkx/pull/1649#discussion_r36988452","pull_request_url":"https://api.github.com/repos/networkx/networkx/pulls/1649","_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments/36988452"},"html":{"href":"https://github.com/networkx/networkx/pull/1649#discussion_r36988452"},"pull_request":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1649"}}},"pull_request":{"url":"https://api.github.com/repos/networkx/networkx/pulls/1649","id":39627018,"html_url":"https://github.com/networkx/networkx/pull/1649","diff_url":"https://github.com/networkx/networkx/pull/1649.diff","patch_url":"https://github.com/networkx/networkx/pull/1649.patch","issue_url":"https://api.github.com/repos/networkx/networkx/issues/1649","number":1649,"state":"open","locked":false,"title":"Feature add mcb","user":{"login":"debsankha","id":313429,"avatar_url":"https://avatars.githubusercontent.com/u/313429?v=3","gravatar_id":"","url":"https://api.github.com/users/debsankha","html_url":"https://github.com/debsankha","followers_url":"https://api.github.com/users/debsankha/followers","following_url":"https://api.github.com/users/debsankha/following{/other_user}","gists_url":"https://api.github.com/users/debsankha/gists{/gist_id}","starred_url":"https://api.github.com/users/debsankha/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debsankha/subscriptions","organizations_url":"https://api.github.com/users/debsankha/orgs","repos_url":"https://api.github.com/users/debsankha/repos","events_url":"https://api.github.com/users/debsankha/events{/privacy}","received_events_url":"https://api.github.com/users/debsankha/received_events","type":"User","site_admin":false},"body":"I have added a function to compute [minimum weight cycle basis](https://en.wikipedia.org/wiki/Cycle_basis#Minimum_weight) for an undirected graph following [de Pina's algorithm](https://people.mpi-inf.mpg.de/~mehlhorn/ftp/CycleBasisImpl.pdf). \r\n","created_at":"2015-07-09T20:52:28Z","updated_at":"2015-08-13T15:34:17Z","closed_at":null,"merged_at":null,"merge_commit_sha":"a4dd49d1bf9f46de285c465717a4800039e26a13","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/networkx/networkx/pulls/1649/commits","review_comments_url":"https://api.github.com/repos/networkx/networkx/pulls/1649/comments","review_comment_url":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}","comments_url":"https://api.github.com/repos/networkx/networkx/issues/1649/comments","statuses_url":"https://api.github.com/repos/networkx/networkx/statuses/88c3f21c565de7fadd16af532d5cfc553f5bba9c","head":{"label":"debsankha:feature-add-mcb","ref":"feature-add-mcb","sha":"88c3f21c565de7fadd16af532d5cfc553f5bba9c","user":{"login":"debsankha","id":313429,"avatar_url":"https://avatars.githubusercontent.com/u/313429?v=3","gravatar_id":"","url":"https://api.github.com/users/debsankha","html_url":"https://github.com/debsankha","followers_url":"https://api.github.com/users/debsankha/followers","following_url":"https://api.github.com/users/debsankha/following{/other_user}","gists_url":"https://api.github.com/users/debsankha/gists{/gist_id}","starred_url":"https://api.github.com/users/debsankha/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debsankha/subscriptions","organizations_url":"https://api.github.com/users/debsankha/orgs","repos_url":"https://api.github.com/users/debsankha/repos","events_url":"https://api.github.com/users/debsankha/events{/privacy}","received_events_url":"https://api.github.com/users/debsankha/received_events","type":"User","site_admin":false},"repo":{"id":38744810,"name":"networkx","full_name":"debsankha/networkx","owner":{"login":"debsankha","id":313429,"avatar_url":"https://avatars.githubusercontent.com/u/313429?v=3","gravatar_id":"","url":"https://api.github.com/users/debsankha","html_url":"https://github.com/debsankha","followers_url":"https://api.github.com/users/debsankha/followers","following_url":"https://api.github.com/users/debsankha/following{/other_user}","gists_url":"https://api.github.com/users/debsankha/gists{/gist_id}","starred_url":"https://api.github.com/users/debsankha/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/debsankha/subscriptions","organizations_url":"https://api.github.com/users/debsankha/orgs","repos_url":"https://api.github.com/users/debsankha/repos","events_url":"https://api.github.com/users/debsankha/events{/privacy}","received_events_url":"https://api.github.com/users/debsankha/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/debsankha/networkx","description":"Official NetworkX source code repository.  ","fork":true,"url":"https://api.github.com/repos/debsankha/networkx","forks_url":"https://api.github.com/repos/debsankha/networkx/forks","keys_url":"https://api.github.com/repos/debsankha/networkx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/debsankha/networkx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/debsankha/networkx/teams","hooks_url":"https://api.github.com/repos/debsankha/networkx/hooks","issue_events_url":"https://api.github.com/repos/debsankha/networkx/issues/events{/number}","events_url":"https://api.github.com/repos/debsankha/networkx/events","assignees_url":"https://api.github.com/repos/debsankha/networkx/assignees{/user}","branches_url":"https://api.github.com/repos/debsankha/networkx/branches{/branch}","tags_url":"https://api.github.com/repos/debsankha/networkx/tags","blobs_url":"https://api.github.com/repos/debsankha/networkx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/debsankha/networkx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/debsankha/networkx/git/refs{/sha}","trees_url":"https://api.github.com/repos/debsankha/networkx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/debsankha/networkx/statuses/{sha}","languages_url":"https://api.github.com/repos/debsankha/networkx/languages","stargazers_url":"https://api.github.com/repos/debsankha/networkx/stargazers","contributors_url":"https://api.github.com/repos/debsankha/networkx/contributors","subscribers_url":"https://api.github.com/repos/debsankha/networkx/subscribers","subscription_url":"https://api.github.com/repos/debsankha/networkx/subscription","commits_url":"https://api.github.com/repos/debsankha/networkx/commits{/sha}","git_commits_url":"https://api.github.com/repos/debsankha/networkx/git/commits{/sha}","comments_url":"https://api.github.com/repos/debsankha/networkx/comments{/number}","issue_comment_url":"https://api.github.com/repos/debsankha/networkx/issues/comments{/number}","contents_url":"https://api.github.com/repos/debsankha/networkx/contents/{+path}","compare_url":"https://api.github.com/repos/debsankha/networkx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/debsankha/networkx/merges","archive_url":"https://api.github.com/repos/debsankha/networkx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/debsankha/networkx/downloads","issues_url":"https://api.github.com/repos/debsankha/networkx/issues{/number}","pulls_url":"https://api.github.com/repos/debsankha/networkx/pulls{/number}","milestones_url":"https://api.github.com/repos/debsankha/networkx/milestones{/number}","notifications_url":"https://api.github.com/repos/debsankha/networkx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/debsankha/networkx/labels{/name}","releases_url":"https://api.github.com/repos/debsankha/networkx/releases{/id}","created_at":"2015-07-08T09:30:26Z","updated_at":"2015-08-10T09:02:16Z","pushed_at":"2015-08-13T15:34:01Z","git_url":"git://github.com/debsankha/networkx.git","ssh_url":"git@github.com:debsankha/networkx.git","clone_url":"https://github.com/debsankha/networkx.git","svn_url":"https://github.com/debsankha/networkx","homepage":"http://networkx.github.io","size":13208,"stargazers_count":1,"watchers_count":1,"language":"Python","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":1,"default_branch":"placeholder"}},"base":{"label":"networkx:master","ref":"master","sha":"342e421eee255f508b77ed2a3ce4b55aae5edd9c","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-08-12T09:20:41Z","pushed_at":"2015-08-13T15:34:02Z","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":24432,"stargazers_count":1531,"watchers_count":1531,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":504,"mirror_url":null,"open_issues_count":272,"forks":504,"open_issues":272,"watchers":1531,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1649"},"html":{"href":"https://github.com/networkx/networkx/pull/1649"},"issue":{"href":"https://api.github.com/repos/networkx/networkx/issues/1649"},"comments":{"href":"https://api.github.com/repos/networkx/networkx/issues/1649/comments"},"review_comments":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1649/comments"},"review_comment":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1649/commits"},"statuses":{"href":"https://api.github.com/repos/networkx/networkx/statuses/88c3f21c565de7fadd16af532d5cfc553f5bba9c"}}}}