Implement a Graph in Python

Read a bit about the Graph data structure.

Tasks

Once you have a grasp of the basic idea, implement a simple graph (unweighted, directed) in Python. You may use any of the Python primitive data types that are available without importing any additional libraries (str, unicode, dict, list, tuple).

Your graph should support the following operations:

  • g.nodes(): return a list of all nodes in the graph
  • g.edges(): return a list of all edges in the graph
  • g.add_node(val): adds a new node with value ‘n’ to the graph
  • g.add_edge(val1, val2): adds a new edge to the graph connecting the node containing ‘val1’ and the node containing ‘val2’. If either val1 or val2 are not already present in the graph, they should be added. If an edge already exists, overwrite it.
  • g.del_node(val): deletes the node containing ‘val’ from the graph; raises an error if no such node exists
  • g.del_edge(val1, val2): deletes the edge connecting ‘val1’ and ‘val2’ from the graph; raises an error if no such edge exists
  • g.has_node(val): True if node containing ‘val’ is contained in the graph, False if not.
  • g.neighbors(val): returns the list of all nodes connected to the node containing ‘val’ by edges; raises an error if val is not in g
  • g.adjacent(val1, val2): returns True if there is an edge connecting val1 and val2, False if not; raises an error if either of the supplied values are not in g

Begin by creating a new branch graph_1 in your data-structures repository. For each method of your graph class (including the constructor), write tests first that demonstrates the functionality of that method, then implement the method to make the tests pass.

Focus on making small, atomic commits to git with well-written and meaningful commit messages.

Remember to update your README file with a description of this new data type as well as any additional sources, references or collaborations you may have used in completing the work. It is a requirement that for each method of this data structure, you include in the README a description of its time complexity in Big-O notation! Expect to lose credit if you don’t have this.

Submitting Your Work

When your work is complete and all tests are passing, push your work to github and issue a Pull Request to your master branch. Submit the URL for your pull request. After this is complete, you may merge your work to master.

As usual, use the comments function in canvas to submit questions, comments and reflections on this work.