Last active
January 20, 2026 03:41
-
-
Save felipebastosweb/d2ab21ef0245899f5ecdbfe732e7fb52 to your computer and use it in GitHub Desktop.
exemplo completo em C# utilizando DFS (Busca em Profundidade) para detecção de ciclos na normalização do banco de dados
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Collections.Generic; | |
| using System.Linq; | |
| public class EntityNode | |
| { | |
| public string Name { get; set; } | |
| public List<string> Dependencies { get; set; } = new List<string>(); | |
| public EntityNode(string name) | |
| { | |
| Name = name; | |
| } | |
| } | |
| public class SchemaNormalizer | |
| { | |
| private Dictionary<string, EntityNode> _graph = new Dictionary<string, EntityNode>(); | |
| // Adiciona ou atualiza uma entidade | |
| public void AddEntity(string entityName, List<string> dependencies) | |
| { | |
| if (!_graph.ContainsKey(entityName)) | |
| { | |
| _graph[entityName] = new EntityNode(entityName); | |
| } | |
| _graph[entityName].Dependencies = dependencies; | |
| } | |
| // Verifica se a estrutura atual tem ciclos | |
| public bool HasCycle() | |
| { | |
| var visited = new HashSet<string>(); | |
| var recStack = new HashSet<string>(); | |
| foreach (var node in _graph.Keys) | |
| { | |
| if (CheckCycle(node, visited, recStack)) | |
| return true; | |
| } | |
| return false; | |
| } | |
| private bool CheckCycle(string node, HashSet<string> visited, HashSet<string> recStack) | |
| { | |
| if (recStack.Contains(node)) return true; // Ciclo detectado | |
| if (visited.Contains(node)) return false; | |
| visited.Add(node); | |
| recStack.Add(node); | |
| if (_graph.ContainsKey(node)) | |
| { | |
| foreach (var dep in _graph[node].Dependencies) | |
| { | |
| if (CheckCycle(dep, visited, recStack)) | |
| return true; | |
| } | |
| } | |
| recStack.Remove(node); | |
| return false; | |
| } | |
| // Normaliza: Adiciona dependência apenas se não gerar ciclo | |
| public bool TryNormalize(string parent, string child) | |
| { | |
| var originalDeps = new List<string>(_graph.ContainsKey(parent) ? _graph[parent].Dependencies : new List<string>()); | |
| // Simula a adição | |
| if (!_graph.ContainsKey(parent)) _graph[parent] = new EntityNode(parent); | |
| _graph[parent].Dependencies.Add(child); | |
| if (HasCycle()) | |
| { | |
| Console.WriteLine($"ERRO: A relação {parent} -> {child} gera ciclo. Normalização cancelada."); | |
| _graph[parent].Dependencies = originalDeps; // Rollback | |
| return false; | |
| } | |
| Console.WriteLine($"Sucesso: {parent} agora depende de {child}."); | |
| return true; | |
| } | |
| } | |
| // Exemplo de uso | |
| public class Program | |
| { | |
| public static void Main() | |
| { | |
| SchemaNormalizer sn = new SchemaNormalizer(); | |
| // Cenário: Pedido depende de Cliente, Cliente depende de Cidade | |
| sn.AddEntity("Empresa", []); | |
| sn.AddEntity("AnoLetivo", ["Empresa"]); | |
| sn.AddEntity("Segmento", ["AnoLetivo"]); | |
| sn.AddEntity("Serie", ["Segmento"]); | |
| sn.AddEntity("Disciplina", ["Segmento"]); | |
| sn.AddEntity("Turma", ["Serie"]); | |
| sn.AddEntity("Aluno", []); | |
| sn.AddEntity("Matricula", ["Turma", "Aluno"]); | |
| sn.AddEntity("Filiacao", ["Aluno"]); | |
| sn.AddEntity("Departamento", ["Empresa"]); | |
| sn.AddEntity("Cargo", ["Empresa"]); | |
| sn.AddEntity("Fabricante", []); | |
| sn.AddEntity("Categoria", []); | |
| sn.AddEntity("Produto", ["Fabricante", "Categoria"]); | |
| sn.AddEntity("Opcao", []); | |
| sn.AddEntity("OpcaoValor", ["Opcao", "Produto"]); | |
| sn.AddEntity("Funcionario", ["Departamento", "Cargo"]); | |
| sn.AddEntity("Professor", ["Funcionario"]); | |
| // Turma e Disciplina que Professor Leciona | |
| sn.AddEntity("ProfessorTurmaDisciplina", ["Professor", "Turma", "Disciplina"]); | |
| //sn.AddEntity("EmpresaProduto", ["Empresa", "Produto"]); | |
| sn.AddEntity("Compra", ["Fornecedor", "Empresa"]); | |
| sn.AddEntity("CompraItem", ["Compra", "Produto", "OpcaoValor"]); | |
| sn.AddEntity("Venda", ["Empresa", "Cliente"]); | |
| sn.AddEntity("VendaItem", ["Venda", "CompraItem"]); | |
| Console.WriteLine("Grafo atual tem ciclo? " + sn.HasCycle()); // False | |
| // Tentativa de criar um ciclo: Cidade depende de Pedido | |
| //sn.TryNormalize("Cidade", "Pedido"); // Erro detectado | |
| // Adição segura: Pedido depende de Funcionario | |
| //sn.TryNormalize("Pedido", "Funcionario"); // Sucesso | |
| } | |
| } | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment