After struggling for a long while on this through the algorithms course on Udacity, I finally understood enough of the concept to develop this implementation. However, it lacks efficiency and finesse. Would love some feedback on how to improve this and what it might be getting wrong about the concept of graphs, tours/paths, and depth-first search. The code is heavily commented, but let me know if you have any questions.
I lumped the graphs into three types and figured out how to solve each one and combined it in this implementation while adding the ability to make random permutations.
Intuitively, I think the "Simple" (all even nodes of degree 2) graphs would require O(E) to solve because the graph losses an edge every iteration. Then the depth-first search implementation...is not ideal. My intuition is that in the worst case (each of the initial node/edges traversed are exactly the wrong ones) this would require O([E*(E-1)]/2) because there must be a bound on on how deep it has to go before finding out that it as to backtrack. Given the initial checks, there is a tour/path there, so it will eventually find it. The last type of graph uses DFS plus some constant. Also, the algorithm tries to fall back on the "simple" graph solution when it can, so that makes the average case a little better. As for best case, I'd say O(1) when it can't be done...haha, or maybe O(E) for simple graphs or graphs that decompose to a simple graph. I worked on having the algorithm work forwards and backwards for the 2 odd degrees graphs, (which has passed a number of tests) because I didn't think those graphs could be solved as a simple graph because it would never get there. Not sure how to account for that in my conception of complexity...I feel like it would probably cause more issues in the limit than not...
Also, there is at least one graph that I found it doesn't work for: [(1, 2), (2, 3), (3, 2)], which is solvable - and it does tend to find the right answer. Any others?
Appreciate the feedback and corrections.
#!/bin/python/
import sys
import random
from queue import Queue
from threading import Thread
class Graph_Traveler(Thread):
def __init__(self, queue, graph, path, start, tag):
Thread.__init__(self)
self.tag = tag
self.queue = queue
self.graph = graph[:]
self.start_node = start
if len(path) == 0:
self.path = [start]
else:
self.path = path[:]
def run(self):
graph_cache, path_cache = self.graph[:], self.path[:]
while True:
if self.queue.empty() and len(graph_cache) == 0:
self.queue.task_done()
for edge in self.queue.get():
if type(edge) == int:
continue
if self.start_node not in edge:
self.queue.put(edge)
else:
ddegrees = get_graph_info(graph_cache, nodes = False)
curr_idx = edge.index(path_cache[-1])
node = edge[curr_idx ^ 1]
path_cache.append(node)
graph_cache, path_cache = dfs_traversal(graph_cache,
node, path_cache, ddegrees)
if check_path_issues(path_cache):
# Reset progress and move on to next node
path_cache = self.path[:]
graph_cache = self.graph[:]
continue
else:
# Search has succesfully from the starting point 'node'
#self.queue.put(1)
self.queue.put(self.path)
#print(self.path)
if self.queue.empty():
self.queue.task_done()
else:
continue
def find_eulerian_tour(graph, path = None):
"""Given a list of tuples representing a graph,
return the eulerian tour on that graph as a list of the nodes.
Failing that, return the eulerian path.
This implementation includes random permutations depending on the graph
or it returns 'No possible eulerian tour' if there is no possible path or
this algorithm cannot yet handle that.
Primarily works by segmenting the incoming graph into different types and
then calling different recursive algorithms depending on the type.
OEO graphs (or Odd-Even-Odd graphs) are graphs that initially have two odd
degree nodes and any number of even degree nodes. In order to make this a
tour, these will begin with one of the odd nodes and then use
the other general algorithms
Simple graphs are graphs that have all degree two nodes. These are easily
solved as a tour by following the edges. The algorithms check if the
graphs have reduced to this one and try more easily/quickly solve them.
Looped graphs are any graphs that at least one even degree node that is
larger than two. These graphs have a loop that is not as easy to solve
as the simple graphs. A breath-first search algorithm is used for to solve
these, but it also checks if the graph has reduced to a simple graph
and applies that.
Althought this is a path and not a tour algorithm, it had to be named this
way for a project that was submitted. For intitially even graphs,
it will always produce a tour.
"""
# Base case
if path and not graph:
return path
search_graph = graph[:]
ddegrees, even_nodes, odd_nodes = get_graph_info(search_graph)
if path == None:
if not is_eulerian(ddegrees):
return "No possible eulerian tour" #Or not yet for some...
# Case: OEO Graph{guaranteed to end on Odd node}
if odd_nodes:
start_node = odd_nodes[random.randint(0, 1)] #there's ever only 2 initially
edge, curr_node = find_edge_alg(search_graph, start_node, ddegrees)
search_graph, path = update(graph, path, edge,
curr_node ^ 1, curr_node)
end_node = odd_nodes[odd_nodes.index(start_node) ^ 1]
queue = Queue(maxsize=0)
goals = [start_node, end_node]
paths = [path[:], []]
tag = ['a', 'b']
for ii in range(2):
walker = Graph_Traveler(queue, search_graph[:], paths[ii], goals[ii], tag[ii])
walker.daemon = True
walker.start()
for edge in graph:
queue.put(edge)
else:
path = []
else:
# Case: Simple Graph
if is_simple_graph(ddegrees):
search_graph, path = solve_simple_graph(search_graph, path)
else:
# Case: Looped Graph
if is_looped(ddegrees):
search_graph, path = solve_looped_graph(search_graph, path)
else:
current = path[-1]
edge, curr_node = \
find_edge_alg(search_graph, current, ddegrees)
assert edge != None
if len(path) < 1:
both_idx = curr_node
else:
both_idx = None
search_graph, path = \
update(search_graph, path, edge,
curr_node ^ 1, both_idx)
path = find_eulerian_tour(search_graph, path)
return path
#
## Algorithm for solving looped graphs with a Depth-First Search
#
def is_looped(ddegrees):
"""Check if graph is looped.
Any even node with degree greather than 2"""
counts = list(set(get_counts_from_dict(ddegrees)))
loop_num = [count for count in counts
if count % 2 == 0 and count not in [0, 2]]
return len(loop_num) > 0
def solve_looped_graph(looped_graph, path):
"""Depth-First search through the state space of the looped graphs
See is_looped for a definition
Recursive implementation of the helper function dfs_traversal, where most
of the work is done.
Initialize the path list for initially even-node looped graphs and
is main level of interaction between dfs_traversal and other functions.
Checks if graph has become a simple graph and uses that to solve the rest"""
start = False
search_graph = looped_graph[:]
dfs_path = path[:]
if len(path) > 0:
curr_node = path[-1]
else:
start = True
ddegrees = get_graph_info(search_graph, nodes = False)
# Solve simple graph
if is_simple_graph(ddegrees):
search_graph, path = solve_simple_graph(search_graph, path)
if start:
#Initializes search for initially even looped graphs
nodes = list(ddegrees.keys())
random.shuffle(nodes)
for node in nodes:
search_graph, dfs_path = dfs_traversal(search_graph, node,
dfs_path, ddegrees, start)
if check_path_issues(dfs_path):
# Reset progress and move on to next node
dfs_path = path[:]
search_graph = looped_graph[:]
continue
else:
# Search has succesfully from the starting point 'node'
break
else:
#This generally initializes the dfs_traversal for all
#OEO graphs that are looped
search_graph, dfs_path = dfs_traversal(search_graph, curr_node,
dfs_path, ddegrees)
return search_graph, dfs_path
def dfs_traversal(search_graph, curr_node, path, ddegrees, intialize = False):
"""Performs Breatdh-First Search traversal of the graph
Most of the power of the looped graph solver lies here.
Initializes the path list if it hasn't been initialized via [initialize]
In each iteration, it produces a copy of the path and graph after checking
for the base case.
Attempts to solve simple graph if possible
Otherwise, randomly traverses through the nodes of the graph via the edges
until it encounters an empty list of edges from that node or
complete explores the nodes from that node without any success.
The first is done by checking for an empty edge_list retrun.
The second is done by checking if the whole list of nodes from the current
node were exhausted without adding anything to the path.
(Additionally, could be done via a non-empty graph or identical graph -
as that is also part of the base case.)"""
#Base case
if path and not search_graph:
return search_graph, path
if check_path_issues(path):
path.append(None)
return [], path
#initialize temp vars to re-set progress
dfs_graph = search_graph[:]
dfs_path = path[:]
if is_simple_graph(ddegrees): #Solve simple graph
dfs_graph, dfs_path = solve_simple_graph(dfs_graph, dfs_path)
else:
edge_list = find_edge_alg(dfs_graph, curr_node, ddegrees,
return_edges = True)
if len(edge_list) == 0:
path.append(None) #No more arcs from here
return [], path
random.shuffle(edge_list)
#indicies for the current node for all its edges
curr_idx_list = [edge.index(curr_node) for edge in edge_list]
#list of to_nodes to explore (this is the frontier)
nodes = [edge[idx ^ 1] for idx, edge in zip(curr_idx_list, edge_list)]
for idx, node in enumerate(nodes):
edge = edge_list[idx]
to_node_idx = curr_idx_list[idx] ^ 1
#Initialize dfs_path
if intialize:
both_idx = curr_idx_list[idx]
else:
both_idx = None
dfs_graph, dfs_path = update(dfs_graph, dfs_path, edge,
to_node_idx, both_idx)
#Main recursive call to this function
#If a graph or path make it past here, they are either the solution
#or they mean we should move on
dfs_graph, dfs_path = dfs_traversal(dfs_graph, node,
dfs_path, ddegrees)
if check_path_issues(dfs_path):
#Reinitialize graph and path list and re-start search
dfs_path = path[:]
dfs_graph = search_graph[:]
continue
else:
#if the recursion ended and the path list has no issues,
#we break out of the loop to check another condition
#which will bring us out even further back up the graph
break
if dfs_path == path and idx == len(nodes) - 1:
#if the loop over the frontier/nodes ended without the
#path list changing, we should move up a level (or go back)
path.append(None)
return [], path
return dfs_graph, dfs_path
def check_path_issues(path):
"""Helper function to test the condition of the path list
Looks for a None in the path list to indicate that there is nothing
more to explore from there"""
return (path == None) or (type(path) == list and None in path)
#
## Algorithm for solving the simple graph
#
def is_simple_graph(ddegrees):
"""Check if the graph is simple from its dictionary of counts:
All edges are of degree 2
Input: ddegrees"""
unique_counts = list(set(get_counts_from_dict(ddegrees)))
return len(unique_counts) == 1 and 2 in unique_counts
def solve_simple_graph(graph, path):
"""Main algorith used to solve a simple graph
Initializes the path list if it hasn't been initialized then moves
from one edge to the next removing each edge from a temporary graph
until the graph is empty"""
# Base case
if path and not graph:
return graph, path
simple_graph = graph[:] #Temp graph
if len(path) > 0:
curr_node = path[-1]
else:
rand_start = random.randint(0, len(graph)) - 1 #just to randomize
curr_node = graph[rand_start][0]
edge_idx = get_idx_of_edge(simple_graph, curr_node)
if edge_idx == None: #unsure if needed
return None
edge = simple_graph[edge_idx]
curr_node = edge.index(curr_node)
if len(path) < 1:
both_idx = curr_node #initializes path list to remove whole edge
else:
both_idx = None
simple_graph, path = \
update(simple_graph, path, edge, curr_node ^ 1, both_idx)
return solve_simple_graph(simple_graph, path)
#
## General Helper functions - used by most of the algorithms
#
def find_edge_alg(graph, curr_node, ddegrees, return_edges = False):
"""Given the current node, it returns the edge to traverse next.
Selects edge that leads to the largest degree node.
Input: graph, index for current node, ddegrees (count dictionary),
returning a list of edges
Returns: tuple of edges and the idx of current node
If no available edge found, returns empty list"""
edge_list = []
search_graph = graph[:]
random.shuffle(search_graph)
for edge in search_graph:
if curr_node in edge:
edge_list.append(edge)
if edge_list:
if return_edges:
return edge_list
return get_next(edge_list, curr_node, ddegrees)
return []
def get_next(edge_list, node, ddegrees):
"Given a list of possible edges, selects edge with highest degree node"
idx_list = [edge.index(node) for edge in edge_list]
count_list = [ddegrees[edge[idx]]
for edge, idx in zip(edge_list, idx_list)]
highest = max(count_list)
idx = count_list.index(highest)
edge = edge_list[idx]
idx = edge.index(node)
return edge, idx
#
## BASIC HELPER FUNCTIONS
#
def get_idx_of_edge(graph, node):
"""Given a graph and a node, return the index of the first edge that node
is found in. If not found, returns False.
Used for solving the simple graph"""
missing = True
for ii, edge in enumerate(graph):
if node in edge:
idx = ii
missing &= False
break
if not missing:
return idx
def update(graph, path, edge, to_pos, from_pos = None):
"""Updates important vars and returns an updated graph and path.
Input: to_pos is the idx of node moving to
[from_pos] if passed, path is updated with both from and to nodes
Used to initializing the path list"""
if from_pos != None:
path = [edge[from_pos], edge[to_pos]] #initialize path with both nodes
else:
path.append(edge[to_pos])
graph.pop(graph.index(edge)) #remove edge from graph
return graph, path
def get_counts_from_dict(ddegrees):
"""Returns the degrees of the nodes in a graph via the dictionary of counts
Input: ddegrees"""
return [ddegrees[node] for node in ddegrees.keys()]
def split_nodes(ddegrees):
"""Returns shuffled list of even and odd degree nodes in the most recently
counted graph
Input: ddegrees
"""
even_nodes = [node for node in ddegrees
if ddegrees[node] % 2 == 0 and ddegrees[node] != 0]
odd_nodes = [node for node in ddegrees
if ddegrees[node] % 2 == 1 and ddegrees[node] != 0]
random.shuffle(even_nodes)
random.shuffle(odd_nodes)
return even_nodes, odd_nodes
def get_degrees(graph):
"""Returns a dict with key value pairs {node: degree}
by counting the occurance of each node in the graph"""
nodes_from = [node[0] for node in graph]
nodes_to = [node[1] for node in graph]
nodes = nodes_from[:]
nodes.extend(nodes_to)
nodes = list(set(nodes))
ddegrees = {x: nodes_from.count(x) + nodes_to.count(x) for x in nodes}
return ddegrees
def get_graph_info(graph, nodes = True):
"Returns variables with information about the current graph"
ddegrees = get_degrees(graph)
if nodes:
even_nodes, odd_nodes = split_nodes(ddegrees)
return ddegrees, even_nodes, odd_nodes
return ddegrees
def is_eulerian(ddegrees):
""""Determines if a graph has Eularian path properties:
All even nodes or exactly two odd nodes
Input: ddegrees
Used here only on the initial graph's count dict
No node of degree 1 allowed at start"""
odd_degree = sum([ddegrees[node] % 2 != 0 for node in ddegrees])
counts = get_counts_from_dict(ddegrees)
return odd_degree in [0, 2] and 1 not in counts
#
## Unrellated functions and tests
#
def test(graph, n = 100):
"""Test algorithm on a graph for n permutations"""
matches = []
print('Running the following graph {} times.\n{}.'.format(n, graph))
for ii in range(n):
matches.append(test_tour(find_eulerian_tour(graph[:]), graph[:]))
print('The program successfully executed {} times.'.format(n))
print()
print('{} matches out of {}.\n\n'.format(sum(matches), n))
def make_graph(path):
"""Given a list of numbers that can represent a tour/path,
will return a graph of the edges"""
graph = []
ii = len(path) - 1
while ii > 0:
graph.append((path[ii], path[ii - 1]))
ii -= 1
return graph
def test_tour(path, graph, ret_graph = False):
"""Test if your tour/path actually matches the graph it came from.
It recreates a graph as a list of tuple edges from a list of numbers
that represents a tour/path. Checks if each edge is in the original graph.
It then removes that edge from the original graph and the reconstructed
graph. The test is passed if both graphs are empty at the end.
[ret_graph]: return a copy of the reconstructed graph"""
original_graph = graph[:]
temp_graph = make_graph(path)
if ret_graph:
reconstruced_graph = temp_graph[:]
to_del = []
for arc in temp_graph:
if arc in graph:
original_graph.pop(original_graph.index(arc))
to_del.append(arc)
else:
edge = (arc[1], arc[0])
if edge not in graph:
return False
else:
original_graph.pop(original_graph.index(edge))
to_del.append(arc)
for arc in to_del:
temp_graph.pop(temp_graph.index(arc))
passed = (len(original_graph) == 0) & (len(temp_graph) == 0)
if ret_graph:
return passed, reconstruced_graph
return passed
if __name__ == '__main__':
if len(sys.argv) > 1:
n = int(sys.argv[1])
print('\nWill run {} tests on each graph.\n'.format(n))
else:
n = 100
#Looped graph
t1 = [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9),
(2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]
#Looped graph
t2 = [(1, 13), (1, 6), (6, 11), (3, 13), (8, 13), (0, 6), (8, 9), (5, 9),
(2, 6), (6, 10), (7, 9), (1, 12), (4, 12), (5, 14), (0, 1), (2, 3),
(4, 11), (6, 9), (7, 14), (10, 13)]
#Looped graph with OEO form
t3 = t2[:]
t3.append((1, 4))
g = [(1, 2), (2, 3), (3, 2)] #Can't handle self loop with a temrinal yet
s1 = [(1, 2), (2, 3), (1, 3)] #Simple Graph
s2 = [(1, 2), (2, 3), (3, 4), (4, 1)] #Simple Graph
s3 = [(1, 2), (2, 3), (3, 4), (4, 1), (5, 1), (5, 2)] #OEO
#Big graph to test threading
t4 = t3[:]
for ii in range(6):
t4.extend(t3[:])
data = [t1, s1, s3, t3, s2, t2, g, t4]
for graph in data:
test(graph, n)
Eularianbothers me more than not capitalising Euler.) \$\endgroup\$