# Python OO solution (42 ms) with some optimizations

• A reasonably fast solution, which aims to make the logic fairly readable from the code using object oriented programming. The steps are simple:

1. Build the digraph using the data given.
• Nodes have variable names as values, and edges have numerical values.
• For example, if we have `[x]--(a)-->[y]`, this represents `x/y = a`.
• Automatically add "inverse" edges to represent `y/x = 1/a`.
2. For each (start, end) pair, perform a DFS beginning at start.
• If a path is found, multiply every edge value along that path to get the answer.
• To speed up future searches, add a connection representing that calculation to the digraph (as well as the inverse connection).

For quick lookups, all lists of nodes are actually dictionaries, with variable names as keys and `Node` classes as values. Redundant, but quick!

``````class Node(object):
def __init__(self, name):
self.name = name;
self.outs = {};

""" Create an edge with value "value", and an edge in the reverse direction with value 1/"value". """
if node.name not in self.outs:
self.outs[node.name] = (node, value)
inverse = 1.0/value
if inverse not in node.outs:
node.outs[self.name] = (self, inverse)

def dfs(self, end, visited = []):
""" Attempts to find a path from this node to "end" nodes. """
newvisited = visited + [self.name]
if self.name == end:
return newvisited

for outnode in self.outs:
if self.outs[outnode] [0].name not in visited:     # No loops in our path!
result = self.outs[outnode] [0].dfs(end, newvisited)
if result[-1] == end:   # Success was returned, continue to return it
return result
# Otherwise continue through the outnodes.

return newvisited

class Digraph(object):
def __init__(self, equations, values):
""" Build a digraph with appropriate named nodes and weighted edges. """
self.nodes = {}

# Build the connections.
for i in range(len(equations)):
# Add 0, 1, or 2 nodes as needed
eq = equations[i]
if eq[0] not in self.nodes:
self.nodes[eq[0]] = Node(eq[0])
if eq[1] not in self.nodes:
self.nodes[eq[1]] = Node(eq[1])

def multiplyPath(self, path):
""" Takes a connected path of nodes and returns the product of their edges. """
prod = 1
for i in range(len(path)-1):
prod *= self.nodes[path[i]].outs[ path[i+1] ] [1]

return prod

class Solution(object):
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
# 1. Build the digraph
dg = Digraph(equations, values)
print "Built digraph:";
print dg.display()

# 2. Do a DFS for each query.
# 2.5 to optimize, add each answer as an edge after it's computed.
for (start, end) in queries:
if start not in dg.nodes or end not in dg.nodes:
continue

path = dg.nodes[start].dfs(end)
if path[-1] == end:
prod = dg.multiplyPath(path)