Semana 14 — Grafos y union-find
Objetivos
- Representar un grafo y elegir la representación según el problema.
- Recorrer un grafo con BFS y DFS, y decir qué responde cada uno.
- Implementar union-find con sus dos mejoras.
Teoría — Grafos: representación, BFS y DFS · Union-find
Lectura: Apuntes, semana 14.
Apoyo: Open Data Structures, secs. 12.1 (AdjacencyMatrix), 12.2 (AdjacencyLists) y 12.3 (Graph Traversal). CLRS, capítulos Elementary Graph Algorithms y Data Structures for Disjoint Sets.
Temas:
- Grafos en todas partes: rutas, enlaces, dependencias. Nodos, aristas, dirigidos o no, con pesos o sin ellos.
- Matriz de adyacencia y listas de adyacencia: memoria y costo de cada consulta. Grafos dispersos y densos.
- BFS con una cola: por niveles. Da el camino con menos aristas.
- DFS con recursión o con una pila: componentes conexas y detección de ciclos.
- Costo Θ(V + E), y marcar lo visitado para no repetir ni entrar en un ciclo.
- Reconstruir un camino guardando de dónde se llegó.
- Union-find: ¿están conectados estos dos? Bosque de árboles, unión por rango y compresión de caminos. Costo casi constante por operación, enunciado sin demostración.
- Union-find frente a DFS: por qué uno sirve mejor cuando las conexiones van llegando una a una.
- Error común: marcar un nodo como visitado al sacarlo de la cola de BFS en vez de al meterlo.
Laboratorio — Generar y resolver laberintos
Esta semana una sesión es para la Práctica 4.
Sesión 1:
- Escribir
UnionFind, con pruebas contra una versión ingenua dada. - Generar un laberinto en una cuadrícula: recorrer las paredes en orden al azar y tirar cada una que separe dos regiones distintas.
- Representar el laberinto como un grafo con listas de adyacencia, y resolverlo con BFS y con DFS.
- Imprimir el laberinto y el camino. Comparar los nodos que visitó cada recorrido. Como el laberinto tiene un solo camino entre dos celdas, abrir algunas paredes más, con la función dada, para comparar también el largo de los caminos.
Sesión 2: Práctica 4.
Entregas
- Práctica 4: Árboles AVL y rojinegros, heaps y colas de prioridad. Ver
practicas/README.md.
Preguntas de repaso
- ¿Cuánta memoria usa cada representación con 1000 nodos y 3000 aristas? ¿Cuál elegirían?
- ¿Por qué BFS encuentra el camino con menos aristas? ¿Por qué DFS no lo garantiza?
- Corran BFS a mano sobre un grafo pequeño de su elección, y escriban el orden de visita y la cola en cada paso.
- ¿Qué hace la compresión de caminos? Dibujen un árbol antes y después de un
find. - En el generador del laboratorio, ¿por qué el laberinto resultante tiene exactamente un camino entre dos celdas cualesquiera?
Código de la semana
Compilar y probar dentro del contenedor del curso con make y make test.
Ejemplos (15)Errores (5)Pruebas (4)Laboratorio (10)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// BFS sobre los tres mapas. Las lecturas se cuentan; los tiempos dependen de la máquina.
// Compilar con -O2 y sin sanitizers. Uso: bfs_scaling mapa...
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>
#include "bench.h"
#include "map_file.h"
#include "matrix_graph.h"
#include "traversals.h"
namespace {
// BFS sobre la matriz: para saber los vecinos de u hay que leer su fila completa.
std::int64_t matrix_bfs_reads(const MatrixGraph& matrix, int source) {
int n = matrix.node_count();
std::vector<int> distance(n, -1);
std::queue<int> pending;
std::int64_t reads = 0;
distance[source] = 0;
pending.push(source);
while (!pending.empty()) {
int u = pending.front();
pending.pop();
for (int v = 0; v < n; v++) {
reads++;
if (matrix.has_edge(u, v) && distance[v] == -1) {
distance[v] = distance[u] + 1;
pending.push(v);
}
}
}
return reads;
}
} // namespace
int main(int argc, char* argv[]) {
const int reps = 11;
std::cout << " nodos aristas sacados entradas leidas ms lista ns/(V+E)\n";
for (int i = 1; i < argc; i++) {
Graph graph = read_map(argv[i]);
std::int64_t size = graph.node_count() + static_cast<std::int64_t>(graph.edge_count());
std::int64_t pulled = 0;
std::int64_t reads = 0;
double seconds = median_seconds(reps, [&] {
BfsResult result = bfs(graph, 0);
pulled = static_cast<std::int64_t>(result.order.size());
keep(result.distance.back());
});
for (int u = 0; u < graph.node_count(); u++) {
reads += static_cast<std::int64_t>(graph.neighbors(u).size());
}
std::cout << std::setw(9) << graph.node_count() << std::setw(10) << graph.edge_count() << std::setw(9) << pulled
<< std::setw(17) << reads << std::fixed << std::setprecision(3) << std::setw(11) << seconds * 1000
<< std::setprecision(1) << std::setw(10) << seconds * 1e9 / static_cast<double>(size) << "\n";
std::cout.unsetf(std::ios::fixed);
std::cout << std::setprecision(6);
}
// La matriz solo con el primer mapa: en lima.txt necesitaría más de 6 GB.
Graph first = read_map(argv[1]);
MatrixGraph matrix(first.node_count());
for (int u = 0; u < first.node_count(); u++) {
for (const Edge& edge : first.neighbors(u)) {
if (u < edge.to) {
matrix.add_edge(u, edge.to);
}
}
}
std::int64_t matrix_reads = 0;
double matrix_seconds = median_seconds(reps, [&] { matrix_reads = matrix_bfs_reads(matrix, 0); keep(matrix_reads); });
double list_seconds = median_seconds(reps, [&] { keep(bfs(first, 0).distance.back()); });
std::cout << std::fixed << std::setprecision(3);
std::cout << "matriz en el primer mapa: " << matrix_reads << " celdas leidas, " << matrix_seconds * 1000 << " ms\n";
std::cout << "listas en el primer mapa: " << list_seconds * 1000 << " ms\n";
return 0;
}// Sigue BFS paso a paso sobre el grafo de la clase: qué sale, qué se marca y cómo queda la cola.
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include "sample_graphs.h"
#include "traversals.h"
namespace {
std::string join(const std::vector<int>& nodes) {
std::string text;
for (int node : nodes) {
text += (text.empty() ? "" : " ") + std::to_string(node);
}
return text;
}
} // namespace
int main() {
Graph graph = class_graph();
std::vector<int> distance(graph.node_count(), -1);
std::vector<int> waiting{0};
std::size_t front = 0;
distance[0] = 0;
std::cout << "sale marca cola al terminar el paso\n";
std::cout << " - 0 " << join(waiting) << "\n";
while (front < waiting.size()) {
int u = waiting[front];
front++;
std::vector<int> newly_marked;
for (const Edge& edge : graph.neighbors(u)) {
if (distance[edge.to] == -1) {
distance[edge.to] = distance[u] + 1;
waiting.push_back(edge.to);
newly_marked.push_back(edge.to);
}
}
std::vector<int> queue_now(waiting.begin() + static_cast<std::ptrdiff_t>(front), waiting.end());
std::cout << std::setw(4) << u << " " << std::left << std::setw(10) << join(newly_marked)
<< std::right << join(queue_now) << "\n";
}
BfsResult result = bfs(graph, 0);
std::cout << "orden: ";
print_nodes(result.order);
std::cout << "distancia: ";
print_nodes(result.distance);
std::cout << "padre: ";
print_nodes(result.parent);
std::cout << "camino a 6: ";
print_nodes(path_to(result.parent, 6));
return 0;
}// Bosque de union-find que cuenta los saltos por parent, con cada mejora opcional. Sirve para
// medir y dibujar. La clase del laboratorio tiene otra interfaz, y siempre usa las dos mejoras.
#ifndef COUNTING_FOREST_H
#define COUNTING_FOREST_H
#include <algorithm>
#include <cstdint>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
// Invariantes: una raíz es su propio padre; si x no es raíz y se usa rango,
// rank[x] < rank[parent[x]]; sets_ es la cantidad de raíces.
class CountingForest {
public:
CountingForest(int n, bool by_rank, bool compress)
: parent_(n), rank_(n, 0), sets_(n), by_rank_(by_rank), compress_(compress) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
int root = x;
while (parent_[root] != root) {
root = parent_[root];
hops_++;
}
while (compress_ && parent_[x] != root && x != root) {
int next = parent_[x];
parent_[x] = root;
x = next;
}
return root;
}
bool unite(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a == root_b) {
return false;
}
if (by_rank_) {
if (rank_[root_a] < rank_[root_b]) {
std::swap(root_a, root_b);
}
if (rank_[root_a] == rank_[root_b]) {
rank_[root_a]++;
}
parent_[root_b] = root_a;
} else {
parent_[root_a] = root_b;
}
sets_--;
return true;
}
int sets() const { return sets_; }
std::int64_t hops() const { return hops_; }
const std::vector<int>& parents() const { return parent_; }
const std::vector<int>& ranks() const { return rank_; }
// Profundidad de x, sin comprimir ni contar.
int depth(int x) const {
int steps = 0;
while (parent_[x] != x) {
x = parent_[x];
steps++;
}
return steps;
}
int height() const {
int best = 0;
for (int x = 0; x < static_cast<int>(parent_.size()); x++) {
best = std::max(best, depth(x));
}
return best;
}
// El árbol de root, escrito como en la semana 10: 0(1,2(3)).
std::string shape(int root) const {
std::string text = std::to_string(root);
std::string children;
for (int x = 0; x < static_cast<int>(parent_.size()); x++) {
if (x != root && parent_[x] == root) {
children += (children.empty() ? "" : ",") + shape(x);
}
}
return children.empty() ? text : text + "(" + children + ")";
}
bool check_invariants() const {
int roots = 0;
for (int x = 0; x < static_cast<int>(parent_.size()); x++) {
if (parent_[x] == x) {
roots++;
} else if (by_rank_ && rank_[x] >= rank_[parent_[x]]) {
return false;
}
}
return roots == sets_;
}
private:
std::vector<int> parent_;
std::vector<int> rank_;
int sets_;
bool by_rank_;
bool compress_;
std::int64_t hops_ = 0;
};
#endif// DFS sobre el grafo de la clase, y lo que responde: orden, componentes y ciclos.
#include <iostream>
#include <vector>
#include "sample_graphs.h"
#include "traversals.h"
int main() {
Graph graph = class_graph();
std::cout << "BFS desde 0: ";
print_nodes(bfs(graph, 0).order);
std::cout << "DFS recursivo desde 0: ";
print_nodes(dfs_recursive(graph, 0));
std::cout << "DFS con pila de marcos: ";
print_nodes(dfs_iterative(graph, 0));
std::cout << "cola de BFS con una pila: ";
print_nodes(stack_search(graph, 0));
Graph pieces(8);
pieces.add_edge(0, 1);
pieces.add_edge(1, 2);
pieces.add_edge(3, 4);
pieces.add_edge(5, 6);
pieces.add_edge(6, 7);
pieces.add_edge(7, 5);
std::cout << "componentes de cada nodo: ";
print_nodes(component_labels(pieces));
std::cout << "con ciclo (no dirigido): " << (has_cycle_undirected(pieces) ? "si" : "no") << "\n";
Graph tree(4);
tree.add_edge(0, 1);
tree.add_edge(1, 2);
tree.add_edge(1, 3);
std::cout << "arbol con ciclo: " << (has_cycle_undirected(tree) ? "si" : "no") << "\n";
Graph tasks(4, true);
tasks.add_edge(0, 1);
tasks.add_edge(0, 2);
tasks.add_edge(1, 3);
tasks.add_edge(2, 3);
std::cout << "dependencias con ciclo: " << (has_cycle_directed(tasks) ? "si" : "no") << "\n";
tasks.add_edge(3, 0);
std::cout << "agregando 3 -> 0: " << (has_cycle_directed(tasks) ? "si" : "no") << "\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 un mapa de data/mapas: V E, luego V líneas de coordenadas y E líneas "u v metros".
#ifndef MAP_FILE_H
#define MAP_FILE_H
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include "graph.h"
struct MapEdge {
int u;
int v;
int meters;
};
// Devuelve V en node_count y las aristas en el orden del archivo. Sale del programa si falla.
inline std::vector<MapEdge> read_map_edges(const std::string& file_name, int& node_count) {
std::ifstream file(file_name);
std::size_t edge_count = 0;
if (!(file >> node_count >> edge_count)) {
std::cerr << "no se pudo leer " << file_name << "\n";
std::exit(1);
}
double latitude = 0;
double longitude = 0;
for (int i = 0; i < node_count; i++) {
file >> latitude >> longitude;
}
std::vector<MapEdge> edges(edge_count);
for (MapEdge& edge : edges) {
file >> edge.u >> edge.v >> edge.meters;
}
if (!file) {
std::cerr << "archivo incompleto: " << file_name << "\n";
std::exit(1);
}
return edges;
}
inline Graph read_map(const std::string& file_name) {
int node_count = 0;
std::vector<MapEdge> edges = read_map_edges(file_name, node_count);
Graph graph(node_count);
for (const MapEdge& edge : edges) {
graph.add_edge(edge.u, edge.v, edge.meters);
}
return graph;
}
// Memoria de las listas: un vector por nodo más su capacidad reservada. No incluye lo que
// agrega el administrador de memoria a cada bloque.
inline std::size_t list_bytes(const Graph& graph) {
std::size_t bytes = sizeof(Graph) + graph.node_count() * sizeof(std::vector<Edge>);
for (int u = 0; u < graph.node_count(); u++) {
bytes += graph.neighbors(u).capacity() * sizeof(Edge);
}
return bytes;
}
#endif// Un grafo real: las calles alrededor de Miraflores. Tamaño, memoria, y BFS frente a DFS.
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include "map_file.h"
#include "traversals.h"
namespace {
std::int64_t path_meters(const Graph& graph, const std::vector<int>& path) {
std::int64_t meters = 0;
for (std::size_t i = 0; i + 1 < path.size(); i++) {
for (const Edge& edge : graph.neighbors(path[i])) {
if (edge.to == path[i + 1]) {
meters += edge.weight;
break;
}
}
}
return meters;
}
// Camino de DFS: la pila de marcos en el momento de llegar al destino. Es igual a dfs_iterative.
std::vector<int> dfs_path(const Graph& graph, int source, int target, int& marked_count) {
std::vector<bool> marked(graph.node_count(), false);
std::vector<std::pair<int, std::size_t>> stack;
marked[source] = true;
marked_count = 1;
stack.push_back({source, 0});
while (!stack.empty() && stack.back().first != target) {
auto& [u, next] = stack.back();
const std::vector<Edge>& list = graph.neighbors(u);
if (next == list.size()) {
stack.pop_back();
continue;
}
int v = list[next].to;
next++;
if (!marked[v]) {
marked[v] = true;
marked_count++;
stack.push_back({v, 0});
}
}
std::vector<int> path;
for (const auto& frame : stack) {
path.push_back(frame.first);
}
return path;
}
} // namespace
int main(int argc, char* argv[]) {
if (argc != 4) {
std::cerr << "uso: map_tour mapa origen destino\n";
return 1;
}
Graph graph = read_map(argv[1]);
int source = std::stoi(argv[2]);
int target = std::stoi(argv[3]);
std::int64_t v = graph.node_count();
std::int64_t e = static_cast<std::int64_t>(graph.edge_count());
std::size_t largest = 0;
for (int u = 0; u < v; u++) {
largest = std::max(largest, graph.neighbors(u).size());
}
std::cout << "nodos: " << v << ", aristas: " << e << "\n";
std::cout << "grado medio: " << 2.0 * static_cast<double>(e) / static_cast<double>(v) << ", grado maximo: " << largest << "\n";
std::cout << "aristas sobre las posibles: " << 100.0 * static_cast<double>(e) / (static_cast<double>(v) * (v - 1) / 2) << " %\n";
std::cout << "matriz de un byte por celda: " << v * v << " bytes\n";
std::cout << "listas: " << list_bytes(graph) << " bytes\n";
std::vector<int> labels = component_labels(graph);
std::cout << "componentes: " << *std::max_element(labels.begin(), labels.end()) + 1 << "\n";
BfsResult result = bfs(graph, source);
std::vector<int> by_bfs = path_to(result.parent, target);
int dfs_marked = 0;
std::vector<int> by_dfs = dfs_path(graph, source, target, dfs_marked);
// BFS saca los nodos en el orden en que los marcó: este es el conteo al marcar el destino.
int bfs_marked = 0;
for (int u : result.order) {
bfs_marked++;
if (u == target) {
break;
}
}
std::cout << "de " << source << " a " << target << ":\n";
std::cout << "BFS: " << by_bfs.size() - 1 << " aristas, " << path_meters(graph, by_bfs)
<< " metros, nodos marcados: " << bfs_marked << "\n";
std::cout << "DFS: " << by_dfs.size() - 1 << " aristas, " << path_meters(graph, by_dfs)
<< " metros, nodos marcados: " << dfs_marked << "\n";
return 0;
}// Grafo no dirigido con matriz de adyacencia: un byte por cada par de nodos.
#ifndef MATRIX_GRAPH_H
#define MATRIX_GRAPH_H
#include <cassert>
#include <cstddef>
#include <vector>
// Invariantes: la tabla tiene n * n celdas, es simétrica y su diagonal vale 0.
class MatrixGraph {
public:
explicit MatrixGraph(int node_count)
: n_(node_count), cells_(static_cast<std::size_t>(node_count) * node_count, 0) {}
void add_edge(int u, int v) {
assert(u != v);
cell(u, v) = 1;
cell(v, u) = 1;
}
// Una sola lectura, sin importar cuántas aristas haya.
bool has_edge(int u, int v) const { return cells_[index(u, v)] != 0; }
int node_count() const { return n_; }
std::size_t bytes() const { return sizeof(MatrixGraph) + cells_.capacity(); }
bool check_invariants() const {
if (cells_.size() != static_cast<std::size_t>(n_) * n_) {
return false;
}
for (int u = 0; u < n_; u++) {
if (has_edge(u, u)) {
return false;
}
for (int v = 0; v < u; v++) {
if (has_edge(u, v) != has_edge(v, u)) {
return false;
}
}
}
return true;
}
private:
std::size_t index(int u, int v) const {
assert(0 <= u && u < n_ && 0 <= v && v < n_);
return static_cast<std::size_t>(u) * n_ + v;
}
char& cell(int u, int v) { return cells_[index(u, v)]; }
int n_;
std::vector<char> cells_;
};
#endif// Las calles de un mapa llegan una a una, al azar, y tras cada una se pregunta si dos nodos al
// azar están conectados. Cuenta el trabajo de DFS y de union-find. No mide tiempos.
#include <cstdint>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
#include "counting_forest.h"
#include "map_file.h"
#include "traversals.h"
namespace {
// DFS desde a hasta encontrar b. Suma los nodos marcados y las entradas leídas.
bool connected_by_dfs(const Graph& graph, int a, int b, std::vector<int>& stamp, int query, std::int64_t& reads) {
std::vector<int> stack{a};
stamp[a] = query;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
if (u == b) {
return true;
}
for (const Edge& edge : graph.neighbors(u)) {
reads++;
if (stamp[edge.to] != query) {
stamp[edge.to] = query;
stack.push_back(edge.to);
}
}
}
return false;
}
} // namespace
int main(int argc, char* argv[]) {
if (argc != 2) {
std::cerr << "uso: online_connectivity mapa\n";
return 1;
}
int n = 0;
std::vector<MapEdge> edges = read_map_edges(argv[1], n);
std::mt19937 rng(14);
for (std::size_t i = edges.size() - 1; i > 0; i--) {
std::swap(edges[i], edges[rng() % (i + 1)]);
}
Graph graph(n);
CountingForest forest(n, true, true);
std::vector<int> stamp(n, -1);
std::int64_t dfs_reads = 0;
std::int64_t answers_yes = 0;
std::size_t joined_at = 0;
int query = 0;
for (const MapEdge& edge : edges) {
graph.add_edge(edge.u, edge.v, edge.meters);
forest.unite(edge.u, edge.v);
int a = static_cast<int>(rng() % n);
int b = static_cast<int>(rng() % n);
bool by_dfs = connected_by_dfs(graph, a, b, stamp, query, dfs_reads);
bool by_forest = forest.find(a) == forest.find(b);
if (by_dfs != by_forest) {
std::cout << "no coinciden\n";
return 1;
}
answers_yes += by_dfs ? 1 : 0;
query++;
if (joined_at == 0 && forest.sets() == 1) {
joined_at = static_cast<std::size_t>(query);
}
}
std::cout << "nodos: " << n << ", aristas que llegan: " << edges.size() << ", preguntas: " << query << "\n";
std::cout << "respuestas si: " << answers_yes << " (todo unido tras la arista " << joined_at << ")\n";
std::cout << "DFS en cada pregunta, entradas leidas: " << dfs_reads << "\n";
std::cout << "union-find, saltos por parent: " << forest.hops() << "\n";
std::cout << "por pregunta: DFS " << static_cast<double>(dfs_reads) / query << ", union-find "
<< static_cast<double>(forest.hops()) / query << "\n";
// Si primero llegan todas las aristas, basta una pasada y un arreglo.
std::vector<int> labels = component_labels(graph);
std::cout << "todas primero: una pasada lee " << 2 * edges.size() << " entradas, y cada pregunta compara "
<< "dos etiquetas: " << (labels[0] == labels[n - 1] ? "conectados" : "separados") << "\n";
return 0;
}// Memoria y costo de consulta de las dos representaciones, con 1000 nodos y 3000 aristas.
#include <cstdint>
#include <iostream>
#include <random>
#include <set>
#include <utility>
#include <vector>
#include "graph.h"
#include "map_file.h"
#include "matrix_graph.h"
int main() {
const int nodes = 1000;
const std::size_t edges = 3000;
Graph lists(nodes);
MatrixGraph matrix(nodes);
std::set<std::pair<int, int>> seen;
std::mt19937 rng(14);
while (seen.size() < edges) {
int u = static_cast<int>(rng() % nodes);
int v = static_cast<int>(rng() % nodes);
if (u > v) {
std::swap(u, v);
}
if (u != v && seen.insert({u, v}).second) {
lists.add_edge(u, v);
matrix.add_edge(u, v);
}
}
std::size_t entries = 0;
std::size_t capacity = 0;
std::size_t longest = 0;
for (int u = 0; u < nodes; u++) {
entries += lists.neighbors(u).size();
capacity += lists.neighbors(u).capacity();
longest = std::max(longest, lists.neighbors(u).size());
}
std::cout << "nodos: " << nodes << ", aristas: " << edges << "\n";
std::cout << "sizeof(std::vector<Edge>): " << sizeof(std::vector<Edge>)
<< ", sizeof(Edge): " << sizeof(Edge) << "\n";
std::cout << "matriz, bytes: " << matrix.bytes() << "\n";
std::cout << "listas, entradas: " << entries << ", capacidad reservada: " << capacity << "\n";
std::cout << "listas, bytes: " << list_bytes(lists) << "\n";
std::cout << "lista mas larga: " << longest << "\n";
// Celdas leídas por cada pregunta, sin contar la lectura de la lista.
std::int64_t list_reads = 0;
std::int64_t matrix_reads = 0;
std::int64_t found = 0;
for (int u = 0; u < nodes; u++) {
for (int v = 0; v < nodes; v++) {
matrix_reads++;
bool in_matrix = matrix.has_edge(u, v);
bool in_lists = false;
for (const Edge& edge : lists.neighbors(u)) {
list_reads++;
if (edge.to == v) {
in_lists = true;
break;
}
}
if (in_matrix != in_lists) {
std::cout << "no coinciden\n";
return 1;
}
found += in_lists ? 1 : 0;
}
}
std::cout << "preguntas has_edge: " << matrix_reads << ", respuestas si: " << found << "\n";
std::cout << "lecturas por pregunta, matriz: 1.00, listas: " << static_cast<double>(list_reads) / matrix_reads << "\n";
// Recorrer los vecinos de todos los nodos.
std::cout << "recorrer todos los vecinos, matriz: " << static_cast<std::int64_t>(nodes) * nodes
<< " lecturas, listas: " << entries << " lecturas\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: 7 nodos y 8 aristas. Tiene ciclos.
inline Graph class_graph() {
Graph graph(7);
graph.add_edge(0, 1);
graph.add_edge(0, 2);
graph.add_edge(1, 3);
graph.add_edge(2, 3);
graph.add_edge(2, 4);
graph.add_edge(3, 5);
graph.add_edge(4, 5);
graph.add_edge(5, 6);
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// Recorridos de un grafo: BFS, DFS, caminos, componentes y ciclos.
#ifndef TRAVERSALS_H
#define TRAVERSALS_H
#include <algorithm>
#include <cstddef>
#include <queue>
#include <utility>
#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.
// order: los nodos en el orden en que salieron de la cola.
struct BfsResult {
std::vector<int> distance;
std::vector<int> parent;
std::vector<int> order;
};
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();
result.order.push_back(u);
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;
}
inline void dfs_visit(const Graph& graph, int u, std::vector<bool>& marked, std::vector<int>& order) {
marked[u] = true;
order.push_back(u);
for (const Edge& edge : graph.neighbors(u)) {
if (!marked[edge.to]) {
dfs_visit(graph, edge.to, marked, order);
}
}
}
// DFS recursivo: gasta un marco de llamada por cada nodo del camino actual.
inline std::vector<int> dfs_recursive(const Graph& graph, int source) {
std::vector<bool> marked(graph.node_count(), false);
std::vector<int> order;
dfs_visit(graph, source, marked, order);
return order;
}
// El mismo orden que la versión recursiva, con una pila propia: cada entrada es un nodo y la
// posición de su lista por la que iba, justo lo que guardaría su marco de llamada.
inline std::vector<int> dfs_iterative(const Graph& graph, int source) {
std::vector<bool> marked(graph.node_count(), false);
std::vector<int> order;
std::vector<std::pair<int, std::size_t>> stack;
marked[source] = true;
order.push_back(source);
stack.push_back({source, 0});
while (!stack.empty()) {
auto& [u, next] = stack.back();
const std::vector<Edge>& list = graph.neighbors(u);
if (next == list.size()) {
stack.pop_back();
continue;
}
int v = list[next].to;
next++;
if (!marked[v]) {
marked[v] = true;
order.push_back(v);
stack.push_back({v, 0}); // invalida u y next, que no se vuelven a usar en esta vuelta
}
}
return order;
}
// La cola de BFS cambiada por una pila: se marca al sacar, y un nodo puede estar varias veces.
// Visita lo mismo, pero en otro orden, y la pila puede llegar a tener Θ(E) entradas.
inline std::vector<int> stack_search(const Graph& graph, int source) {
std::vector<bool> marked(graph.node_count(), false);
std::vector<int> order;
std::vector<int> stack{source};
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
if (marked[u]) {
continue;
}
marked[u] = true;
order.push_back(u);
for (const Edge& edge : graph.neighbors(u)) {
if (!marked[edge.to]) {
stack.push_back(edge.to);
}
}
}
return order;
}
// Componente de cada nodo, numeradas desde 0. Una búsqueda por cada nodo sin marcar.
inline std::vector<int> component_labels(const Graph& graph) {
std::vector<int> label(graph.node_count(), -1);
int count = 0;
for (int start = 0; start < graph.node_count(); start++) {
if (label[start] != -1) {
continue;
}
std::vector<int> stack{start};
label[start] = count;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
for (const Edge& edge : graph.neighbors(u)) {
if (label[edge.to] == -1) {
label[edge.to] = count;
stack.push_back(edge.to);
}
}
}
count++;
}
return label;
}
inline bool undirected_cycle_from(const Graph& graph, int u, int parent, std::vector<bool>& marked) {
marked[u] = true;
for (const Edge& edge : graph.neighbors(u)) {
if (!marked[edge.to]) {
if (undirected_cycle_from(graph, edge.to, u, marked)) {
return true;
}
} else if (edge.to != parent) {
return true; // ya marcado y no es de donde vengo: hay otro camino hasta él
}
}
return false;
}
// Para un grafo no dirigido sin aristas repetidas.
inline bool has_cycle_undirected(const Graph& graph) {
std::vector<bool> marked(graph.node_count(), false);
for (int start = 0; start < graph.node_count(); start++) {
if (!marked[start] && undirected_cycle_from(graph, start, -1, marked)) {
return true;
}
}
return false;
}
enum class Color { White, Gray, Black }; // sin ver, en el camino actual, terminado
inline bool directed_cycle_from(const Graph& graph, int u, std::vector<Color>& color) {
color[u] = Color::Gray;
for (const Edge& edge : graph.neighbors(u)) {
if (color[edge.to] == Color::Gray) {
return true; // volvió a un nodo del camino actual
}
if (color[edge.to] == Color::White && directed_cycle_from(graph, edge.to, color)) {
return true;
}
}
color[u] = Color::Black;
return false;
}
// Para un grafo dirigido: hacen falta tres estados, no dos.
inline bool has_cycle_directed(const Graph& graph) {
std::vector<Color> color(graph.node_count(), Color::White);
for (int start = 0; start < graph.node_count(); start++) {
if (color[start] == Color::White && directed_cycle_from(graph, start, color)) {
return true;
}
}
return false;
}
#endif// Cuenta los saltos por parent de union-find, con y sin cada mejora. No mide tiempos.
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <random>
#include <string>
#include <vector>
#include "counting_forest.h"
namespace {
struct Result {
std::int64_t hops;
std::int64_t operations;
int height;
};
// Une 0-1, 1-2, 2-3... y después pregunta por todos.
Result chain(int n, bool by_rank, bool compress) {
CountingForest forest(n, by_rank, compress);
std::int64_t operations = 0;
for (int i = 0; i + 1 < n; i++) {
forest.unite(i, i + 1);
operations++;
}
int height = forest.height();
for (int i = 0; i < n; i++) {
forest.find(i);
operations++;
}
return {forest.hops(), operations, height};
}
// 4n operaciones al azar: la mitad son unite y la mitad find.
Result random_work(int n, bool by_rank, bool compress) {
CountingForest forest(n, by_rank, compress);
std::mt19937 rng(14);
std::int64_t operations = 4 * static_cast<std::int64_t>(n);
for (std::int64_t i = 0; i < operations; i++) {
int a = static_cast<int>(rng() % n);
int b = static_cast<int>(rng() % n);
if (i % 2 == 0) {
forest.unite(a, b);
} else {
forest.find(a);
}
}
return {forest.hops(), operations, forest.height()};
}
// Une árboles iguales: 2^k nodos con altura k, y el nodo más hondo es n - 1 en este armado.
CountingForest binomial(int n, bool compress) {
CountingForest forest(n, true, compress);
for (int size = 1; size < n; size *= 2) {
for (int start = 0; start + size < n; start += 2 * size) {
forest.unite(start, start + size);
}
}
return forest;
}
void print_row(const std::string& name, int n, const Result& result) {
std::cout << std::left << std::setw(26) << name << std::right << std::setw(9) << n << std::setw(8) << result.height
<< std::setw(13) << result.hops << std::setw(12) << std::fixed << std::setprecision(2)
<< static_cast<double>(result.hops) / static_cast<double>(result.operations) << "\n";
}
} // namespace
int main() {
std::cout << "Cadena 0-1, 1-2, 2-3...\n";
std::cout << "variante n altura saltos saltos/op\n";
for (int n : {1 << 10, 1 << 14}) {
print_row("sin mejoras", n, chain(n, false, false));
print_row("solo rango", n, chain(n, true, false));
print_row("solo compresion", n, chain(n, false, true));
print_row("rango y compresion", n, chain(n, true, true));
}
std::cout << "\nAl azar, 4n operaciones\n";
std::cout << "variante n altura saltos saltos/op\n";
for (int n : {1 << 10, 1 << 14, 1 << 18, 1 << 20}) {
print_row("solo rango", n, random_work(n, true, false));
print_row("rango y compresion", n, random_work(n, true, true));
}
std::cout << "\nUn solo find en el peor arbol, con las dos mejoras\n";
std::cout << " n log2 n primer find segundo find\n";
for (int exponent : {10, 14, 18, 20}) {
int n = 1 << exponent;
CountingForest forest = binomial(n, true);
int deepest = 0;
for (int x = 0; x < n; x++) {
if (forest.depth(x) > forest.depth(deepest)) {
deepest = x;
}
}
std::int64_t start = forest.hops();
forest.find(deepest);
std::int64_t first = forest.hops() - start;
start = forest.hops();
forest.find(deepest);
std::cout << std::setw(9) << n << std::setw(8) << exponent << std::setw(13) << first << std::setw(14)
<< forest.hops() - start << "\n";
}
return 0;
}// Un árbol de union-find antes y después de un find con compresión.
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
#include "counting_forest.h"
#include "sample_graphs.h"
int main() {
CountingForest forest(8, true, true);
for (auto [a, b] : std::vector<std::pair<int, int>>{{0, 1}, {2, 3}, {0, 2}, {4, 5}, {6, 7}, {4, 6}, {0, 4}}) {
forest.unite(a, b);
std::cout << "unite(" << a << ", " << b << ") parent: ";
print_nodes(forest.parents());
}
std::cout << "rangos: ";
print_nodes(forest.ranks());
std::cout << "antes: " << forest.shape(0) << "\n";
std::cout << "altura: " << forest.height() << "\n";
std::int64_t before = forest.hops();
int root = forest.find(7);
std::cout << "find(7) = " << root << ", saltos: " << forest.hops() - before << "\n";
std::cout << "despues: " << forest.shape(0) << "\n";
std::cout << "parent: ";
print_nodes(forest.parents());
std::cout << "rangos: ";
print_nodes(forest.ranks());
std::cout << "altura: " << forest.height() << ", rango de la raiz: " << forest.ranks()[0] << "\n";
before = forest.hops();
forest.find(7);
std::cout << "otro find(7), saltos: " << forest.hops() - before << "\n";
return 0;
}Errores
Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.
// ERROR A PROPÓSITO: BFS que marca un nodo al sacarlo de la cola, y no al meterlo.
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <queue>
#include <vector>
#include "../graph.h"
namespace {
struct Run {
std::vector<int> distance;
std::int64_t pushes;
};
// skip_marked agrega el arreglo más común: al sacar un nodo ya marcado, se ignora.
Run wrong_bfs(const Graph& graph, int source, bool skip_marked) {
std::vector<bool> marked(graph.node_count(), false);
std::vector<int> distance(graph.node_count(), -1);
std::queue<int> pending;
std::int64_t pushes = 1;
distance[source] = 0;
pending.push(source);
while (!pending.empty()) {
int u = pending.front();
pending.pop();
if (skip_marked && marked[u]) {
continue;
}
marked[u] = true; // demasiado tarde
for (const Edge& edge : graph.neighbors(u)) {
if (!marked[edge.to]) {
distance[edge.to] = distance[u] + 1;
pending.push(edge.to);
pushes++;
}
}
}
return {distance, pushes};
}
// k rombos en fila: de cada cruce salen dos caminos que se juntan en el siguiente.
Graph diamonds(int k) {
Graph graph(3 * k + 1);
for (int i = 0; i < k; i++) {
int top = 3 * i;
graph.add_edge(top, top + 1);
graph.add_edge(top, top + 2);
graph.add_edge(top + 1, top + 3);
graph.add_edge(top + 2, top + 3);
}
return graph;
}
} // namespace
int main() {
Graph triangle(3);
triangle.add_edge(0, 1);
triangle.add_edge(0, 2);
triangle.add_edge(1, 2);
std::cout << "triangulo, distancia de 0 a 2 (la verdadera es 1):\n";
std::cout << " marcando al sacar: " << wrong_bfs(triangle, 0, false).distance[2] << "\n";
std::cout << " e ignorando los ya marcados: " << wrong_bfs(triangle, 0, true).distance[2] << "\n";
std::cout << "rombos nodos aristas entradas a la cola ignorando marcados\n";
for (int k : {2, 4, 8, 12, 16}) {
Graph graph = diamonds(k);
std::cout << std::setw(6) << k << std::setw(7) << graph.node_count() << std::setw(9) << graph.edge_count()
<< std::setw(20) << wrong_bfs(graph, 0, false).pushes << std::setw(20)
<< wrong_bfs(graph, 0, true).pushes << "\n";
}
return 0;
}// ERROR A PROPÓSITO: la revisión de ciclos no dirigida, usada en un grafo dirigido.
#include <iostream>
#include "../traversals.h"
int main() {
// Dos caminos de 0 a 3. No hay ciclo: de 3 no se puede volver.
Graph tasks(4, true);
tasks.add_edge(0, 1);
tasks.add_edge(0, 2);
tasks.add_edge(1, 3);
tasks.add_edge(2, 3);
std::cout << "revision no dirigida: " << (has_cycle_undirected(tasks) ? "hay ciclo" : "sin ciclo") << "\n";
std::cout << "revision con tres colores: " << (has_cycle_directed(tasks) ? "hay ciclo" : "sin ciclo") << "\n";
return 0;
}// ERROR A PROPÓSITO: una búsqueda sin marcas. En un ciclo no termina, así que aquí se corta.
#include <iostream>
#include <queue>
#include "../graph.h"
int main() {
Graph graph(3);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(2, 0);
std::queue<int> pending;
pending.push(0);
int steps = 0;
const int limit = 20;
while (!pending.empty() && steps < limit) {
int u = pending.front();
pending.pop();
steps++;
for (const Edge& edge : graph.neighbors(u)) {
pending.push(edge.to);
}
}
std::cout << "cortado tras " << steps << " pasos, con " << pending.size() << " entradas en la cola\n";
return 0;
}// ERROR A PROPÓSITO: DFS recursivo sobre un camino muy largo. Cada nodo gasta un marco de llamada.
#include <cstdlib>
#include <iostream>
#include "../traversals.h"
int main(int argc, char* argv[]) {
int n = argc > 1 ? std::atoi(argv[1]) : 1000;
Graph path(n);
for (int i = 0; i + 1 < n; i++) {
path.add_edge(i, i + 1);
}
std::cout << "con pila propia: " << dfs_iterative(path, 0).size() << " nodos" << std::endl;
std::cout << "con recursion: " << dfs_recursive(path, 0).size() << " nodos" << std::endl;
return 0;
}// ERROR A PROPÓSITO: unir enlazando los elementos y no sus raíces.
#include <iostream>
#include <numeric>
#include <vector>
namespace {
int find(const std::vector<int>& parent, int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
} // namespace
int main() {
std::vector<int> parent(4);
std::iota(parent.begin(), parent.end(), 0);
parent[0] = 1; // unir 0 con 1
parent[0] = 2; // unir 0 con 2: debió enlazar las raíces, y 0 ya no es raíz
parent[3] = 3;
std::cout << "0 y 2: " << (find(parent, 0) == find(parent, 2) ? "juntos" : "separados") << "\n";
std::cout << "0 y 1: " << (find(parent, 0) == find(parent, 1) ? "juntos" : "separados") << "\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")
MIRAFLORES = f"{DATA}/mapas/miraflores.txt"
MAPS = [MIRAFLORES, f"{DATA}/mapas/lima-sur.txt", f"{DATA}/mapas/lima.txt"]
SAN = ["g++", "-Wall", "-Wextra", "-std=c++20", "-g", "-fsanitize=address,undefined"]
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):
for name in ["bfs_trace", "dfs_demo", "representations", "uf_demo", "uf_costs"]:
with self.subTest(program=name):
done = run(f"build/{name}")
self.assertEqual(done.returncode, 0, done.stdout)
def test_bfs_reads_each_list_once_on_real_maps(self):
"""Cuenta V nodos sacados y 2E entradas leídas. Los tiempos no se comparan."""
lines = run("build/bfs_scaling", *MAPS).stdout.splitlines()
for row in lines[1:4]:
nodes, edges, pulled, reads, *_ = row.split()
self.assertEqual(pulled, nodes)
self.assertEqual(int(reads), 2 * int(edges))
self.assertIn("matriz en el primer mapa: 5026564 celdas leidas", lines[4])
def test_review_question_memory(self):
lines = run("build/representations").stdout.splitlines()
self.assertIn("matriz, bytes: 1000032", lines)
self.assertTrue(any(line.startswith("listas, entradas: 6000,") for line in lines))
def test_sequence_without_improvements_is_quadratic(self):
"""n(n - 1)/2 saltos exactos en la cadena: la fórmula de los apuntes."""
lines = run("build/uf_costs").stdout.splitlines()
rows = [line.split() for line in lines if line.startswith("sin mejoras")]
for row in rows:
n, hops = int(row[2]), int(row[4])
self.assertEqual(hops, n * (n - 1) // 2)
def test_single_find_can_cost_log_n(self):
lines = run("build/uf_costs").stdout.splitlines()
start = next(i for i, line in enumerate(lines) if line.startswith("Un solo find"))
rows = [line.split() for line in lines[start + 2:]]
self.assertEqual(len(rows), 4)
for n, log_n, first, second in rows:
self.assertEqual(int(n), 2 ** int(log_n))
self.assertEqual(first, log_n)
self.assertEqual(second, "1")
def test_online_connectivity_answers_agree(self):
done = run("build/online_connectivity", MIRAFLORES)
self.assertEqual(done.returncode, 0, done.stdout)
self.assertNotIn("no coinciden", done.stdout)
def test_map_is_one_component_and_bfs_is_not_longer(self):
lines = run("build/map_tour", MIRAFLORES, "0", "2000").stdout.splitlines()
self.assertIn("nodos: 2242, aristas: 3474", lines)
self.assertIn("componentes: 1", lines)
by_bfs = next(line for line in lines if line.startswith("BFS:"))
by_dfs = next(line for line in lines if line.startswith("DFS:"))
self.assertLess(int(by_bfs.split()[1]), int(by_dfs.split()[1]))
class DeliberateErrors(unittest.TestCase):
def build(self, name):
binary = f"build/{name}"
done = run(*SAN, f"errors/{name}.cpp", "-o", binary)
self.assertEqual(done.returncode, 0, done.stdout)
self.assertNotIn("warning", done.stdout)
return binary
def test_marking_on_pop_breaks_distance_and_queue(self):
lines = run(self.build("bfs_mark_on_pop")).stdout.splitlines()
self.assertEqual(lines[1], " marcando al sacar: 2")
self.assertEqual(lines[2], " e ignorando los ya marcados: 2")
for row in lines[4:]:
k, _, edges, entries, skipping = (int(field) for field in row.split())
self.assertEqual(entries, 2 ** (k + 2) - 3)
self.assertLessEqual(skipping, 2 * edges + 1)
def test_no_marks_never_empties_the_queue(self):
done = run(self.build("no_marks"))
self.assertIn("cortado tras 20 pasos", done.stdout)
def test_recursive_dfs_overflows(self):
binary = self.build("recursive_dfs_overflow")
self.assertEqual(run(binary, "1000").returncode, 0)
done = run(binary, "1000000")
self.assertNotEqual(done.returncode, 0)
self.assertIn("con pila propia: 1000000 nodos", done.stdout)
self.assertIn("stack-overflow", done.stdout)
def test_undirected_check_lies_on_directed_graph(self):
done = run(self.build("directed_false_cycle"))
self.assertIn("revision no dirigida: hay ciclo", done.stdout)
self.assertIn("revision con tres colores: sin ciclo", done.stdout)
def test_unite_without_find_loses_a_connection(self):
done = run(self.build("unite_without_find"))
self.assertIn("0 y 1: separados", done.stdout)
if __name__ == "__main__":
unittest.main()"""Pruebas del laboratorio. 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 resource
import subprocess
import unittest
HERE = pathlib.Path(__file__).parent
LAB_DIR = os.environ.get("LAB_DIR", "solution")
BINARY = HERE / "build" / LAB_DIR / "lab_tests"
MAZE = HERE / "build" / LAB_DIR / "maze"
UNION_FIND = [
"new_sets_are_separate", "unite_reports_and_counts", "unite_uses_roots", "rank_rises_only_on_ties",
"height_stays_logarithmic", "compression_flattens_the_whole_path", "compression_leaves_other_branches",
"compression_keeps_ranks", "random_against_naive",
]
GENERATOR = ["generator_makes_a_tree", "generator_opens_only_real_walls", "generator_depends_on_seed"]
SEARCH = [
"maze_graph_has_each_passage", "maze_graph_keeps_passage_order", "bfs_small_case",
"bfs_stops_when_marking_target", "bfs_source_is_target", "bfs_unreachable", "bfs_random_against_brute_force",
"dfs_small_case", "dfs_path_skips_dead_ends", "dfs_source_is_target", "dfs_unreachable",
"dfs_random_paths_are_valid", "perfect_maze_gives_the_same_path", "cycles_separate_the_paths",
]
# Pila de 128 KB: alcanza para el programa, y no para una recursión de 6000 niveles.
SMALL_STACK = 128 * 1024
# Un BFS que marca al sacar se queda sin memoria o sin tiempo en la prueba de los rombos.
LIMIT_SECONDS = 20
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"(union_find\.h|maze\.h|solver\.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 run_case(name, setup=None, env=None):
return subprocess.run(
[str(BINARY), name], cwd=HERE, text=True, encoding="utf-8", errors="replace", preexec_fn=setup, env=env,
stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=LIMIT_SECONDS,
)
def small_stack():
resource.setrlimit(resource.RLIMIT_STACK, (SMALL_STACK, SMALL_STACK))
# ASan reserva mucha memoria virtual, así que el límite de memoria se le pasa en sus opciones.
LIMITED_MEMORY = {**os.environ, "ASAN_OPTIONS": "hard_rss_limit_mb=800"}
def add_cases(cls, names):
for name in names:
def case(self, name=name):
done = run_case(name)
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", "maze", "compare_mazes"]:
(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 TestUnionFind(LabCase):
"""Paso 1: UnionFind, contra la versión ingenua."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestGenerator(LabCase):
"""Paso 2: el generador de laberintos."""
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestSearch(LabCase):
"""Paso 3: el grafo del laberinto, BFS y DFS."""
def test_bfs_marks_when_pushing(self):
try:
done = run_case("bfs_marks_when_pushing", env=LIMITED_MEMORY)
except subprocess.TimeoutExpired:
self.fail("no terminó a tiempo: ¿marcan el nodo al sacarlo de la cola, y no al meterlo?")
self.assertEqual(done.returncode, 0, short_report(done.stdout))
def test_dfs_long_corridor(self):
done = run_case("dfs_long_corridor", small_stack)
self.assertEqual(done.returncode, 0, short_report(done.stdout))
@unittest.skipUnless((HERE / LAB_DIR).is_dir(), f"no existe la carpeta {LAB_DIR}")
class TestProgram(unittest.TestCase):
"""Paso 4: el programa completo, y su dibujo."""
@classmethod
def setUpClass(cls):
code, output = build("maze")
if code != 0:
raise AssertionError(output)
def run_maze(self, *args):
return subprocess.run(
[str(MAZE), *args], cwd=HERE, text=True, encoding="utf-8", errors="replace",
stdout=subprocess.PIPE, stderr=subprocess.STDOUT, timeout=LIMIT_SECONDS,
)
def test_draws_both_searches(self):
done = self.run_maze("8", "4", "1")
self.assertEqual(done.returncode, 0, short_report(done.stdout))
lines = done.stdout.splitlines()
self.assertTrue(lines[0].startswith("BFS: camino de "), lines[0])
self.assertEqual(lines[1], "+--" * 8 + "+")
self.assertEqual(lines[2][1:3], "SS")
self.assertTrue(lines[10].startswith("DFS: camino de "), lines[10])
self.assertEqual(lines[8][-3:-1], "EE")
def test_bad_usage(self):
self.assertNotEqual(self.run_maze().returncode, 0)
self.assertNotEqual(self.run_maze("0", "4", "1").returncode, 0)
add_cases(TestUnionFind, UNION_FIND)
add_cases(TestGenerator, GENERATOR)
add_cases(TestSearch, SEARCH)
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 os
import pathlib
import platform
import re
import subprocess
import unittest
try:
import pty
except ImportError:
pty = None
HERE = pathlib.Path(__file__).parent
ROOT = HERE.parent.parent
NOTES = ROOT / "notes" / "week-14.md"
SLIDES = ROOT / "slides" / "week-14.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 informe de ASan. Puede omitir líneas, pero no cambiarlas ni reordenarlas.
# Las direcciones y los números de proceso no se comparan.
REPORT = "<!-- informe recortado -->"
# 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()
# Los informes se capturaron en esta arquitectura: en otra cambian líneas de las bibliotecas.
REPORT_MACHINE = "aarch64"
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 run_in_terminal(command):
"""Corre el comando en una terminal de verdad: así se intercala la salida del programa
con el informe, igual que cuando ustedes lo corren."""
master, slave = pty.openpty()
process = subprocess.Popen(
["bash", "-c", command], cwd=HERE, stdin=subprocess.DEVNULL, stdout=slave, stderr=slave,
)
os.close(slave)
data = b""
while True:
try:
chunk = os.read(master, 4096)
except OSError:
break
if not chunk:
break
data += chunk
os.close(master)
process.wait(timeout=120)
text = data.decode("utf-8", errors="replace").replace("\r", "")
return normalize(re.sub(r"\x1b\[[0-9;]*[mK]", "", text))
def clean_lines(text):
return [line.rstrip() for line in text.splitlines()]
def stable(line):
"""Quita de una línea de informe lo que cambia en cada corrida."""
line = re.sub(r"0x[0-9a-f]+", "ADDR", line.strip())
return re.sub(r"==\d+==", "==N==", line)
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("*"))
for source in sources:
lines.update(line.strip() for line in source.read_text(encoding="utf-8").splitlines())
return lines
class ReportCheck(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 = [stable(line) for line in expected if line.strip() and line.strip() != "..."]
real = [stable(line) 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(ReportCheck):
@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("$ ") or mark == REPORT:
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")
@unittest.skipUnless(pty and platform.machine() == REPORT_MACHINE, "los informes son de aarch64")
def test_reports_in_notes(self):
checked = 0
for lines, mark in note_blocks("text"):
if mark != REPORT:
continue
for command, expected in split_commands(lines):
actual = clean_lines(run_in_terminal(command))
self.assert_in_order(command, expected, actual)
checked += 1
self.assertGreaterEqual(checked, 1)
@unittest.skipUnless(NOTES.exists(), "faltan los apuntes")
def test_code_blocks_in_notes_exist(self):
known = known_code_lines()
for lines, _ in note_blocks("cpp"):
for line in lines:
if line.strip() and line.strip() != "...":
with self.subTest(line=line):
self.assertIn(line.strip(), known)
class SlidesAreTrue(ReportCheck):
@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)))
# Algunos informes usan programas que compiló la prueba de los apuntes, que corre antes.
@unittest.skipUnless(SLIDES.exists(), "faltan las diapositivas")
@unittest.skipUnless(pty and platform.machine() == REPORT_MACHINE, "los informes son de aarch64")
def test_reports_in_slides(self):
for block in slide_blocks("informe"):
for command, expected in split_commands(block):
self.assert_in_order(command, expected, clean_lines(run_in_terminal(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")
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_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 de Graph, MatrixGraph, los recorridos y CountingForest: casos dirigidos, y grafos al azar con
// semilla fija. La biblioteca estándar no trae grafos: la referencia es un cálculo por fuerza bruta.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <utility>
#include <vector>
#include "counting_forest.h"
#include "graph.h"
#include "matrix_graph.h"
#include "sample_graphs.h"
#include "traversals.h"
// Permite dañar un grafo, para ver si check_invariants lo nota.
struct GraphTestAccess {
static std::vector<std::vector<Edge>>& lists(Graph& graph) { return graph.adjacency_; }
};
namespace {
Graph random_graph(int n, int edges, std::mt19937& rng, bool directed = false) {
Graph graph(n, directed);
std::set<std::pair<int, int>> seen;
for (int i = 0; i < edges; i++) {
int u = static_cast<int>(rng() % n);
int v = static_cast<int>(rng() % n);
if (!directed && u > v) {
std::swap(u, v);
}
if (u != v && seen.insert({u, v}).second) {
graph.add_edge(u, v);
}
}
return graph;
}
std::vector<int> brute_distances(const Graph& graph, int source) {
int n = graph.node_count();
std::vector<int> distance(n, -1);
distance[source] = 0;
bool changed = true;
while (changed) {
changed = false;
for (int u = 0; u < n; u++) {
for (const Edge& edge : graph.neighbors(u)) {
if (distance[u] != -1 && (distance[edge.to] == -1 || distance[u] + 1 < distance[edge.to])) {
distance[edge.to] = distance[u] + 1;
changed = true;
}
}
}
}
return distance;
}
void test_graph_basics() {
Graph graph = class_graph();
assert(graph.node_count() == 7);
assert(graph.edge_count() == 8);
assert(graph.has_edge(5, 6) && graph.has_edge(6, 5));
assert(!graph.has_edge(0, 6));
assert(graph.check_invariants());
Graph directed(3, true);
directed.add_edge(0, 1, 7);
assert(directed.has_edge(0, 1) && !directed.has_edge(1, 0));
assert(directed.neighbors(0)[0].weight == 7);
assert(directed.check_invariants());
}
void test_check_invariants_notices_damage() {
Graph lost_pair = class_graph();
GraphTestAccess::lists(lost_pair)[0].pop_back();
assert(!lost_pair.check_invariants());
Graph swapped = class_graph();
GraphTestAccess::lists(swapped)[0][0].to = 6;
assert(!swapped.check_invariants());
Graph out_of_range = class_graph();
GraphTestAccess::lists(out_of_range)[0][0].to = 7;
assert(!out_of_range.check_invariants());
Graph other_weight = class_graph();
GraphTestAccess::lists(other_weight)[0][0].weight = 9;
assert(!other_weight.check_invariants());
}
void test_matrix_agrees_with_lists() {
std::mt19937 rng(14);
Graph lists = random_graph(60, 200, rng);
MatrixGraph matrix(60);
for (int u = 0; u < 60; u++) {
for (const Edge& edge : lists.neighbors(u)) {
if (u < edge.to) {
matrix.add_edge(u, edge.to);
}
}
}
assert(matrix.check_invariants());
for (int u = 0; u < 60; u++) {
for (int v = 0; v < 60; v++) {
assert(matrix.has_edge(u, v) == lists.has_edge(u, v));
}
}
}
void test_bfs_by_hand() {
BfsResult result = bfs(class_graph(), 0);
assert((result.order == std::vector<int>{0, 1, 2, 3, 4, 5, 6}));
assert((result.distance == std::vector<int>{0, 1, 1, 2, 2, 3, 4}));
assert((path_to(result.parent, 6) == std::vector<int>{0, 1, 3, 5, 6}));
Graph apart(3);
apart.add_edge(0, 1);
BfsResult partial = bfs(apart, 0);
assert(partial.distance[2] == -1);
assert(path_to(partial.parent, 2).empty());
assert((path_to(partial.parent, 0) == std::vector<int>{0}));
}
void test_bfs_random() {
std::mt19937 rng(14);
for (int round = 0; round < 200; round++) {
int n = 1 + static_cast<int>(rng() % 50);
Graph graph = random_graph(n, static_cast<int>(rng() % (3 * n)), rng);
int source = static_cast<int>(rng() % n);
BfsResult result = bfs(graph, source);
assert(result.distance == brute_distances(graph, source));
for (std::size_t i = 0; i + 1 < result.order.size(); i++) {
assert(result.distance[result.order[i]] <= result.distance[result.order[i + 1]]);
}
for (int v = 0; v < n; v++) {
std::vector<int> path = path_to(result.parent, v);
assert(static_cast<int>(path.size()) - 1 == result.distance[v] || (path.empty() && result.distance[v] == -1));
}
}
}
void test_dfs_versions_agree() {
std::mt19937 rng(21);
for (int round = 0; round < 200; round++) {
int n = 1 + static_cast<int>(rng() % 50);
Graph graph = random_graph(n, static_cast<int>(rng() % (3 * n)), rng);
int source = static_cast<int>(rng() % n);
std::vector<int> recursive = dfs_recursive(graph, source);
assert(recursive == dfs_iterative(graph, source));
std::vector<int> by_stack = stack_search(graph, source);
std::vector<int> by_bfs = bfs(graph, source).order;
std::sort(recursive.begin(), recursive.end());
std::sort(by_stack.begin(), by_stack.end());
std::sort(by_bfs.begin(), by_bfs.end());
assert(recursive == by_stack);
assert(recursive == by_bfs);
}
}
void test_components_against_forest() {
std::mt19937 rng(7);
for (int round = 0; round < 200; round++) {
int n = 1 + static_cast<int>(rng() % 60);
Graph graph = random_graph(n, static_cast<int>(rng() % (2 * n)), rng);
CountingForest forest(n, true, true);
for (int u = 0; u < n; u++) {
for (const Edge& edge : graph.neighbors(u)) {
forest.unite(u, edge.to);
}
}
std::vector<int> labels = component_labels(graph);
assert(*std::max_element(labels.begin(), labels.end()) + 1 == forest.sets());
for (int a = 0; a < n; a++) {
for (int b = 0; b < n; b++) {
assert((labels[a] == labels[b]) == (forest.find(a) == forest.find(b)));
}
}
}
}
// Un grafo no dirigido sin ciclos es un bosque: exactamente V - C aristas.
void test_undirected_cycles_random() {
std::mt19937 rng(9);
for (int round = 0; round < 300; round++) {
int n = 1 + static_cast<int>(rng() % 30);
Graph graph = random_graph(n, static_cast<int>(rng() % (n + 2)), rng);
std::vector<int> labels = component_labels(graph);
int components = *std::max_element(labels.begin(), labels.end()) + 1;
bool is_forest = static_cast<int>(graph.edge_count()) == n - components;
assert(has_cycle_undirected(graph) == !is_forest);
}
}
// Un grafo dirigido no tiene ciclos si y solo si se puede vaciar quitando nodos sin entradas.
void test_directed_cycles_random() {
std::mt19937 rng(11);
for (int round = 0; round < 300; round++) {
int n = 1 + static_cast<int>(rng() % 20);
Graph graph = random_graph(n, static_cast<int>(rng() % (2 * n)), rng, true);
std::vector<int> incoming(n, 0);
for (int u = 0; u < n; u++) {
for (const Edge& edge : graph.neighbors(u)) {
incoming[edge.to]++;
}
}
std::vector<int> ready;
for (int u = 0; u < n; u++) {
if (incoming[u] == 0) {
ready.push_back(u);
}
}
int removed = 0;
while (!ready.empty()) {
int u = ready.back();
ready.pop_back();
removed++;
for (const Edge& edge : graph.neighbors(u)) {
if (--incoming[edge.to] == 0) {
ready.push_back(edge.to);
}
}
}
assert(has_cycle_directed(graph) == (removed != n));
}
}
void test_forest_variants_agree() {
for (bool by_rank : {false, true}) {
for (bool compress : {false, true}) {
std::mt19937 rng(5);
int n = 200;
CountingForest forest(n, by_rank, compress);
std::vector<int> label(n);
for (int i = 0; i < n; i++) {
label[i] = i;
}
int sets = n;
for (int step = 0; step < 2000; step++) {
int a = static_cast<int>(rng() % n);
int b = static_cast<int>(rng() % n);
if (step % 2 == 0) {
bool different = label[a] != label[b];
assert(forest.unite(a, b) == different);
if (different) {
int from = label[a];
std::replace(label.begin(), label.end(), from, label[b]);
sets--;
}
} else {
assert((forest.find(a) == forest.find(b)) == (label[a] == label[b]));
}
assert(forest.sets() == sets);
assert(forest.check_invariants());
}
}
}
}
// Con rango y sin compresión, el rango de una raíz es la altura, y no pasa de log2 n.
void test_rank_bounds_height() {
std::mt19937 rng(6);
int n = 4096;
CountingForest forest(n, true, false);
for (int step = 0; step < 3 * n; step++) {
forest.unite(static_cast<int>(rng() % n), static_cast<int>(rng() % n));
}
assert(forest.height() <= 12);
for (int x = 0; x < n; x++) {
if (forest.parents()[x] == x) {
int tallest = 0;
for (int y = 0; y < n; y++) {
if (forest.find(y) == x) {
tallest = std::max(tallest, forest.depth(y));
}
}
assert(tallest == forest.ranks()[x]);
}
}
}
// Con compresión, el rango de una raíz queda como cota: puede ser mayor que la altura.
void test_compression_leaves_rank_as_bound() {
CountingForest forest(8, true, true);
for (auto [a, b] : std::vector<std::pair<int, int>>{{0, 1}, {2, 3}, {0, 2}, {4, 5}, {6, 7}, {4, 6}, {0, 4}}) {
forest.unite(a, b);
}
assert(forest.height() == 3);
assert(forest.ranks()[0] == 3);
for (int x = 0; x < 8; x++) {
forest.find(x);
}
assert(forest.height() == 1);
assert(forest.ranks()[0] == 3);
assert(forest.shape(0) == "0(1,2,3,4,5,6,7)");
}
} // namespace
int main() {
test_graph_basics();
test_check_invariants_notices_damage();
test_matrix_agrees_with_lists();
test_bfs_by_hand();
test_bfs_random();
test_dfs_versions_agree();
test_components_against_forest();
test_undirected_cycles_random();
test_directed_cycles_random();
test_forest_variants_agree();
test_rank_bounds_height();
test_compression_leaves_rank_as_bound();
std::cout << "todas las pruebas pasaron\n";
return 0;
}Laboratorio
Archivos de partida del laboratorio de la semana.
// 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// El laberinto: una cuadrícula de celdas con paredes entre vecinas. Completen generate_maze; lo demás ya viene hecho.
#ifndef MAZE_H
#define MAZE_H
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "not_implemented.h"
#include "union_find.h"
// Una pared separa dos celdas vecinas, con a < b.
struct Wall {
int a;
int b;
};
// Baraja con Fisher-Yates sobre números del generador. No usa std::shuffle: su resultado depende de
// la biblioteca, y así la misma semilla da el mismo laberinto en cualquier máquina.
inline void shuffle_walls(std::vector<Wall>& walls, std::mt19937& rng) {
for (std::size_t i = walls.size(); i > 1; i--) {
std::swap(walls[i - 1], walls[rng() % i]);
}
}
// Las celdas se numeran por filas: la celda de la columna x y la fila y es y * width + x.
// Invariantes: cada pasaje une dos celdas vecinas, y ninguno se repite.
class Maze {
public:
Maze(int width, int height) : width_(width), height_(height) {
assert(width > 0 && height > 0);
}
int width() const { return width_; }
int height() const { return height_; }
int cell_count() const { return width_ * height_; }
int cell(int x, int y) const { return y * width_ + x; }
// Los pasajes abiertos, en el orden en que se abrieron.
const std::vector<Wall>& passages() const { return passages_; }
bool is_open(int a, int b) const {
for (const Wall& wall : passages_) {
if ((wall.a == a && wall.b == b) || (wall.a == b && wall.b == a)) {
return true;
}
}
return false;
}
void open(const Wall& wall) { passages_.push_back(wall); }
// Todas las paredes entre celdas vecinas, abiertas o no: de izquierda a derecha y de arriba abajo.
std::vector<Wall> all_walls() const {
std::vector<Wall> walls;
for (int y = 0; y < height_; y++) {
for (int x = 0; x < width_; x++) {
if (x + 1 < width_) {
walls.push_back({cell(x, y), cell(x + 1, y)});
}
if (y + 1 < height_) {
walls.push_back({cell(x, y), cell(x, y + 1)});
}
}
}
return walls;
}
// Dibuja el laberinto. Marca con . los visitados y con * el camino; el primero y el último del
// camino salen como S y E.
std::string render(const std::vector<int>& path = {}, const std::vector<int>& visited = {}) const {
std::vector<char> mark(cell_count(), ' ');
for (int node : visited) {
mark[node] = '.';
}
for (int node : path) {
mark[node] = '*';
}
if (!path.empty()) {
mark[path.front()] = 'S';
mark[path.back()] = 'E';
}
std::vector<char> open_right(cell_count(), 0);
std::vector<char> open_down(cell_count(), 0);
for (const Wall& wall : passages_) {
(wall.b == wall.a + 1 ? open_right : open_down)[wall.a] = 1;
}
std::string text;
for (int x = 0; x < width_; x++) {
text += "+--";
}
text += "+\n";
for (int y = 0; y < height_; y++) {
text += "|";
for (int x = 0; x < width_; x++) {
text += mark[cell(x, y)];
text += mark[cell(x, y)];
text += open_right[cell(x, y)] ? ' ' : '|';
}
text += "\n+";
for (int x = 0; x < width_; x++) {
text += open_down[cell(x, y)] ? " +" : "--+";
}
text += "\n";
}
return text;
}
private:
int width_;
int height_;
std::vector<Wall> passages_;
};
// Abre hasta `extra` paredes más, al azar: aparecen ciclos. Devuelve cuántas abrió.
inline int open_extra_walls(Maze& maze, int extra, std::mt19937& rng) {
std::vector<char> is_open_right(maze.cell_count(), 0);
std::vector<char> is_open_down(maze.cell_count(), 0);
for (const Wall& wall : maze.passages()) {
(wall.b == wall.a + 1 ? is_open_right : is_open_down)[wall.a] = 1;
}
std::vector<Wall> closed;
for (const Wall& wall : maze.all_walls()) {
bool is_right = wall.b == wall.a + 1;
if (!(is_right ? is_open_right : is_open_down)[wall.a]) {
closed.push_back(wall);
}
}
shuffle_walls(closed, rng);
int opened = 0;
for (const Wall& wall : closed) {
if (opened == extra) {
break;
}
maze.open(wall);
opened++;
}
return opened;
}
// Paso 2: abre paredes hasta dejar un laberinto perfecto. Tomen todas las paredes, barájenlas con
// shuffle_walls, recórranlas en ese orden, y abran cada una que separe dos regiones distintas.
inline void generate_maze(Maze& maze, std::mt19937& rng) {
(void)maze;
(void)rng;
not_implemented("generate_maze");
}
#endif// Versión ingenua, ya hecha: guarda la etiqueta de cada elemento. Unir recorre todo el arreglo.
// Sirve de referencia para probar su UnionFind.
#ifndef NAIVE_UNION_FIND_H
#define NAIVE_UNION_FIND_H
#include <numeric>
#include <vector>
class NaiveUnionFind {
public:
explicit NaiveUnionFind(int n) : label_(n), count_(n) {
std::iota(label_.begin(), label_.end(), 0);
}
bool connected(int a, int b) const { return label_[a] == label_[b]; }
bool unite(int a, int b) {
if (connected(a, b)) {
return false;
}
int from = label_[a];
int to = label_[b];
for (int& label : label_) {
if (label == from) {
label = to;
}
}
count_--;
return true;
}
int component_count() const { return count_; }
private:
std::vector<int> label_;
int count_;
};
#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
Peguen aquí la tabla de `make compare` y respondan con sus propios números.
## Tabla
## Sin paredes extra
¿Cuánto vale la columna de caminos de BFS frente a la de DFS? ¿Por qué tiene que ser así en estos laberintos?
Mirando los dibujos de `build/lab/maze`, ¿por qué los nodos visitados sí cambian?
## Con paredes extra
¿Qué cambió en los caminos? Busquen una fila donde la diferencia sea grande y dibújenla con `build/lab/maze`.
¿Quién visitó menos nodos? ¿Gana siempre el mismo? Digan qué se puede concluir de estas filas y qué no.// Resolver el laberinto: de pasajes a un grafo, y buscar con BFS y con DFS. Completen los tres.
#ifndef SOLVER_H
#define SOLVER_H
#include <algorithm>
#include <cstddef>
#include <queue>
#include <utility>
#include <vector>
#include "graph.h"
#include "maze.h"
#include "not_implemented.h"
// Lo que devuelve una búsqueda:
// - path: del origen al destino, los dos incluidos. Vacío si no se llega.
// - visited: los nodos marcados, en el orden en que se marcaron, sin repetir.
// Las dos búsquedas marcan igual y paran igual: se detienen apenas marcan el destino.
struct SearchResult {
std::vector<int> path;
std::vector<int> visited;
};
// Paso 3: un nodo por celda, y una arista sin peso por cada pasaje, en el orden de maze.passages().
inline Graph maze_graph(const Maze& maze) {
(void)maze;
not_implemented("maze_graph");
}
// Paso 3: BFS que marca al meter a la cola y guarda de dónde se llegó. Recorre los vecinos en el
// orden de la lista. El camino sale de los padres, y hay que darle la vuelta.
inline SearchResult bfs_search(const Graph& graph, int source, int target) {
(void)graph;
(void)source;
(void)target;
not_implemented("bfs_search");
}
// Paso 3: DFS con pila propia, no recursivo: una prueba corre un pasillo largo con poca pila.
// Recorre los vecinos en el orden de la lista, como lo haría la versión recursiva.
inline SearchResult dfs_search(const Graph& graph, int source, int target) {
(void)graph;
(void)source;
(void)target;
not_implemented("dfs_search");
}
#endif// Union-find con unión por rango y compresión de caminos. Completen lo marcado con not_implemented.
#ifndef UNION_FIND_H
#define UNION_FIND_H
#include <cstddef>
#include <vector>
#include "not_implemented.h"
// Invariantes:
// - parent_[x] es un elemento válido, y las raíces son las x con parent_[x] == x.
// - Si x no es raíz, rank_[x] < rank_[parent_[x]]: subir por los padres siempre termina.
// - Sin compresión, el rango de una raíz sería la altura de su árbol. Con compresión, es solo una cota.
// - components_ es la cantidad de raíces.
class UnionFind {
public:
// Paso 1: n elementos, cada uno en su propio conjunto: padre de sí mismo y rango 0.
explicit UnionFind(int n) {
(void)n;
not_implemented("UnionFind::UnionFind");
}
// Paso 1: devuelve la raíz de x y deja a todos los nodos del camino colgando de la raíz.
int find(int x) {
(void)x;
not_implemented("UnionFind::find");
}
// Paso 1: une los conjuntos de a y de b. Devuelve true si estaban separados. El árbol de menor
// rango cuelga de la raíz del otro, y el rango solo sube si los dos eran iguales.
bool unite(int a, int b) {
(void)a;
(void)b;
not_implemented("UnionFind::unite");
}
// Paso 1: ¿están a y b en el mismo conjunto?
bool connected(int a, int b) {
(void)a;
(void)b;
not_implemented("UnionFind::connected");
}
int size() const { return static_cast<int>(parent_.size()); }
int component_count() const { return components_; }
// Para las pruebas y para dibujar: leen sin comprimir.
int parent_of(int x) const { return parent_[x]; }
int rank_of(int x) const { return rank_[x]; }
bool check_invariants() const {
int roots = 0;
for (int x = 0; x < size(); x++) {
int up = parent_[x];
if (up < 0 || up >= size()) {
return false;
}
if (up == x) {
roots++;
} else if (rank_[x] >= rank_[up]) {
return false;
}
}
return roots == components_;
}
private:
std::vector<int> parent_;
std::vector<int> rank_;
int components_ = 0;
};
#endif// Paso 4: la tabla para el informe. Compara BFS y DFS en laberintos sin ciclos y con ciclos.
#include <iomanip>
#include <iostream>
#include <random>
#include "maze.h"
#include "solver.h"
int main() {
const int width = 40;
const int height = 20;
std::cout << "laberinto de " << width << " x " << height << ", " << width * height << " celdas\n";
std::cout << "extra semilla camino BFS camino DFS visitados BFS visitados DFS\n";
for (int extra : {0, 40, 200}) {
for (int seed = 1; seed <= 5; seed++) {
std::mt19937 rng(static_cast<std::mt19937::result_type>(seed));
Maze maze(width, height);
generate_maze(maze, rng);
open_extra_walls(maze, extra, rng);
Graph graph = maze_graph(maze);
int target = maze.cell_count() - 1;
SearchResult by_bfs = bfs_search(graph, 0, target);
SearchResult by_dfs = dfs_search(graph, 0, target);
std::cout << std::setw(5) << extra << std::setw(9) << seed << std::setw(12) << by_bfs.path.size() - 1
<< std::setw(12) << by_dfs.path.size() - 1 << std::setw(15) << by_bfs.visited.size()
<< std::setw(15) << by_dfs.visited.size() << "\n";
}
}
return 0;
}// Pruebas públicas del laboratorio. Se corre una por proceso: lab_tests nombre.
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include "graph.h"
#include "maze.h"
#include "naive_union_find.h"
#include "solver.h"
#include "union_find.h"
namespace {
int depth_of(const UnionFind& sets, int x) {
int steps = 0;
while (sets.parent_of(x) != x) {
x = sets.parent_of(x);
steps++;
}
return steps;
}
int floor_log2(int n) {
int result = 0;
while (n > 1) {
n /= 2;
result++;
}
return result;
}
// ---------- Paso 1: UnionFind ----------
void new_sets_are_separate() {
UnionFind sets(5);
assert(sets.size() == 5);
assert(sets.component_count() == 5);
assert(sets.check_invariants());
for (int x = 0; x < 5; x++) {
assert(sets.find(x) == x);
assert(sets.parent_of(x) == x);
assert(sets.rank_of(x) == 0);
}
assert(!sets.connected(0, 1));
assert(sets.connected(3, 3));
}
void unite_reports_and_counts() {
UnionFind sets(4);
assert(sets.unite(0, 1));
assert(sets.component_count() == 3);
assert(sets.connected(0, 1));
assert(!sets.connected(1, 2));
assert(!sets.unite(1, 0));
assert(sets.component_count() == 3);
assert(!sets.unite(2, 2));
assert(sets.component_count() == 3);
assert(sets.unite(1, 2));
assert(sets.connected(0, 2));
assert(sets.component_count() == 2);
assert(sets.check_invariants());
}
// unir a través de un elemento que no es raíz no debe perder a nadie
void unite_uses_roots() {
UnionFind sets(6);
sets.unite(0, 1);
sets.unite(2, 3);
sets.unite(0, 2);
sets.unite(4, 5);
int outsider = -1;
for (int x = 0; x < 4; x++) {
if (sets.parent_of(x) != x) {
outsider = x; // cualquiera que no sea raíz
}
}
assert(outsider != -1);
sets.unite(outsider, 4);
assert(sets.component_count() == 1);
for (int x = 0; x < 6; x++) {
assert(sets.connected(0, x));
}
assert(sets.check_invariants());
}
void rank_rises_only_on_ties() {
UnionFind sets(8);
sets.unite(0, 1);
int root = sets.find(0);
assert(sets.rank_of(root) == 1);
assert(sets.rank_of(root == 0 ? 1 : 0) == 0);
// Un rango 0 cuelga de un rango 1: la raíz no cambia y su rango tampoco.
sets.unite(2, 0);
assert(sets.find(2) == root);
assert(sets.rank_of(root) == 1);
sets.unite(root, 3);
assert(sets.find(3) == root);
assert(sets.rank_of(root) == 1);
// Dos de rango 1: sube a 2.
sets.unite(4, 5);
sets.unite(0, 4);
assert(sets.rank_of(sets.find(0)) == 2);
assert(sets.check_invariants());
}
// Una unión que pone el árbol pequeño arriba crecería hasta n - 1.
void height_stays_logarithmic() {
for (int n : {16, 256, 1024}) {
UnionFind sets(n);
for (int i = 0; i + 1 < n; i++) {
sets.unite(i + 1, i);
int height = 0;
for (int x = 0; x <= i + 1; x++) {
height = std::max(height, depth_of(sets, x));
}
assert(height <= floor_log2(n));
}
assert(sets.check_invariants());
}
// El peor armado: uniones de árboles iguales, sin ningún find de por medio.
int n = 1024;
UnionFind sets(n);
for (int size = 1; size < n; size *= 2) {
for (int start = 0; start + size < n; start += 2 * size) {
sets.unite(start, start + size);
}
}
assert(sets.rank_of(sets.find(0)) == 10);
assert(sets.check_invariants());
}
// Arma un árbol alto, de abajo hacia arriba, y devuelve su nodo más hondo.
int deepest_of(const UnionFind& sets) {
int deepest = 0;
for (int x = 0; x < sets.size(); x++) {
if (depth_of(sets, x) > depth_of(sets, deepest)) {
deepest = x;
}
}
return deepest;
}
int root_without_compressing(const UnionFind& sets, int x) {
while (sets.parent_of(x) != x) {
x = sets.parent_of(x);
}
return x;
}
UnionFind tall_tree(int n) {
UnionFind sets(n);
for (int size = 1; size < n; size *= 2) {
for (int start = 0; start + size < n; start += 2 * size) {
// Se une por las raíces para que la compresión no aplane nada mientras se arma.
sets.unite(root_without_compressing(sets, start), root_without_compressing(sets, start + size));
}
}
return sets;
}
void compression_flattens_the_whole_path() {
UnionFind sets = tall_tree(64);
int deepest = deepest_of(sets);
int height = depth_of(sets, deepest);
assert(height == 6);
std::vector<int> path;
for (int x = deepest; sets.parent_of(x) != x; x = sets.parent_of(x)) {
path.push_back(x);
}
int root = sets.find(deepest);
for (int x : path) {
assert(sets.parent_of(x) == root);
}
assert(depth_of(sets, deepest) == 1);
assert(sets.check_invariants());
}
void compression_leaves_other_branches() {
UnionFind sets = tall_tree(64);
int deepest = deepest_of(sets);
std::vector<int> before;
for (int x = 0; x < sets.size(); x++) {
before.push_back(sets.parent_of(x));
}
std::set<int> on_path;
for (int x = deepest; sets.parent_of(x) != x; x = sets.parent_of(x)) {
on_path.insert(x);
}
sets.find(deepest);
for (int x = 0; x < sets.size(); x++) {
if (on_path.count(x) == 0) {
assert(sets.parent_of(x) == before[x]);
}
}
}
void compression_keeps_ranks() {
UnionFind sets = tall_tree(64);
std::vector<int> before;
for (int x = 0; x < sets.size(); x++) {
before.push_back(sets.rank_of(x));
}
for (int x = 0; x < sets.size(); x++) {
sets.find(x);
}
for (int x = 0; x < sets.size(); x++) {
assert(sets.rank_of(x) == before[x]);
}
assert(sets.check_invariants());
}
void random_against_naive() {
std::mt19937 rng(14);
for (int n : {1, 2, 10, 100, 500}) {
UnionFind sets(n);
NaiveUnionFind naive(n);
for (int step = 0; step < 4 * n + 20; step++) {
int a = static_cast<int>(rng() % n);
int b = static_cast<int>(rng() % n);
if (rng() % 2 == 0) {
assert(sets.unite(a, b) == naive.unite(a, b));
} else {
assert(sets.connected(a, b) == naive.connected(a, b));
}
assert(sets.component_count() == naive.component_count());
if (step % 16 == 0) {
assert(sets.check_invariants());
}
}
for (int a = 0; a < std::min(n, 40); a++) {
for (int b = 0; b < std::min(n, 40); b++) {
assert(sets.connected(a, b) == naive.connected(a, b));
}
}
assert(sets.check_invariants());
}
}
// ---------- Paso 2: generar ----------
// Revisa con una búsqueda propia: no depende de lo que el estudiante escribe en el paso 3.
void assert_connected_tree(const Maze& maze) {
int n = maze.cell_count();
assert(static_cast<int>(maze.passages().size()) == n - 1);
std::vector<std::vector<int>> lists(n);
for (const Wall& wall : maze.passages()) {
lists[wall.a].push_back(wall.b);
lists[wall.b].push_back(wall.a);
}
std::vector<char> seen(n, 0);
std::vector<int> stack{0};
seen[0] = 1;
int reached = 0;
while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
reached++;
for (int v : lists[u]) {
if (!seen[v]) {
seen[v] = 1;
stack.push_back(v);
}
}
}
assert(reached == n);
}
void generator_makes_a_tree() {
for (auto [width, height] : std::vector<std::pair<int, int>>{{1, 1}, {1, 8}, {8, 1}, {2, 2}, {7, 5}, {30, 20}}) {
for (unsigned seed = 1; seed <= 5; seed++) {
std::mt19937 rng(seed);
Maze maze(width, height);
generate_maze(maze, rng);
assert_connected_tree(maze);
}
}
}
void generator_opens_only_real_walls() {
std::mt19937 rng(3);
Maze maze(9, 6);
generate_maze(maze, rng);
std::set<std::pair<int, int>> walls;
for (const Wall& wall : maze.all_walls()) {
walls.insert({wall.a, wall.b});
}
std::set<std::pair<int, int>> opened;
for (const Wall& wall : maze.passages()) {
assert(walls.count({wall.a, wall.b}) == 1);
assert(opened.insert({wall.a, wall.b}).second);
}
}
void generator_depends_on_seed() {
std::set<std::string> drawings;
for (unsigned seed = 1; seed <= 8; seed++) {
std::mt19937 rng(seed);
Maze maze(10, 10);
generate_maze(maze, rng);
drawings.insert(maze.render());
}
assert(drawings.size() == 8);
// Misma semilla, mismo laberinto.
std::mt19937 first(5);
std::mt19937 second(5);
Maze a(10, 10);
Maze b(10, 10);
generate_maze(a, first);
generate_maze(b, second);
assert(a.render() == b.render());
}
// ---------- Paso 3: grafo y búsquedas ----------
void assert_valid_path(const Graph& graph, const std::vector<int>& path, int source, int target) {
assert(!path.empty());
assert(path.front() == source);
assert(path.back() == target);
for (std::size_t i = 0; i + 1 < path.size(); i++) {
assert(graph.has_edge(path[i], path[i + 1]));
}
std::set<int> distinct(path.begin(), path.end());
assert(distinct.size() == path.size());
}
void assert_visited_clean(const std::vector<int>& visited, int source) {
assert(!visited.empty());
assert(visited.front() == source);
std::set<int> distinct(visited.begin(), visited.end());
assert(distinct.size() == visited.size());
}
// Referencia: la distancia en aristas, bajando valores hasta que nada cambia.
std::vector<int> brute_distances(const Graph& graph, int source) {
int n = graph.node_count();
const int unreached = n + 1;
std::vector<int> distance(n, unreached);
distance[source] = 0;
bool changed = true;
while (changed) {
changed = false;
for (int u = 0; u < n; u++) {
for (const Edge& edge : graph.neighbors(u)) {
if (distance[u] != unreached && distance[u] + 1 < distance[edge.to]) {
distance[edge.to] = distance[u] + 1;
changed = true;
}
}
}
}
return distance;
}
Graph random_graph(int n, int edges, std::mt19937& rng) {
Graph graph(n);
std::set<std::pair<int, int>> seen;
for (int i = 0; i < edges; i++) {
int u = static_cast<int>(rng() % n);
int v = static_cast<int>(rng() % n);
if (u > v) {
std::swap(u, v);
}
if (u != v && seen.insert({u, v}).second) {
graph.add_edge(u, v);
}
}
return graph;
}
// El grafo de la clase: de 0 a 6 hay caminos de 4 y de 6 aristas.
Graph class_graph() {
Graph graph(7);
graph.add_edge(0, 1);
graph.add_edge(0, 2);
graph.add_edge(1, 3);
graph.add_edge(2, 3);
graph.add_edge(2, 4);
graph.add_edge(3, 5);
graph.add_edge(4, 5);
graph.add_edge(5, 6);
return graph;
}
void maze_graph_has_each_passage() {
std::mt19937 rng(2);
Maze maze(6, 4);
generate_maze(maze, rng);
open_extra_walls(maze, 3, rng);
Graph graph = maze_graph(maze);
assert(graph.node_count() == 24);
assert(graph.edge_count() == maze.passages().size());
assert(!graph.directed());
assert(graph.check_invariants());
for (const Wall& wall : maze.passages()) {
assert(graph.has_edge(wall.a, wall.b));
assert(graph.has_edge(wall.b, wall.a));
}
}
void maze_graph_keeps_passage_order() {
Maze maze(3, 1);
maze.open({1, 2});
maze.open({0, 1});
Graph graph = maze_graph(maze);
assert(graph.neighbors(1)[0].to == 2);
assert(graph.neighbors(1)[1].to == 0);
}
void bfs_small_case() {
Graph graph = class_graph();
SearchResult result = bfs_search(graph, 0, 6);
assert_valid_path(graph, result.path, 0, 6);
assert(result.path.size() == 5);
assert((result.visited == std::vector<int>{0, 1, 2, 3, 4, 5, 6}));
}
void bfs_stops_when_marking_target() {
Graph graph = class_graph();
SearchResult result = bfs_search(graph, 0, 3);
assert((result.path == std::vector<int>{0, 1, 3}));
assert((result.visited == std::vector<int>{0, 1, 2, 3}));
}
void bfs_source_is_target() {
Graph graph = class_graph();
SearchResult result = bfs_search(graph, 4, 4);
assert((result.path == std::vector<int>{4}));
assert((result.visited == std::vector<int>{4}));
}
void bfs_unreachable() {
Graph graph(5);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(3, 4);
SearchResult result = bfs_search(graph, 0, 4);
assert(result.path.empty());
assert((result.visited == std::vector<int>{0, 1, 2}));
}
void bfs_random_against_brute_force() {
std::mt19937 rng(14);
for (int round = 0; round < 60; round++) {
int n = 2 + static_cast<int>(rng() % 40);
Graph graph = random_graph(n, n + static_cast<int>(rng() % (2 * n)), rng);
int source = static_cast<int>(rng() % n);
std::vector<int> distance = brute_distances(graph, source);
for (int target = 0; target < n; target++) {
SearchResult result = bfs_search(graph, source, target);
assert_visited_clean(result.visited, source);
if (distance[target] == n + 1) {
assert(result.path.empty());
} else {
assert_valid_path(graph, result.path, source, target);
assert(static_cast<int>(result.path.size()) - 1 == distance[target]);
assert(result.visited.back() == target);
}
}
}
}
// Si se marca al sacar, un nodo entra muchas veces a la cola: aquí, una cantidad que se duplica con
// cada rombo. Esta prueba no terminaría, o se quedaría sin memoria.
void bfs_marks_when_pushing() {
const int diamonds = 40;
Graph graph(3 * diamonds + 1);
for (int i = 0; i < diamonds; i++) {
int top = 3 * i;
graph.add_edge(top, top + 1);
graph.add_edge(top, top + 2);
graph.add_edge(top + 1, top + 3);
graph.add_edge(top + 2, top + 3);
}
SearchResult result = bfs_search(graph, 0, 3 * diamonds);
assert(static_cast<int>(result.path.size()) == 2 * diamonds + 1);
assert_visited_clean(result.visited, 0);
assert(static_cast<int>(result.visited.size()) == 3 * diamonds + 1);
}
void dfs_small_case() {
Graph graph = class_graph();
SearchResult result = dfs_search(graph, 0, 6);
assert((result.path == std::vector<int>{0, 1, 3, 2, 4, 5, 6}));
assert((result.visited == std::vector<int>{0, 1, 3, 2, 4, 5, 6}));
}
// Retrocede de un callejón: 3 se visita, pero no está en el camino.
void dfs_path_skips_dead_ends() {
Graph graph(5);
graph.add_edge(0, 1);
graph.add_edge(1, 3);
graph.add_edge(1, 2);
graph.add_edge(2, 4);
SearchResult result = dfs_search(graph, 0, 4);
assert((result.path == std::vector<int>{0, 1, 2, 4}));
assert((result.visited == std::vector<int>{0, 1, 3, 2, 4}));
}
void dfs_source_is_target() {
Graph graph = class_graph();
SearchResult result = dfs_search(graph, 4, 4);
assert((result.path == std::vector<int>{4}));
assert((result.visited == std::vector<int>{4}));
}
void dfs_unreachable() {
Graph graph(5);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(3, 4);
SearchResult result = dfs_search(graph, 0, 4);
assert(result.path.empty());
assert((result.visited == std::vector<int>{0, 1, 2}));
}
void dfs_random_paths_are_valid() {
std::mt19937 rng(21);
for (int round = 0; round < 60; round++) {
int n = 2 + static_cast<int>(rng() % 40);
Graph graph = random_graph(n, n + static_cast<int>(rng() % (2 * n)), rng);
int source = static_cast<int>(rng() % n);
std::vector<int> distance = brute_distances(graph, source);
for (int target = 0; target < n; target++) {
SearchResult result = dfs_search(graph, source, target);
assert_visited_clean(result.visited, source);
if (distance[target] == n + 1) {
assert(result.path.empty());
} else {
assert_valid_path(graph, result.path, source, target);
assert(static_cast<int>(result.path.size()) - 1 >= distance[target]);
assert(result.visited.back() == target);
}
}
}
}
// Se corre con 128 KB de pila: una recursión de 6000 niveles no alcanza.
void dfs_long_corridor() {
const int n = 6000;
Graph graph(n);
for (int i = 0; i + 1 < n; i++) {
graph.add_edge(i, i + 1);
}
SearchResult result = dfs_search(graph, 0, n - 1);
assert(static_cast<int>(result.path.size()) == n);
assert(static_cast<int>(result.visited.size()) == n);
}
// ---------- Paso 3 y 4: juntos ----------
// Sin ciclos hay un solo camino: los dos recorridos deben dar exactamente el mismo.
void perfect_maze_gives_the_same_path() {
for (unsigned seed = 1; seed <= 20; seed++) {
std::mt19937 rng(seed);
Maze maze(20, 12);
generate_maze(maze, rng);
Graph graph = maze_graph(maze);
int target = maze.cell_count() - 1;
SearchResult by_bfs = bfs_search(graph, 0, target);
SearchResult by_dfs = dfs_search(graph, 0, target);
assert_valid_path(graph, by_bfs.path, 0, target);
assert(by_bfs.path == by_dfs.path);
}
}
// Con ciclos, BFS nunca pierde, y en esta muestra DFS da un camino más largo varias veces.
void cycles_separate_the_paths() {
int longer = 0;
for (unsigned seed = 1; seed <= 20; seed++) {
std::mt19937 rng(seed);
Maze maze(20, 12);
generate_maze(maze, rng);
open_extra_walls(maze, 40, rng);
Graph graph = maze_graph(maze);
int target = maze.cell_count() - 1;
SearchResult by_bfs = bfs_search(graph, 0, target);
SearchResult by_dfs = dfs_search(graph, 0, target);
assert_valid_path(graph, by_bfs.path, 0, target);
assert_valid_path(graph, by_dfs.path, 0, target);
assert(by_bfs.path.size() <= by_dfs.path.size());
longer += by_bfs.path.size() < by_dfs.path.size() ? 1 : 0;
}
assert(longer >= 10);
}
struct Case {
const char* name;
void (*run)();
};
const Case CASES[] = {
{"new_sets_are_separate", new_sets_are_separate},
{"unite_reports_and_counts", unite_reports_and_counts},
{"unite_uses_roots", unite_uses_roots},
{"rank_rises_only_on_ties", rank_rises_only_on_ties},
{"height_stays_logarithmic", height_stays_logarithmic},
{"compression_flattens_the_whole_path", compression_flattens_the_whole_path},
{"compression_leaves_other_branches", compression_leaves_other_branches},
{"compression_keeps_ranks", compression_keeps_ranks},
{"random_against_naive", random_against_naive},
{"generator_makes_a_tree", generator_makes_a_tree},
{"generator_opens_only_real_walls", generator_opens_only_real_walls},
{"generator_depends_on_seed", generator_depends_on_seed},
{"maze_graph_has_each_passage", maze_graph_has_each_passage},
{"maze_graph_keeps_passage_order", maze_graph_keeps_passage_order},
{"bfs_small_case", bfs_small_case},
{"bfs_stops_when_marking_target", bfs_stops_when_marking_target},
{"bfs_source_is_target", bfs_source_is_target},
{"bfs_unreachable", bfs_unreachable},
{"bfs_random_against_brute_force", bfs_random_against_brute_force},
{"bfs_marks_when_pushing", bfs_marks_when_pushing},
{"dfs_small_case", dfs_small_case},
{"dfs_path_skips_dead_ends", dfs_path_skips_dead_ends},
{"dfs_source_is_target", dfs_source_is_target},
{"dfs_unreachable", dfs_unreachable},
{"dfs_random_paths_are_valid", dfs_random_paths_are_valid},
{"dfs_long_corridor", dfs_long_corridor},
{"perfect_maze_gives_the_same_path", perfect_maze_gives_the_same_path},
{"cycles_separate_the_paths", cycles_separate_the_paths},
};
} // namespace
int main(int argc, char* argv[]) {
if (argc == 2) {
for (const Case& test : CASES) {
if (std::strcmp(test.name, argv[1]) == 0) {
test.run();
return 0;
}
}
}
std::cerr << "uso: lab_tests nombre\n";
return 2;
}// Genera un laberinto, lo resuelve con BFS y con DFS, y lo dibuja.
// Uso: maze ancho alto semilla [paredes_extra]
#include <cstdlib>
#include <iostream>
#include <random>
#include "maze.h"
#include "solver.h"
int main(int argc, char* argv[]) {
if (argc != 4 && argc != 5) {
std::cerr << "uso: maze ancho alto semilla [paredes_extra]\n";
return 1;
}
int width = std::atoi(argv[1]);
int height = std::atoi(argv[2]);
int extra = argc == 5 ? std::atoi(argv[4]) : 0;
if (width <= 0 || height <= 0 || extra < 0) {
std::cerr << "ancho y alto deben ser positivos, y paredes_extra no puede ser negativo\n";
return 1;
}
std::mt19937 rng(static_cast<std::mt19937::result_type>(std::atoi(argv[3])));
Maze maze(width, height);
generate_maze(maze, rng);
open_extra_walls(maze, extra, rng);
Graph graph = maze_graph(maze);
int source = 0;
int target = maze.cell_count() - 1;
SearchResult by_bfs = bfs_search(graph, source, target);
SearchResult by_dfs = dfs_search(graph, source, target);
std::cout << "BFS: camino de " << by_bfs.path.size() - 1 << " aristas, " << by_bfs.visited.size() << " nodos visitados\n";
std::cout << maze.render(by_bfs.path, by_bfs.visited);
std::cout << "DFS: camino de " << by_dfs.path.size() - 1 << " aristas, " << by_dfs.visited.size() << " nodos visitados\n";
std::cout << maze.render(by_dfs.path, by_dfs.visited);
return 0;
}Compilación
Cómo se compilan y ejecutan los ejemplos.
# Semana 14: grafos y union-find. 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-uf paso 1: UnionFind, contra la versión ingenua
# make test-maze paso 2: el generador
# make test-search paso 3: el grafo, BFS y DFS
# make test-lab prueba todo su laboratorio; falla hasta que lo terminen
# make compare paso 4: la tabla para su informe
# 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 = bfs_trace dfs_demo representations uf_demo uf_costs test_structures
BENCHES = map_tour online_connectivity bfs_scaling
COMMON_HEADERS = graph.h matrix_graph.h traversals.h sample_graphs.h map_file.h counting_forest.h bench.h
LAB_HEADERS = $(LAB_DIR)/union_find.h $(LAB_DIR)/maze.h $(LAB_DIR)/solver.h lab/graph.h lab/naive_union_find.h lab/not_implemented.h
.PHONY: all lab test test-uf test-maze test-search test-lab compare 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.
$(BUILD)/$(LAB_DIR)/lab_tests: lab/tests/lab_tests.cpp $(LAB_HEADERS) | $(BUILD)/$(LAB_DIR)
$(CXX) $(CXXFLAGS) -I$(LAB_DIR) -Ilab $< -o $@
$(BUILD)/$(LAB_DIR)/maze: lab/tests/maze_main.cpp $(LAB_HEADERS) | $(BUILD)/$(LAB_DIR)
$(CXX) $(CXXFLAGS) -I$(LAB_DIR) -Ilab $< -o $@
$(BUILD)/$(LAB_DIR)/compare_mazes: lab/tests/compare_mazes.cpp $(LAB_HEADERS) | $(BUILD)/$(LAB_DIR)
$(CXX) $(CXXFLAGS) -I$(LAB_DIR) -Ilab $< -o $@
$(BUILD) $(BUILD)/$(LAB_DIR):
mkdir -p $@
lab: $(BUILD)/$(LAB_DIR)/lab_tests $(BUILD)/$(LAB_DIR)/maze $(BUILD)/$(LAB_DIR)/compare_mazes
# 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; fi
DATA=$(DATA) python3 -m unittest discover -p 'test_*.py'
test-uf: lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestUnionFind
test-maze: lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestGenerator
test-search: lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab.TestSearch
test-lab: all lab
LAB_DIR=$(LAB_DIR) python3 -m unittest -v test_lab
compare: $(BUILD)/$(LAB_DIR)/compare_mazes
$<
clean:
rm -rf $(BUILD) __pycache__