graph = {1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1]}

graph

"""
Explanation: Eulerian path
Humberto Ortiz-Zuazaga
Introduction
To actually find an Eulerian path in a graph requires a bit more work than checking if the path exists. I'll present some example code and present an algorithm, and you should convert the algorithm to working code.
Here's the graph from last assignment.
End of explanation
"""


import copy
g2 = copy.deepcopy(graph)

g2

"""
Explanation: Copying graphs
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.
End of explanation
"""


g2[1].remove(2)

g2

"""
Explanation: Removing edges
If we want to remove the edge between node 1 and 2 in the graph g2, we can use remove:
End of explanation
"""


g2[2].remove(1)

g2

"""
Explanation: 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:
End of explanation
"""


graph

"""
Explanation: We can check to make sure we haven't mangled the original graph by accident.
End of explanation
"""


g2 = copy.deepcopy(graph)

def remove_edge(G, v1, v2):
    ## You write the code to delete the edge, instead of `pass`
    pass

"""
Explanation: Exercise: remove_edge
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.
End of explanation
"""


remove_edge(g2, 3, 2)
g2

graph

g2

"""
Explanation: When you write your code, this next block should work correctly:
End of explanation
"""


shortpath = []

shortpath.append(2)
shortpath.append(3)
shortpath.append(1)

shortpath

"""
Explanation: Representing paths
We can represent paths as lists (of vertices), so we can build a path by appending vertices to a list.
End of explanation
"""


stack = []

"""
Explanation: Python data structure: stack
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.
End of explanation
"""


stack.append("North")

stack.append("East")

"""
Explanation: We can add an element to the stack with append.
End of explanation
"""


stack[-1]

"""
Explanation: We can peek at the top of the stack using list syntax. This examines, but does not remove an element from the stack.
End of explanation
"""


stack.pop()

"""
Explanation: The pop() operation removes an element from the stack and returns it.
End of explanation
"""


stack[-1]

stack.pop()

stack

"""
Explanation: After poping 'East' from the stack, the top of the stack is now 'North'.
End of explanation
"""


if stack:
    print("stack has stuff")
else:
    print("stack has no stuff")

"""
Explanation: An empty stack is a false in logical expressions:
End of explanation
"""


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

"""
Explanation: Assignment: find_path
Define a function find_path(G) that finds and returns an Eulerian path through a graph G if it exists. I'll provide an algorithm and some comments, you need to complete the function body.
End of explanation
"""


find_path(graph)

"""
Explanation: 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.
End of explanation
"""


sevenbridges = {}
sevenbridges["North"] = ["West", "West", "East"]
sevenbridges["East"] = ["North", "South", "West"]
sevenbridges["South"] = ["West", "West", "East"]
sevenbridges["West"] = ["North", "North", "South", "South", "East"]

find_path(sevenbridges)

"""
Explanation: As a counterexample, the Seven Bridges graph has no Eulerian path. Your function should complain, or at least not find a path.
End of explanation
"""


