Grafo com Matriz de Adjacência em Rust

/// Grafo usando matriz de adjacência.
/// Suporta grafos direcionados/não-direcionados e ponderados.
struct GrafoMatriz {
    /// Matriz de adjacência: None = sem aresta, Some(peso) = aresta com peso
    matriz: Vec<Vec<Option<i64>>>,
    /// Número de vértices
    num_vertices: usize,
    /// Se o grafo é direcionado
    direcionado: bool,
    /// Número de arestas
    num_arestas: usize,
}

impl GrafoMatriz {
    /// Cria um grafo vazio com n vértices
    fn novo(num_vertices: usize, direcionado: bool) -> Self {
        GrafoMatriz {
            matriz: vec![vec![None; num_vertices]; num_vertices],
            num_vertices,
            direcionado,
            num_arestas: 0,
        }
    }

    /// Adiciona uma aresta com peso entre os vértices u e v
    fn adicionar_aresta(&mut self, u: usize, v: usize, peso: i64) {
        assert!(u < self.num_vertices && v < self.num_vertices);

        self.matriz[u][v] = Some(peso);
        if !self.direcionado {
            self.matriz[v][u] = Some(peso);
        }
        self.num_arestas += 1;
    }

    /// Adiciona aresta sem peso (peso = 1)
    fn adicionar_aresta_simples(&mut self, u: usize, v: usize) {
        self.adicionar_aresta(u, v, 1);
    }

    /// Remove a aresta entre u e v
    fn remover_aresta(&mut self, u: usize, v: usize) {
        if self.matriz[u][v].is_some() {
            self.matriz[u][v] = None;
            if !self.direcionado {
                self.matriz[v][u] = None;
            }
            self.num_arestas -= 1;
        }
    }

    /// Verifica se existe aresta entre u e v — O(1)
    fn tem_aresta(&self, u: usize, v: usize) -> bool {
        self.matriz[u][v].is_some()
    }

    /// Retorna o peso da aresta entre u e v
    fn peso_aresta(&self, u: usize, v: usize) -> Option<i64> {
        self.matriz[u][v]
    }

    /// Retorna os vizinhos do vértice v
    fn vizinhos(&self, v: usize) -> Vec<usize> {
        (0..self.num_vertices)
            .filter(|&u| self.matriz[v][u].is_some())
            .collect()
    }

    /// Retorna vizinhos com pesos
    fn vizinhos_com_peso(&self, v: usize) -> Vec<(usize, i64)> {
        (0..self.num_vertices)
            .filter_map(|u| self.matriz[v][u].map(|peso| (u, peso)))
            .collect()
    }

    /// Grau do vértice (número de arestas incidentes)
    fn grau(&self, v: usize) -> usize {
        self.matriz[v].iter().filter(|x| x.is_some()).count()
    }

    /// Grau de entrada (para grafos direcionados)
    fn grau_entrada(&self, v: usize) -> usize {
        (0..self.num_vertices)
            .filter(|&u| self.matriz[u][v].is_some())
            .count()
    }

    /// Grau de saída (para grafos direcionados)
    fn grau_saida(&self, v: usize) -> usize {
        self.grau(v) // É o mesmo que percorrer a linha
    }

    /// Exibe a matriz
    fn exibir(&self) {
        let tipo = if self.direcionado { "Direcionado" } else { "Não-direcionado" };
        println!("Grafo {} ({} vértices, {} arestas):", tipo, self.num_vertices, self.num_arestas);

        // Cabeçalho
        print!("     ");
        for j in 0..self.num_vertices {
            print!("{:>5}", j);
        }
        println!();

        // Linhas da matriz
        for i in 0..self.num_vertices {
            print!("  {} [", i);
            for j in 0..self.num_vertices {
                match self.matriz[i][j] {
                    Some(peso) => print!("{:>5}", peso),
                    None => print!("    ."),
                }
            }
            println!("  ]");
        }
    }
}

/// Floyd-Warshall: encontra o menor caminho entre TODOS os pares de vértices.
/// Complexidade: O(V³)
fn floyd_warshall(grafo: &GrafoMatriz) -> Vec<Vec<i64>> {
    let n = grafo.num_vertices;
    let inf = i64::MAX / 2; // Evita overflow na soma

    // Inicializa a matriz de distâncias
    let mut dist = vec![vec![inf; n]; n];

    // Distância de cada vértice a si mesmo é 0
    for i in 0..n {
        dist[i][i] = 0;
    }

    // Copia as arestas do grafo
    for i in 0..n {
        for j in 0..n {
            if let Some(peso) = grafo.peso_aresta(i, j) {
                dist[i][j] = peso;
            }
        }
    }

    // Algoritmo principal: para cada vértice intermediário k
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                // Se passar por k é mais curto, atualiza
                if dist[i][k] + dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    dist
}

/// Exibe a matriz de distâncias de forma formatada
fn exibir_distancias(dist: &[Vec<i64>], nomes: &[&str]) {
    let n = nomes.len();
    let inf = i64::MAX / 2;

    print!("{:>12}", "");
    for nome in nomes {
        print!("{:>10}", nome);
    }
    println!();

    for i in 0..n {
        print!("{:>12}", nomes[i]);
        for j in 0..n {
            if dist[i][j] >= inf {
                print!("{:>10}", "∞");
            } else {
                print!("{:>10}", dist[i][j]);
            }
        }
        println!();
    }
}

impl GrafoMatriz {
    /// Verifica se o grafo é completo (todas as arestas possíveis existem)
    fn eh_completo(&self) -> bool {
        for i in 0..self.num_vertices {
            for j in 0..self.num_vertices {
                if i != j && self.matriz[i][j].is_none() {
                    return false;
                }
            }
        }
        true
    }

    /// Calcula a densidade do grafo (proporção de arestas existentes)
    fn densidade(&self) -> f64 {
        let max_arestas = if self.direcionado {
            self.num_vertices * (self.num_vertices - 1)
        } else {
            self.num_vertices * (self.num_vertices - 1) / 2
        };

        if max_arestas == 0 {
            return 0.0;
        }

        self.num_arestas as f64 / max_arestas as f64
    }

    /// Transposição do grafo (inverte direção das arestas)
    fn transpor(&self) -> GrafoMatriz {
        let mut transposto = GrafoMatriz::novo(self.num_vertices, self.direcionado);
        for i in 0..self.num_vertices {
            for j in 0..self.num_vertices {
                if let Some(peso) = self.matriz[i][j] {
                    transposto.matriz[j][i] = Some(peso);
                }
            }
        }
        transposto.num_arestas = self.num_arestas;
        transposto
    }
}

use std::collections::VecDeque;

/// Sistema de conexões aéreas entre cidades
struct MalhaAerea {
    grafo: GrafoMatriz,
    cidades: Vec<String>,
}

impl MalhaAerea {
    fn nova(cidades: Vec<&str>) -> Self {
        let n = cidades.len();
        MalhaAerea {
            grafo: GrafoMatriz::novo(n, false),
            cidades: cidades.into_iter().map(String::from).collect(),
        }
    }

    /// Encontra o índice de uma cidade pelo nome
    fn indice_cidade(&self, nome: &str) -> Option<usize> {
        self.cidades.iter().position(|c| c == nome)
    }

    /// Adiciona um voo entre duas cidades com o custo em reais
    fn adicionar_voo(&mut self, de: &str, para: &str, custo: i64) {
        if let (Some(i), Some(j)) = (self.indice_cidade(de), self.indice_cidade(para)) {
            self.grafo.adicionar_aresta(i, j, custo);
        }
    }

    /// Encontra o voo mais barato entre duas cidades (Floyd-Warshall)
    fn menor_custo(&self, de: &str, para: &str) -> Option<i64> {
        let dist = floyd_warshall(&self.grafo);
        let inf = i64::MAX / 2;

        if let (Some(i), Some(j)) = (self.indice_cidade(de), self.indice_cidade(para)) {
            if dist[i][j] < inf {
                Some(dist[i][j])
            } else {
                None
            }
        } else {
            None
        }
    }

    /// Lista todos os destinos diretos de uma cidade
    fn destinos_diretos(&self, cidade: &str) -> Vec<(String, i64)> {
        match self.indice_cidade(cidade) {
            Some(idx) => {
                self.grafo
                    .vizinhos_com_peso(idx)
                    .into_iter()
                    .map(|(v, peso)| (self.cidades[v].clone(), peso))
                    .collect()
            }
            None => vec![],
        }
    }

    /// Encontra a cidade mais conectada (hub principal)
    fn hub_principal(&self) -> (&str, usize) {
        let mut melhor_idx = 0;
        let mut melhor_grau = 0;

        for i in 0..self.cidades.len() {
            let grau = self.grafo.grau(i);
            if grau > melhor_grau {
                melhor_grau = grau;
                melhor_idx = i;
            }
        }

        (&self.cidades[melhor_idx], melhor_grau)
    }

    /// Encontra menor número de conexões (escalas) entre duas cidades
    fn menor_escalas(&self, de: &str, para: &str) -> Option<usize> {
        let (idx_de, idx_para) = match (self.indice_cidade(de), self.indice_cidade(para)) {
            (Some(a), Some(b)) => (a, b),
            _ => return None,
        };

        // BFS para encontrar menor número de arestas
        let n = self.cidades.len();
        let mut dist = vec![usize::MAX; n];
        let mut fila = VecDeque::new();

        dist[idx_de] = 0;
        fila.push_back(idx_de);

        while let Some(atual) = fila.pop_front() {
            if atual == idx_para {
                return Some(dist[atual]);
            }
            for vizinho in self.grafo.vizinhos(atual) {
                if dist[vizinho] == usize::MAX {
                    dist[vizinho] = dist[atual] + 1;
                    fila.push_back(vizinho);
                }
            }
        }

        None
    }

    /// Exibe a tabela completa de distâncias
    fn tabela_custos(&self) {
        let dist = floyd_warshall(&self.grafo);
        let nomes: Vec<&str> = self.cidades.iter().map(|s| s.as_str()).collect();
        println!("\n=== Tabela de Menores Custos (R$) ===");
        exibir_distancias(&dist, &nomes);
    }

    /// Exibe informações da malha aérea
    fn exibir_info(&self) {
        println!("╔═══════════════════════════════════════════╗");
        println!("║         Malha Aérea Brasileira            ║");
        println!("╠═══════════════════════════════════════════╣");
        println!("║ Cidades: {}                               ", self.cidades.len());
        println!("║ Rotas:   {}                               ", self.grafo.num_arestas);
        println!("║ Densidade: {:.1}%                         ", self.grafo.densidade() * 100.0);

        let (hub, grau) = self.hub_principal();
        println!("║ Hub principal: {} ({} conexões)           ", hub, grau);
        println!("╚═══════════════════════════════════════════╝");
    }
}

fn main() {
    let cidades = vec![
        "São Paulo", "Rio de Janeiro", "Brasília",
        "Salvador", "Manaus", "Porto Alegre",
    ];

    let mut malha = MalhaAerea::nova(cidades);

    // Adicionando voos com custos em reais
    malha.adicionar_voo("São Paulo", "Rio de Janeiro", 350);
    malha.adicionar_voo("São Paulo", "Brasília", 500);
    malha.adicionar_voo("São Paulo", "Porto Alegre", 450);
    malha.adicionar_voo("São Paulo", "Salvador", 600);
    malha.adicionar_voo("Rio de Janeiro", "Salvador", 550);
    malha.adicionar_voo("Brasília", "Manaus", 800);
    malha.adicionar_voo("Brasília", "Salvador", 400);
    malha.adicionar_voo("Salvador", "Manaus", 900);

    malha.exibir_info();

    // Destinos diretos
    println!("\nDestinos diretos de São Paulo:");
    for (cidade, custo) in malha.destinos_diretos("São Paulo") {
        println!("  -> {} (R$ {})", cidade, custo);
    }

    // Menor custo
    println!("\nMenor custo Porto Alegre -> Manaus:");
    match malha.menor_custo("Porto Alegre", "Manaus") {
        Some(custo) => println!("  R$ {} (possivelmente com conexões)", custo),
        None => println!("  Sem rota disponível"),
    }

    // Escalas
    println!("\nMenor número de escalas Porto Alegre -> Manaus:");
    match malha.menor_escalas("Porto Alegre", "Manaus") {
        Some(n) => println!("  {} voo(s) / {} escala(s)", n, n.saturating_sub(1)),
        None => println!("  Sem rota disponível"),
    }

    // Tabela completa
    malha.tabela_custos();

    // Exibe a matriz
    println!("\n=== Matriz de Adjacência ===");
    malha.grafo.exibir();
}

fn tem_ciclo_negativo(grafo: &GrafoMatriz) -> bool {
    // Dica: execute Floyd-Warshall e verifique a diagonal
    todo!()
}

fn floyd_warshall_com_caminho(grafo: &GrafoMatriz) -> (Vec<Vec<i64>>, Vec<Vec<Option<usize>>>) {
    // Retorna (dist, next) onde next[i][j] é o próximo vértice no caminho i->j
    todo!()
}

fn reconstruir_caminho(next: &[Vec<Option<usize>>], de: usize, para: usize) -> Vec<usize> {
    todo!()
}

fn eh_fortemente_conectado(grafo: &GrafoMatriz) -> bool {
    // Dica: após Floyd-Warshall, verifique se dist[i][j] < ∞ para todo i, j
    todo!()
}