<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 The goals of this notebook
Step3:  Function to take connected component id as input and update all states in that component by setting the solution depth and the optimal neighbor game number.
Step5:  The algorithm is to follow breadth-first search but from a starting set rather than a single node.
Step6:  Saving Updates to the DB
Step7:  Develop data structures to support drawing the connected component.
<ASSISTANT_TASK:>
Python Code:
%matplotlib inline
import os
import pandas as pd
import copy
from IPython.display import HTML
import sqlite3 as db
import networkx as nx
import collections
con = db.connect('C:/Users/cliff/workspace/rushHour/Data Model and SQL/Schema Definition and Bulk Load/rush_hour.db')
c = con.cursor()
Explanation: The goals of this notebook:
Develop the algoithm to determine the solution depth and optimal neighbor.
A separate notebook will explore visualizations of the rush hour graph.
End of explanation
connected_component_id = 30 # component with 104 states
sql =  select s.comb_class_id, s.game_number, s.is_goal_state
          from connected_component c
               inner join game_state s on c.id = s.connected_component_id
          where connected_component_id = %d
      %(connected_component_id)
c.execute(sql)
component_states = c.fetchall() # 
#component_states
#df = pd.read_sql(sql,con)
#len(df)
# each edge will match twice against the nodes - once for the pre transition state and once for the post transition state.
# at the time of this writing, I am using distint to remove the duplicates. 
sql = select distinct t.*
         from connected_component c
              inner join game_state s on c.id = s.connected_component_id 
              inner join state_transition t 
              on (s.comb_class_id = t.comb_class_id
                  and s.game_number = t.pre_transition_game_number
                 )
                  or
                 (t.comb_class_id = s.comb_class_id 
                  and s.game_number = t.post_transition_game_number 
                 )
         where c.id = %d
       %(connected_component_id)
c.execute(sql)
component_edges = c.fetchall()
Explanation: Function to take connected component id as input and update all states in that component by setting the solution depth and the optimal neighbor game number.
End of explanation
#gray_states = collections.OrderedDict()
# test code in preparation for work in next cell
adj_list = {x[1]:[] for x in component_states} # component_state = ()
for [x,y,z]in component_edges: # [t1,t2,...tn] ti = (pre_tran_state_game_number, post_tran_state_game_number, comb_class_id):
    adj_list[x].append(y)
    adj_list[y].append(x)
# component_states: (comb class id, game number, is Goal State?)
# states as an array of dictionaries: [d1,d2,d3,...dn] di = {game_number:{'depth':,'optimal_nbr_game_number}}
white_states = { x[1]:{'depth':None, 'optimal_nbr_game_number':None} for x in component_states if x[2] !=1}
gray_states =  collections.OrderedDict( { x[1]:{'depth':0, 'optimal_nbr_game_number':None} for x in component_states if x[2] == 1 })
black_states = {}
    
len(gray_states), len(white_states),set([x for k in adj_list.keys() for x in adj_list[k] if x not in white_states])
len(set([k for k in white_states.keys()]))
#cur_state_key,cur_state_values = gray_states.popitem(last=False)
#nbr = (adj_list[cur_state_key])[0]
#cur_state_key,nbr, [x for x in component_states if x[1] == nbr],nbr in gray_states,nbr in white_states, gray_states
adj_list = {x[1]:[] for x in component_states} # component_state = ()
for [x,y,z]in component_edges: # [t1,t2,...tn] ti = (pre_tran_state_game_number, post_tran_state_game_number, comb_class_id):
    adj_list[x].append(y)
    adj_list[y].append(x)
    
# component_states: (comb class id, game number, is Goal State?)
# states as an array of dictionaries: [d1,d2,d3,...dn] di = {game_number:{'depth':,'optimal_nbr_game_number}}
white_states = { x[1]:{'depth':None, 'optimal_nbr_game_number':None} for x in component_states if x[2] !=1}
gray_states =  collections.OrderedDict( { x[1]:{'depth':0, 'optimal_nbr_game_number':None} for x in component_states if x[2] == 1 })
black_states = {}
while gray_states:
    cur_state_key,cur_state_values = gray_states.popitem(last=False)
    for nbr in adj_list[cur_state_key]:
        if nbr in white_states:
            gray_states[nbr] = {'depth': cur_state_values['depth'] + 1, 'optimal_nbr_game_number':cur_state_key} 
            del white_states[nbr]
    black_states[cur_state_key] = cur_state_values
    
distance_partition_max = max( v['depth'] for k,v in black_states.items()  )
distance_partition = { i:[] for i in range(distance_partition_max + 1) }
for k,v in black_states.items() :
    (distance_partition[v['depth'] ]).append(k)
    
len(black_states), len(white_states),len(gray_states),len(adj_list),distance_partition_max,distance_partition
[len(v) for k,v in distance_partition.items() ]
# need to save depth and optimal neighbor back into the db
# need to make
Explanation: The algorithm is to follow breadth-first search but from a starting set rather than a single node.
End of explanation
comb_class_id = 36
update_sql = "update game_state set optimal_transition_game_number = ?, solution_distance = ? where comb_class_id = ? and game_number = ?"
update_data = [ (v['optimal_nbr_game_number'], v['depth'],comb_class_id, k) for k,v in black_states.items() ]
c.executemany(update_sql,update_data)
con.commit()
%run compute_edges_connected_components
set_solution_data_for_comb_class(36)
#res = solution_data_for_connected_component(20)
#res
#conn = db.connect('C:/Users/cliff/workspace/rushHour/Data Model and SQL/Schema Definition and Bulk Load/rush_hour.db')
#cursor = conn.cursor()
sql = 'select distinct connected_component_id from game_state where comb_class_id = %d' %(comb_class_id)
c.execute(sql)
component_ids = c.fetchall()
component_ids
Explanation: Saving Updates to the DB
End of explanation
def partition_color(depth):
    return depth
    #if depth == 0:
    #    return 'r'
    #else:
    #    return depth
        
    #if depth >0  and depth < 9:
    #    return 'g'
    #if depth == 9:
    #    return 'b'
def nodes_colors(dist_partition): #dist_partition is dict k:v, K is partition depth (0,...,n); v is list of game numbers
    partition_list = [[k,elt] for k in dist_partition.keys() for elt in dist_partition[k]]
    nodes = [x[1] for x in partition_list]
    colors = [partition_color(x[0]) for x in partition_list]
    
    return [nodes,colors]
    
[graph_nodes,graph_colors] = nodes_colors(dist_partition)
node_labels = {node:str(depth) for (depth,nodes) in dist_partition.items() for node in nodes}
shell_list = [list(dist_partition[k]) for k in dist_partition.keys() ]
#nodes,node_labels
#nx.draw(G)
%pylab qt
G=nx.Graph()
G.add_nodes_from(graph_nodes)
G.add_edges_from([ [x[0],x[1]] for x in component_edges])
nx.draw_shell(G,nlist=shell_list,scale=23,nodelist=graph_nodes, node_color=graph_colors, with_labels=True,labels=node_labels,font_size=24,node_size=300)
Explanation: Develop data structures to support drawing the connected component.
End of explanation
<END_TASK>