attachment:wagner.sage of interact/graph_theory

   1 def animate_contraction(g, e, frames = 12, **kwds):
   2     v1, v2 = e
   3     if not g.has_edge(v1,v2):
   4         raise ValueError, "Given edge not found on Graph"
   5     ls = []
   6     posd = g.get_pos()
   7     for j in range(frames):
   8         gp = Graph(g)
   9         posdp = dict(posd)
  10         p1 = posdp[v1]
  11         p2 = posdp[v2]
  12         posdp[v2] = [a*(frames-j)/frames + b*j/frames
  13                     for a,b in zip(p2,p1)]
  14 
  15         gp.set_pos(posdp)
  16         ls.append(plot(gp, **kwds))
  17     return ls
  18     
  19 def animate_vertex_deletion(g, v, frames = 12, **kwds):
  20     kwds2 = dict(kwds)
  21     if 'vertex_colors' in kwds:
  22         cs = dict(kwds['vertex_colors'])
  23         for c, vs in kwds['vertex_colors'].items():
  24             if v in vs:
  25                 vs2 = list(vs)
  26                 vs2.remove(v)
  27                 cs[c] = vs2
  28         kwds2['vertex_colors'] = cs
  29     else:
  30         kwds2 = dict(kwds)
  31     g2 = Graph(g)
  32     posd = dict(g.get_pos())
  33     del posd[v]
  34     g2.delete_vertex(v)
  35     g2.set_pos(posd)
  36     return [plot(g, **kwds),plot(g2, **kwds2)]*int(frames/2)
  37     
  38 def animate_edge_deletion(g, e, frames = 12, **kwds):
  39     v1, v2 = e
  40     g2 = Graph(g)
  41     g2.delete_edge(e)
  42     return [plot(g, **kwds),plot(g2, **kwds)]*int(frames/2)
  43     
  44 def animate_glide(g, pos1, pos2, frames = 12, **kwds):
  45     ls = []
  46     for j in range(frames):
  47         gp = Graph(g)
  48         pos = {}
  49         for v in gp.vertices():
  50             p1 = pos1[v]
  51             p2 = pos2[v]
  52             pos[v] = [b*j/frames + a*(frames-j)/frames
  53                         for a,b in zip(p1,p2)]    
  54         gp.set_pos(pos)
  55         ls.append(plot(gp, **kwds))
  56     return ls
  57     
  58 def medio(p1, p2):
  59     return tuple((a+b)/2 for a,b in zip(p1, p2))
  60 
  61 def new_color():
  62     return (0.1+0.8*random(), 0.1+0.8*random(), 0.1+0.8*random())
  63     
  64 def animate_minor(g, m, frames = 12, pause = 50, step_time = 100):
  65     '''Crea una animación que muestra cómo un grafo tiene un menor m
  66     '''
  67     posd = dict(g.get_pos())
  68     posg = posd.values()
  69     posm = m.get_pos().values()
  70     xmax = max(max(x for x,y in posg), max(x for x,y in posm))
  71     ymax = max(max(y for x,y in posg), max(y for x,y in posm))
  72     xmin = min(min(x for x,y in posg), min(x for x,y in posm))
  73     ymin = min(min(y for x,y in posg), min(y for x,y in posm))
  74     dd = g.minor(m)
  75     
  76     #Set colors
  77     m_colors = dict((v,new_color()) for v in m.vertices())
  78     g_colors = dict((m_colors[k],vs) 
  79                         for k,vs in dd.items())
  80 
  81     extra_vs = (set(g.vertices()) - 
  82                 set(v for vs in dd.values() 
  83                       for v in vs))
  84     g_colors[(0,0,0)] = list(extra_vs)
  85 
  86     #pics contains the frames of the animation 
  87     #no colors at the beggining   
  88     gg = Graph(g)
  89     pics = [plot(gg)]*frames
  90 
  91     #First: eliminate extra vertices
  92     for v in extra_vs:
  93         pics.extend(animate_vertex_deletion(gg, v, frames,
  94                             vertex_colors = g_colors))
  95         gg.delete_vertex(v)
  96         del posd[v]
  97         g_colors[(0,0,0)].remove(v)
  98     del g_colors[(0,0,0)]
  99     
 100     #Second: contract edges
 101     for color, vs in g_colors.items():
 102         while len(vs)>1:
 103             for j in xrange(1,len(vs)):
 104                 if gg.has_edge(vs[0], vs[j]):
 105                     break
 106             pics.extend(animate_contraction(gg, (vs[0], vs[j]), frames,
 107                                 vertex_colors = g_colors))
 108             for v in gg.neighbors(vs[j]):
 109                 gg.add_edge(vs[0],v)
 110             gg.delete_vertex(vs[j])
 111             del posd[vs[j]]
 112             gg.set_pos(posd)
 113             posd = dict(gg.get_pos())
 114             del vs[j]
 115 
 116     #Relabel vertices of m so that they match with those of gg
 117     m = Graph(m)
 118     dd0 = dict((k, vs[0])  
 119                   for k,vs in dd.items() )
 120     m.relabel(dd0)
 121     
 122 
 123     #Third: glide to position in m
 124     pos_m = m.get_pos()
 125     pos_g = gg.get_pos()
 126     pics.extend(animate_glide(gg, pos_g, pos_m, frames,
 127                                 vertex_colors = g_colors))
 128     gg.set_pos(pos_m)
 129             
 130     #Fourth: delete redundant edges
 131     for e in gg.edges(labels = False):
 132         if not m.has_edge(e):
 133             pics.extend(animate_edge_deletion(gg, e, frames,
 134                                 vertex_colors = g_colors))
 135             gg.delete_edge(*e)
 136 
 137     #And wait for a moment
 138     pics.extend([plot(gg, vertex_colors = g_colors)]*frames)
 139     
 140     return animate(pics, xmin = xmin - 0.1, xmax = xmax + 0.1, 
 141                          ymin = ymin - 0.1, ymax = ymax + 0.1)