{"action":"created","comment":{"url":"https://api.github.com/repos/networkx/networkx/pulls/comments/29430825","id":29430825,"diff_hunk":"@@ -0,0 +1,223 @@\n+import networkx as nx\n+\n+\"\"\" \n+Find an eulerian path\n+\"\"\"\n+#    Copyright (C) 2015 by\n+#    Edwardo S. Rivera <edwardo.rivera@upr.edu>\n+#    Humberto Ortiz <humberto@hpcf.upr.edu>\n+#    BSD license. \n+#    All rights reserved.\n+\n+\n+__author__ = \"\"\"\\n\"\"\".join(['Edwardo Rivera <edwardo.rivera@urp.edu>','Humberto Ortiz <humberto@hpcf.upr.edu>'])\n+\n+__all__ = ['find_eulerian_path'] \n+\n+def find_eulerian_path(G):\n+    \"\"\"Returns the edges of an Eulerian path in G, (if it exits).\n+\n+    An Eulerian path is a path that crosses every edge in G\n+    exactly once.\n+\n+    Parameters\n+    ----------\n+    G: NetworkX Graph, DiGraph, MultiGraph or MultiDiGraph \n+        A directed or undirected Graph or MultiGraph.\n+\n+    Returns\n+    -------\n+    edges: generator\n+        A generator that produces edges in the Eulerian path.\n+\n+    Raises\n+    ------\n+    NetworkXError: If the graph does not have an eulerian path.\n+\n+    Notes\n+    -----\n+    Linear time algorithm, adapted from [1]_ and [3]_.\n+    Information about euler paths in [2]_.\n+    Code for eulerian circuit in [3]_.\n+\n+    Important: In [1], euler path is in reverse order,\n+    this implementation gives the path in correct order\n+    as in [3]_ for eulerian_circuit. The distinction for \n+    directed graph is in using the in_degree neighbors, not the out\n+    ones. for undirected, it is using itemgetter(1) for get_vertex, \n+    which uses the correct vertex for this order. Also, every graph\n+    has an even number of odd vertices by the Handshaking Theorem [4]_. \n+\n+    References\n+    ----------\n+    .. [1] http://www.graph-magics.com/articles/euler.php\n+    .. [2] http://en.wikipedia.org/wiki/Eulerian_path\n+    .. [3] https://github.com/networkx/networkx/blob/master/networkx/algorithms/euler.py\n+    .. [4] https://www.math.ku.edu/~jmartin/courses/math105-F11/Lectures/chapter5-part2.pdf\n+    \n+    Examples \n+    --------\n+    >>> G = nx.Graph([('W', 'N'), ('N', 'E'), ('E', 'W'), ('W', 'S'), ('S', 'E')])\n+    >>> list(nx.find_eulerian_path(G))\n+    [('W', 'N'), ('N', 'E'), ('E', 'W'), ('W', 'S'), ('S', 'E')]\n+\n+    >>> G = nx.Digraph([(1, 2), (2, 3)])\n+    >>> list(nx.find_eulerian_path(G))\n+    [(1,2),(2,3)]\n+    \"\"\"\n+    from operator import itemgetter \n+\n+    # Verify that graph is connected, short circuit\n+    if G.is_directed() and not nx.is_weakly_connected(G):\n+        raise nx.NetworkXError(\"G is not connected.\")    \n+\n+    # is undirected\n+    if not G.is_directed() and not nx.is_connected(G):\n+        raise nx.NetworkXError(\"G is not connected.\")\n+\n+    # Now verify if has an eulerian circuit: even condition of all nodes is satified.\n+    if nx.is_eulerian(G):\n+        x = nx.eulerian_circuit(G) # generator of edges\n+        for i in x:\n+            yield i\n+        \n+    # Not all vertex have even degree, check if exactly two vertex have odd degrees.\n+    # If yes, then there is an Euler path. If not, raise an error (no euler path can be found)\n+    else:\n+        g = G.__class__(G)  # copy graph structure (not attributes)\n+        \n+        # list to check the odd degree condition, and a flag\n+        check_odd = []\n+        directed = False\n+    \n+        if g.is_directed():\n+            degree = g.in_degree\n+            out_degree = g.out_degree\n+            edges = g.in_edges_iter\n+            get_vertex = itemgetter(0)\n+            directed = True\n+        else:\n+            degree = g.degree\n+            edges = g.edges_iter\n+            get_vertex = itemgetter(1)\n+            \n+        # Verify if an euler path can be found. Complexity O(n) ?\n+        for vertex in g.nodes():\n+            deg = degree(vertex)\n+            # directed case\n+            if directed:\n+                outdeg = out_degree(vertex)\n+                if deg != outdeg:\n+                    # if we have more than 2 odd nodes, we do a raise (no euler path)\n+                    if len(check_odd) > 2:\n+                        raise nx.NetworkXError(\"G doesn't have an Euler Path.\")\n+                # is odd and we append it. \n+                    else:\n+                        check_odd.append(vertex)\n+            # undirected case        \n+            else:\n+                if deg % 2 != 0:\n+                    # if we have more than 2 odd nodes, we do a raise (no euler path)\n+                    if len(check_odd) > 2:\n+                        raise nx.NetworkXError(\"G doesn't have an Euler Path.\")\n+                    # is odd and we append it. \n+                    else:\n+                        check_odd.append(vertex)\n+\n+        if directed:\n+            def verify_odd_cond(g,check_odd):\n+                first = check_odd[0]\n+                second = check_odd[1]\n+                if  g.out_degree(first) == g.in_degree(first) + 1 and g.in_degree(second) == g.out_degree(second) + 1:\n+                    return second\n+                elif g.out_degree(second) == g.in_degree(second) + 1 and g.in_degree(first)  == g.out_degree(first) + 1:\n+                    return first\n+                else:\n+                    return None\n+            start = verify_odd_cond(g,check_odd)\n+        else:\n+            start = check_odd[0]\n+\n+        # if the odd condition is not meet, raise an error.\n+        if not start:\n+            raise nx.NetworkXError(\"G doesn't have an Euler Path\")\n+        # Begin algorithm: \n+        vertex_stack = [start]\n+        last_vertex = None\n+\n+        while vertex_stack:\n+\n+            current_vertex = vertex_stack[-1] #(4)\n+            # if no neighbors:\n+            if degree(current_vertex) == 0:\n+                # Special case, we cannot add a None vertex to the path.\n+                if last_vertex is not None:\n+                    yield (last_vertex, current_vertex)\n+                last_vertex = current_vertex\n+                vertex_stack.pop()\n+            # we have neighbors, so add the vertex to the stack (2), take any of its neighbors (1)\n+            # remove the edge between selected neighbor and that vertex,\n+            # and set that neighbor as the current vertex (4).\n+            else:\n+                random_edge = next(edges(current_vertex)) #(1)\n+                vertex_stack.append(get_vertex(random_edge)) #(2)\n+                g.remove_edge(*random_edge) #(3)\n+\n+# tests\n+if __name__ == \"__main__\":\n+\n+    # An example, undirected:\n+    G = nx.Graph()\n+    G.add_edge(\"W\",\"N\")\n+    G.add_edge(\"N\",\"E\")\n+    G.add_edge(\"E\",\"S\")\n+    G.add_edge(\"S\",\"W\")\n+    G.add_edge(\"W\",\"E\")\n+    x = find_eulerian_path(G)\n+    nodepath = [u for u, v in x]\n+    print nodepath\n+\n+    G = nx.DiGraph([(1,2),(2,3)])\n+    print list(find_eulerian_path(G))","path":"networkx/algorithms/find_euler_path.py","position":181,"original_position":181,"commit_id":"64c4b69a9cc79b13cd595b38e8bc01b6d79d7b2a","original_commit_id":"64c4b69a9cc79b13cd595b38e8bc01b6d79d7b2a","user":{"login":"edwardo2013","id":4259541,"avatar_url":"https://avatars.githubusercontent.com/u/4259541?v=3","gravatar_id":"","url":"https://api.github.com/users/edwardo2013","html_url":"https://github.com/edwardo2013","followers_url":"https://api.github.com/users/edwardo2013/followers","following_url":"https://api.github.com/users/edwardo2013/following{/other_user}","gists_url":"https://api.github.com/users/edwardo2013/gists{/gist_id}","starred_url":"https://api.github.com/users/edwardo2013/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/edwardo2013/subscriptions","organizations_url":"https://api.github.com/users/edwardo2013/orgs","repos_url":"https://api.github.com/users/edwardo2013/repos","events_url":"https://api.github.com/users/edwardo2013/events{/privacy}","received_events_url":"https://api.github.com/users/edwardo2013/received_events","type":"User","site_admin":false},"body":"I would use nose to do the testing (as in euler.py tests).","created_at":"2015-04-30T13:54:06Z","updated_at":"2015-04-30T13:54:06Z","html_url":"https://github.com/networkx/networkx/pull/1488#discussion_r29430825","pull_request_url":"https://api.github.com/repos/networkx/networkx/pulls/1488","_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments/29430825"},"html":{"href":"https://github.com/networkx/networkx/pull/1488#discussion_r29430825"},"pull_request":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1488"}}},"pull_request":{"url":"https://api.github.com/repos/networkx/networkx/pulls/1488","id":34296391,"html_url":"https://github.com/networkx/networkx/pull/1488","diff_url":"https://github.com/networkx/networkx/pull/1488.diff","patch_url":"https://github.com/networkx/networkx/pull/1488.patch","issue_url":"https://api.github.com/repos/networkx/networkx/issues/1488","number":1488,"state":"open","locked":false,"title":"Added euler path for Graphs, Digraphs and Multigraphs","user":{"login":"edwardo2013","id":4259541,"avatar_url":"https://avatars.githubusercontent.com/u/4259541?v=3","gravatar_id":"","url":"https://api.github.com/users/edwardo2013","html_url":"https://github.com/edwardo2013","followers_url":"https://api.github.com/users/edwardo2013/followers","following_url":"https://api.github.com/users/edwardo2013/following{/other_user}","gists_url":"https://api.github.com/users/edwardo2013/gists{/gist_id}","starred_url":"https://api.github.com/users/edwardo2013/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/edwardo2013/subscriptions","organizations_url":"https://api.github.com/users/edwardo2013/orgs","repos_url":"https://api.github.com/users/edwardo2013/repos","events_url":"https://api.github.com/users/edwardo2013/events{/privacy}","received_events_url":"https://api.github.com/users/edwardo2013/received_events","type":"User","site_admin":false},"body":"We added the file find_euler_path.py which has an implementation of the euler path algorithm. It is general: It works for Graphs, Digraphs and Multigraphs. We added some tests after the function. It uses the eulerian_circuit() function, which is implemented in euler.py . We make the comments following the aforementioned file.\r\n\r\nPlease tell us is this is the way to document the function. If not, provide information/files to add the required documentation.\r\n\r\nAbout the code: the function receives a networkx graph G. If G is eulerian, then just returns the eulerian circuit. If not, then verify degree condition of nodes to see if it has an euler path. If it does not have it, raise an error. Then, at line 145 the code to find the euler path is given (this works because we know that we have the conditions to have an euler path). It returns a generator which has the euler path. \r\n\r\nPlease review this code, we would be happy to see it merged in the networkx project. Please let us know if some changes must be made (emails are in the file) or if it is posible to make the code more compact.\r\n\r\nThanks,\r\nEdwardo S. Rivera\r\n ","created_at":"2015-04-28T18:26:26Z","updated_at":"2015-04-30T13:54:06Z","closed_at":null,"merged_at":null,"merge_commit_sha":"563c63e17e2100877b70de4b127e16f3d77629e2","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/networkx/networkx/pulls/1488/commits","review_comments_url":"https://api.github.com/repos/networkx/networkx/pulls/1488/comments","review_comment_url":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}","comments_url":"https://api.github.com/repos/networkx/networkx/issues/1488/comments","statuses_url":"https://api.github.com/repos/networkx/networkx/statuses/64c4b69a9cc79b13cd595b38e8bc01b6d79d7b2a","head":{"label":"edwardo2013:add-euler-path","ref":"add-euler-path","sha":"64c4b69a9cc79b13cd595b38e8bc01b6d79d7b2a","user":{"login":"edwardo2013","id":4259541,"avatar_url":"https://avatars.githubusercontent.com/u/4259541?v=3","gravatar_id":"","url":"https://api.github.com/users/edwardo2013","html_url":"https://github.com/edwardo2013","followers_url":"https://api.github.com/users/edwardo2013/followers","following_url":"https://api.github.com/users/edwardo2013/following{/other_user}","gists_url":"https://api.github.com/users/edwardo2013/gists{/gist_id}","starred_url":"https://api.github.com/users/edwardo2013/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/edwardo2013/subscriptions","organizations_url":"https://api.github.com/users/edwardo2013/orgs","repos_url":"https://api.github.com/users/edwardo2013/repos","events_url":"https://api.github.com/users/edwardo2013/events{/privacy}","received_events_url":"https://api.github.com/users/edwardo2013/received_events","type":"User","site_admin":false},"repo":{"id":33684016,"name":"networkx","full_name":"edwardo2013/networkx","owner":{"login":"edwardo2013","id":4259541,"avatar_url":"https://avatars.githubusercontent.com/u/4259541?v=3","gravatar_id":"","url":"https://api.github.com/users/edwardo2013","html_url":"https://github.com/edwardo2013","followers_url":"https://api.github.com/users/edwardo2013/followers","following_url":"https://api.github.com/users/edwardo2013/following{/other_user}","gists_url":"https://api.github.com/users/edwardo2013/gists{/gist_id}","starred_url":"https://api.github.com/users/edwardo2013/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/edwardo2013/subscriptions","organizations_url":"https://api.github.com/users/edwardo2013/orgs","repos_url":"https://api.github.com/users/edwardo2013/repos","events_url":"https://api.github.com/users/edwardo2013/events{/privacy}","received_events_url":"https://api.github.com/users/edwardo2013/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/edwardo2013/networkx","description":"Official NetworkX source code repository.  ","fork":true,"url":"https://api.github.com/repos/edwardo2013/networkx","forks_url":"https://api.github.com/repos/edwardo2013/networkx/forks","keys_url":"https://api.github.com/repos/edwardo2013/networkx/keys{/key_id}","collaborators_url":"https://api.github.com/repos/edwardo2013/networkx/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/edwardo2013/networkx/teams","hooks_url":"https://api.github.com/repos/edwardo2013/networkx/hooks","issue_events_url":"https://api.github.com/repos/edwardo2013/networkx/issues/events{/number}","events_url":"https://api.github.com/repos/edwardo2013/networkx/events","assignees_url":"https://api.github.com/repos/edwardo2013/networkx/assignees{/user}","branches_url":"https://api.github.com/repos/edwardo2013/networkx/branches{/branch}","tags_url":"https://api.github.com/repos/edwardo2013/networkx/tags","blobs_url":"https://api.github.com/repos/edwardo2013/networkx/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/edwardo2013/networkx/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/edwardo2013/networkx/git/refs{/sha}","trees_url":"https://api.github.com/repos/edwardo2013/networkx/git/trees{/sha}","statuses_url":"https://api.github.com/repos/edwardo2013/networkx/statuses/{sha}","languages_url":"https://api.github.com/repos/edwardo2013/networkx/languages","stargazers_url":"https://api.github.com/repos/edwardo2013/networkx/stargazers","contributors_url":"https://api.github.com/repos/edwardo2013/networkx/contributors","subscribers_url":"https://api.github.com/repos/edwardo2013/networkx/subscribers","subscription_url":"https://api.github.com/repos/edwardo2013/networkx/subscription","commits_url":"https://api.github.com/repos/edwardo2013/networkx/commits{/sha}","git_commits_url":"https://api.github.com/repos/edwardo2013/networkx/git/commits{/sha}","comments_url":"https://api.github.com/repos/edwardo2013/networkx/comments{/number}","issue_comment_url":"https://api.github.com/repos/edwardo2013/networkx/issues/comments{/number}","contents_url":"https://api.github.com/repos/edwardo2013/networkx/contents/{+path}","compare_url":"https://api.github.com/repos/edwardo2013/networkx/compare/{base}...{head}","merges_url":"https://api.github.com/repos/edwardo2013/networkx/merges","archive_url":"https://api.github.com/repos/edwardo2013/networkx/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/edwardo2013/networkx/downloads","issues_url":"https://api.github.com/repos/edwardo2013/networkx/issues{/number}","pulls_url":"https://api.github.com/repos/edwardo2013/networkx/pulls{/number}","milestones_url":"https://api.github.com/repos/edwardo2013/networkx/milestones{/number}","notifications_url":"https://api.github.com/repos/edwardo2013/networkx/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/edwardo2013/networkx/labels{/name}","releases_url":"https://api.github.com/repos/edwardo2013/networkx/releases{/id}","created_at":"2015-04-09T17:58:49Z","updated_at":"2015-04-09T17:58:51Z","pushed_at":"2015-04-28T18:03:56Z","git_url":"git://github.com/edwardo2013/networkx.git","ssh_url":"git@github.com:edwardo2013/networkx.git","clone_url":"https://github.com/edwardo2013/networkx.git","svn_url":"https://github.com/edwardo2013/networkx","homepage":"http://networkx.github.io","size":12600,"stargazers_count":0,"watchers_count":0,"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":0,"default_branch":"placeholder"}},"base":{"label":"networkx:master","ref":"master","sha":"38b9ba5dfef7f5d702e450e82e493d6dc4dc67cb","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-04-30T01:01:05Z","pushed_at":"2015-04-29T23:08:21Z","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":22692,"stargazers_count":1361,"watchers_count":1361,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":430,"mirror_url":null,"open_issues_count":188,"forks":430,"open_issues":188,"watchers":1361,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1488"},"html":{"href":"https://github.com/networkx/networkx/pull/1488"},"issue":{"href":"https://api.github.com/repos/networkx/networkx/issues/1488"},"comments":{"href":"https://api.github.com/repos/networkx/networkx/issues/1488/comments"},"review_comments":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1488/comments"},"review_comment":{"href":"https://api.github.com/repos/networkx/networkx/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/networkx/networkx/pulls/1488/commits"},"statuses":{"href":"https://api.github.com/repos/networkx/networkx/statuses/64c4b69a9cc79b13cd595b38e8bc01b6d79d7b2a"}}}}