Here's the graph from last assignment.
In [1]:
graph = {1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1]}
In [2]:
graph
Out[2]:
If we want to make changes to the structure of the graph, but want to keep the original, we need to make a copy. Since we used dictionaries to construct the graph, we need to be careful how we copy the graph. In particular, we need to make a "deep copy", that builds a new graph with the same structure, instead of just simple assignment (in particular, g2 = graph would not work, it's like using a nickname). We can make a deep copy using the copy module.
In [3]:
import copy
g2 = copy.deepcopy(graph)
In [4]:
g2
Out[4]:
In [5]:
g2[1].remove(2)
In [6]:
g2
Out[6]:
Note that node 2 was removed from node 1's neighbor list, but node 1 is still in node 2's neighbor list. To really delete the edge, we need to delete the remaining neighbor:
In [7]:
g2[2].remove(1)
In [8]:
g2
Out[8]:
We can check to make sure we haven't mangled the original graph by accident.
In [9]:
graph
Out[9]:
I'm going to make a new copy of the graph, and you should write a function, remove_edge(G, v1, v2), that deletes the v1-v2 edge in graph G.
In [10]:
g2 = copy.deepcopy(graph)
In [11]:
def remove_edge(G, v1, v2):
## You write the code to delete the edge, instead of `pass`
pass
When you write your code, this next block should work correctly:
In [12]:
remove_edge(g2, 3, 2)
g2
Out[12]:
In [13]:
graph
Out[13]:
In [14]:
g2
Out[14]:
In [15]:
shortpath = []
In [16]:
shortpath.append(2)
shortpath.append(3)
shortpath.append(1)
In [17]:
shortpath
Out[17]:
Sometimes we want to keep track of some computation done during a program. Many times in this course we have used recursion to keep track of what we have done and what remains. Recursion uses a function call stack to keep track of partial results. Another way of keeping track is to use an explicit stack. A stack is a data structure with two operations, push puts an additional element on the stack, and pop removes an element from the stack. In python we can implement stacks with python lists.
In [18]:
stack = []
We can add an element to the stack with append.
In [19]:
stack.append("North")
In [20]:
stack.append("East")
We can peek at the top of the stack using list syntax. This examines, but does not remove an element from the stack.
In [21]:
stack[-1]
Out[21]:
The pop() operation removes an element from the stack and returns it.
In [22]:
stack.pop()
Out[22]:
After poping 'East' from the stack, the top of the stack is now 'North'.
In [23]:
stack[-1]
Out[23]:
In [24]:
stack.pop()
Out[24]:
In [25]:
stack
Out[25]:
An empty stack is a false in logical expressions:
In [26]:
if stack:
print("stack has stuff")
else:
print("stack has no stuff")
In [27]:
def find_path(G):
"Find an Eulerian path through G."
path = []
# Check if G has an Eulerian path or exit
# make a copy of G (from now on work on the copy)
# Choose a starting vertex
# Push starting vertex onto stack
# while items remain on the stack:
# set current vertex to top of stack
# if current vertex has edges
# put neighbor on stack
# remove edge from current vertex to neighbor
# else
# append current vertex to path
# pop current vertex from stack
return path
Upon sucessfull completion of your homework, this should return a valid Eulerian path through the graph, like [1 ,2, 3, 1, 4]. There are multiple valid Eulerian paths through this graph, you don't have to find exactly the one in the example.
In [28]:
find_path(graph)
Out[28]:
As a counterexample, the Seven Bridges graph has no Eulerian path. Your function should complain, or at least not find a path.
In [29]:
sevenbridges = {}
sevenbridges["North"] = ["West", "West", "East"]
sevenbridges["East"] = ["North", "South", "West"]
sevenbridges["South"] = ["West", "West", "East"]
sevenbridges["West"] = ["North", "North", "South", "South", "East"]
In [30]:
find_path(sevenbridges)
Out[30]: