articulo1.html

Un Orden Topológico ordena los nodos de un grafo dirigido acíclico de forma que si hay una camino del nodo A al nodo B entonces A aparece antes que B en la ordenación.
<br /><br />
Ej: 
<br />
<img  alt="Grafo acíclico dirigido" title="Grafo acíclico dirigido" src="http://theproc.es/files/1376" />
<br />
El sentido de las flechas indica las dependencias. A depende de B y C, B depende de C, etc, etc.
<br /><br />
<img  alt="Grafo ordenado topológicamente" title="Grafo ordenado topológicamente" src="http://theproc.es/files/1375" />
<br />
La librería standard de Ruby tiene un módulo (TSort) que implementa el orden topológico usando el algoritmo de Tarjan y nos ofrece una interfaz para utilizarlo.
<br /><br />
El módulo TSort está diseñado para ser utilizado con cualquier objeto que pueda ser modelado como un grafo dirígido.
<br /><br />
Por ejemplo, usando la clase Hash el grafo anterior quedaría así:

<script src="http://gist.github.com/96932.js"></script>
<p>
Según la documentación TSort necesita de dos métodos para interpretar un objeto como grafo, tsort_each_node y tsort_each_child.

<br />
&nbsp;&nbsp;<strong>tsort_each_node</strong> itera sobre todos los nodos del grafo
<br />
&nbsp;&nbsp;<strong>tsort_each_child</strong> itera sobre los nodos hijo de un un nodo dado
</p>
<script src="http://gist.github.com/96922.js"></script>

<p>De esta forma:</p>

<script src="http://gist.github.com/96929.js"></script>

<p>
En 3sellers hemos utilizado este algoritmo para insertar datos de ejemplo en las nuevas tiendas que se den de alta.
<br /><br />
Primero hemos creado un script que recorre todos los modelos de una determinada tienda y nos crea un archivo con los registros en formato yaml (similar a las fixtures):
</p>
<script src="http://gist.github.com/96927.js"></script>
<p>
Cada vez que una nueva tienda es creada se ejecuta un segundo script que interpreta este fichero e inserta los nuevos registros en las bases de datos respetando las asociaciaciones entre objetos.
<br /><br />
Esto no se pudo hacer con simples fixtures de Rails ya que las fixtures utilizan una función hash para calcular los ids.
<br /><br />
Este segundo script carga los objetos y utiliza la ordenación topologica para obtener un array de objectos ordenados.
<br /><br />
En el código de ejemplo, primero insertaría el Blog_223 y luego el Post_364, ya que en el momento de su inserción ya conoceremos el id del Blog_233.
<br /><br />
Esto nos facilita el crear un set de datos para una plantilla de tienda es tan facil como crear una tienda de prueba, añadir datos coherentes mediante el panel de administración de la tienta, e importarlos con el script.
<br /><br />
A la hora de volcar los datos a la nueva tienda éstos respetaran las asociaciones y el orden de inserción sera el correcto.
</p>