Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Eulerian Tour Ver 1
- #
- # Write a function, `create_tour` that takes as
- # input a list of nodes
- # and outputs a list of tuples representing
- # edges between nodes that have an Eulerian tour.
- #
- def create_tour(nodes):
- # your code here
- return []
- #########
- def get_degree(tour):
- degree = {}
- for x, y in tour:
- degree[x] = degree.get(x, 0) + 1
- degree[y] = degree.get(y, 0) + 1
- return degree
- def check_edge(t, b, nodes):
- """
- t: tuple representing an edge
- b: origin node
- nodes: set of nodes already visited
- if we can get to a new node from `b` following `t`
- then return that node, else return None
- """
- if t[0] == b:
- if t[1] not in nodes:
- return t[1]
- elif t[1] == b:
- if t[0] not in nodes:
- return t[0]
- return None
- def connected_nodes(tour):
- """return the set of nodes reachable from
- the first node in `tour`"""
- a = tour[0][0]
- nodes = set([a])
- explore = set([a])
- while len(explore) > 0:
- # see what other nodes we can reach
- b = explore.pop()
- for t in tour:
- node = check_edge(t, b, nodes)
- if node is None:
- continue
- nodes.add(node)
- explore.add(node)
- return nodes
- def is_eulerian_tour(nodes, tour):
- # all nodes must be even degree
- # and every node must be in graph
- degree = get_degree(tour)
- for node in nodes:
- try:
- d = degree[node]
- if d % 2 == 1:
- print "Node %s has odd degree" % node
- return False
- except KeyError:
- print "Node %s was not in your tour" % node
- return False
- connected = connected_nodes(tour)
- if len(connected) == len(nodes):
- return True
- else:
- print "Your graph wasn't connected"
- return False
- def test():
- nodes = [20, 21, 22, 23, 24, 25]
- tour = create_tour(nodes)
- return is_eulerian_tour(nodes, tour)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement