El Amor Por Sobre Todo El Encanto De Volare Para Siempre

Código e Implementación

Datos

Implementación de la tarea

C

Java

Implementación de nodos

Implementación de arcos

Tareas

Informe

Hipótesis

Diseño Experimental

Presentación de Resultados

Análisis

Conclusiones

Anexos

Código e Implementación

Datos

Los datos son un grafo no dirigido. La lectura de datos es muy simple (a diferencia de la tarea anterior, no se preocupen por eso).

[pancho]: dato rosa: hay 175813 nodos y 179179 arcos en la base de gatos.

Implementación de nodos

typedef struct { /* O class si es java */

int id;

long long int coords[2]; /* Coordenadas X e Y normalizadas a enteros */

} nodo;

Implementación de aristas

typedef struct {

double distancia;

nodo *n1;

nodo *n2;

} arista;

Implementación de arcos

Tres opciones:

Agregar una lista de nodos vecinos (y sus pesos) a la definición de nodo.

Matriz de incidencia (Son pocos arcos, así que no es muy buena idea).

Crear estructura de arcos con su peso, nodo origen, y nodo destino. Se puede agregar a cada nodo una lista con punteros a los arcos en cuestión.

Tareas

Kruskal:[pancho] works

Prim: [pancho] works

Dijkstra: [pancho] works

QuickSort: [pancho] works

RadixSort: [pancho] works

HeapSort: [pancho] works

TestSort: (testear los sorts de arriba) works

PQ con Heaps: [pancho] works

PQ con vEB: (el nico dice que es peludo)

PQ con Treaps: [rodrigo] works

PQ con arreglo simple:[pancho] works

Union Find (con y sin compresión de caminos): [pancho] works

Leer nodos y aristas de la Base de Gatos: [pancho] works

Detectar componentes conexas: [pancho] works

Experimentación (gprof …): works (es super “fácil” ocupar grof)

Crear tests para resultados definitivos: corrí 100 y 1000 repeticiones para cada variante.

% gcc -o binario asdf.c qwerty.c zxcv.c -pg

% ./binario

% gprof binario gmon.out > archivo_resultados

% gedit archivo_resultados

-> resultados \:D/

Informe

Introducción

Es común encontrar problemas reales cuya solución se basa en determinar cierta información a partir de un grafo. Algunos de estos problemas se pueden reducir a problemas recurrentes de teoría de grafos, tales como buscar la mejor forma de ir de un lugar a otro, el máximo flujo entre dos puntos del espacio, búsqueda de ciclos, caminos disjuntos, entre otros. Por ello, los grafos son un área de estudio importante para las ciencias de la computación.

En el contexto de este curso, se han estudiado diversas estructuras auxiliares para resolver problemas como encontrar componentes débilmente conexas de un grafo dirigido, obtener el árbol cobertor mínimo o MST de un grafo dirigido (usando para ello el algoritmo de Kruskal y el de Prim) y obtener el camino de menor costo de un nodo al resto de los nodos de un grafo (usando el algoritmo de Dijkstra). Estas estructuras representan conjuntos de los cuales queremos extraer eficientemente el mayor (o menor) elemento en un instante dado.

En particular, nos interesa comprobar si algoritmos de ordenamiento de tiempo O(n log u) en un intervalo acotado, como RadixSort, son más rápidos en la práctica que los algoritmos clásicos de ordenamiento de tiempo O(n log n), en otras palabras, que sus constantes no sean excesivamente grandes. Además, nos interesa conocer cuál implementación es más eficiente para una cola de prioridad: con un arreglo, con un heap, o con un treap.

Diseño Experimental

\begin{itemize}

\item Lectura de nodos y aristas.

\begin{itemize}

\item Para la experimentación se usó la información del grafo de distancias correspondiente a Norteamérica de la base de datos en http://www.cs.fsu.edu/~lifeifei/SpatialDataset.htm.

\item Las distancias de las aristas y posiciones de los nodos fueron multiplicadas por 10000 para trabajar sin decimales.

\item Se identificaron 175813 nodos y 179179 arcos en la base de datos.

\end{itemize}

\item Kruskal: se implementó como un método que recibe nodos y aristas, y retorna una lista de las aristas (struct aristak) correspondientes al MST. Se incorporó también un método para destruir esas aristas. Primero, se procede a ordenar las aristas ascendentemente según sus distancias; luego, se crea una “clase” por cada nodo. Cada clase será un árbol de nodos, de esta manera, se puede encontrar al representante de un nodo llegando hasta el nodo raíz (Find). Además, se pueden unir dos clases (Union) colgando un representante de otro (se cuelga el de menor cantidad de nodos). El procedimiento consiste en ir tomando arista por arista (en orden) y preguntar si los nodos que conforman la arista están en la misma clase (se compara el representante de cada uno en sus respectivos árboles). Si no lo están, se unen sus clases (Union) y se agrega la arista al MST. Lo anterior se repite hasta que todos los elementos de una misma componente conexa estén en la misma clase, o bien, hasta que no queden aristas en la estructura.

\begin{itemize}

\item Se implementaron variantes de Union-Find con y sin compresión de caminos. Para esto se usaron nodos especiales (struct nodok) que dieran soporte a la estructura del árbol de cada clase. Éstos almacenaban un puntero a un nodo real, un puntero al padre en el árbol, un peso correspondiente a la cantidad de nodos que cuelgan de él (para distinguir al árbol de menor peso al momento de hacer Union) y un puntero a un nodo siguiente (para almacenar en una lista los nodos que deben actualizar su representante en la variante con compresión de caminos). Luego la operación Union simplemente cuelga al representante del árbol de menor peso de otro de mayor peso, y actualiza el peso de la nueva raíz. El Find sube por el árbol correspondiente a la clase de un nodok hasta encontrar la raíz y retorna el representante, actualizando los

...