Semana 15 — Caminos mínimos y cierre
Objetivos
- Implementar Dijkstra usando el heap de la semana 13.
- Explicar qué supone Dijkstra sobre los pesos y qué pasa si no se cumple.
- Reconocer cuándo un trie o un filtro de Bloom resuelven mejor un problema conocido.
Teoría — Dijkstra con un heap · ✂️ Tries · ✂️ Filtros de Bloom · Repaso
Lectura: Apuntes, semana 15.
Apoyo: Open Data Structures, cap. 12 para la representación de grafos. CLRS, capítulo Single-Source Shortest Paths, la sección de Dijkstra. Sobre Dijkstra, tries de cadenas y filtros de Bloom los apuntes son el texto principal.
Temas:
- Con pesos, BFS ya no alcanza. El camino con menos aristas puede no ser el más corto.
- Relajar una arista. Dijkstra: sacar el nodo con la menor distancia conocida y relajar sus aristas.
- Cada estructura en su sitio: lista de adyacencia, heap como cola de prioridad y arreglo de distancias. Costo O((V + E) log V).
- Entradas viejas en el heap: se ignoran al sacarlas. Por qué es más simple que actualizar.
- Requiere pesos no negativos, con un contraejemplo. La demostración y otros algoritmos quedan para Algoritmos.
- ✂️ Tries: un diccionario de cadenas por prefijos. Otra forma de hacer el autocompletado de la semana 6.
- ✂️ Filtros de Bloom: k funciones hash sobre un arreglo de bits. Puede dar falsos positivos, nunca falsos negativos. Se ve con intuición y midiendo.
- Repaso: elegir una estructura según las operaciones que el problema necesita.
- Error común: detener Dijkstra al meter el destino al heap, y no al sacarlo.
Laboratorio — Rutas sobre un mapa real
Sesión 1:
- Cargar un mapa real dado como archivo de nodos y aristas con distancia en metros, en listas de adyacencia.
- Escribir Dijkstra con el
MinHeapde la semana 13 y reconstruir la ruta. - Comparar la ruta de Dijkstra con la de BFS entre varios pares de puntos: número de aristas y metros.
Sesión 2:
4. Detener la búsqueda al sacar el destino, y medir cuántos nodos se ahorran según la distancia.
5. Medir Dijkstra con su heap y con std::priority_queue, y con un arreglo sin heap, en mapas de tamaño creciente.
6. Opcional: escribir un trie para buscar lugares por prefijo, o un filtro de Bloom, y medir sus falsos positivos según su tamaño.
Preguntas de repaso
- Corran Dijkstra a mano sobre un grafo pequeño de su elección, y escriban el heap y las distancias en cada paso.
- Den un grafo con una arista negativa donde Dijkstra dé un resultado incorrecto.
- ¿De dónde sale cada factor en O((V + E) log V)?
- ¿Por qué un filtro de Bloom nunca dice “no está” para una clave que sí se insertó?
- Para cada problema, elijan una estructura y justifíquenla: las 10 palabras más frecuentes de un texto; todas las claves entre dos valores; saber si una palabra está en un diccionario fijo; un historial con deshacer.
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (10)Errores (5)Pruebas (5)Laboratorio (19)Compilación (1)
Ejemplos
Los programas que usan los apuntes y la clase.
// Medidor de tiempos del curso. Compilar con -O2 y sin sanitizers.
#ifndef BENCH_H
#define BENCH_H
#include <algorithm>
#include <chrono>
#include <vector>
// Corre fn `reps` veces y devuelve la mediana en segundos.
template <typename Fn>
double median_seconds(int reps, Fn fn) {
std::vector<double> times;
times.reserve(reps);
for (int i = 0; i < reps; i++) {
auto start = std::chrono::steady_clock::now();
fn();
auto stop = std::chrono::steady_clock::now();
times.push_back(std::chrono::duration<double>(stop - start).count());
}
std::sort(times.begin(), times.end());
return times[times.size() / 2];
}
// Evita que el compilador borre un cálculo cuyo resultado no se usa.
template <typename T>
void keep(const T& value) {
volatile T sink = value;
(void)sink;
}
#endif// Cuenta el trabajo de Dijkstra, y lo mide, sobre mapas de tamaño creciente.
// Va con -O2 y sin sanitizers. Los conteos son exactos, y los tiempos dependen de la máquina.
#include <cmath>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include "bench.h"
#include "map_file.h"
#include "shortest_paths.h"
int main(int argc, char* argv[]) {
std::cout << " nodos aristas sacados aristas leidas entradas viejas heap maximo ms ns/((V+E)log V)\n";
for (int i = 1; i < argc; i++) {
Graph graph = graph_of(read_map_file(argv[i]));
DijkstraResult result = dijkstra(graph, 0);
double seconds = median_seconds(11, [&] { keep(dijkstra(graph, 0).distance.back()); });
double v = graph.node_count();
double e = static_cast<double>(graph.edge_count());
const DijkstraCounts& c = result.counts;
std::cout << std::setw(9) << graph.node_count() << std::setw(10) << graph.edge_count() << std::setw(9)
<< c.settled << std::setw(16) << c.edges_read << std::setw(10) << c.pushes << std::setw(8) << c.stale
<< std::setw(13) << c.peak_heap << std::fixed << std::setprecision(3) << std::setw(8)
<< seconds * 1e3 << std::setprecision(2) << std::setw(17)
<< seconds * 1e9 / ((v + e) * std::log2(v)) << "\n";
}
return 0;
}// Dijkstra paso a paso sobre el grafo de la clase, desde el nodo 0.
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include "sample_graphs.h"
#include "shortest_paths.h"
#include "traversals.h"
namespace {
// El heap en orden de salida: una copia que se vacía. No es el orden del arreglo interno.
std::string heap_text(MinFirstQueue heap) {
std::ostringstream text;
while (!heap.empty()) {
text << "(" << heap.top().first << "," << heap.top().second << ") ";
heap.pop();
}
return text.str();
}
std::string distances_text(const std::vector<Meters>& distance) {
std::ostringstream text;
for (std::size_t v = 0; v < distance.size(); v++) {
text << (v == 0 ? "" : " ");
if (distance[v] == UNREACHABLE) {
text << "-";
} else {
text << distance[v];
}
}
return text.str();
}
} // namespace
int main() {
Graph graph = weighted_class_graph();
int n = graph.node_count();
std::vector<Meters> distance(n, UNREACHABLE);
std::vector<int> parent(n, -1);
std::vector<bool> settled(n, false);
MinFirstQueue heap;
distance[0] = 0;
parent[0] = 0;
heap.push({0, 0});
std::cout << std::left << std::setw(9) << "sale" << std::setw(11) << "relaja" << std::setw(16) << "distancias"
<< "heap\n";
std::cout << std::setw(9) << "-" << std::setw(11) << "-" << std::setw(16) << distances_text(distance)
<< heap_text(heap) << "\n";
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
std::ostringstream popped;
popped << "(" << d << "," << u << ")";
if (settled[u]) {
std::cout << std::setw(9) << popped.str() << std::setw(11) << "vieja" << std::setw(16)
<< distances_text(distance) << heap_text(heap) << "\n";
continue;
}
settled[u] = true;
std::ostringstream relaxed;
for (const Edge& edge : graph.neighbors(u)) {
if (d + edge.weight < distance[edge.to]) {
distance[edge.to] = d + edge.weight;
parent[edge.to] = u;
heap.push({distance[edge.to], edge.to});
relaxed << edge.to << " ";
}
}
std::cout << std::setw(9) << popped.str() << std::setw(11) << relaxed.str() << std::setw(16)
<< distances_text(distance) << heap_text(heap) << "\n";
}
std::cout << "ruta de Dijkstra a 6: ";
std::vector<int> route = path_to(parent, 6);
print_nodes(route);
std::cout << " aristas: " << route.size() - 1 << ", metros: " << path_meters(graph, route) << "\n";
std::vector<int> fewest = path_to(bfs(graph, 0).parent, 6);
std::cout << "ruta de BFS a 6: ";
print_nodes(fewest);
std::cout << " aristas: " << fewest.size() - 1 << ", metros: " << path_meters(graph, fewest) << "\n";
return 0;
}// ¿Puede hacer overflow un int al sumar metros? Lo que dice cada mapa, sin suposiciones.
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include "map_file.h"
#include "shortest_paths.h"
int main(int argc, char* argv[]) {
std::cout << "int llega hasta " << std::numeric_limits<int>::max() << "\n";
std::cout << "sizeof(HeapEntry): " << sizeof(HeapEntry) << "\n";
for (int i = 1; i < argc; i++) {
MapFile map = read_map_file(argv[i]);
Graph graph = graph_of(map);
Meters total = 0;
int longest = 0;
for (const MapEdge& edge : map.edges) {
total += edge.meters;
longest = std::max(longest, edge.meters);
}
// Dos pasadas: del nodo 0 al más lejano, y de ese al más lejano de él.
int start = 0;
Meters farthest = 0;
for (int pass = 0; pass < 2; pass++) {
DijkstraResult result = dijkstra(graph, start);
farthest = 0;
for (int v = 0; v < graph.node_count(); v++) {
if (result.distance[v] > farthest) {
farthest = result.distance[v];
start = v;
}
}
}
std::cout << argv[i] << ": arista mas larga " << longest << ", suma de todas " << total
<< ", ruta larga encontrada " << farthest << "\n";
}
return 0;
}// Grafo con listas de adyacencia. Los nodos son los enteros de 0 a node_count() - 1.
#ifndef GRAPH_H
#define GRAPH_H
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <tuple>
#include <vector>
// Una entrada de la lista de un nodo: a quién llega y cuánto pesa. Sin pesos, weight vale 1.
struct Edge {
int to;
int weight;
};
// Invariantes:
// - Todo destino de una lista es un nodo válido.
// - Las listas suman edge_count_ entradas si es dirigido, y 2 * edge_count_ si no lo es.
// - Si no es dirigido, cada entrada u -> v con peso w tiene su pareja v -> u con peso w, y no hay
// lazos (aristas de un nodo a sí mismo).
//
// No revisa aristas repetidas: hacerlo costaría recorrer una lista en cada add_edge.
// std::vector es owner de toda la memoria, así que copiar, mover y destruir ya funcionan.
class Graph {
public:
explicit Graph(int node_count, bool directed = false)
: adjacency_(node_count), directed_(directed) {}
void add_edge(int u, int v, int weight = 1) {
assert(valid(u) && valid(v));
assert(directed_ || u != v);
adjacency_[u].push_back({v, weight});
if (!directed_) {
adjacency_[v].push_back({u, weight});
}
edge_count_++;
}
int node_count() const { return static_cast<int>(adjacency_.size()); }
std::size_t edge_count() const { return edge_count_; }
bool directed() const { return directed_; }
// Referencia a la lista: recorrerla no copia nada. No agreguen aristas mientras la recorren.
const std::vector<Edge>& neighbors(int u) const {
assert(valid(u));
return adjacency_[u];
}
// Recorre la lista de u: Θ(grado de u) en el peor caso.
bool has_edge(int u, int v) const {
for (const Edge& edge : neighbors(u)) {
if (edge.to == v) {
return true;
}
}
return false;
}
bool check_invariants() const {
using Arc = std::tuple<int, int, int>;
std::vector<Arc> forward;
std::vector<Arc> backward;
for (int u = 0; u < node_count(); u++) {
for (const Edge& edge : adjacency_[u]) {
if (!valid(edge.to) || (!directed_ && edge.to == u)) {
return false;
}
forward.emplace_back(u, edge.to, edge.weight);
backward.emplace_back(edge.to, u, edge.weight);
}
}
if (forward.size() != (directed_ ? edge_count_ : 2 * edge_count_)) {
return false;
}
if (directed_) {
return true;
}
std::sort(forward.begin(), forward.end());
std::sort(backward.begin(), backward.end());
return forward == backward;
}
private:
friend struct GraphTestAccess;
bool valid(int u) const { return 0 <= u && u < node_count(); }
std::vector<std::vector<Edge>> adjacency_;
std::size_t edge_count_ = 0;
bool directed_;
};
#endif// Lee los archivos de data/mapas y arma el grafo.
#ifndef MAP_FILE_H
#define MAP_FILE_H
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include "graph.h"
struct MapEdge {
int u;
int v;
int meters;
};
struct MapPoint {
double latitude;
double longitude;
};
// Lo que dice el archivo: V nodos con sus coordenadas, y E tramos de calle, en el orden del archivo.
struct MapFile {
int node_count = 0;
std::vector<MapPoint> points;
std::vector<MapEdge> edges;
};
// Sale del programa si no puede leer el archivo completo.
inline MapFile read_map_file(const std::string& file_name) {
std::ifstream file(file_name);
MapFile map;
std::size_t edge_count = 0;
if (!(file >> map.node_count >> edge_count)) {
std::cerr << "no se pudo leer " << file_name << "\n";
std::exit(1);
}
map.points.resize(map.node_count);
for (MapPoint& point : map.points) {
file >> point.latitude >> point.longitude;
}
map.edges.resize(edge_count);
for (MapEdge& edge : map.edges) {
file >> edge.u >> edge.v >> edge.meters;
}
if (!file) {
std::cerr << "archivo incompleto: " << file_name << "\n";
std::exit(1);
}
return map;
}
inline Graph graph_of(const MapFile& map) {
Graph graph(map.node_count);
for (const MapEdge& edge : map.edges) {
graph.add_edge(edge.u, edge.v, edge.meters);
}
return graph;
}
// Un archivo *-calles.tsv: por cada nombre de calle, un nodo de esa calle.
struct Street {
int node;
std::string name;
};
inline std::vector<Street> read_streets(const std::string& file_name) {
std::ifstream file(file_name);
if (!file) {
std::cerr << "no se pudo leer " << file_name << "\n";
std::exit(1);
}
std::vector<Street> streets;
int node = 0;
std::string name;
while (file >> node) {
file.get(); // el tabulador
std::getline(file, name);
streets.push_back({node, name});
}
return streets;
}
// El nodo de una calle con ese nombre exacto. Sale del programa si no está.
inline int node_of_street(const std::vector<Street>& streets, const std::string& name) {
for (const Street& street : streets) {
if (street.name == name) {
return street.node;
}
}
std::cerr << "no hay ninguna calle con ese nombre: " << name << "\n";
std::exit(1);
}
// Metros en línea recta sobre la esfera, con la fórmula de los mapas del curso. Sirve para
// revisar si una ruta es razonable: ninguna ruta puede ser más corta que esto.
inline double straight_meters(const MapPoint& a, const MapPoint& b) {
const double to_radians = std::acos(-1.0) / 180.0;
double half_latitude = (b.latitude - a.latitude) * to_radians / 2;
double half_longitude = (b.longitude - a.longitude) * to_radians / 2;
double h = std::sin(half_latitude) * std::sin(half_latitude) +
std::cos(a.latitude * to_radians) * std::cos(b.latitude * to_radians) *
std::sin(half_longitude) * std::sin(half_longitude);
return 2 * 6371008.8 * std::asin(std::sqrt(h));
}
#endif// Una ruta sobre un mapa real: BFS frente a Dijkstra, y la línea recta para revisarla.
// Uso: route_demo mapa.txt calles.tsv "calle de origen" "calle de destino"
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include "map_file.h"
#include "shortest_paths.h"
#include "traversals.h"
int main(int argc, char* argv[]) {
if (argc != 5) {
std::cerr << "uso: route_demo mapa.txt calles.tsv origen destino\n";
return 2;
}
MapFile map = read_map_file(argv[1]);
std::vector<Street> streets = read_streets(argv[2]);
Graph graph = graph_of(map);
int from = node_of_street(streets, argv[3]);
int to = node_of_street(streets, argv[4]);
std::cout << "de " << argv[3] << " (nodo " << from << ") a " << argv[4] << " (nodo " << to << ")\n";
double straight = straight_meters(map.points[from], map.points[to]);
std::cout << std::fixed << std::setprecision(0) << "linea recta: " << straight << " metros\n";
std::vector<int> fewest = path_to(bfs(graph, from).parent, to);
Meters fewest_meters = path_meters(graph, fewest);
std::cout << "BFS: " << fewest.size() - 1 << " aristas, " << fewest_meters << " metros\n";
DijkstraResult result = dijkstra(graph, from);
std::vector<int> route = path_to(result.parent, to);
std::cout << "Dijkstra: " << route.size() - 1 << " aristas, " << result.distance[to] << " metros\n";
std::cout << std::setprecision(2) << "ruta sobre linea recta: " << result.distance[to] / straight << "\n";
return 0;
}// Los grafos pequeños de los apuntes.
#ifndef SAMPLE_GRAPHS_H
#define SAMPLE_GRAPHS_H
#include <iostream>
#include <vector>
#include "graph.h"
// El grafo de la clase de la semana 14, ahora con pesos.
inline Graph weighted_class_graph() {
Graph graph(7);
graph.add_edge(0, 1, 2);
graph.add_edge(0, 2, 9);
graph.add_edge(1, 3, 1);
graph.add_edge(2, 3, 1);
graph.add_edge(2, 4, 2);
graph.add_edge(3, 5, 8);
graph.add_edge(4, 5, 1);
graph.add_edge(5, 6, 3);
return graph;
}
// El contraejemplo de los apuntes. Dirigido: en uno no dirigido, una arista negativa ya es un ciclo.
inline Graph negative_edge_graph() {
Graph graph(4, true);
graph.add_edge(0, 1, 2);
graph.add_edge(0, 2, 3);
graph.add_edge(2, 1, -2);
graph.add_edge(1, 3, 1);
return graph;
}
inline void print_nodes(const std::vector<int>& nodes) {
for (std::size_t i = 0; i < nodes.size(); i++) {
std::cout << (i == 0 ? "" : " ") << nodes[i];
}
std::cout << "\n";
}
#endif// Dijkstra con std::priority_queue. En el laboratorio lo escriben con su propio MinHeap.
#ifndef SHORTEST_PATHS_H
#define SHORTEST_PATHS_H
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
#include "graph.h"
// 64 bits: dos aristas de 2 000 000 000 ya no caben en un int.
using Meters = std::int64_t;
// Distancia de un nodo al que no se llega. Nunca se le suma nada: solo se suma desde un nodo sacado.
const Meters UNREACHABLE = std::numeric_limits<Meters>::max();
// Distancia primero: std::pair compara por first y, si empatan, por second.
using HeapEntry = std::pair<Meters, int>;
using MinFirstQueue = std::priority_queue<HeapEntry, std::vector<HeapEntry>, std::greater<HeapEntry>>;
struct DijkstraCounts {
std::size_t settled = 0; // nodos que salieron con su distancia definitiva
std::size_t pushes = 0; // entradas que entraron al heap
std::size_t stale = 0; // entradas viejas, ignoradas al sacarlas
std::size_t edges_read = 0; // entradas de listas leídas
std::size_t peak_heap = 0; // el mayor tamaño que tuvo el heap
};
struct DijkstraResult {
std::vector<Meters> distance; // UNREACHABLE si no se llega
std::vector<int> parent; // -1 si no se llega, y el origen es su propio padre
DijkstraCounts counts;
};
// Requiere pesos no negativos.
inline DijkstraResult dijkstra(const Graph& graph, int source) {
int n = graph.node_count();
DijkstraResult result{std::vector<Meters>(n, UNREACHABLE), std::vector<int>(n, -1), {}};
std::vector<bool> settled(n, false);
MinFirstQueue heap;
result.distance[source] = 0;
result.parent[source] = source;
heap.push({0, source});
result.counts.pushes++;
result.counts.peak_heap = 1;
while (!heap.empty()) {
int u = heap.top().second;
heap.pop();
if (settled[u]) { // entrada vieja: ya salió con una distancia menor
result.counts.stale++;
continue;
}
settled[u] = true;
result.counts.settled++;
for (const Edge& edge : graph.neighbors(u)) {
result.counts.edges_read++;
Meters through_u = result.distance[u] + edge.weight;
if (through_u < result.distance[edge.to]) { // relajar la arista
result.distance[edge.to] = through_u;
result.parent[edge.to] = u;
heap.push({through_u, edge.to});
result.counts.pushes++;
result.counts.peak_heap = std::max(result.counts.peak_heap, heap.size());
}
}
}
return result;
}
// Suma los pesos de un camino. El camino tiene que usar aristas que existan.
inline Meters path_meters(const Graph& graph, const std::vector<int>& path) {
Meters total = 0;
for (std::size_t i = 1; i < path.size(); i++) {
bool found = false;
for (const Edge& edge : graph.neighbors(path[i - 1])) {
if (edge.to == path[i]) {
total += edge.weight;
found = true;
break;
}
}
assert(found);
}
return total;
}
#endif// BFS y reconstrucción de caminos, tal como quedaron en la semana 14.
#ifndef TRAVERSALS_H
#define TRAVERSALS_H
#include <algorithm>
#include <queue>
#include <vector>
#include "graph.h"
// distance[v]: aristas desde el origen, o -1 si no se llega a v.
// parent[v]: de dónde se llegó a v. -1 si no se llega, y el origen es su propio padre.
struct BfsResult {
std::vector<int> distance;
std::vector<int> parent;
};
inline BfsResult bfs(const Graph& graph, int source) {
int n = graph.node_count();
BfsResult result{std::vector<int>(n, -1), std::vector<int>(n, -1)};
std::queue<int> pending;
result.distance[source] = 0;
result.parent[source] = source;
pending.push(source);
while (!pending.empty()) {
int u = pending.front();
pending.pop();
for (const Edge& edge : graph.neighbors(u)) {
if (result.distance[edge.to] == -1) { // se marca al meterlo a la cola
result.distance[edge.to] = result.distance[u] + 1;
result.parent[edge.to] = u;
pending.push(edge.to);
}
}
}
return result;
}
// Camino del origen a target, siguiendo parent hacia atrás. Vacío si no se llega.
inline std::vector<int> path_to(const std::vector<int>& parent, int target) {
std::vector<int> path;
if (parent[target] == -1) {
return path;
}
int node = target;
while (parent[node] != node) {
path.push_back(node);
node = parent[node];
}
path.push_back(node);
std::reverse(path.begin(), path.end());
return path;
}
#endifErrores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
// Error: un heap de nodos, cuyo comparador lee el arreglo de distancias. Relajar cambia las claves
// de lo que ya está dentro, sin que el heap se entere, y deja de cumplir su invariante.
#include <iostream>
#include <queue>
#include <vector>
#include "../map_file.h"
#include "../shortest_paths.h"
int main(int argc, char* argv[]) {
if (argc != 2) {
std::cerr << "uso: comparator_reads_distance mapa.txt\n";
return 2;
}
Graph graph = graph_of(read_map_file(argv[1]));
int bad_runs = 0;
int bad_nodes = 0;
const int runs = 200;
for (int source = 0; source < runs; source++) {
std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
std::vector<bool> settled(graph.node_count(), false);
// Una lambda que captura no tiene constructor por defecto: hay que pasarla al construir.
auto farther = [&distance](int a, int b) { return distance[a] > distance[b]; };
std::priority_queue<int, std::vector<int>, decltype(farther)> heap(farther);
distance[source] = 0;
heap.push(source);
while (!heap.empty()) {
int u = heap.top();
heap.pop();
if (settled[u]) {
continue;
}
settled[u] = true;
for (const Edge& edge : graph.neighbors(u)) {
if (distance[u] + edge.weight < distance[edge.to]) {
distance[edge.to] = distance[u] + edge.weight;
heap.push(edge.to);
}
}
}
std::vector<Meters> right = dijkstra(graph, source).distance;
int bad = 0;
for (int v = 0; v < graph.node_count(); v++) {
bad += distance[v] != right[v] ? 1 : 0;
}
bad_nodes += bad;
bad_runs += bad > 0 ? 1 : 0;
}
std::cout << "origenes con alguna distancia equivocada: " << bad_runs << " de " << runs << "\n";
std::cout << "distancias equivocadas en total: " << bad_nodes << "\n";
return 0;
}// Error: std::priority_queue sin std::greater. Saca primero lo más lejano.
#include <iostream>
#include <queue>
#include <random>
#include <vector>
#include "../map_file.h"
#include "../shortest_paths.h"
namespace {
std::vector<Meters> farthest_first(const Graph& graph, int source) {
std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
std::vector<bool> settled(graph.node_count(), false);
std::priority_queue<HeapEntry> heap; // falta std::greater
distance[source] = 0;
heap.push({0, source});
while (!heap.empty()) {
int u = heap.top().second;
heap.pop();
if (settled[u]) {
continue;
}
settled[u] = true;
for (const Edge& edge : graph.neighbors(u)) {
if (distance[u] + edge.weight < distance[edge.to]) {
distance[edge.to] = distance[u] + edge.weight;
heap.push({distance[edge.to], edge.to});
}
}
}
return distance;
}
} // namespace
int main(int argc, char* argv[]) {
if (argc != 2) {
std::cerr << "uso: forgot_greater mapa.txt\n";
return 2;
}
Graph graph = graph_of(read_map_file(argv[1]));
std::vector<Meters> wrong = farthest_first(graph, 0);
std::vector<Meters> right = dijkstra(graph, 0).distance;
int bad = 0;
for (int v = 0; v < graph.node_count(); v++) {
if (wrong[v] != right[v]) {
bad++;
}
}
std::cout << "distancias equivocadas: " << bad << " de " << graph.node_count() << "\n";
return 0;
}// Una arista negativa: Dijkstra da por definitivo un nodo que todavía podía mejorar.
#include <iostream>
#include <vector>
#include "../sample_graphs.h"
#include "../shortest_paths.h"
namespace {
// La misma idea sin arreglo de sacados: una entrada es vieja si no coincide con la distancia.
// Si target no es -1, se detiene al sacarlo.
std::vector<Meters> without_settled_array(const Graph& graph, int source, int target, int& pulled) {
std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
MinFirstQueue heap;
distance[source] = 0;
heap.push({0, source});
while (!heap.empty() && pulled < 100) {
auto [d, u] = heap.top();
heap.pop();
pulled++;
if (d != distance[u]) {
continue;
}
if (u == target) {
break;
}
for (const Edge& edge : graph.neighbors(u)) {
if (d + edge.weight < distance[edge.to]) {
distance[edge.to] = d + edge.weight;
heap.push({distance[edge.to], edge.to});
}
}
}
return distance;
}
void print(const char* title, const std::vector<Meters>& distance) {
std::cout << title;
for (Meters d : distance) {
std::cout << " " << d;
}
std::cout << "\n";
}
} // namespace
int main() {
Graph graph = negative_edge_graph();
DijkstraResult result = dijkstra(graph, 0);
print("dijkstra: ", result.distance);
std::cout << "ruta real a 3: 0 2 1 3, con 3 + (-2) + 1 = 2\n";
int pulled = 0;
print("sin arreglo: ", without_settled_array(graph, 0, -1, pulled));
std::cout << "entradas sacadas: " << pulled << "\n";
pulled = 0;
std::cout << "sin arreglo, parando al sacar el 1: " << without_settled_array(graph, 0, 1, pulled)[1]
<< " (la verdad es 1)\n";
Graph cycle(3, true);
cycle.add_edge(0, 1, 1);
cycle.add_edge(1, 2, -3);
cycle.add_edge(2, 1, 1);
pulled = 0;
without_settled_array(cycle, 0, -1, pulled);
std::cout << "con un ciclo negativo, cortado tras " << pulled << " entradas sacadas\n";
return 0;
}// Error: guardar una referencia a top() y hacer pop(). La referencia queda mirando otra entrada.
#include <iostream>
#include <vector>
#include "../shortest_paths.h"
int main() {
MinFirstQueue heap;
heap.push({5, 1});
heap.push({3, 2});
heap.push({9, 3});
const HeapEntry& front = heap.top();
std::cout << "antes de pop: (" << front.first << "," << front.second << ")\n";
heap.pop();
std::cout << "despues de pop: (" << front.first << "," << front.second << ")\n";
return 0;
}// Error: detener Dijkstra al meter el destino al heap, como se detenía BFS en la semana 14.
// Uso: stop_at_push [mapa.txt]
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
#include "../map_file.h"
#include "../shortest_paths.h"
namespace {
Meters stop_when(const Graph& graph, int source, int target, bool at_push) {
int n = graph.node_count();
std::vector<Meters> distance(n, UNREACHABLE);
MinFirstQueue heap;
distance[source] = 0;
heap.push({0, source});
while (!heap.empty()) {
auto [d, u] = heap.top();
heap.pop();
if (d != distance[u]) {
continue;
}
if (!at_push && u == target) {
return d; // al sacarlo
}
for (const Edge& edge : graph.neighbors(u)) {
if (d + edge.weight < distance[edge.to]) {
distance[edge.to] = d + edge.weight;
if (at_push && edge.to == target) {
return distance[target]; // demasiado pronto
}
heap.push({distance[edge.to], edge.to});
}
}
}
return distance[target];
}
} // namespace
int main(int argc, char* argv[]) {
Graph tiny(3);
tiny.add_edge(0, 2, 5);
tiny.add_edge(0, 1, 1);
tiny.add_edge(1, 2, 1);
std::cout << "de 0 a 2, al meter: " << stop_when(tiny, 0, 2, true) << ", al sacar: " << stop_when(tiny, 0, 2, false)
<< "\n";
if (argc != 2) {
return 0;
}
Graph graph = graph_of(read_map_file(argv[1]));
std::mt19937 random(15);
int wrong = 0;
Meters worst = 0;
const int pairs = 1000;
for (int i = 0; i < pairs; i++) {
int source = static_cast<int>(random() % graph.node_count());
int target = static_cast<int>(random() % graph.node_count());
Meters early = stop_when(graph, source, target, true);
Meters right = stop_when(graph, source, target, false);
if (early != right) {
wrong++;
worst = std::max(worst, early - right);
}
}
std::cout << "en el mapa, " << wrong << " de " << pairs << " pares dan una distancia equivocada\n";
std::cout << "la peor sobra " << worst << " metros\n";
return 0;
}Pruebas
Comprueban lo que afirman los apuntes; se ejecutan con make test.
"""Corre los ejemplos de la semana y comprueba lo que se puede contar: nunca tiempos."""
import os
import pathlib
import subprocess
import unittest
HERE = pathlib.Path(__file__).parent
DATA = os.environ.get("DATA", "../../data")
MAPS = [f"{DATA}/mapas/miraflores.txt", f"{DATA}/mapas/lima-sur.txt", f"{DATA}/mapas/lima.txt"]
def run(*command):
return subprocess.run(
list(command), cwd=HERE, text=True, encoding="utf-8", errors="replace", stdin=subprocess.DEVNULL,
stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=300,
)
class Examples(unittest.TestCase):
def test_structure_tests_pass(self):
done = run("build/test_structures")
self.assertEqual(done.returncode, 0, done.stdout)
def test_programs_exit_cleanly(self):
done = run("build/dijkstra_trace")
self.assertEqual(done.returncode, 0, done.stdout)
def test_counts_on_real_maps(self):
"""V nodos sacados, 2E aristas leídas, y cada entrada sale: los números de la tabla."""
lines = run("build/dijkstra_counts", *MAPS).stdout.splitlines()
self.assertEqual(len(lines), 4)
for row in lines[1:]:
nodes, edges, settled, reads, pushes, stale, peak, *_ = (int(float(x)) for x in row.split())
self.assertEqual(settled, nodes)
self.assertEqual(reads, 2 * edges)
self.assertEqual(pushes, settled + stale)
self.assertLessEqual(pushes, 2 * edges + 1)
self.assertLessEqual(peak, pushes)
def test_int_cannot_overflow_on_these_maps(self):
"""Ninguna ruta sin repetir nodos pasa de la suma de todas las aristas."""
lines = run("build/distance_range", *MAPS).stdout.splitlines()
limit = int(lines[0].split()[-1])
for line in lines[2:]:
parts = line.replace(",", "").split()
total = int(parts[parts.index("todas") + 1])
self.assertLess(total, limit)
def test_public_tests_catch_nothing_written(self):
"""La carpeta de los estudiantes compila y se detiene en lo que falta."""
done = subprocess.run(
["make", "--no-print-directory", "LAB_DIR=lab", "build/lab/lab_tests", "build/lab/optional_tests"],
cwd=HERE, text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
)
self.assertEqual(done.returncode, 0, done.stdout)
self.assertNotIn("warning", done.stdout)
if __name__ == "__main__":
unittest.main()"""Pruebas del laboratorio, pasos 1 a 5. LAB_DIR dice dónde están sus archivos: lab o solution.
Cada prueba corre en su propio proceso, con sanitizers: una fuga o un acceso inválido
la hace fallar aunque el resultado parezca correcto.
"""
import os
import pathlib
import re
import subprocess
import unittest
HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
DATA = os.environ.get("DATA", "../../data")
BINARY = HERE / "build" / LAB_DIR / "lab_tests"
# Si una prueba no termina, lo más probable es un ciclo que no se detiene.
LIMIT_SECONDS = 60
def short_report(text):
"""Deja lo útil de un informe: el tipo de error y las líneas de sus archivos."""
if "ERROR:" not in text and "runtime error" not in text:
return text.strip()
useful = [line.strip() for line in text.splitlines()
if "ERROR:" in line or "SUMMARY:" in line or "runtime error" in line
or re.search(r"(routes\.h|min_heap\.h|lab_tests\.cpp):\d+", line)]
return "\n".join(useful[:12])
def build(target):
done = subprocess.run(
["make", "--no-print-directory", f"LAB_DIR={LAB_DIR}", f"build/{LAB_DIR}/{target}"],
cwd=HERE, text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
)
return done.returncode, done.stdout
def add_cases(cls, names):
for name in names:
def case(self, name=name):
try:
done = subprocess.run(
[str(BINARY), name, DATA], cwd=HERE, text=True, encoding="utf-8", errors="replace",
stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=LIMIT_SECONDS,
)
except subprocess.TimeoutExpired:
self.fail("no terminó a tiempo: ¿hay un ciclo que no se detiene?")
self.assertEqual(done.returncode, 0, short_report(done.stdout))
setattr(cls, f"test_{name}", case)
class LabCase(unittest.TestCase):
@classmethod
def setUpClass(cls):
code, output = build("lab_tests")
if code != 0:
raise AssertionError(output)
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class Builds(unittest.TestCase):
def test_builds_without_warnings(self):
for target in ["lab_tests", "compare_routes", "savings"]:
(HERE / "build" / LAB_DIR / target).unlink(missing_ok=True)
code, output = build(target)
self.assertEqual(code, 0, output)
self.assertNotIn("warning", output)
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestHeap(LabCase):
"""Antes de empezar: su MinHeap de la semana 13."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestMap(LabCase):
"""Paso 1: cargar el mapa en listas de adyacencia."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestDijkstra(LabCase):
"""Paso 2: Dijkstra con su MinHeap, y la ruta."""
def test_uses_min_heap(self):
text = (HERE / LAB_DIR / "routes.h").read_text(encoding="utf-8")
self.assertRegex(text, r"MinHeap\s*<", "dijkstra tiene que usar su MinHeap de la semana 13")
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestRoutes(LabCase):
"""Paso 3: BFS frente a Dijkstra."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestStop(LabCase):
"""Paso 4: detenerse al sacar el destino."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestQueues(LabCase):
"""Paso 5: std::priority_queue y el arreglo sin heap."""
add_cases(TestHeap, ["heap_from_week_13"])
add_cases(TestMap, ["map_graph_small", "map_graph_real"])
add_cases(TestDijkstra, [
"dijkstra_hand_case", "dijkstra_random_against_brute_force", "dijkstra_unreachable", "dijkstra_large_weights",
"dijkstra_counts_on_real_map", "dijkstra_many_sources_on_real_map", "route_on_hand_case", "route_on_real_map",
])
add_cases(TestRoutes, ["route_meters_hand_case", "routes_against_bfs"])
add_cases(TestStop, [
"stop_tiny_case", "stop_hand_case", "stop_random_against_brute_force", "stop_saves_nodes_on_real_map",
])
add_cases(TestQueues, [
"priority_queue_random_against_brute_force", "priority_queue_same_counts", "array_random_against_brute_force",
"array_disconnected", "array_reads_the_whole_array",
])
if __name__ == "__main__":
unittest.main()"""Vuelve a correr los comandos que aparecen en los apuntes y en las diapositivas
y comprueba que el código citado existe de verdad en esta carpeta."""
import pathlib
import re
import subprocess
import unittest
HERE = pathlib.Path(__file__).parent
ROOT = HERE.parent.parent
NOTES = ROOT / "notes" / "week-15.md"
SLIDES = ROOT / "slides" / "week-15.tex"
# Antes de un bloque cuya salida cambia con el sistema. Se corre, pero no se compara.
SYSTEM_DEPENDENT = "<!-- depende del sistema -->"
# Antes de un bloque que corre la solución: los estudiantes no tienen esa carpeta.
NEEDS_SOLUTION = "<!-- requiere la solucion -->"
HAS_SOLUTION = (HERE / "solution").is_dir()
def normalize(text):
# Según el idioma del entorno, gcc usa comillas tipográficas o rectas.
return text.replace("‘", "'").replace("’", "'")
def run_shell(command):
done = subprocess.run(
["bash", "-c", command], cwd=HERE, text=True, encoding="utf-8",
stdin=subprocess.DEVNULL, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=120,
)
return normalize(done.stdout)
def clean_lines(text):
return [line.rstrip() for line in text.splitlines()]
def split_commands(lines):
"""Parte un bloque de terminal en pares (comando, líneas de salida)."""
pairs = []
for line in lines:
if line.startswith("$ "):
pairs.append((line[2:], []))
elif pairs:
pairs[-1][1].append(normalize(line.rstrip()))
return pairs
def note_blocks(language):
"""Devuelve (líneas, marca) de cada bloque de los apuntes."""
blocks, current, mark, previous = [], None, "", ""
for raw in NOTES.read_text(encoding="utf-8").splitlines():
line = re.sub(r"^> ?", "", raw)
if current is None:
if line.strip() == "```" + language:
current, mark = [], previous.strip()
elif line.strip():
previous = line
elif line.strip() == "```":
blocks.append((current, mark))
current = None
else:
current.append(line)
return blocks
def slide_blocks(environments):
text = SLIDES.read_text(encoding="utf-8")
pattern = r"\\begin\{(?:%s)\}[^\n]*\n(.*?)\\end\{(?:%s)\}" % (environments, environments)
return [match.group(1).splitlines() for match in re.finditer(pattern, text, re.S)]
def known_code_lines():
lines = set()
sources = list(HERE.glob("*.cpp")) + list(HERE.glob("*.h")) + list((HERE / "errors").glob("*.cpp"))
sources += list((HERE / "lab").glob("*.h")) + list((HERE / "lab" / "tests").glob("*.cpp"))
for source in sources:
lines.update(line.strip() for line in source.read_text(encoding="utf-8").splitlines())
return lines
class OutputCheck(unittest.TestCase):
def assert_in_order(self, command, expected, actual):
"""Las líneas esperadas aparecen en la salida real, en orden. '...' marca un recorte."""
wanted = [line.strip() for line in expected if line.strip() and line.strip() != "..."]
real = [line.strip() for line in actual]
position = 0
for line in wanted:
with self.subTest(command=command, line=line):
found = [i for i in range(position, len(real)) if real[i] == line]
self.assertTrue(found, f"no aparece en la salida real: {line}")
if found:
position = found[0] + 1
class NotesAreTrue(OutputCheck):
@unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
def test_terminal_blocks_in_notes(self):
checked = 0
for lines, mark in note_blocks("text"):
if not lines or not lines[0].startswith("$ "):
continue
if mark == NEEDS_SOLUTION and not HAS_SOLUTION:
continue
for command, expected in split_commands(lines):
actual = clean_lines(run_shell(command))
checked += 1
if mark != SYSTEM_DEPENDENT:
with self.subTest(command=command):
self.assertEqual(actual, expected)
self.assertGreater(checked, 5)
@unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
def test_maps_are_credited_next_to_every_output(self):
"""Toda salida que usa un mapa lleva cerca el crédito. Las rutas, también el aviso de los sentidos."""
text = NOTES.read_text(encoding="utf-8")
for match in re.finditer(r"^\$ .*data/mapas", text, re.M):
after = text[match.start():match.start() + 1600]
self.assertIn("OpenStreetMap", after, match.group(0))
if "route_demo" in match.group(0):
self.assertIn("sentido", after)
class SlidesAreTrue(OutputCheck):
@unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
def test_program_output_in_slides(self):
for block in slide_blocks("terminal|salida"):
for command, expected in split_commands(block):
if "build/solution" in command and not HAS_SOLUTION:
continue
self.assert_in_order(command, expected, clean_lines(run_shell(command)))
@unittest.skipUnless(NOTES.exists() and SLIDES.exists(), "faltan los apuntes o las diapositivas")
def test_measurements_in_slides_come_from_notes(self):
"""Los tiempos dependen de la máquina: las diapositivas copian los de los apuntes."""
notes = NOTES.read_text(encoding="utf-8").splitlines()
blocks = slide_blocks("medicion|medicionchica")
self.assertGreaterEqual(len(blocks), 2)
for block in blocks:
for line in block:
with self.subTest(line=line):
self.assertIn(line, notes)
@unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
def test_maps_are_credited_in_slides(self):
text = SLIDES.read_text(encoding="utf-8")
self.assertIn("colaboradores de OpenStreetMap", text)
self.assertIn("sentido de circulación", text)
for frame in text.split("\\begin{frame}"):
if "route\\_demo" in frame or "Miraflores" in frame and "medicion" in frame:
self.assertIn("OpenStreetMap", frame.replace("creditomapa", "OpenStreetMap"))
@unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
def test_code_blocks_in_slides_exist(self):
known = known_code_lines()
for block in slide_blocks("codigo|codigochico|codigomini"):
for line in block:
if line.strip() and line.strip() != "...":
with self.subTest(line=line):
self.assertIn(line.strip(), known)
if __name__ == "__main__":
unittest.main()"""Pruebas del paso 6, que es opcional. LAB_DIR dice dónde están sus archivos: lab o solution."""
import os
import pathlib
import subprocess
import unittest
HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
BINARY = HERE / "build" / LAB_DIR / "optional_tests"
LIMIT_SECONDS = 60
def add_cases(cls, names):
for name in names:
def case(self, name=name):
done = subprocess.run(
[str(BINARY), name, "lab/tests"], cwd=HERE, text=True, encoding="utf-8", errors="replace",
stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=LIMIT_SECONDS,
)
self.assertEqual(done.returncode, 0, done.stdout.strip())
setattr(cls, f"test_{name}", case)
class OptionalCase(unittest.TestCase):
@classmethod
def setUpClass(cls):
done = subprocess.run(
["make", "--no-print-directory", f"LAB_DIR={LAB_DIR}", f"build/{LAB_DIR}/optional_tests"],
cwd=HERE, text=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT,
)
if done.returncode != 0:
raise AssertionError(done.stdout)
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestTrie(OptionalCase):
"""Paso 6: el trie."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestBloom(OptionalCase):
"""Paso 6: el filtro de Bloom."""
add_cases(TestTrie, [
"trie_insert_and_find", "trie_shares_prefixes", "trie_prefix_in_byte_order", "trie_random_against_map",
])
add_cases(TestBloom, [
"bloom_sets_the_right_bits", "bloom_no_false_negatives", "bloom_false_positives_fall_with_size",
"bloom_uses_all_hashes",
])
if __name__ == "__main__":
unittest.main()// Pruebas de los ejemplos: Dijkstra contra un cálculo por fuerza bruta, y lo que dicen los apuntes.
#include <cassert>
#include <iostream>
#include <random>
#include <vector>
#include "graph.h"
#include "sample_graphs.h"
#include "shortest_paths.h"
#include "traversals.h"
namespace {
std::vector<Meters> brute_force(const Graph& graph, int source) {
std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
distance[source] = 0;
bool changed = true;
while (changed) {
changed = false;
for (int u = 0; u < graph.node_count(); u++) {
if (distance[u] == UNREACHABLE) {
continue;
}
for (const Edge& edge : graph.neighbors(u)) {
if (distance[u] + edge.weight < distance[edge.to]) {
distance[edge.to] = distance[u] + edge.weight;
changed = true;
}
}
}
}
return distance;
}
void test_class_graph() {
Graph graph = weighted_class_graph();
assert(graph.check_invariants());
DijkstraResult result = dijkstra(graph, 0);
std::vector<Meters> expected{0, 2, 4, 3, 6, 7, 10};
assert(result.distance == expected);
assert(result.counts.settled == 7);
assert(result.counts.pushes == 9);
assert(result.counts.stale == 2);
assert(result.counts.edges_read == 16);
std::vector<int> route{0, 1, 3, 2, 4, 5, 6};
assert(path_to(result.parent, 6) == route);
assert(path_meters(graph, route) == 10);
std::vector<int> fewest{0, 1, 3, 5, 6};
assert(path_to(bfs(graph, 0).parent, 6) == fewest);
assert(path_meters(graph, fewest) == 14);
}
// La corrida a mano de los apuntes.
void test_hand_run() {
Graph graph(5);
graph.add_edge(0, 1, 4);
graph.add_edge(0, 2, 1);
graph.add_edge(2, 1, 2);
graph.add_edge(1, 3, 5);
graph.add_edge(2, 3, 8);
graph.add_edge(3, 4, 3);
DijkstraResult result = dijkstra(graph, 0);
std::vector<Meters> expected{0, 3, 1, 8, 11};
assert(result.distance == expected);
assert(result.counts.stale == 2);
assert(result.counts.pushes == 7);
std::vector<int> route{0, 2, 1, 3, 4};
assert(path_to(result.parent, 4) == route);
}
void test_random_against_brute_force() {
std::mt19937 random(150);
for (int round = 0; round < 500; round++) {
int n = 1 + static_cast<int>(random() % 12);
Graph graph(n, random() % 2 == 0);
int edges = static_cast<int>(random() % (2 * n + 1));
for (int i = 0; i < edges; i++) {
int u = static_cast<int>(random() % n);
int v = static_cast<int>(random() % n);
if (u != v) {
graph.add_edge(u, v, static_cast<int>(random() % 10));
}
}
int source = static_cast<int>(random() % n);
DijkstraResult result = dijkstra(graph, source);
assert(result.distance == brute_force(graph, source));
assert(result.counts.pushes == result.counts.settled + result.counts.stale);
std::size_t entries = 0;
for (int u = 0; u < n; u++) {
entries += graph.neighbors(u).size();
}
assert(result.counts.pushes <= entries + 1);
}
}
void test_large_weights() {
Graph graph(3);
graph.add_edge(0, 1, 2000000000);
graph.add_edge(1, 2, 2000000000);
assert(dijkstra(graph, 0).distance[2] == 4000000000LL);
}
// Con todas las aristas de peso 1, las distancias son las de BFS.
void test_unit_weights_match_bfs() {
std::mt19937 random(151);
for (int round = 0; round < 200; round++) {
int n = 2 + static_cast<int>(random() % 15);
Graph graph(n);
for (int i = 0; i < 2 * n; i++) {
int u = static_cast<int>(random() % n);
int v = static_cast<int>(random() % n);
if (u != v) {
graph.add_edge(u, v);
}
}
DijkstraResult result = dijkstra(graph, 0);
BfsResult levels = bfs(graph, 0);
for (int v = 0; v < n; v++) {
Meters expected = levels.distance[v] == -1 ? UNREACHABLE : levels.distance[v];
assert(result.distance[v] == expected);
}
}
}
void test_negative_edge_gives_wrong_answer() {
Graph graph = negative_edge_graph();
assert(dijkstra(graph, 0).distance[3] == 3);
assert(brute_force(graph, 0)[3] == 2);
}
} // namespace
int main() {
test_class_graph();
test_hand_run();
test_random_against_brute_force();
test_large_weights();
test_unit_weights_match_bfs();
test_negative_edge_gives_wrong_answer();
std::cout << "ok\n";
return 0;
}Laboratorio
Archivos de partida del laboratorio de la semana.
// Paso 6, opcional: un filtro de Bloom.
#ifndef BLOOM_H
#define BLOOM_H
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
#include "not_implemented.h"
// El FNV-1a de 64 bits de la semana 7.
inline std::uint64_t fnv1a(const std::string& key) {
std::uint64_t hash = 14695981039346656037ULL;
for (char c : key) {
hash ^= static_cast<unsigned char>(c);
hash *= 1099511628211ULL;
}
return hash;
}
// De un solo hash salen k posiciones. La mitad baja es h1 y la mitad alta, forzada a impar, es h2:
// así, con bits par, h2 nunca es múltiplo de bits. La posición i es (h1 + i * h2) mod bits.
inline std::size_t bloom_position(const std::string& key, int i, std::size_t bits) {
std::uint64_t hash = fnv1a(key);
std::uint64_t h1 = hash & 0xFFFFFFFFULL;
std::uint64_t h2 = (hash >> 32) | 1;
return static_cast<std::size_t>((h1 + static_cast<std::uint64_t>(i) * h2) % bits);
}
// Invariante: bits_.size() es el tamaño pedido, y un bit encendido nunca se apaga.
class BloomFilter {
public:
BloomFilter(std::size_t bits, int hash_count) : bits_(bits, false), hash_count_(hash_count) {
assert(bits > 0 && hash_count > 0);
}
// Enciende las hash_count posiciones de key.
void add(const std::string& key) {
(void)key;
not_implemented("BloomFilter::add");
}
// false: seguro que key no se agregó. true: quizás se agregó.
bool possibly_contains(const std::string& key) const {
(void)key;
not_implemented("BloomFilter::possibly_contains");
}
// Cuántos bits están encendidos.
std::size_t bits_on() const {
not_implemented("BloomFilter::bits_on");
}
std::size_t bit_count() const { return bits_.size(); }
int hash_count() const { return hash_count_; }
private:
std::vector<bool> bits_;
int hash_count_;
};
#endif// Grafo con listas de adyacencia. Los nodos son los enteros de 0 a node_count() - 1.
#ifndef GRAPH_H
#define GRAPH_H
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <tuple>
#include <vector>
// Una entrada de la lista de un nodo: a quién llega y cuánto pesa. Sin pesos, weight vale 1.
struct Edge {
int to;
int weight;
};
// Invariantes:
// - Todo destino de una lista es un nodo válido.
// - Las listas suman edge_count_ entradas si es dirigido, y 2 * edge_count_ si no lo es.
// - Si no es dirigido, cada entrada u -> v con peso w tiene su pareja v -> u con peso w, y no hay
// lazos (aristas de un nodo a sí mismo).
//
// No revisa aristas repetidas: hacerlo costaría recorrer una lista en cada add_edge.
// std::vector es owner de toda la memoria, así que copiar, mover y destruir ya funcionan.
class Graph {
public:
explicit Graph(int node_count, bool directed = false)
: adjacency_(node_count), directed_(directed) {}
void add_edge(int u, int v, int weight = 1) {
assert(valid(u) && valid(v));
assert(directed_ || u != v);
adjacency_[u].push_back({v, weight});
if (!directed_) {
adjacency_[v].push_back({u, weight});
}
edge_count_++;
}
int node_count() const { return static_cast<int>(adjacency_.size()); }
std::size_t edge_count() const { return edge_count_; }
bool directed() const { return directed_; }
// Referencia a la lista: recorrerla no copia nada. No agreguen aristas mientras la recorren.
const std::vector<Edge>& neighbors(int u) const {
assert(valid(u));
return adjacency_[u];
}
// Recorre la lista de u: Θ(grado de u) en el peor caso.
bool has_edge(int u, int v) const {
for (const Edge& edge : neighbors(u)) {
if (edge.to == v) {
return true;
}
}
return false;
}
bool check_invariants() const {
using Arc = std::tuple<int, int, int>;
std::vector<Arc> forward;
std::vector<Arc> backward;
for (int u = 0; u < node_count(); u++) {
for (const Edge& edge : adjacency_[u]) {
if (!valid(edge.to) || (!directed_ && edge.to == u)) {
return false;
}
forward.emplace_back(u, edge.to, edge.weight);
backward.emplace_back(edge.to, u, edge.weight);
}
}
if (forward.size() != (directed_ ? edge_count_ : 2 * edge_count_)) {
return false;
}
if (directed_) {
return true;
}
std::sort(forward.begin(), forward.end());
std::sort(backward.begin(), backward.end());
return forward == backward;
}
private:
friend struct GraphTestAccess;
bool valid(int u) const { return 0 <= u && u < node_count(); }
std::vector<std::vector<Edge>> adjacency_;
std::size_t edge_count_ = 0;
bool directed_;
};
#endif// Lee los archivos de data/mapas. Solo los lee: armar el grafo es su trabajo, en el paso 1.
#ifndef MAP_FILE_H
#define MAP_FILE_H
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
struct MapEdge {
int u;
int v;
int meters;
};
struct MapPoint {
double latitude;
double longitude;
};
// Lo que dice el archivo: V nodos con sus coordenadas, y E tramos de calle, en el orden del archivo.
struct MapFile {
int node_count = 0;
std::vector<MapPoint> points;
std::vector<MapEdge> edges;
};
// Sale del programa si no puede leer el archivo completo.
inline MapFile read_map_file(const std::string& file_name) {
std::ifstream file(file_name);
MapFile map;
std::size_t edge_count = 0;
if (!(file >> map.node_count >> edge_count)) {
std::cerr << "no se pudo leer " << file_name << "\n";
std::exit(1);
}
map.points.resize(map.node_count);
for (MapPoint& point : map.points) {
file >> point.latitude >> point.longitude;
}
map.edges.resize(edge_count);
for (MapEdge& edge : map.edges) {
file >> edge.u >> edge.v >> edge.meters;
}
if (!file) {
std::cerr << "archivo incompleto: " << file_name << "\n";
std::exit(1);
}
return map;
}
// Un archivo *-calles.tsv: por cada nombre de calle, un nodo de esa calle.
struct Street {
int node;
std::string name;
};
inline std::vector<Street> read_streets(const std::string& file_name) {
std::ifstream file(file_name);
if (!file) {
std::cerr << "no se pudo leer " << file_name << "\n";
std::exit(1);
}
std::vector<Street> streets;
int node = 0;
std::string name;
while (file >> node) {
file.get(); // el tabulador
std::getline(file, name);
streets.push_back({node, name});
}
return streets;
}
// El nodo de una calle con ese nombre exacto. Sale del programa si no está.
inline int node_of_street(const std::vector<Street>& streets, const std::string& name) {
for (const Street& street : streets) {
if (street.name == name) {
return street.node;
}
}
std::cerr << "no hay ninguna calle con ese nombre: " << name << "\n";
std::exit(1);
}
// Metros en línea recta sobre la esfera, con la fórmula de los mapas del curso. Sirve para
// revisar si una ruta es razonable: ninguna ruta puede ser más corta que esto.
inline double straight_meters(const MapPoint& a, const MapPoint& b) {
const double to_radians = std::acos(-1.0) / 180.0;
double half_latitude = (b.latitude - a.latitude) * to_radians / 2;
double half_longitude = (b.longitude - a.longitude) * to_radians / 2;
double h = std::sin(half_latitude) * std::sin(half_latitude) +
std::cos(a.latitude * to_radians) * std::cos(b.latitude * to_radians) *
std::sin(half_longitude) * std::sin(half_longitude);
return 2 * 6371008.8 * std::asin(std::sqrt(h));
}
#endif// Lugar para su MinHeap de la semana 13. REEMPLACEN este archivo por el suyo:
//
// cp ../week-13/lab/min_heap.h lab/min_heap.h
//
// Mientras no lo hagan, compila, pero el programa se detiene al usar el heap.
#ifndef MIN_HEAP_H
#define MIN_HEAP_H
#include <cstddef>
#include <functional>
#include <utility>
#include <vector>
#include "not_implemented.h"
template <typename T, typename Less = std::less<T>>
class MinHeap {
public:
MinHeap() = default;
explicit MinHeap(Less less) : less_(std::move(less)) {}
explicit MinHeap(std::vector<T> items, Less less = Less()) : items_(std::move(items)), less_(std::move(less)) {
not_implemented("MinHeap: copien su min_heap.h de la semana 13");
}
void push(T) { not_implemented("MinHeap: copien su min_heap.h de la semana 13"); }
void pop() { not_implemented("MinHeap: copien su min_heap.h de la semana 13"); }
const T& top() const { not_implemented("MinHeap: copien su min_heap.h de la semana 13"); }
bool empty() const { not_implemented("MinHeap: copien su min_heap.h de la semana 13"); }
std::size_t size() const { not_implemented("MinHeap: copien su min_heap.h de la semana 13"); }
void check_invariants() const { not_implemented("MinHeap: copien su min_heap.h de la semana 13"); }
private:
std::vector<T> items_;
Less less_{};
};
#endif// Para los métodos que todavía no escriben: detiene el programa y dice cuál falta.
#ifndef NOT_IMPLEMENTED_H
#define NOT_IMPLEMENTED_H
#include <cstdio>
#include <cstdlib>
[[noreturn]] inline void not_implemented(const char* name) {
std::fprintf(stderr, "sin implementar: %s\n", name);
std::abort();
}
#endif# Informe del laboratorio
Respondan con sus propios números. Las rutas ignoran el sentido de circulación, y los mapas son datos de © colaboradores
de OpenStreetMap.
## Paso 3: BFS frente a Dijkstra
Peguen la tabla de `make compare`. ¿En cuántas filas son distintas las dos rutas? Busquen la fila con la mayor diferencia en
metros. ¿Dijkstra siempre usa más aristas, o puede usar las mismas? ¿Qué nunca puede pasar en esa tabla?
Revisen una de las rutas contra la línea recta. ¿Cuánto más larga es? ¿Qué se puede concluir de esa revisión, y qué no?
## Paso 4: detenerse al sacar el destino
Peguen la tabla de `make savings`. ¿Cómo cambia el ahorro con la distancia? ¿Por qué ese porcentaje se parece tanto a la primera
columna? ¿Cuánto se ahorra si el destino es el nodo más lejano?
## Paso 5: tres colas
Peguen la tabla de `make measure`, de tres corridas. Digan en qué máquina midieron. ¿Cuánto crece cada columna entre un mapa y el
siguiente? ¿Es lo que predicen O((V + E) log V) y Θ(V²)? ¿Qué parte de sus conclusiones se sostiene en las tres corridas? ¿Por
qué no se corre el arreglo sobre `lima.txt`? Estimen cuánto tardaría.
## Paso 6, opcional
Si hicieron el filtro de Bloom, peguen la tabla de `make measure-bloom` y digan cuántos bits por clave pedirían para una tasa de
1 %. Si hicieron el trie, peguen la de `make trie-sizes` y comparen sus nodos con los bytes de las claves.// Rutas sobre un mapa real. Completen cada función marcada con not_implemented.
#ifndef ROUTES_H
#define ROUTES_H
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
#include "graph.h"
#include "map_file.h"
#include "min_heap.h"
#include "not_implemented.h"
// 64 bits: dos aristas de 2 000 000 000 ya no caben en un int.
using Meters = std::int64_t;
// Distancia de un nodo al que no se llega.
const Meters UNREACHABLE = std::numeric_limits<Meters>::max();
// Distancia primero: std::pair compara por first y, si empatan, por second. Usen este tipo en los
// heaps: así su MinHeap y std::priority_queue sacan las entradas en el mismo orden.
using HeapEntry = std::pair<Meters, int>;
struct DijkstraCounts {
std::size_t settled = 0; // nodos que salieron con su distancia definitiva
std::size_t pushes = 0; // entradas que entraron al heap, contando la del origen
std::size_t stale = 0; // entradas viejas, ignoradas al sacarlas
std::size_t edges_read = 0; // entradas de listas leídas al relajar
std::size_t scanned = 0; // solo sin heap: lecturas del arreglo para buscar el menor
};
struct DijkstraResult {
std::vector<Meters> distance; // UNREACHABLE si no se llega
std::vector<int> parent; // -1 si no se llega, y el origen es su propio padre
DijkstraCounts counts;
};
// Paso 1: un nodo por cada nodo del archivo, y una arista no dirigida por cada tramo, con sus metros.
inline Graph build_map_graph(const MapFile& map) {
(void)map;
not_implemented("build_map_graph");
}
// Paso 2: Dijkstra con su MinHeap, hasta vaciar el heap. Requiere pesos no negativos.
inline DijkstraResult dijkstra(const Graph& graph, int source) {
(void)graph;
(void)source;
not_implemented("dijkstra");
}
// Paso 2: del origen a target, los dos incluidos. Vacío si no se llega. El origen es su propio padre.
inline std::vector<int> route_to(const std::vector<int>& parent, int target) {
(void)parent;
(void)target;
not_implemented("route_to");
}
// Paso 3: suma los pesos de una ruta. Requiere que cada par seguido de la ruta sea una arista.
// Una ruta vacía o de un solo nodo suma 0.
inline Meters route_meters(const Graph& graph, const std::vector<int>& route) {
(void)graph;
(void)route;
not_implemented("route_meters");
}
// Paso 4: igual que dijkstra, pero se detiene al SACAR a target del heap, sin leer su lista. Solo las distancias
// de los nodos sacados quedan definitivas. Si no se llega a target, termina vaciando el heap.
inline DijkstraResult dijkstra_to(const Graph& graph, int source, int target) {
(void)graph;
(void)source;
(void)target;
not_implemented("dijkstra_to");
}
// Paso 5: igual que dijkstra, con std::priority_queue en vez de su MinHeap. Cuidado con el comparador.
inline DijkstraResult dijkstra_priority_queue(const Graph& graph, int source) {
(void)graph;
(void)source;
not_implemented("dijkstra_priority_queue");
}
// Paso 5: sin heap. En cada vuelta recorre todo el arreglo buscando el nodo sin sacar con menor distancia,
// y cuenta esas lecturas en counts.scanned. Termina cuando no queda ninguno alcanzable.
inline DijkstraResult dijkstra_array(const Graph& graph, int source) {
(void)graph;
(void)source;
not_implemented("dijkstra_array");
}
#endif// BFS y reconstrucción de caminos, tal como quedaron en la semana 14.
#ifndef TRAVERSALS_H
#define TRAVERSALS_H
#include <algorithm>
#include <queue>
#include <vector>
#include "graph.h"
// distance[v]: aristas desde el origen, o -1 si no se llega a v.
// parent[v]: de dónde se llegó a v. -1 si no se llega, y el origen es su propio padre.
struct BfsResult {
std::vector<int> distance;
std::vector<int> parent;
};
inline BfsResult bfs(const Graph& graph, int source) {
int n = graph.node_count();
BfsResult result{std::vector<int>(n, -1), std::vector<int>(n, -1)};
std::queue<int> pending;
result.distance[source] = 0;
result.parent[source] = source;
pending.push(source);
while (!pending.empty()) {
int u = pending.front();
pending.pop();
for (const Edge& edge : graph.neighbors(u)) {
if (result.distance[edge.to] == -1) { // se marca al meterlo a la cola
result.distance[edge.to] = result.distance[u] + 1;
result.parent[edge.to] = u;
pending.push(edge.to);
}
}
}
return result;
}
// Camino del origen a target, siguiendo parent hacia atrás. Vacío si no se llega.
inline std::vector<int> path_to(const std::vector<int>& parent, int target) {
std::vector<int> path;
if (parent[target] == -1) {
return path;
}
int node = target;
while (parent[node] != node) {
path.push_back(node);
node = parent[node];
}
path.push_back(node);
std::reverse(path.begin(), path.end());
return path;
}
#endif// Paso 6, opcional: un trie para buscar lugares por prefijo.
// Cada nodo es un prefijo, y sus hijos se indexan por byte. Trabaja con bytes: una letra con tilde son dos
// bytes, y dos niveles del trie.
#ifndef TRIE_H
#define TRIE_H
#include <cstddef>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include "not_implemented.h"
// Invariantes, en un comentario y en check_invariants, como siempre:
// - La raíz es nodes_[0], y todo hijo es un índice válido de nodes_.
// - Cada nodo menos la raíz es hijo de exactamente uno.
// - place_count_ es la cantidad de nodos con place != -1.
// Los nodos viven en un std::vector y se apuntan por índice: no hay new ni delete, y copiar ya funciona.
class PlaceTrie {
public:
PlaceTrie() : nodes_(1) {}
// Guarda un lugar con su nodo del mapa. node >= 0. Si el nombre ya estaba, cambia su nodo.
void insert(const std::string& name, int node) {
(void)name;
(void)node;
not_implemented("PlaceTrie::insert");
}
// El nodo del mapa con ese nombre exacto, o -1 si no está.
int find(const std::string& name) const {
(void)name;
not_implemented("PlaceTrie::find");
}
// Todos los lugares que empiezan con prefix, en orden de bytes. El prefijo vacío los da todos.
std::vector<std::pair<std::string, int>> with_prefix(const std::string& prefix) const {
(void)prefix;
not_implemented("PlaceTrie::with_prefix");
}
std::size_t place_count() const { return place_count_; }
std::size_t node_count() const { return nodes_.size(); }
bool check_invariants() const {
std::vector<int> times_child(nodes_.size(), 0);
std::size_t places = 0;
for (const TrieNode& node : nodes_) {
places += node.place != -1 ? 1 : 0;
for (const auto& [byte, child] : node.children) {
if (child <= 0 || static_cast<std::size_t>(child) >= nodes_.size()) {
return false;
}
times_child[child]++;
}
}
for (std::size_t i = 1; i < nodes_.size(); i++) {
if (times_child[i] != 1) {
return false;
}
}
return times_child[0] == 0 && places == place_count_;
}
private:
struct TrieNode {
std::map<unsigned char, int> children; // sin signo: así el orden es el de bytes
int place = -1; // nodo del mapa, o -1 si aquí no termina ningún nombre
};
std::vector<TrieNode> nodes_;
std::size_t place_count_ = 0;
};
#endif// Paso 5: su heap, std::priority_queue y el arreglo, en mapas de tamaño creciente.
// Corre desde el nodo 0, sin parar en ningún destino. Va con -O2 y sin sanitizers.
// El arreglo solo corre en mapas de hasta LIMIT_FOR_ARRAY nodos: en lima.txt son unas 6250 millones de
// lecturas por corrida, y cinco corridas tardan demasiado para repetirlas a cada rato.
// Uso: bench_routes mapa.txt...
#include <iomanip>
#include <iostream>
#include "bench.h"
#include "map_file.h"
#include "routes.h"
int main(int argc, char* argv[]) {
const int LIMIT_FOR_ARRAY = 25000;
std::cout << " nodos aristas su heap ms biblioteca ms arreglo ms lecturas del arreglo\n";
for (int i = 1; i < argc; i++) {
Graph graph = build_map_graph(read_map_file(argv[i]));
double own = median_seconds(11, [&] { keep(dijkstra(graph, 0).distance.back()); });
double library = median_seconds(11, [&] { keep(dijkstra_priority_queue(graph, 0).distance.back()); });
std::cout << std::setw(9) << graph.node_count() << std::setw(10) << graph.edge_count() << std::fixed
<< std::setprecision(3) << std::setw(13) << own * 1e3 << std::setw(16) << library * 1e3;
if (graph.node_count() <= LIMIT_FOR_ARRAY) {
std::size_t reads = 0;
double array = median_seconds(5, [&] { reads = dijkstra_array(graph, 0).counts.scanned; });
std::cout << std::setw(13) << array * 1e3 << std::setw(23) << reads << "\n";
} else {
std::cout << " no se corre\n";
}
}
return 0;
}// Paso 6, con filtro de Bloom: mide los falsos positivos. Agrega una línea de cada dos del
// archivo y pregunta por las otras: esas no están, así que todo sí es un falso positivo.
// Uso: bloom_measure palabras.txt
#include <fstream>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
#include "bloom.h"
namespace {
void print_row(const std::vector<std::string>& words, std::size_t bits_per_key, int k) {
std::size_t keys = (words.size() + 1) / 2;
BloomFilter filter(keys * bits_per_key, k);
for (std::size_t i = 0; i < words.size(); i += 2) {
filter.add(words[i]);
}
std::size_t asked = 0;
std::size_t positives = 0;
for (std::size_t i = 1; i < words.size(); i += 2) {
asked++;
positives += filter.possibly_contains(words[i]) ? 1 : 0;
}
std::cout << std::fixed << std::setw(14) << bits_per_key << std::setw(4) << k << std::setprecision(2) << std::setw(8)
<< static_cast<double>(filter.bit_count()) / 8e6 << std::setw(11) << positives << std::setprecision(3)
<< std::setw(9) << 100.0 * static_cast<double>(positives) / asked << " %" << std::setprecision(1)
<< std::setw(16) << 100.0 * static_cast<double>(filter.bits_on()) / filter.bit_count() << " %\n";
}
} // namespace
int main(int argc, char* argv[]) {
if (argc != 2) {
std::cerr << "uso: bloom_measure palabras.txt\n";
return 2;
}
std::ifstream file(argv[1]);
std::vector<std::string> words;
std::string word;
while (file >> word) {
words.push_back(word);
}
std::cout << "agregadas: " << (words.size() + 1) / 2 << ", preguntadas: " << words.size() / 2 << "\n";
std::cout << "bits por clave k MB positivos tasa bits encendidos\n";
for (std::size_t bits_per_key : {2, 4, 8, 10, 16}) {
print_row(words, bits_per_key, 1);
print_row(words, bits_per_key, 4);
}
std::cout << "con 10 bits por clave, cambiando k:\n";
for (int k : {1, 2, 3, 5, 7, 10, 15, 25}) {
print_row(words, 10, k);
}
return 0;
}// Paso 3: BFS frente a Dijkstra entre pares de calles.
// Uso: compare_routes mapa.txt calles.tsv pares.tsv
#include <fstream>
#include <iomanip>
#include <iostream>
#include <random>
#include <string>
#include <vector>
#include "map_file.h"
#include "routes.h"
#include "traversals.h"
namespace {
void print_row(const Graph& graph, const MapFile& map, int from, int to, const std::string& label) {
std::vector<int> fewest = path_to(bfs(graph, from).parent, to);
DijkstraResult result = dijkstra_to(graph, from, to);
std::vector<int> best = route_to(result.parent, to);
std::cout << std::setw(8) << static_cast<long long>(straight_meters(map.points[from], map.points[to]))
<< std::setw(9) << fewest.size() - 1 << std::setw(9) << route_meters(graph, fewest) << std::setw(9)
<< best.size() - 1 << std::setw(9) << route_meters(graph, best) << " " << label << "\n";
}
} // namespace
int main(int argc, char* argv[]) {
if (argc != 4) {
std::cerr << "uso: compare_routes mapa.txt calles.tsv pares.tsv\n";
return 2;
}
MapFile map = read_map_file(argv[1]);
std::vector<Street> streets = read_streets(argv[2]);
Graph graph = build_map_graph(map);
std::cout << " BFS Dijkstra\n";
std::cout << " recta aristas metros aristas metros\n";
std::ifstream pairs(argv[3]);
std::string from;
std::string to;
while (std::getline(pairs, from, '\t') && std::getline(pairs, to)) {
print_row(graph, map, node_of_street(streets, from), node_of_street(streets, to), from + " - " + to);
}
std::mt19937 random(15);
for (int i = 0; i < 6; i++) {
int source = static_cast<int>(random() % graph.node_count());
int target = static_cast<int>(random() % graph.node_count());
print_row(graph, map, source, target, "al azar");
}
return 0;
}// Pruebas públicas del laboratorio. Se corre una por proceso: lab_tests nombre carpeta_de_datos.
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <random>
#include <string>
#include <vector>
#include "graph.h"
#include "map_file.h"
#include "min_heap.h"
#include "routes.h"
#include "traversals.h"
namespace {
std::string data_dir;
std::string map_path(const std::string& name) { return data_dir + "/mapas/" + name + ".txt"; }
Graph hand_graph() {
Graph graph(7);
graph.add_edge(0, 1, 2);
graph.add_edge(0, 2, 9);
graph.add_edge(1, 3, 1);
graph.add_edge(2, 3, 1);
graph.add_edge(2, 4, 2);
graph.add_edge(3, 5, 8);
graph.add_edge(4, 5, 1);
graph.add_edge(5, 6, 3);
return graph;
}
// Un grafo al azar: a veces dirigido, a veces con pedazos separados, con empates y con pesos 0.
// Sin aristas repetidas.
Graph random_graph(std::mt19937& random) {
int n = 1 + static_cast<int>(random() % 12);
bool directed = random() % 2 == 0;
int edges = static_cast<int>(random() % (2 * n + 1));
int top_weight = 1 + static_cast<int>(random() % 12);
Graph graph(n, directed);
for (int i = 0; i < edges; i++) {
int u = static_cast<int>(random() % n);
int v = static_cast<int>(random() % n);
if (u != v && !graph.has_edge(u, v)) {
graph.add_edge(u, v, static_cast<int>(random() % top_weight));
}
}
return graph;
}
// Fuerza bruta: relajar todas las aristas, una y otra vez, hasta que nada cambie.
std::vector<Meters> brute_force(const Graph& graph, int source) {
std::vector<Meters> distance(graph.node_count(), UNREACHABLE);
distance[source] = 0;
bool changed = true;
while (changed) {
changed = false;
for (int u = 0; u < graph.node_count(); u++) {
if (distance[u] == UNREACHABLE) {
continue;
}
for (const Edge& edge : graph.neighbors(u)) {
if (distance[u] + edge.weight < distance[edge.to]) {
distance[edge.to] = distance[u] + edge.weight;
changed = true;
}
}
}
}
return distance;
}
// El padre de cada nodo tiene que explicar su distancia, con una arista que exista.
void check_parents(const Graph& graph, int source, const DijkstraResult& result) {
assert(result.parent[source] == source);
for (int v = 0; v < graph.node_count(); v++) {
if (v == source) {
continue;
}
if (result.distance[v] == UNREACHABLE) {
assert(result.parent[v] == -1);
continue;
}
int parent = result.parent[v];
assert(parent != -1);
bool explained = false;
for (const Edge& edge : graph.neighbors(parent)) {
if (edge.to == v && result.distance[parent] + edge.weight == result.distance[v]) {
explained = true;
}
}
assert(explained);
}
}
using Search = DijkstraResult (*)(const Graph&, int);
void check_against_brute_force(Search search, int graphs) {
std::mt19937 random(1500);
for (int i = 0; i < graphs; i++) {
Graph graph = random_graph(random);
int source = static_cast<int>(random() % graph.node_count());
DijkstraResult result = search(graph, source);
assert(result.distance == brute_force(graph, source));
check_parents(graph, source, result);
}
}
// ---------- Antes de empezar: su heap ----------
void heap_from_week_13() {
std::mt19937 random(13);
MinHeap<HeapEntry> heap;
std::vector<HeapEntry> expected;
for (int i = 0; i < 500; i++) {
HeapEntry entry{static_cast<Meters>(random() % 100), i};
heap.push(entry);
expected.push_back(entry);
}
heap.check_invariants();
std::sort(expected.begin(), expected.end());
for (const HeapEntry& entry : expected) {
assert(!heap.empty());
assert(heap.top() == entry);
heap.pop();
}
assert(heap.empty());
}
// ---------- Paso 1: cargar el mapa ----------
void map_graph_small() {
MapFile map;
map.node_count = 4;
map.points.resize(4);
map.edges = {{0, 1, 70}, {1, 2, 30}, {2, 0, 500}};
Graph graph = build_map_graph(map);
assert(graph.check_invariants());
assert(graph.node_count() == 4);
assert(graph.edge_count() == 3);
assert(!graph.directed());
assert(graph.neighbors(3).empty());
assert(graph.neighbors(1).size() == 2);
for (const Edge& edge : graph.neighbors(1)) {
assert((edge.to == 0 && edge.weight == 70) || (edge.to == 2 && edge.weight == 30));
}
}
void map_graph_real() {
MapFile map = read_map_file(map_path("miraflores"));
Graph graph = build_map_graph(map);
assert(graph.check_invariants());
assert(graph.node_count() == 2242);
assert(graph.edge_count() == 3474);
std::size_t entries = 0;
for (int u = 0; u < graph.node_count(); u++) {
entries += graph.neighbors(u).size();
}
assert(entries == 2 * 3474);
for (const MapEdge& edge : map.edges) {
bool found = false;
for (const Edge& entry : graph.neighbors(edge.u)) {
found = found || (entry.to == edge.v && entry.weight == edge.meters);
}
assert(found);
}
}
// ---------- Paso 2: Dijkstra y la ruta ----------
void dijkstra_hand_case() {
Graph graph = hand_graph();
DijkstraResult result = dijkstra(graph, 0);
std::vector<Meters> expected{0, 2, 4, 3, 6, 7, 10};
assert(result.distance == expected);
std::vector<int> parents{0, 0, 3, 1, 2, 4, 5};
assert(result.parent == parents);
assert(result.counts.settled == 7);
assert(result.counts.pushes == 9);
assert(result.counts.stale == 2);
assert(result.counts.edges_read == 16);
}
void dijkstra_random_against_brute_force() { check_against_brute_force(dijkstra, 400); }
void dijkstra_unreachable() {
Graph graph(5);
graph.add_edge(0, 1, 4);
graph.add_edge(2, 3, 1);
DijkstraResult result = dijkstra(graph, 0);
assert(result.distance[1] == 4);
assert(result.distance[2] == UNREACHABLE);
assert(result.distance[4] == UNREACHABLE);
assert(result.parent[3] == -1);
assert(result.counts.settled == 2);
assert(route_to(result.parent, 3).empty());
}
void dijkstra_large_weights() {
Graph graph(4);
graph.add_edge(0, 1, 2000000000);
graph.add_edge(1, 2, 2000000000);
graph.add_edge(2, 3, 2000000000);
DijkstraResult result = dijkstra(graph, 0);
assert(result.distance[3] == 6000000000LL);
}
void dijkstra_counts_on_real_map() {
Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
DijkstraResult result = dijkstra(graph, 0);
assert(result.counts.settled == 2242);
assert(result.counts.edges_read == 2 * 3474); // cada lista se lee una sola vez
assert(result.counts.pushes <= 2 * 3474 + 1);
assert(result.counts.pushes == result.counts.settled + result.counts.stale); // toda entrada sale
assert(result.counts.stale > 0);
}
// Muchos orígenes: un heap con las claves cambiando por dentro falla en muy pocos.
void dijkstra_many_sources_on_real_map() {
Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
for (int source = 0; source < 300; source++) {
DijkstraResult result = dijkstra(graph, source);
assert(result.distance == brute_force(graph, source));
}
}
void route_on_hand_case() {
Graph graph = hand_graph();
DijkstraResult result = dijkstra(graph, 0);
std::vector<int> route{0, 1, 3, 2, 4, 5, 6};
assert(route_to(result.parent, 6) == route);
std::vector<int> alone{0};
assert(route_to(result.parent, 0) == alone);
}
void route_on_real_map() {
Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
DijkstraResult result = dijkstra(graph, 1839);
assert(result.distance[1883] == 1512);
std::vector<int> route = route_to(result.parent, 1883);
assert(route.front() == 1839 && route.back() == 1883);
Meters total = 0;
for (std::size_t i = 1; i < route.size(); i++) {
Meters best = UNREACHABLE;
for (const Edge& edge : graph.neighbors(route[i - 1])) {
if (edge.to == route[i]) {
best = edge.weight;
}
}
assert(best != UNREACHABLE);
total += best;
}
assert(total == 1512);
}
// ---------- Paso 3: BFS frente a Dijkstra ----------
void route_meters_hand_case() {
Graph graph = hand_graph();
std::vector<int> route{0, 1, 3, 5, 6};
assert(route_meters(graph, route) == 14);
assert(route_meters(graph, {3}) == 0);
assert(route_meters(graph, {}) == 0);
assert(route_meters(graph, {6, 5, 4}) == 4); // no dirigido: también de vuelta
}
void routes_against_bfs() {
Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
std::mt19937 random(15);
int fewer_meters = 0;
int more_edges = 0;
for (int i = 0; i < 40; i++) {
int source = static_cast<int>(random() % graph.node_count());
int target = static_cast<int>(random() % graph.node_count());
DijkstraResult result = dijkstra(graph, source);
std::vector<int> best = route_to(result.parent, target);
std::vector<int> fewest = path_to(bfs(graph, source).parent, target);
assert(route_meters(graph, best) == result.distance[target]);
assert(result.distance[target] <= route_meters(graph, fewest));
assert(fewest.size() <= best.size());
fewer_meters += result.distance[target] < route_meters(graph, fewest) ? 1 : 0;
more_edges += fewest.size() < best.size() ? 1 : 0;
}
assert(fewer_meters > 0 && more_edges > 0);
}
// ---------- Paso 4: detenerse al sacar el destino ----------
// Dijkstra saca a los nodos de menor a mayor distancia: hasta target salen todos los que están
// más cerca, nunca uno que esté más lejos, y los empatados dependen del orden.
void check_stop(const Graph& graph, int source, int target) {
std::vector<Meters> truth = brute_force(graph, source);
DijkstraResult result = dijkstra_to(graph, source, target);
assert(result.distance[target] == truth[target]);
std::size_t closer = 0;
std::size_t up_to_target = 0;
for (Meters d : truth) {
if (d == UNREACHABLE) {
continue;
}
if (truth[target] == UNREACHABLE) {
closer++;
up_to_target++;
continue;
}
closer += d < truth[target] ? 1 : 0;
up_to_target += d <= truth[target] ? 1 : 0;
}
if (truth[target] == UNREACHABLE) {
assert(result.counts.settled == closer);
} else {
assert(closer + 1 <= result.counts.settled);
assert(result.counts.settled <= up_to_target);
}
if (truth[target] != UNREACHABLE) {
std::vector<int> route = route_to(result.parent, target);
assert(route.front() == source && route.back() == target);
assert(route_meters(graph, route) == truth[target]);
}
}
void stop_tiny_case() {
Graph graph(3);
graph.add_edge(0, 2, 5);
graph.add_edge(0, 1, 1);
graph.add_edge(1, 2, 1);
DijkstraResult result = dijkstra_to(graph, 0, 2);
assert(result.distance[2] == 2);
assert(result.counts.settled == 3);
}
void stop_hand_case() {
Graph graph = hand_graph();
DijkstraResult result = dijkstra_to(graph, 0, 5);
assert(result.distance[5] == 7);
assert(result.counts.settled == 6); // 0, 1, 3, 2, 4 y 5: el 6 no sale
assert(result.counts.edges_read == 12); // no lee la lista de target
assert(result.parent[5] == 4);
result = dijkstra_to(graph, 0, 0);
assert(result.distance[0] == 0);
assert(result.counts.settled == 1);
assert(result.counts.edges_read == 0);
}
void stop_random_against_brute_force() {
std::mt19937 random(1504);
for (int i = 0; i < 400; i++) {
Graph graph = random_graph(random);
int source = static_cast<int>(random() % graph.node_count());
int target = static_cast<int>(random() % graph.node_count());
check_stop(graph, source, target);
}
}
void stop_saves_nodes_on_real_map() {
Graph graph = build_map_graph(read_map_file(map_path("miraflores")));
DijkstraResult whole = dijkstra(graph, 1839);
check_stop(graph, 1839, 1883);
DijkstraResult near = dijkstra_to(graph, 1839, 1883);
assert(near.counts.settled < whole.counts.settled);
assert(near.counts.edges_read < whole.counts.edges_read);
}
// ---------- Paso 5: otras dos colas ----------
void priority_queue_random_against_brute_force() { check_against_brute_force(dijkstra_priority_queue, 400); }
void priority_queue_same_counts() {
Graph graph = hand_graph();
DijkstraResult result = dijkstra_priority_queue(graph, 0);
assert(result.counts.settled == 7);
assert(result.counts.pushes == 9);
assert(result.counts.stale == 2);
Graph real = build_map_graph(read_map_file(map_path("miraflores")));
DijkstraResult own = dijkstra(real, 0);
DijkstraResult library = dijkstra_priority_queue(real, 0);
assert(own.distance == library.distance);
assert(own.counts.pushes == library.counts.pushes);
assert(own.counts.stale == library.counts.stale);
}
void array_random_against_brute_force() { check_against_brute_force(dijkstra_array, 400); }
void array_disconnected() {
Graph graph(6);
graph.add_edge(0, 1, 4);
graph.add_edge(2, 3, 1);
DijkstraResult result = dijkstra_array(graph, 0);
assert(result.distance[1] == 4);
assert(result.distance[2] == UNREACHABLE);
assert(result.parent[2] == -1);
assert(result.counts.settled == 2);
}
void array_reads_the_whole_array() {
Graph graph = hand_graph();
DijkstraResult result = dijkstra_array(graph, 0);
assert(result.counts.settled == 7);
assert(result.counts.pushes == 0);
assert(result.counts.edges_read == 16);
assert(result.counts.scanned >= 7 * 7 && result.counts.scanned <= 8 * 7);
Graph real = build_map_graph(read_map_file(map_path("miraflores")));
DijkstraResult whole = dijkstra_array(real, 0);
std::size_t v = 2242;
assert(whole.distance == dijkstra(real, 0).distance);
assert(whole.counts.scanned >= v * v && whole.counts.scanned <= (v + 1) * v);
}
struct Case {
const char* name;
void (*run)();
};
const Case CASES[] = {
{"heap_from_week_13", heap_from_week_13},
{"map_graph_small", map_graph_small},
{"map_graph_real", map_graph_real},
{"dijkstra_hand_case", dijkstra_hand_case},
{"dijkstra_random_against_brute_force", dijkstra_random_against_brute_force},
{"dijkstra_unreachable", dijkstra_unreachable},
{"dijkstra_large_weights", dijkstra_large_weights},
{"dijkstra_counts_on_real_map", dijkstra_counts_on_real_map},
{"dijkstra_many_sources_on_real_map", dijkstra_many_sources_on_real_map},
{"route_on_hand_case", route_on_hand_case},
{"route_on_real_map", route_on_real_map},
{"route_meters_hand_case", route_meters_hand_case},
{"routes_against_bfs", routes_against_bfs},
{"stop_tiny_case", stop_tiny_case},
{"stop_hand_case", stop_hand_case},
{"stop_random_against_brute_force", stop_random_against_brute_force},
{"stop_saves_nodes_on_real_map", stop_saves_nodes_on_real_map},
{"priority_queue_random_against_brute_force", priority_queue_random_against_brute_force},
{"priority_queue_same_counts", priority_queue_same_counts},
{"array_random_against_brute_force", array_random_against_brute_force},
{"array_disconnected", array_disconnected},
{"array_reads_the_whole_array", array_reads_the_whole_array},
};
} // namespace
int main(int argc, char* argv[]) {
if (argc == 3) {
data_dir = argv[2];
for (const Case& test : CASES) {
if (std::strcmp(test.name, argv[1]) == 0) {
test.run();
return 0;
}
}
}
std::cerr << "uso: lab_tests nombre carpeta_de_datos\n";
return 2;
}// Pruebas del paso 6, que es opcional. Se corre una por proceso: optional_tests nombre carpeta_de_pruebas.
#include <algorithm>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <random>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include "bloom.h"
#include "trie.h"
namespace {
std::string tests_dir;
std::vector<std::string> sample_words() {
std::ifstream file(tests_dir + "/fixtures/palabras_muestra.txt");
std::vector<std::string> words;
std::string word;
while (file >> word) {
words.push_back(word);
}
assert(words.size() > 1000);
return words;
}
// ---------- Trie ----------
void trie_insert_and_find() {
PlaceTrie trie;
assert(trie.find("Larco") == -1);
assert(trie.find("") == -1);
trie.insert("Larco", 38);
trie.insert("Lar", 7);
trie.insert("Lima", 9);
assert(trie.find("Larco") == 38);
assert(trie.find("Lar") == 7);
assert(trie.find("La") == -1);
assert(trie.find("Larcomar") == -1);
assert(trie.place_count() == 3);
trie.insert("Lar", 8);
assert(trie.find("Lar") == 8);
assert(trie.place_count() == 3);
assert(trie.check_invariants());
}
void trie_shares_prefixes() {
PlaceTrie trie;
trie.insert("ab", 1);
trie.insert("abc", 2);
trie.insert("abd", 3);
assert(trie.node_count() == 5); // raíz, a, ab, abc, abd
assert(trie.check_invariants());
}
void trie_prefix_in_byte_order() {
PlaceTrie trie;
trie.insert("cazo", 1);
trie.insert("cañón", 2);
trie.insert("ca", 3);
trie.insert("caña", 4);
trie.insert("cámara", 5);
trie.insert("dos", 6);
std::vector<std::pair<std::string, int>> expected{{"ca", 3}, {"cazo", 1}, {"caña", 4}, {"cañón", 2}};
assert(trie.with_prefix("ca") == expected);
assert(trie.with_prefix("zzz").empty());
assert(trie.with_prefix("").size() == 6);
std::vector<std::pair<std::string, int>> accented{{"cámara", 5}};
assert(trie.with_prefix("cá") == accented);
}
void trie_random_against_map() {
std::vector<std::string> words = sample_words();
std::map<std::string, int> model;
PlaceTrie trie;
for (std::size_t i = 0; i < words.size(); i++) {
trie.insert(words[i], static_cast<int>(i));
model[words[i]] = static_cast<int>(i);
}
assert(trie.check_invariants());
assert(trie.place_count() == model.size());
std::mt19937 random(150);
for (int round = 0; round < 200; round++) {
const std::string& word = words[random() % words.size()];
std::string prefix = word.substr(0, random() % (word.size() + 1));
std::vector<std::pair<std::string, int>> expected;
for (auto it = model.lower_bound(prefix); it != model.end() && it->first.compare(0, prefix.size(), prefix) == 0; ++it) {
expected.push_back(*it);
}
assert(trie.with_prefix(prefix) == expected);
assert(trie.find(word) == model[word]);
}
}
// ---------- Filtro de Bloom ----------
void bloom_sets_the_right_bits() {
BloomFilter filter(1009, 3);
assert(filter.bits_on() == 0);
assert(!filter.possibly_contains("lima"));
filter.add("lima");
std::set<std::size_t> positions;
for (int i = 0; i < 3; i++) {
positions.insert(bloom_position("lima", i, 1009));
}
assert(filter.bits_on() == positions.size());
assert(filter.possibly_contains("lima"));
filter.add("lima");
assert(filter.bits_on() == positions.size());
}
void bloom_no_false_negatives() {
std::vector<std::string> words = sample_words();
for (std::size_t bits : {64, 1000, 20000}) {
BloomFilter filter(bits, 4);
for (const std::string& word : words) {
filter.add(word);
}
for (const std::string& word : words) {
assert(filter.possibly_contains(word));
}
}
}
// Agrega las líneas pares y pregunta por las impares, que no están.
std::size_t false_positives(const std::vector<std::string>& words, std::size_t bits, int k) {
BloomFilter filter(bits, k);
for (std::size_t i = 0; i < words.size(); i += 2) {
filter.add(words[i]);
}
std::size_t positives = 0;
for (std::size_t i = 1; i < words.size(); i += 2) {
positives += filter.possibly_contains(words[i]) ? 1 : 0;
}
return positives;
}
void bloom_false_positives_fall_with_size() {
std::vector<std::string> words = sample_words();
std::size_t keys = words.size() / 2;
std::size_t small = false_positives(words, keys * 2, 1);
std::size_t large = false_positives(words, keys * 16, 1);
assert(large < small);
assert(small > 0);
assert(false_positives(words, keys * 32, 5) <= keys / 50);
}
void bloom_uses_all_hashes() {
BloomFilter one(100000, 1);
BloomFilter five(100000, 5);
one.add("lima");
five.add("lima");
assert(one.bits_on() == 1);
assert(five.bits_on() == 5);
assert(five.hash_count() == 5);
assert(five.bit_count() == 100000);
}
struct Case {
const char* name;
void (*run)();
};
const Case CASES[] = {
{"trie_insert_and_find", trie_insert_and_find},
{"trie_shares_prefixes", trie_shares_prefixes},
{"trie_prefix_in_byte_order", trie_prefix_in_byte_order},
{"trie_random_against_map", trie_random_against_map},
{"bloom_sets_the_right_bits", bloom_sets_the_right_bits},
{"bloom_no_false_negatives", bloom_no_false_negatives},
{"bloom_false_positives_fall_with_size", bloom_false_positives_fall_with_size},
{"bloom_uses_all_hashes", bloom_uses_all_hashes},
};
} // namespace
int main(int argc, char* argv[]) {
if (argc == 3) {
tests_dir = argv[2];
for (const Case& test : CASES) {
if (std::strcmp(test.name, argv[1]) == 0) {
test.run();
return 0;
}
}
}
std::cerr << "uso: optional_tests nombre carpeta_de_pruebas\n";
return 2;
}// Paso 6, con trie: busca lugares por prefijo y da su nodo del mapa.
// Uso: places calles.tsv prefijo [cuantos]
#include <cstdlib>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include "map_file.h"
#include "trie.h"
int main(int argc, char* argv[]) {
if (argc < 3) {
std::cerr << "uso: places calles.tsv prefijo [cuantos]\n";
return 2;
}
PlaceTrie trie;
for (const Street& street : read_streets(argv[1])) {
trie.insert(street.name, street.node);
}
std::size_t limit = argc > 3 ? static_cast<std::size_t>(std::atoi(argv[3])) : 10;
std::vector<std::pair<std::string, int>> found = trie.with_prefix(argv[2]);
std::cout << found.size() << " lugares empiezan con \"" << argv[2] << "\"\n";
for (std::size_t i = 0; i < found.size() && i < limit; i++) {
std::cout << " " << found[i].second << " " << found[i].first << "\n";
}
return 0;
}// Paso 4: cuántos nodos se ahorra Dijkstra al detenerse, según lo lejos que esté el destino.
// Uso: savings mapa.txt calles.tsv "calle de origen"
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
#include "map_file.h"
#include "routes.h"
int main(int argc, char* argv[]) {
if (argc != 4) {
std::cerr << "uso: savings mapa.txt calles.tsv origen\n";
return 2;
}
Graph graph = build_map_graph(read_map_file(argv[1]));
int source = node_of_street(read_streets(argv[2]), argv[3]);
DijkstraResult whole = dijkstra(graph, source);
std::vector<int> by_distance(graph.node_count());
std::iota(by_distance.begin(), by_distance.end(), 0);
std::sort(by_distance.begin(), by_distance.end(),
[&](int a, int b) { return whole.distance[a] < whole.distance[b]; });
std::cout << "origen: " << argv[3] << ", nodo " << source << ", " << whole.counts.settled << " nodos sacados sin parar\n";
std::cout << "destino metros sacados ahorro aristas leidas\n";
for (int percent : {1, 5, 10, 25, 50, 75, 90, 100}) {
std::size_t position = (by_distance.size() - 1) * percent / 100;
int target = by_distance[position];
DijkstraResult stopped = dijkstra_to(graph, source, target);
double saved = 100.0 * (1.0 - static_cast<double>(stopped.counts.settled) / whole.counts.settled);
std::cout << std::setw(6) << percent << " %" << std::setw(9) << stopped.distance[target] << std::setw(9)
<< stopped.counts.settled << std::fixed << std::setprecision(1) << std::setw(6) << saved << " %"
<< std::setw(16) << stopped.counts.edges_read << "\n";
}
return 0;
}// Paso 6, con trie: cuántos nodos ocupa, según las claves. Uso: trie_sizes archivo...
// Lee un .tsv como calles (nodo, nombre) y cualquier otro archivo como una palabra por línea.
#include <fstream>
#include <iomanip>
#include <iostream>
#include <string>
#include "trie.h"
int main(int argc, char* argv[]) {
std::cout << " claves bytes de claves nodos nodos/byte con 256 hijos, MB\n";
for (int i = 1; i < argc; i++) {
PlaceTrie trie;
std::size_t bytes = 0;
std::ifstream file(argv[i]);
std::string line;
int id = 0;
while (std::getline(file, line)) {
std::size_t tab = line.find('\t');
std::string name = tab == std::string::npos ? line : line.substr(tab + 1);
bytes += name.size();
trie.insert(name, id++);
}
std::cout << std::setw(10) << trie.place_count() << std::setw(18) << bytes << std::setw(11) << trie.node_count()
<< std::fixed << std::setprecision(2) << std::setw(12)
<< static_cast<double>(trie.node_count()) / static_cast<double>(bytes) << std::setw(19)
<< static_cast<double>(trie.node_count()) * 256 * sizeof(int) / 1e6 << "\n";
}
return 0;
}a
abandonadlos
abarcándoles
abatila
abinasteis
abocetaréis
abominare
abortaríais
abrazame
abriolaréis
abrácela
abstráemelos
aburríos
acabándoles
acamados
acarearan
acatarrabas
acechadas
acentuároslas
acetonas
achatándooslos
achuchadlas
acicateare
aclocarían
acogiere
acometida
acondicionádnoslos
acoran
acortándola
acotádnoslo
acriminabas
acuadrillara
acuite
acusádselas
adecenemos
adentres
adietares
adminiculasen
adoctrinánosla
adornarte
adstringido
adunaba
afanémonos
afeándoosla
afilorás
afligiríais
afosen
afueren
agarradlo
agenciándotela
aglutínenmelo
agracíelo
agravándotelas
agriégalos
aguarapabais
aguizgaré
aherrojemos
ahorcármela
ahumándomela
ajamonaban
ajustare
alambicabais
alarmárselo
alborozarían
alcoholizases
alegorizó
aletargara
algodonad
alimentabais
alistás
allanás
almibarábamos
alojándonosla
alternarles
aluné
amacollarais
amallaremos
amanzanéis
amartelarais
amechéis
amenorara
aminoráis
amolando
amoratarse
amortiguaría
amparáselos
amueblándooslas
anacrónicos
anclámelos
anexalas
anhelando
aniñado
antarquease
antigramaticales
anulé
apachaseis
apaleárselos
aparentara
apastran
apegualases
aperad
apestillaste
apiojares
aplanás
aplíquelas
aporismas
apostrofaré
apremiándoles
apretaran
apropiará
apulgaráis
apuñalándomelos
aquiláteme
arcabucearé
arengárnoslos
aristocratiza
arpeos
arrancándoos
arrebujareis
arrejacaseis
arrepintiéndose
arrimándomela
arrodriga
arropádnoslo
arrumas
artesonares
asaetás
asediar
asentándole
aseverarlas
asiláramos
asolanarían
asordase
astillares
aséemela
atalajen
ataviares
atenebraréis
aterrárselas
atigrada
atoaremos
atornillándomelas
atragantádmelo
atravéselos
atrojará
aturullaron
augurándoosla
auscultándoles
autoconvencerá
autoflagelándoselo
autoproclamanos
avadarías
avejigaríamos
avergonzalo
avisalo
axiomatizasen
azogamiento
azuzádmelos
baboseaseis
bailáis
balcones
baléenme
banquetearéis
barbullaran
barrenánoslo
basculó
batanearse
bazucabas
beldad
bermeja
bieldaré
birlárselas
bizquearía
blindaran
bodijo
bombardeareis
borbotásemos
bosqueja
braseen
brindáramos
brujulearíamos
burguesías
búrlate
cablearéis
cacheareis
caduceador
calagurritanos
calcínalas
caligrafiásemos
calumniáis
cambizara
camparé
cancero
canonizáremos
cantándotelos
capitanearan
captúreles
carbonatabas
carearme
carnavalada
carroñero
cascamajes
castraran
catastrofismo
catéeselo
cavilados
cañonearía
cegárnoslas
cendraseis
centitelepáticísimo
cercenádnoslo
cerrará
chachareen
chamboneéis
chantajeándoselos
chapuzabas
chaspada
chicheabas
chinchánoslo
chirrisquearás
chochearía
chucaneaba
churrarán
cicatrícelas
cinematografiá
circunscribiéndooslos
cizallases
clasifíquenselas
clonámelo
coartaron
cocinaríamos
codirigiéramos
cohibidles
colapsará
colgánosla
colonizarme
comadreabais
comemos
comiquearemos
compagínenoslas
compendiarse
complementándoselos
compostelana
compréndelos
comándelas
conceptúas
concluiéndoles
concurrieres
condicionáselas
conectividad
configuradles
conflictuasen
confutares
congratulada
conjurádnosla
conmocióneme
conreé
considerándotelos
constarán
constátala
contactábamos
contenedoras
contoneareis
contraerle
contraponelo
contrasellarán
controlándonos
convenciéndooslas
convocándomela
copiles
coraza
cornees
correosos
corroyere
cortéjanoslos
cosquilleánoslo
coto
cremámelas
crismeras
crió
cráneo
cuajánoslas
cubicánoslo
cuemani
culmino
cumplimentádmelos
curioseándomelo
custridas
cítenlas
davalabais
debruzaréis
decapopularísimo
decisoria
decomisándotelas
dedicatoria
definírmelo
degollándose
delegue
delineándonoslo
dementánoslo
demórenla
denotándolos
depauperada
deposítenoslo
derogarla
derrocase
desabarrancabas
desaceleración
desacreditalas
desafinaran
desagravíenos
desaislé
desalojaren
desamorando
desanimaste
desapliquéis
desapuntalaseis
desarriméis
desasnádmela
desatiéndele
desavisabas
desbaratádnoslos
desbocar
desbrozarme
descacharren
descalifiquémonos
descantonaríamos
descarriladuras
descañonaréis
descervigaseis
descoagularais
descolonizarás
descompusiesen
descongeládsela
descontinuas
descoritaban
describiéndonoslo
descubrieren
desdeñádnosla
deselectrizamos
desembebeciera
desembucharás
desempercudiendo
desencabalgándose
desencastilláremos
desencuadernare
desenganchales
desenguantó
desenojase
desensoberbeció
desentrañaríamos
desequipadlas
desestabilizándolo
desfajéis
desfogonaría
desgarrate
desgraciaron
desguazáselo
desheredadles
deshojados
desilusionadla
desinficionáis
desintoxicánosla
deslechuguillado
deslomaríais
desmandar
desmayárnoslas
desmerecida
desmogados
desmotabas
desnucándose
desolarse
desortijasteis
despaldaseis
desparramaran
despedácenlos
despeluzaríais
desperfilás
despicháremos
desplacémonos
despoblases
desposéamelos
desprestigíenselas
despéguesela
desrabotaría
destacárselas
destensado
destituímelas
destrocasteis
desubstanciaría
desvaloraran
desvendaréis
desvirtuándooslas
deszumásemos
deteriorárselos
devalúo
devuelves
diamantásemos
difamándolo
difumínemelas
dignificárselos
diluviarais
dinamítelo
disceptaseis
discrimínate
diseñadlos
disgustándonos
disolviéndome
dispusieron
distorsionadlo
disyuntivamente
divinádmelas
diñándooslas
documentádnoslas
domiciliase
dormidores
dragó
dudásela
déjelas
ectasias
edulcorándola
ejecutándoosla
elata
eliminarías
emancipándomelos
embalándolos
embargánoslas
embaucase
embellecénosla
embobaron
emborracé
embotellarás
embriagándonoslos
embrujásemos
embótennos
empadrónate
empantanaron
emparchaban
empastánoslas
empederneciese
empequeñecédnoslas
empeñaré
emplantillasen
empobrecerlo
empotraréis
empujan
emulároslos
enamoraras
enastilando
encabullado
encalamoqué
encamisarais
encaneces
encaprichádmelos
encargalo
encarrilártelas
encasquetárselos
encañamaremos
enceléis
enceránoslo
enchironarán
enciéndase
encofrás
encomiádnoslos
encorajinaban
encorujada
encuadrarme
encunó
enderezáselos
endominguéis
enemistarlo
enfardo
enflacarán
enfrentándonosla
enfuriando
enganchador
engarronarías
engañáis
engomaría
engranujasen
engrumecéis
engurrabas
enhebrarle
enjabuénate
enjicaríamos
enlaciaremos
enlenzábamos
enloquezlo
enmarañadle
enmendándoselo
ennegreciéndose
enraigonaba
enrejalada
enrodrigados
enrostrádselos
ensalzadores
ensayándomelo
ensilvecían
ensortijada
entallan
entenebrare
entibiados
entonces
entrador
entrechocame
entrelazare
entrenánoslas
entreténganse
entristezlas
entréguelo
entusiasmárselo
envanecédnoslas
enverdeciste
envinagrabas
enyuguen
epitomaseis
erabas
erosiónese
esbozándose
escalaríais
escamosas
escaneándolas
escarchemos
escarpada
escenificándosela
escocara
escoltánoslos
escotaríais
escuchaos
escupidores
esforzadme
eslabonareis
espabilártelos
esparciéramos
especificásemos
esperriarían
espiritualizará
esponjaros
espéralo
esquivez
estafa
estaquilla
estertorosas
estipendiaríamos
estorbárnoslas
estrellados
estropearíamos
estudíenmelos
etimologizáremos
evaneceremos
evitable
exaltándotela
exceptuaban
excrecencias
exhibieres
existencialismos
expectoró
expiándoles
explotad
expresáselas
extasialos
externalizarse
extraditádmelo
extraviarme
eyaculadlo
facinerosa
falcareis
faltó
farfullaré
favorecelas
felicítame
fertilícelas
fichármelo
filio
fincaren
fisiologías
flatuosa
florearíais
fogueaste
forcatearán
formulando
fortifíquemelos
fotografíenmela
fraguaste
fregad
friccionámelo
frustráselos
fulmínalos
fundían
fóllelo
gallundera
ganzuaremos
gargarizas
gastándosela
generalízate
gestádsela
glas
gobernases
golpeánoslos
gozarte
granaran
gratificándoosla
grietearía
guachineaba
guarecémelas
guillotes
guiñáis
habilitándomelos
haciende
hamacá
hastiamos
hedieras
herbecieras
herniaban
hibernó
himplaréis
hipocondría
hiñida
hombrease
honestaron
hornearéis
hospitalícenos
huevadas
humillaré
husmasteis
identificadoras
igualándolos
ilustraban
imitémonos
imperantes
implicarlo
imposibilitaseis
imprimírnoslo
imputásemos
incardinara
incitádselas
incomunicádselos
increméntele
inculque
independentismo
indiscriminada
indultárselo
infectarías
inflexibidad
informáis
ingeriros
inhibitorios
injuriándolas
inmovilizándose
inquietaríamos
insensibilizármelo
inspeccionás
institucionalícenla
insuflar
intemperadas
intercambíeles
interfiérenos
interpelamos
interrumpídselo
intranquilicen
intuyéndose
inventariárselos
invitadlas
ionizaría
irruidas
jabalonar
jalearnos
jardinera
jeringaré
jolito
judicializando
jurádmelas
kaquiabamba
laceralos
laicismo
lampeó
lapsa
latigueasen
lañareis
legásela
levantabas
libertadla
licitárselos
lijámelas
linchate
lisonjéanosla
llameaseis
llevádselas
lobeá
losare
ludiabas
líanos
machucaban
maduradlos
magrearán
malbarataré
malentrada
mallorcas
maltraen
mamáis
mandándonos
manicortos
manotee
manándoselas
marcadla
marginala
marramizada
masacraríais
mastícanosla
matutease
mazase
meciéndoselos
medranas
melas
menciónele
mentale
merdosa
mestizarás
mezcladores
microvoltiamente
mimaríais
minigramo
mirificándose
mitigá
modernizando
moho
molina
moneareis
montanismos
mordacearéis
morrudos
mostrábamos
mucacal
multabas
murguía
musítenla
míralo
nanoingenuísimo
navajeas
negrearse
nevadas
nocedas
norma
notorias
numérenos
objetivárselo
observaran
obteniéndote
ocluyéramos
odíenmela
ofrezcas
olfativa
omináis
opinándose
orare
organízala
orlarse
osearían
ovacionaos
pacificalos
pagárselo
palideceré
palotease
panegíricos
paquetearíais
paramentemos
parearás
parpes
paránoslos
pasteleándose
pateándooslas
paulare
peatonalizás
pedídnoslo
pelgar
pendamos
pentágona
percíbeselo
perfecciónenme
perineales
permutaste
perseguírsela
persépolis
pesquisada
piariego
picotelepáticos
pillártela
pintados
pirateares
pisoteárnoslas
placada
planificádnoslas
plastezco
plomaban
podrimientos
politizás
poniéndoles
porrean
posibilidades
postinea
potasa
precaverían
precociéndoselas
predisponiéndotelas
preguntadores
premostres
preparaseis
presentadlo
prestancias
presurizáremos
previeron
priorizándooslos
procedéis
prodigarais
profesionalizároslo
prohijaban
promisoria
pronunciárosla
propondrás
prorroguémonos
protagonizad
provincialismos
ptolemaica
puericia
pumitas
purgárselas
págala
quebrádmelo
quero
quinoleado
rabiaseis
racionaran
raednos
rampé
rareá
raspándoles
ratificáselas
reabriríais
reajustaremos
reanúdenos
rebalsaren
rebelarías
rebozádmelos
recabándolo
recambiar
recavaremos
rechazárnoslas
recizalla
recodarse
recompensarían
recondujeron
reconstrúyanla
recorrédmela
recrimínalo
recuerdo
recóndita
redimiéndosela
redundarse
reemplazales
reenvides
referenciamos
reflotame
refregaba
refrigérenlo
regabinaría
regeneres
regocijo
regularizareis
reherró
reilarías
reinicíenos
reitérenlas
relajar
relegarías
relingabais
remallasen
remediándose
remirara
remontadme
remudarse
rendídmela
renunciándonos
repapilará
repeinasteis
repetimos
replantársela
reponiéndooslos
representártelas
repudiarte
repónganlo
resalgamos
rescindiera
reseñaras
resinifiquemos
respaldo
responsabilizará
restaurándooslo
restándome
retablero
retemblabais
retocártelo
retractilasen
retrecharías
retráiganla
reuniéndomelo
revelimos
revesamos
revivificados
revolviesen
rezándosela
riles
rizándotelos
rociámelos
rojeabas
ronceemos
rosás
rubilla
rujan
rustiréis
sabinar
saciaríamos
saeteaban
saldadnos
salmásemos
salteándotelo
sambenitado
sangraréis
sanármela
satisfacerla
seccionártelo
secundarías
segméntenosla
selladnos
sensibilizales
septuplicad
serraría
sextaven
sigilarán
silgase
simultanéamelo
sinestesia
sirgándose
soasaría
sobrearasen
sobreentendiera
sobrellevárnoslas
sobrero
sobreviviréis
socavármela
sofocarte
solazarlo
solidarizándose
solucionaseis
someternos
sonoramente
sopalancare
sorbelos
sosañaría
soterraren
subdividiré
sublimando
subsanárselos
subsumiéndoselas
subínoslos
sufrirse
sulfurar
supedítenme
supervisártelas
suprasensibles
suscitases
sustentan
suturá
tablearéis
tajad
tambaleárnoslos
tanguéenosla
taponamiento
tardalas
tasen
tecnificarías
teletransportaríais
templárosla
tentalea
terciará
tertulianos
texturizarías
timbrando
tiquipaya
titeo
tlayudas
tonatico
toquetéemela
torpedéenla
totalizaseis
traduciéndosela
trajeras
transando
transformarlo
transmigraban
transubstancie
trasbordados
trasferidle
trasladate
trasmutó
traspillen
trastejara
trasvasás
trazárosla
trepándolo
trinchaba
tristemente
trocéenme
trotad
tríptico
tupirían
tuteáremos
ubíquenoslos
umpaleño
unisexual
urcos
utilizaríais
vadéemela
valorala
vandalizalos
variados
veintiuna
vendimiamos
ventilaremos
verdegueases
vertebres
vibrara
vigilara
violale
visionádnoslos
vitoreádmelas
viviéndose
volitasteis
voseáramos
vírica
yugules
zahores
zampándote
zapuzaríamos
zendas
zumbándolo
zurríamosAvenida José Larco Avenida Aviación
Avenida Alfredo Benavides Avenida Javier Prado Este
Malecón de la Reserva Avenida Javier Prado OesteCompilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 15: caminos mínimos. Se usa dentro del entorno del curso.
#
# make compila los programas de la clase en build/
# make lab compila el laboratorio en build/lab/
# make test corre las pruebas de los ejemplos y de los apuntes
# make test-heap antes de empezar: su MinHeap de la semana 13
# make test-map paso 1: cargar el mapa
# make test-dijkstra paso 2: Dijkstra y la ruta
# make test-routes paso 3: BFS frente a Dijkstra
# make test-stop paso 4: detenerse al sacar el destino
# make test-queues paso 5: std::priority_queue y el arreglo
# make test-lab prueba los pasos 1 a 5; falla hasta que los terminen
# make test-trie paso 6, opcional: el trie
# make test-bloom paso 6, opcional: el filtro de Bloom
# make compare paso 3: la tabla para su informe
# make savings paso 4: la tabla para su informe
# make measure paso 5: la tabla para su informe, con -O2
# make measure-bloom paso 6: falsos positivos sobre palabras.txt, con -O2
# make trie-sizes paso 6: nodos de un trie, con -O2
# make clean borra lo generado
#
# Los programas de errors/ tienen errores a propósito. No se compilan con make:
# los compilan las pruebas, y ustedes, con los comandos de los apuntes.
CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BENCHFLAGS = -Wall -Wextra -std=c++20 -O2
DATA ?= ../../data
LAB_DIR ?= lab
BUILD = build
PROGRAMS = dijkstra_trace route_demo distance_range test_structures
BENCHES = dijkstra_counts
COMMON_HEADERS = graph.h traversals.h shortest_paths.h sample_graphs.h map_file.h bench.h
GIVEN_HEADERS = lab/graph.h lab/traversals.h lab/map_file.h lab/not_implemented.h
ROUTE_HEADERS = $(LAB_DIR)/routes.h $(LAB_DIR)/min_heap.h $(GIVEN_HEADERS)
OPTIONAL_HEADERS = $(LAB_DIR)/trie.h $(LAB_DIR)/bloom.h lab/map_file.h
LAB_FLAGS = -I$(LAB_DIR) -Ilab
LAB_BUILD = $(BUILD)/$(LAB_DIR)
LAB_PROGRAMS = lab_tests compare_routes savings
LAB_BENCH = bench_routes
OPTIONAL_PROGRAMS = optional_tests places
OPTIONAL_BENCHES = bloom_measure trie_sizes
.PHONY: all lab optional test test-heap test-map test-dijkstra test-routes test-stop test-queues test-lab \
test-trie test-bloom compare savings measure measure-bloom trie-sizes clean
all: $(PROGRAMS:%=$(BUILD)/%) $(BENCHES:%=$(BUILD)/%)
$(PROGRAMS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(COMMON_HEADERS) | $(BUILD)
$(CXX) $(CXXFLAGS) $< -o $@
# Las mediciones van con -O2 y sin sanitizers.
$(BENCHES:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(COMMON_HEADERS) | $(BUILD)
$(CXX) $(BENCHFLAGS) $< -o $@
# LAB_DIR va primero: así los programas toman los archivos de esa carpeta.
$(LAB_PROGRAMS:%=$(LAB_BUILD)/%): $(LAB_BUILD)/%: lab/tests/%.cpp $(ROUTE_HEADERS) | $(LAB_BUILD)
$(CXX) $(CXXFLAGS) $(LAB_FLAGS) $< -o $@
$(LAB_BENCH:%=$(LAB_BUILD)/%): $(LAB_BUILD)/%: lab/tests/%.cpp bench.h $(ROUTE_HEADERS) | $(LAB_BUILD)
$(CXX) $(BENCHFLAGS) $(LAB_FLAGS) -I. $< -o $@
$(OPTIONAL_PROGRAMS:%=$(LAB_BUILD)/%): $(LAB_BUILD)/%: lab/tests/%.cpp $(OPTIONAL_HEADERS) | $(LAB_BUILD)
$(CXX) $(CXXFLAGS) $(LAB_FLAGS) $< -o $@
$(OPTIONAL_BENCHES:%=$(LAB_BUILD)/%): $(LAB_BUILD)/%: lab/tests/%.cpp $(OPTIONAL_HEADERS) | $(LAB_BUILD)
$(CXX) $(BENCHFLAGS) $(LAB_FLAGS) $< -o $@
$(BUILD) $(LAB_BUILD):
mkdir -p $@
lab: $(LAB_PROGRAMS:%=$(LAB_BUILD)/%) $(LAB_BENCH:%=$(LAB_BUILD)/%)
optional: $(OPTIONAL_PROGRAMS:%=$(LAB_BUILD)/%) $(OPTIONAL_BENCHES:%=$(LAB_BUILD)/%)
# Si existe solution/, también se comprueba la solución del laboratorio.
test: all
@if [ -d solution ]; then $(MAKE) --no-print-directory LAB_DIR=solution lab optional; fi
DATA=$(DATA) python3 -m unittest discover -p 'test_*.py'
test-heap: lab
LAB_DIR=$(LAB_DIR) DATA=$(DATA) python3 -m unittest -v test_lab.TestHeap
test-map: lab
LAB_DIR=$(LAB_DIR) DATA=$(DATA) python3 -m unittest -v test_lab.TestMap
test-dijkstra: lab
LAB_DIR=$(LAB_DIR) DATA=$(DATA) python3 -m unittest -v test_lab.TestDijkstra
test-routes: lab
LAB_DIR=$(LAB_DIR) DATA=$(DATA) python3 -m unittest -v test_lab.TestRoutes
test-stop: lab
LAB_DIR=$(LAB_DIR) DATA=$(DATA) python3 -m unittest -v test_lab.TestStop
test-queues: lab
LAB_DIR=$(LAB_DIR) DATA=$(DATA) python3 -m unittest -v test_lab.TestQueues
test-lab: all lab
LAB_DIR=$(LAB_DIR) DATA=$(DATA) python3 -m unittest -v test_lab
test-trie: optional
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_optional.TestTrie
test-bloom: optional
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_optional.TestBloom
compare: $(LAB_BUILD)/compare_routes
$< $(DATA)/mapas/lima-sur.txt $(DATA)/mapas/lima-sur-calles.tsv lab/tests/fixtures/pares-lima-sur.tsv
savings: $(LAB_BUILD)/savings
$< $(DATA)/mapas/lima-sur.txt $(DATA)/mapas/lima-sur-calles.tsv "Avenida José Larco"
measure: $(LAB_BUILD)/bench_routes
$< $(DATA)/mapas/miraflores.txt $(DATA)/mapas/lima-sur.txt $(DATA)/mapas/lima.txt
measure-bloom: $(LAB_BUILD)/bloom_measure
$< $(DATA)/palabras.txt
trie-sizes: $(LAB_BUILD)/trie_sizes
$< $(DATA)/mapas/lima-calles.tsv $(DATA)/terminos.tsv $(DATA)/palabras.txt
clean:
rm -rf $(BUILD) __pycache__