Tarea de filosofía colegio hernesto de moras

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).
: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:
1. Agregar una lista de nodosvecinos (y sus pesos) a la definición de nodo.
2. Matriz de incidencia (Son pocos arcos, así que no es muy buena idea).
3. 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:[] works
Prim: [] works
Dijkstra: [] works
QuickSort: [] works
RadixSort: [] works
HeapSort: [] worksTestSort: (testear los sorts de arriba) works
PQ con Heaps: [] works
PQ con vEB: (el nico dice que es peludo)
PQ con Treaps: [] works
PQ con arreglo simple:[] works
Union Find (con y sin compresión de caminos): [] works
Leer nodos y aristas de la Base de Gatos: [] works
Detectar componentes conexas: [] works
Experimentación (gprof …): works (es super “fácil” ocupar grof)
Crear tests pararesultados 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 puedenreducir 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 resolverproblemas 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 eficientementeel 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 esmá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 delas 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...