{"action":"created","comment":{"url":"https://api.github.com/repos/jacquestardie/data-structures/pulls/comments/25971437","id":25971437,"diff_hunk":"@@ -0,0 +1,113 @@\n+#! /usr/bin/env python\n+# -*- coding: utf-8 -*-\n+\n+import queue as queue\n+\n+\n+class Graph(object):\n+    '''Create a graph.'''\n+\n+    def __init__(self):\n+        '''Initialize a graph.'''\n+        self.graph = {}\n+\n+    def nodes(self):\n+        '''Return each node in the graph.'''\n+        return self.graph.keys()  # Returns all keys in our graph dictionary.\n+\n+    def edges(self):\n+        '''Return each edge in the graph.'''\n+\n+        ''' Learned about iteritems from Constantine, which makes this much\n+            simpler than it was otherwise. Could be a list comp, but this is\n+            easier to understand.\n+        '''\n+        for key, value in self.graph.iteritems():\n+            for item in value:\n+                return (key, item)\n+\n+    def add_node(self, node):\n+        '''Add a node to the graph.'''\n+        self.graph.setdefault(node, [])  # Insert unless already present.\n+\n+    def add_edge(self, first, second):\n+        '''Add an edge between two nodes.'''\n+\n+        self.graph.setdefault(first, [])  # Verify first node in graph.\n+\n+        if second not in self.graph:  # Verify second node in graph.\n+            self.add_node(second)\n+\n+        self.graph[first].append(second)\n+\n+    def del_edge(self, first, second):\n+        '''Remove an edge between two nodes.'''\n+        try:\n+            self.graph[first].remove(second)  # Only works if both present.\n+        except KeyError:\n+            raise KeyError('Node not in graph.')\n+        except ValueError:\n+            raise ValueError('Not a neighbor.')\n+\n+    def del_node(self, node):\n+        '''Remove a node from the graph.'''\n+        del self.graph[node]\n+\n+    def has_node(self, node):\n+        ''' Check if the the specified node is in the graph. If node exists,\n+            return True, otherwise return False.\n+        '''\n+        return node in self.graph\n+\n+    def neighbors(self, node):\n+        '''Return a node's neighbors.'''\n+        try:\n+            return self.graph[node]\n+        except KeyError:\n+            raise KeyError('Node not in graph.')\n+\n+    def adjacent(self, first, second):\n+        '''Check that two nodes share an edge.'''\n+        try:\n+            return second in self.graph[first]  # Returns a boolean.\n+        except KeyError:\n+            raise KeyError('Node not present in graph.')\n+\n+    def breadth_first_traversal(self, start):\n+        queue = [start]\n+        path = []\n+        visited = set()\n+        while queue:\n+            node = queue.pop()\n+            if node not in visited:\n+                visited.add(node)\n+                path.append(node)\n+                queue.extend(self.graph[node])\n+        return path","path":"graph_traversal.py","position":86,"original_position":86,"commit_id":"ceaf5dd203dd751d4a235f436a454b639af29694","original_commit_id":"ceaf5dd203dd751d4a235f436a454b639af29694","user":{"login":"cewing","id":417109,"avatar_url":"https://avatars.githubusercontent.com/u/417109?v=3","gravatar_id":"","url":"https://api.github.com/users/cewing","html_url":"https://github.com/cewing","followers_url":"https://api.github.com/users/cewing/followers","following_url":"https://api.github.com/users/cewing/following{/other_user}","gists_url":"https://api.github.com/users/cewing/gists{/gist_id}","starred_url":"https://api.github.com/users/cewing/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/cewing/subscriptions","organizations_url":"https://api.github.com/users/cewing/orgs","repos_url":"https://api.github.com/users/cewing/repos","events_url":"https://api.github.com/users/cewing/events{/privacy}","received_events_url":"https://api.github.com/users/cewing/received_events","type":"User","site_admin":false},"body":"Because you are using a list rather than a queue, the traversal you have here is not breadth-first, but depth first.  Your tests should show this.","created_at":"2015-03-06T19:39:17Z","updated_at":"2015-03-06T19:39:17Z","html_url":"https://github.com/jacquestardie/data-structures/pull/13#discussion_r25971437","pull_request_url":"https://api.github.com/repos/jacquestardie/data-structures/pulls/13","_links":{"self":{"href":"https://api.github.com/repos/jacquestardie/data-structures/pulls/comments/25971437"},"html":{"href":"https://github.com/jacquestardie/data-structures/pull/13#discussion_r25971437"},"pull_request":{"href":"https://api.github.com/repos/jacquestardie/data-structures/pulls/13"}}},"pull_request":{"url":"https://api.github.com/repos/jacquestardie/data-structures/pulls/13","id":30425412,"html_url":"https://github.com/jacquestardie/data-structures/pull/13","diff_url":"https://github.com/jacquestardie/data-structures/pull/13.diff","patch_url":"https://github.com/jacquestardie/data-structures/pull/13.patch","issue_url":"https://api.github.com/repos/jacquestardie/data-structures/issues/13","number":13,"state":"open","locked":false,"title":"Graph traversal","user":{"login":"alibulota","id":6208373,"avatar_url":"https://avatars.githubusercontent.com/u/6208373?v=3","gravatar_id":"","url":"https://api.github.com/users/alibulota","html_url":"https://github.com/alibulota","followers_url":"https://api.github.com/users/alibulota/followers","following_url":"https://api.github.com/users/alibulota/following{/other_user}","gists_url":"https://api.github.com/users/alibulota/gists{/gist_id}","starred_url":"https://api.github.com/users/alibulota/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alibulota/subscriptions","organizations_url":"https://api.github.com/users/alibulota/orgs","repos_url":"https://api.github.com/users/alibulota/repos","events_url":"https://api.github.com/users/alibulota/events{/privacy}","received_events_url":"https://api.github.com/users/alibulota/received_events","type":"User","site_admin":false},"body":"","created_at":"2015-03-03T23:52:30Z","updated_at":"2015-03-06T19:39:17Z","closed_at":null,"merged_at":null,"merge_commit_sha":"130f8d31a0a49f2042df5815f97a821e30190990","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/jacquestardie/data-structures/pulls/13/commits","review_comments_url":"https://api.github.com/repos/jacquestardie/data-structures/pulls/13/comments","review_comment_url":"https://api.github.com/repos/jacquestardie/data-structures/pulls/comments{/number}","comments_url":"https://api.github.com/repos/jacquestardie/data-structures/issues/13/comments","statuses_url":"https://api.github.com/repos/jacquestardie/data-structures/statuses/ceaf5dd203dd751d4a235f436a454b639af29694","head":{"label":"jacquestardie:graph_traversal","ref":"graph_traversal","sha":"ceaf5dd203dd751d4a235f436a454b639af29694","user":{"login":"jacquestardie","id":192642,"avatar_url":"https://avatars.githubusercontent.com/u/192642?v=3","gravatar_id":"","url":"https://api.github.com/users/jacquestardie","html_url":"https://github.com/jacquestardie","followers_url":"https://api.github.com/users/jacquestardie/followers","following_url":"https://api.github.com/users/jacquestardie/following{/other_user}","gists_url":"https://api.github.com/users/jacquestardie/gists{/gist_id}","starred_url":"https://api.github.com/users/jacquestardie/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jacquestardie/subscriptions","organizations_url":"https://api.github.com/users/jacquestardie/orgs","repos_url":"https://api.github.com/users/jacquestardie/repos","events_url":"https://api.github.com/users/jacquestardie/events{/privacy}","received_events_url":"https://api.github.com/users/jacquestardie/received_events","type":"User","site_admin":false},"repo":{"id":30314410,"name":"data-structures","full_name":"jacquestardie/data-structures","owner":{"login":"jacquestardie","id":192642,"avatar_url":"https://avatars.githubusercontent.com/u/192642?v=3","gravatar_id":"","url":"https://api.github.com/users/jacquestardie","html_url":"https://github.com/jacquestardie","followers_url":"https://api.github.com/users/jacquestardie/followers","following_url":"https://api.github.com/users/jacquestardie/following{/other_user}","gists_url":"https://api.github.com/users/jacquestardie/gists{/gist_id}","starred_url":"https://api.github.com/users/jacquestardie/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jacquestardie/subscriptions","organizations_url":"https://api.github.com/users/jacquestardie/orgs","repos_url":"https://api.github.com/users/jacquestardie/repos","events_url":"https://api.github.com/users/jacquestardie/events{/privacy}","received_events_url":"https://api.github.com/users/jacquestardie/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jacquestardie/data-structures","description":"Python-flavored data structures.","fork":false,"url":"https://api.github.com/repos/jacquestardie/data-structures","forks_url":"https://api.github.com/repos/jacquestardie/data-structures/forks","keys_url":"https://api.github.com/repos/jacquestardie/data-structures/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jacquestardie/data-structures/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jacquestardie/data-structures/teams","hooks_url":"https://api.github.com/repos/jacquestardie/data-structures/hooks","issue_events_url":"https://api.github.com/repos/jacquestardie/data-structures/issues/events{/number}","events_url":"https://api.github.com/repos/jacquestardie/data-structures/events","assignees_url":"https://api.github.com/repos/jacquestardie/data-structures/assignees{/user}","branches_url":"https://api.github.com/repos/jacquestardie/data-structures/branches{/branch}","tags_url":"https://api.github.com/repos/jacquestardie/data-structures/tags","blobs_url":"https://api.github.com/repos/jacquestardie/data-structures/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jacquestardie/data-structures/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jacquestardie/data-structures/git/refs{/sha}","trees_url":"https://api.github.com/repos/jacquestardie/data-structures/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jacquestardie/data-structures/statuses/{sha}","languages_url":"https://api.github.com/repos/jacquestardie/data-structures/languages","stargazers_url":"https://api.github.com/repos/jacquestardie/data-structures/stargazers","contributors_url":"https://api.github.com/repos/jacquestardie/data-structures/contributors","subscribers_url":"https://api.github.com/repos/jacquestardie/data-structures/subscribers","subscription_url":"https://api.github.com/repos/jacquestardie/data-structures/subscription","commits_url":"https://api.github.com/repos/jacquestardie/data-structures/commits{/sha}","git_commits_url":"https://api.github.com/repos/jacquestardie/data-structures/git/commits{/sha}","comments_url":"https://api.github.com/repos/jacquestardie/data-structures/comments{/number}","issue_comment_url":"https://api.github.com/repos/jacquestardie/data-structures/issues/comments{/number}","contents_url":"https://api.github.com/repos/jacquestardie/data-structures/contents/{+path}","compare_url":"https://api.github.com/repos/jacquestardie/data-structures/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jacquestardie/data-structures/merges","archive_url":"https://api.github.com/repos/jacquestardie/data-structures/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jacquestardie/data-structures/downloads","issues_url":"https://api.github.com/repos/jacquestardie/data-structures/issues{/number}","pulls_url":"https://api.github.com/repos/jacquestardie/data-structures/pulls{/number}","milestones_url":"https://api.github.com/repos/jacquestardie/data-structures/milestones{/number}","notifications_url":"https://api.github.com/repos/jacquestardie/data-structures/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jacquestardie/data-structures/labels{/name}","releases_url":"https://api.github.com/repos/jacquestardie/data-structures/releases{/id}","created_at":"2015-02-04T18:34:47Z","updated_at":"2015-03-01T20:02:41Z","pushed_at":"2015-03-04T01:04:43Z","git_url":"git://github.com/jacquestardie/data-structures.git","ssh_url":"git@github.com:jacquestardie/data-structures.git","clone_url":"https://github.com/jacquestardie/data-structures.git","svn_url":"https://github.com/jacquestardie/data-structures","homepage":"","size":440,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":4,"forks":0,"open_issues":4,"watchers":0,"default_branch":"master"}},"base":{"label":"jacquestardie:master","ref":"master","sha":"811d2ca74389a13cdf0c1d9e64d70b567155e922","user":{"login":"jacquestardie","id":192642,"avatar_url":"https://avatars.githubusercontent.com/u/192642?v=3","gravatar_id":"","url":"https://api.github.com/users/jacquestardie","html_url":"https://github.com/jacquestardie","followers_url":"https://api.github.com/users/jacquestardie/followers","following_url":"https://api.github.com/users/jacquestardie/following{/other_user}","gists_url":"https://api.github.com/users/jacquestardie/gists{/gist_id}","starred_url":"https://api.github.com/users/jacquestardie/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jacquestardie/subscriptions","organizations_url":"https://api.github.com/users/jacquestardie/orgs","repos_url":"https://api.github.com/users/jacquestardie/repos","events_url":"https://api.github.com/users/jacquestardie/events{/privacy}","received_events_url":"https://api.github.com/users/jacquestardie/received_events","type":"User","site_admin":false},"repo":{"id":30314410,"name":"data-structures","full_name":"jacquestardie/data-structures","owner":{"login":"jacquestardie","id":192642,"avatar_url":"https://avatars.githubusercontent.com/u/192642?v=3","gravatar_id":"","url":"https://api.github.com/users/jacquestardie","html_url":"https://github.com/jacquestardie","followers_url":"https://api.github.com/users/jacquestardie/followers","following_url":"https://api.github.com/users/jacquestardie/following{/other_user}","gists_url":"https://api.github.com/users/jacquestardie/gists{/gist_id}","starred_url":"https://api.github.com/users/jacquestardie/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jacquestardie/subscriptions","organizations_url":"https://api.github.com/users/jacquestardie/orgs","repos_url":"https://api.github.com/users/jacquestardie/repos","events_url":"https://api.github.com/users/jacquestardie/events{/privacy}","received_events_url":"https://api.github.com/users/jacquestardie/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jacquestardie/data-structures","description":"Python-flavored data structures.","fork":false,"url":"https://api.github.com/repos/jacquestardie/data-structures","forks_url":"https://api.github.com/repos/jacquestardie/data-structures/forks","keys_url":"https://api.github.com/repos/jacquestardie/data-structures/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jacquestardie/data-structures/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jacquestardie/data-structures/teams","hooks_url":"https://api.github.com/repos/jacquestardie/data-structures/hooks","issue_events_url":"https://api.github.com/repos/jacquestardie/data-structures/issues/events{/number}","events_url":"https://api.github.com/repos/jacquestardie/data-structures/events","assignees_url":"https://api.github.com/repos/jacquestardie/data-structures/assignees{/user}","branches_url":"https://api.github.com/repos/jacquestardie/data-structures/branches{/branch}","tags_url":"https://api.github.com/repos/jacquestardie/data-structures/tags","blobs_url":"https://api.github.com/repos/jacquestardie/data-structures/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jacquestardie/data-structures/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jacquestardie/data-structures/git/refs{/sha}","trees_url":"https://api.github.com/repos/jacquestardie/data-structures/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jacquestardie/data-structures/statuses/{sha}","languages_url":"https://api.github.com/repos/jacquestardie/data-structures/languages","stargazers_url":"https://api.github.com/repos/jacquestardie/data-structures/stargazers","contributors_url":"https://api.github.com/repos/jacquestardie/data-structures/contributors","subscribers_url":"https://api.github.com/repos/jacquestardie/data-structures/subscribers","subscription_url":"https://api.github.com/repos/jacquestardie/data-structures/subscription","commits_url":"https://api.github.com/repos/jacquestardie/data-structures/commits{/sha}","git_commits_url":"https://api.github.com/repos/jacquestardie/data-structures/git/commits{/sha}","comments_url":"https://api.github.com/repos/jacquestardie/data-structures/comments{/number}","issue_comment_url":"https://api.github.com/repos/jacquestardie/data-structures/issues/comments{/number}","contents_url":"https://api.github.com/repos/jacquestardie/data-structures/contents/{+path}","compare_url":"https://api.github.com/repos/jacquestardie/data-structures/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jacquestardie/data-structures/merges","archive_url":"https://api.github.com/repos/jacquestardie/data-structures/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jacquestardie/data-structures/downloads","issues_url":"https://api.github.com/repos/jacquestardie/data-structures/issues{/number}","pulls_url":"https://api.github.com/repos/jacquestardie/data-structures/pulls{/number}","milestones_url":"https://api.github.com/repos/jacquestardie/data-structures/milestones{/number}","notifications_url":"https://api.github.com/repos/jacquestardie/data-structures/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jacquestardie/data-structures/labels{/name}","releases_url":"https://api.github.com/repos/jacquestardie/data-structures/releases{/id}","created_at":"2015-02-04T18:34:47Z","updated_at":"2015-03-01T20:02:41Z","pushed_at":"2015-03-04T01:04:43Z","git_url":"git://github.com/jacquestardie/data-structures.git","ssh_url":"git@github.com:jacquestardie/data-structures.git","clone_url":"https://github.com/jacquestardie/data-structures.git","svn_url":"https://github.com/jacquestardie/data-structures","homepage":"","size":440,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":4,"forks":0,"open_issues":4,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/jacquestardie/data-structures/pulls/13"},"html":{"href":"https://github.com/jacquestardie/data-structures/pull/13"},"issue":{"href":"https://api.github.com/repos/jacquestardie/data-structures/issues/13"},"comments":{"href":"https://api.github.com/repos/jacquestardie/data-structures/issues/13/comments"},"review_comments":{"href":"https://api.github.com/repos/jacquestardie/data-structures/pulls/13/comments"},"review_comment":{"href":"https://api.github.com/repos/jacquestardie/data-structures/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/jacquestardie/data-structures/pulls/13/commits"},"statuses":{"href":"https://api.github.com/repos/jacquestardie/data-structures/statuses/ceaf5dd203dd751d4a235f436a454b639af29694"}}}}