.. -*- coding: utf-8 -*-

Malabares y teoría de grafos
============================

Introducción al site swap
:::::::::::::::::::::::::

En todo modelo matemático debemos seleccionar las características del problema 
que nos interesa estudiar, y descartar toda aquella información que hace el
análisis más complicado pero no es esencial.

En este caso, pretendemos estudiar los trucos que son posibles desde un punto 
*combinatorio*, es decir, que descartamos variables continuas como la fuerza
con la que se debe lanzar cada objeto, su tiempo de vuelo o la altura que 
alcanza, y nos fijamos sólamente en información discreta.

Como primer paso, dividimos el tiempo en instantes de igual longitud (y a cada
instante lo llamamos un *beat*, o un pulso). A 
continuación, anotamos qué hacemos en cada pulso. Cada vez que 
lanzamos un objeto, anotamos dentro de cuántos pulsos lo volveremos a lanzar. 
Si en un instante no lanzamos ningún objeto, anotamos un cero.

De esta forma, toda la complejidad del movimiento del malabarista queda reducida
a una secuencia de numéros enteros: 3535004130... A cada uno de los números de
la secuencia, lo llamamos la *altura*, porque cuando lanzamos un objeto más 
alto, tarda más tiempo en caer. 
Sin embargo, no es una altura medida en metros
ni en ninguna otra unidad de medida, ya que para si para que un objeto caiga
dentro de 1 instante necesitamos lanzarlo a una altura h, para que caiga dentro
de k instantes necesitaremos lanzarlo a altura h*k^2.


Si observamos a los malabaristas ejecutar varios trucos clásicos, encontraremos
que las secuencias de números a que dan lugar son periódicas:

cascada de 3 bolas
    ...33333...
"shower" de 3 bolas
    ...515151...

Aunque si le pedimos al malabarista que comience con una cascada y cambie a una
"shower", encontraremos la secuencia ..33341515... y viceversa, si comienza con
una "shower" y cambia a una casacada, encontramos ..1515152333...

¿Qué secuencias podemos encontrar? Si asumimos que en cada instante el 
malabarista puede hacer a lo sumo una acción (e.g., recoger una bola y volverla 
a lanzar, pero no recoger dos bolas ni lanzar dos bolas), entonces cualquier
secuencia que contenga un 4 seguido de un 3 es inviable, porque 4 instantes 
después del primer lanzamiento, el malabarista recibiría a la vez dos bolas, a 
las que no podría atender.

Para completar nuestra imagen mental, visualizamos un malabarista haciendo 
trucos con las dos manos, usando la mano izquierda y la derecha 
alternativamente, de modo que en los instantes impares usa la mano izquierda y 
en los pares la derecha.

Nos preguntamos cuáles son las secuencias de números que corresponden a trucos
de malabares válidos.

Si estudiamos sólamente patrones periódicos, nos encontramos con la teoría del
**Site Swap**. Quien tenga interés, le recomiendo el documento Pedagogía de los 
malabares, de Daniel Sánchez, que os adjuntamos como información extra.

En lugar de seguir ese enfoque, estudiaremos una visión complementaria, usando
grafos.

Nota: en un principio no hablamos de cómo empiezan los trucos, asumimos que los trucos ya están en marcha, con todas las pelotas en el aire de modo que en ningún instante futuro esté prevista la caída de dos bolas. Sin embargo, en todos los grafos que dibujaremos hay una forma sencilla de empezar.

Grafo de estados de k bolas y altura h
::::::::::::::::::::::::::::::::::::::

.. index:: estado fundamental en malabares

Estado
~~~~~~


Un instante está caracterizado por los tiempos esperados de caída de cada bola. Un estado sólo es válido si cada bola en el aire caerá en un instante futuro distinto. Representamos un estado mediante una secuencia de bola '*' y no bola '_'. En la posición i-ésima ponemos una bola si se espera que una bola caiga dentro de i instantes y no-bola si ninguna bola caerá dentro de i instantes. Por ejemplo ``'**__*'`` quiere decir que hay tres bolas en el aire y que caerán dentro de 1, 2 y 5 instantes.


Nota: Al estado en el que las bolas caerán en los instantes sucesivos inmediatos, lo denominamos  **estado fundamental**  ( ``'***_'`` , ó  ``'***__'`` , ó lo que toque).


Altura
~~~~~~


La fuerza y la precisión del malabarista limitan el número máximo de instantes en el que futuro al que puede enviar una bola. A este número lo llamamos  **altura** .


Hay una cantidad finita de estados posibles con k bolas y una altura h. Concretamente, cada una de las k bolas caerá en un instante entre 1 y h que es distinto para cada bola, luego se trata de elegir k números entre 1 y h, y la cantidad de formas de hacer esta elección es :math:`{h \choose k}`


::

    sage: bolas = 3
    sage: altura = 4
    sage: estados = [ ''.join(('*' if j in ss else '_') for j in range(altura))
    ...               for ss in Subsets(range(altura), bolas) ]
    sage: estados
    ['***_', '**_*', '*_**', '_***']


Transiciones
~~~~~~~~~~~~


¿A qué estados podemos cambiar partiendo de un estado dado? En el instante siguiente todas las bolas están un instante más próximas a caer en la mano del malabarista, luego pasamos por ejemplo de ``'_*_**'``  a  ``'*_**_'`` , pero si teníamos una bola a punto de caer, el malabarista la recibe y la lanza de forma que caiga dentro de un cierto número de instantes de tiempo, y puede elegir cualquier momento futuro en el que no esté prevista la caída de ninguna otra bola. Por ejemplo, del estado  ``'*_**_'``  podemos pasar a  ``'**__'``, ``'_** * _'`` o ``'_**_ * '``.


Junto a cada posible transición, guardamos la altura a la que lanzamos la bola (usando un 0 cuando no hacemos nada).


::

    sage: def opciones(estado):
    ...       pasa = estado[1:] + '_'
    ...       if estado[0]=='_': return {pasa:0}
    ...       opciones = {}
    ...       for j,s in enumerate(pasa):
    ...           if s=='_':
    ...               opciones[pasa[:j] + '*'+ pasa[j+1:]] = j + 1
    ...       return opciones
    sage: transiciones = dict((estado,opciones(estado)) for estado in estados)
    sage: transiciones
    {'***_': {'***_': 3, '**_*': 4}, '_***': {'***_': 0}, '*_**': {'***_': 1, '_***': 4}, '**_*': {'***_': 2, '*_**': 4}}

::

    sage: def grafo_malabar(bolas, altura):
    ...       '''Crea el grafo de malabares con numero de bolas
    ...       y altura dadas'''
    ...       estados = [ ''.join(('*' if j in ss else '_') for j in range(altura))
    ...                   for ss in Subsets(range(altura), bolas) ]
    ...       
    ...       transiciones = dict((estado,opciones(estado)) for estado in estados)
    ...       return DiGraph(transiciones)



Dibujamos el grafo


::

    sage: g = grafo_malabar(3,4)
    sage: g.show(edge_labels=True, layout='circular', vertex_size=300, figsize=8)

.. image:: malabares_media/cell_4_sage0.png
    :align: center



También dibujaremos los diagramas con graphviz, porque las etiquetas se ven más claras (graphviz debe estar instalado).


::

    sage: attach(DATA + 'graphviz.sage')
    sage: graphviz(grafo_malabar(3,4))

.. image:: malabares_media/cell_5_sage1295710983_75.png
    :align: center


::

    sage: graphviz(grafo_malabar(2,4))

.. image:: malabares_media/cell_6_sage1295710985_39.png
    :align: center


::

    sage: graphviz(grafo_malabar(3,5))

.. image:: malabares_media/cell_7_sage1295710986_11.png
    :align: center



¿Qué ventajas ofrece la teoría de grafos sobre el site swap?
::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::


En pocas palabras, los grafos permiten representar situaciones muy diversas de forma muy uniforme.


*Requerimientos del espectáculo*  de lo más variopinto se pueden traducir en  *restricciones sobre el grafo*  de posibles malabares.


Ejemplo práctico
~~~~~~~~~~~~~~~~


Queremos estar  *a distancia menor o igual que 4*  del estado ``'___***'``, por ejemplo porque ese estado nos da tiempo para hacer un truco que hemos preparado, o para saludar a un viandante que ha echado una moneda en el plato.


::

    sage: g = grafo_malabar(3,5)
    sage: ds = g.distance_all_pairs()
    sage: v0 = '__***'
    sage: new_labels = {}
    sage: for v in g:
    ...       new_labels[v] = (v, ds[v][v0])
    sage: g.relabel(new_labels)
    sage: graphviz(g)

.. image:: malabares_media/cell_8_sage1295710987_85.png
    :align: center


::

    sage: g = grafo_malabar(3,5)
    sage: ds = g.distance_all_pairs()
    sage: v0 = '__***'
    sage: vs0 = [v for v in g if ds[v][v0]<=4]
    sage: sg = g.subgraph(vs0)
    sage: graphviz(sg)

.. image:: malabares_media/cell_9_sage1295710989_13.png
    :align: center



Otro ejemplo: poner una pelota en la cabeza
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Ahora podemos  *dejar una pelota en la cabeza*  por tiempo indefinido. Representamos por un '8' una cabeza con una pelota encima, y por una 'o' una cabeza sin pelota encima.


Por ejemplo, para tres pelotas y altura 4, los posibles estados tienen dos pelotas en el aire y una en la cabeza, o tres pelotas en el aire y ninguna en la cabeza.


::

    sage: bolas = 3
    sage: altura = 4
    sage: estados_con_cabeza = ([('o' + ''.join(('*' if j in ss else '_')
    ...                                      for j in range(altura)))
    ...                           for ss in Subsets(range(altura), bolas) ] +
    ...                         [('8' + ''.join(('*' if j in ss else '_')
    ...                                       for j in range(altura)))
    ...                           for ss in Subsets(range(altura), bolas-1) ])
    sage: estados_con_cabeza
    ['o***_', 'o**_*', 'o*_**', 'o_***', '8**__', '8*_*_', '8*__*', '8_**_', '8_*_*', '8__**']


Transiciones con cabeza
~~~~~~~~~~~~~~~~~~~~~~~


Ahora tenemos opciones nuevas para pasar de un estado a otro:




 - Si tenemos la mano vacía y una pelota en la cabeza, podemos cogerla y lanzarla.


 - Si tenemos una pelota en la mano y ninguna en la cabeza, podemos dejar la pelota en la cabeza.


 - Si tenemos una pelota en la mano y otra en la cabeza, tenemos que lanzar la pelota como de costumbre.




::

    sage: def opciones_con_cabeza(estado):
    ...       cabeza = estado[0]
    ...       mano = estado[1]
    ...       bolas1 = estado[2:] + '_'
    ...       opciones = {}
    ...       if mano=='_' and cabeza=='o': 
    ...           opciones = {('o' + bolas1):'0'}
    ...       elif mano=='_': #and cabeza=='8'
    ...           opciones['8' + bolas1] = '0'
    ...           for j,s in enumerate(bolas1):
    ...               if s=='_':
    ...                   opciones[('o' + bolas1[:j] + 
    ...                             '*'+ bolas1[j+1:])] = 'o%d'%(j + 1)
    ...       elif cabeza=='8': #and mano=='*'
    ...           for j,s in enumerate(bolas1):
    ...               if s=='_':
    ...                   opciones[('8' + bolas1[:j] + 
    ...                            '*'+ bolas1[j+1:])] = '%d'%(j + 1)
    ...       else: #cabeza=='o': #and mano=='*'
    ...           opciones['8' + bolas1] = 'o0'
    ...           for j,s in enumerate(bolas1):
    ...               if s=='_':
    ...                   opciones[('o' + bolas1[:j] + 
    ...                             '*'+ bolas1[j+1:])] = '%d'%(j + 1)
    ...       return opciones
    sage: def grafo_malabar_con_cabeza(bolas, altura):
    ...       estados_con_cabeza = ([('o' + ''.join(('*' if j in ss else '_')
    ...                                          for j in range(altura)))
    ...                               for ss in Subsets(range(altura), bolas) ] +
    ...                             [('8' + ''.join(('*' if j in ss else '_')
    ...                                           for j in range(altura)))
    ...                               for ss in Subsets(range(altura), bolas-1) ])
    ...       transiciones = dict((estado,opciones_con_cabeza(estado)) 
    ...                           for estado in estados_con_cabeza)
    ...       g = DiGraph(transiciones)
    ...       return g


::

    sage: g = grafo_malabar_con_cabeza(3, 4)
    sage: graphviz(g)

.. image:: malabares_media/cell_11_sage1295710990_82.png
    :align: center



Y mucho más
~~~~~~~~~~~




 -  Bolas distintas (por su color o por su naturaleza). 


 -  Varios malabaristas. 


 - ...




Más ejemplos en los ejercicios del final.



Propiedades de los grafos malabares
:::::::::::::::::::::::::::::::::::


Y bien, ¿qué hacemos una vez tenemos un grafo? Para empezar, nos podemos preguntar si el grafo tiene algunas propiedades típicas de la teoría de grafos que pueden ser interesantes:




 - ¿El grafo es  **fuertemente conexo** ? Es decir, ¿se puede pasar de un estado a cualquier otro?


 - ¿El grafo de malabares es  **euleriano** ? Es decir, ¿existe un circuito que pasa por cada  **arista**   *exactamente una vez* ?


 - ¿El grafo de malabares es  **hamiltoniano** ? Es decir, ¿existe un circuito que pasa por cada  **vértice**   *exactamente una vez* ?




::

    sage: for j in range(2,5):
    ...       for k in range(j+1,j+4):
    ...           print 'el grafo malabar con %d bolas y altura %d\
    ...    %ses fuertemente conexo'%(j,k,
    ...           '' if grafo_malabar(j,k).is_strongly_connected() else 'no ')
    el grafo malabar con 2 bolas y altura 3 es fuertemente conexo
    el grafo malabar con 2 bolas y altura 4 es fuertemente conexo
    el grafo malabar con 2 bolas y altura 5 es fuertemente conexo
    el grafo malabar con 3 bolas y altura 4 es fuertemente conexo
    el grafo malabar con 3 bolas y altura 5 es fuertemente conexo
    el grafo malabar con 3 bolas y altura 6 es fuertemente conexo
    el grafo malabar con 4 bolas y altura 5 es fuertemente conexo
    el grafo malabar con 4 bolas y altura 6 es fuertemente conexo
    el grafo malabar con 4 bolas y altura 7 es fuertemente conexo

::

    sage: for j in range(2,5):
    ...       for k in range(j+1,j+4):
    ...           print 'el grafo malabar con %d bolas y altura %d\
    ...    %ses euleriano'%(j,k,
    ...           '' if grafo_malabar(j,k).is_eulerian() else 'no ')
    el grafo malabar con 2 bolas y altura 3 no es euleriano
    el grafo malabar con 2 bolas y altura 4 no es euleriano
    el grafo malabar con 2 bolas y altura 5 no es euleriano
    el grafo malabar con 3 bolas y altura 4 no es euleriano
    el grafo malabar con 3 bolas y altura 5 no es euleriano
    el grafo malabar con 3 bolas y altura 6 no es euleriano
    el grafo malabar con 4 bolas y altura 5 no es euleriano
    el grafo malabar con 4 bolas y altura 6 no es euleriano
    el grafo malabar con 4 bolas y altura 7 no es euleriano

::

    sage: for j in range(2,5):
    ...       for k in range(j+1,j+4):
    ...           print 'el grafo malabar con %d bolas y altura %d\
    ...    %ses hamiltoniano'%(j,k,
    ...           '' if grafo_malabar(j,k).is_hamiltonian() else 'no ')
    el grafo malabar con 2 bolas y altura 3 es hamiltoniano
    el grafo malabar con 2 bolas y altura 4 no es hamiltoniano
    el grafo malabar con 2 bolas y altura 5 no es hamiltoniano
    el grafo malabar con 3 bolas y altura 4 es hamiltoniano
    el grafo malabar con 3 bolas y altura 5 no es hamiltoniano
    el grafo malabar con 3 bolas y altura 6 no es hamiltoniano
    el grafo malabar con 4 bolas y altura 5 es hamiltoniano
    el grafo malabar con 4 bolas y altura 6 no es hamiltoniano
    el grafo malabar con 4 bolas y altura 7 no es hamiltoniano

::

    sage: for j in range(2,5):
    ...       for k in range(j+1,j+4):
    ...           print 'el grafo malabar con %d bolas, altura %d y con cabeza\
    ...    %ses hamiltoniano'%(j,k,
    ...           '' if grafo_malabar_con_cabeza(j,k).is_hamiltonian() else 'no ')
    el grafo malabar con 2 bolas, altura 3 y con cabeza es hamiltoniano
    el grafo malabar con 2 bolas, altura 4 y con cabeza es hamiltoniano
    el grafo malabar con 2 bolas, altura 5 y con cabeza es hamiltoniano
    el grafo malabar con 3 bolas, altura 4 y con cabeza es hamiltoniano
    el grafo malabar con 3 bolas, altura 5 y con cabeza es hamiltoniano
    el grafo malabar con 3 bolas, altura 6 y con cabeza es hamiltoniano
    el grafo malabar con 4 bolas, altura 5 y con cabeza es hamiltoniano
    el grafo malabar con 4 bolas, altura 6 y con cabeza es hamiltoniano
    el grafo malabar con 4 bolas, altura 7 y con cabeza es hamiltoniano


Circuitos cerrados
::::::::::::::::::


Aunque podemos movernos indefinidamente por el grafo sin seguir necesariamente un patrón periódico, antes o después pasaremos dos veces por el mismo nodo y en ese momento habremos completado un  **circuito** .


Circuitos primos
~~~~~~~~~~~~~~~~


Si un circuito pasa dos veces por el mismo sitio, es composición de  **circuitos elementales o primos**, en los que no se pasa dos veces por el mismo vértice.


Los caminos en el grafo son composición de estos caminos elementales. En cierto modo, es equivalente a cómo el desarrollo decimal de un número puede no ser periódico (por ejemplo, el desarollo de :math:`\pi`), pero todos los números se pueden desarrollar con los mismos dígitos.


Algoritmo de Johnson
~~~~~~~~~~~~~~~~~~~~


La teoría de circuitos cerrados en un grafo  **no dirigido**  es preciosa y tiene una descripción matemática muy elegante, que en última instancia se debe a se puede definir una suma de caminos. Sin embargo, para grafos dirigidos no se puede definir la suma de caminos y las matemáticas no dan una visión tan clara del conjunto de circuitos. Afortunadamente, existen algoritmos eficientes para encontrar todos los circuitos elementales en un grafo dirigido.


Nota: si listamos la altura a la que debemos lanzar cada pelota (la etiqueta de cada arista), recuperamos la notación  **siteswap** .


Todos los posibles trucos con 3 bolas y altura a lo sumo 4: listamos los circuitos del grafo malabar con 3 bolas y altura máxima 4, en notación siteswap.


::

    sage: attach(DATA + 'circuits.py')
    sage: g = grafo_malabar(3,4)
    sage: for ls in circuits(g):
    ...       aristas = [(ls[j],ls[j+1])
    ...                  for j in range(len(ls)-1)]
    ...       sg = g.subgraph(edges = aristas)
    ...       print [g.edge_label(v1,v2) for v1,v2 in aristas]
    ...       graphviz(sg)
    [3]
    [4, 2]
    [4, 4, 1]
    [4, 4, 4, 0]

.. image:: malabares_media/cell_32_sage1295711065_81.png
    :align: center


.. image:: malabares_media/cell_32_sage1295711066_01.png
    :align: center


.. image:: malabares_media/cell_32_sage1295711066_21.png
    :align: center


.. image:: malabares_media/cell_32_sage1295711066_36.png
    :align: center


::

    sage: g = grafo_malabar(3,4)
    sage: g.show(edge_labels=True, layout='circular', vertex_size=300, figsize=8)
    sage: graphs_list.show_graphs([g.subgraph(edges = [(ls[j],ls[j+1])
    ...                                                for j in range(len(ls)-1)])
    ...                            for ls in circuits(g)])

.. image:: malabares_media/cell_33_sage0.png
    :align: center

.. image:: malabares_media/cell_33_sage1.png
    :align: center


Todos los posibles trucos con 3 bolas y altura a lo sumo 5.


::

    sage: attach(DATA + 'circuits.py')
    sage: g = grafo_malabar(3,5)
    sage: for ls in circuits(g):
    ...       aristas = [(ls[j],ls[j+1])
    ...                  for j in range(len(ls)-1)]
    ...       print ''.join([str(g.edge_label(v1,v2)) for v1,v2 in aristas])
    441
    4440
    45501
    455040
    4530
    42
    3
    5350530
    53502
    531
    5340
    5241
    52440
    525501
    5255040
    52530
    522
    55150530
    551502
    5511
    55140
    55500
    5520
    450
    55050
    51


La misma información, de forma gráfica.


::

    sage: g = grafo_malabar(3,5)
    sage: show(g, edge_labels=True, layout='circular', figsize = 8, vertex_size=400)
    sage: graphs_list.show_graphs([g.subgraph(edges = [(ls[j],ls[j+1])
    ...                                                for j in range(len(ls)-1)])
    ...                            for ls in circuits(g)])

.. image:: malabares_media/cell_35_sage0.png
    :align: center

.. image:: malabares_media/cell_35_sage1.png
    :align: center

.. image:: malabares_media/cell_35_sage2.png
    :align: center