Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Graph Object solution in Clear category for What Is Wrong With This Family? by dobyvillanueva
class Graph(object):
def __init__(self, input_graph={}):
self.graph = {}
if input_graph:
for vertex in input_graph:
self.add_vertex(vertex)
self.foo = [[self.add_edge(vertex, neighbor) for neighbor in input_graph[vertex] ] for vertex in input_graph]
def show(self):
return self.graph
def vertices(self):
return [vertex for vertex in self.graph]
def add_vertex(self,vertex):
if vertex not in self.graph.keys():
self.graph.update({vertex:[]})
def del_vertex(self, vertex):
if vertex in self.graph.keys():
self.graph.pop(vertex)
self.foo = [self.graph[key].remove(vertex) for key, value in self.graph.iteritems() if vertex in self.graph[key]]
def edges(self):
self.edges = set()
self.foo = [[self.edges.add(tuple(sorted((key,item)))) for item in self.graph[key]] for key in self.graph]
return self.edges
def add_edge(self, start, end):
# add vertices if not present
if start not in self.graph.keys():
self.graph[start]=[]
if end not in self.graph.keys():
self.graph[end]=[]
# add edges if not present
if end not in self.graph[start]:
self.graph[start].append(end)
if start not in self.graph[end]:
self.graph[end].append(start)
def del_edge(self,start,end):
if start in self.graph.keys() and end in self.graph.keys():
self.foo = [self.graph[key].remove(start) for key, value in self.graph.iteritems() if start in self.graph[key]]
self.bar = [self.graph[key].remove(end) for key, value in self.graph.iteritems() if end in self.graph[key]]
def is_connected(self, start, end, path=[]): # working 11/26/2017
# checks
if start not in self.graph.keys() or end not in self.graph.keys():
return False
if start == end:
return True
path = path + [start]
# Using DFS
for node in self.graph[start]:
if node not in path:
if self.is_connected(node,end, path):
return True
return False
def find_shortest_path(self, start, end, path=[]): #working 11/29/2017
path = path + [start]
if start == end:
return path
if start not in self.graph.keys():
return []
if not self.is_connected(start,end):
return []
self.shortest = None
for node in self.graph[start]:
if node not in path:
self.newpath = self.find_shortest_path(node, end, path)
if self.newpath:
if not self.shortest or len(self.newpath) < len(self.shortest):
self.shortest = self.newpath
return self.shortest
def find_all_paths(self, start, end, path=[]): #working 11/26/2017
path = path + [start]
if start == end:
return [path]
if start not in self.graph.keys() or end not in self.graph.keys():
return []
paths = []
for node in self.graph[start]:
if node not in path:
paths.extend(self.find_all_paths(node, end, path))
return paths
def find_all_sub_graphs(self):
self.sub_graphs=[]
self.reached_nodes = set()
for self.node in sorted(self.vertices()):
if self.node not in self.reached_nodes:
self.reach = self.bfs(self.node)
self.foo = [self.reached_nodes.add(n) for n in self.reach]
self.sub_graphs.append(self.reach)
return self.sub_graphs
# Graph traversal algorithms
def bfs(self, start): # breadth-first search algorithm
self.visited = []
self.queue = [start] # initialize queue to starting node
while self.queue: # while there are nodes in the queue
self.node = self.queue.pop() # dequeue nodes from queue
if self.node not in self.visited: # if node is not yet visited add node to queue
self.visited.append(self.node)
self.foo = [self.queue.insert(0, n) for n in self.graph[self.node] if n not in self.visited]
return self.visited
def dfs(self, start): # depth-first search algorithm
self.visited = []
self.stack = [start] # initialize stack to starting node
while self.stack: # while stack has items
self.node = self.stack.pop() # pop item from stack
if self.node not in self.visited:
self.visited.append(self.node)
self.stack.extend([n for n in self.graph[self.node] if n not in self.visited])
return self.visited
def is_family(tree):
Family = Graph()
fathers = set()
sons = set()
# create Family tree
for father,son in tree:
if Family.is_connected(father,son):
return False # if father-son loops
Family.add_edge(father,son)
fathers.add(father)
sons.add(son)
# filter sons
for son in sons:
if son not in fathers:
if len(Family.show()[son]) > 1:
return False # if a son has more connections but is not a father
# filter family
if (len(Family.find_all_sub_graphs())) > 1:
return False # if there are strangers in family
return True
if __name__ == "__main__":
#These "asserts" using only for self-checking and not necessary for auto-testing
assert is_family([
['Logan', 'Mike']
]) == True, 'One father, one son'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack']
]) == True, 'Two sons'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Alexander']
]) == True, 'Grandfather'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Logan']
]) == False, 'Can you be a father for your father?'
assert is_family([
['Logan', 'Mike'],
['Logan', 'Jack'],
['Mike', 'Jack']
]) == False, 'Can you be a father for your brather?'
assert is_family([
['Logan', 'William'],
['Logan', 'Jack'],
['Mike', 'Alexander']
]) == False, 'Looks like Mike is stranger in Logan\'s family'
print("Looks like you know everything. It is time for 'Check'!")
March 17, 2018
Comments: