SHARE
TWEET

Untitled

a guest Nov 16th, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. from collections import defaultdict
  2. import Queue
  3.  
  4. class Graph:
  5.     def __init__(self):
  6.         self.edge_map = defaultdict(set)
  7.    
  8.     def connect(self, from_, to_):
  9.         self.edge_map[from_].add(to_)
  10.         self.edge_map[to_].add(from_)
  11.    
  12.     def shortest_path_from(self, start_node, cond):
  13.         visited = set()
  14.         q = Queue.Queue()
  15.         q.put([start_node, 0])
  16.         visited.add(start_node)
  17.        
  18.         while not q.empty():
  19.             source, dist = q.get()
  20.            
  21.             for neighbor in self.edge_map[source]:
  22.                 if not neighbor in visited:
  23.                     if cond(neighbor): return dist+1
  24.  
  25.                     q.put([neighbor, dist+1])
  26.                     visited.add(neighbor)
  27.  
  28.         return -1
  29.  
  30. def add_edges(graph, graph_from, graph_to):
  31.     for i in range(len(graph_from)):
  32.         from_ = graph_from[i]
  33.         to_ = graph_to[i]
  34.         graph.connect(from_, to_)
  35.  
  36. def findShortest(graph_nodes, graph_from, graph_to, ids, val):
  37.     color_to_match = ids[val-1]
  38.    
  39.     g = Graph()
  40.     add_edges(g, graph_from, graph_to)
  41.     return g.shortest_path_from(val, lambda node: ids[node-1] == color_to_match)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top