Implementação de Agenda de Contatos com Árvore B em C ou Golang

Página 1 Este trabalho deve ser implementado em linguagem C ou Golang em plataforma LinuxUnix Problema 1 Implementação de uma Agenda de Contatos indexada por ÁrvoreB 15 pts Deverá ser implementado um aplicativo de agenda de contatos que seja capaz de gerenciar os contatos armazenados em arquivo de dados indexado por uma árvore B permitindo as seguintes operações 1 Inclusão de novo contato deve solicitar as informações sobre o novo contato e realizar a operação de inserção do novo contato no arquivo de dados e atualizando também o arquivo de índice que contém a árvore B 2 Alteração dos dados de um contato Deve permitir que os contatos tenham suas informações alteradas Se ocorrerem alterações na chave de busca estas devem se refletir também na árvore B e em seu respectivo arquivo de índice 3 Listar contatos Deve Produzir uma listagem dos dados armazenados de forma ordenada sendo a ordenação realizada apenas pelo percurso em ordem na árvore B recuperandose os registros de contatos na ordem em que estes aparecem no percurso O arquivo de dados não precisa ser ordenado 4 Enviar para lixeira Exclusão Lógica Esta operação deve marcar o contato selecionado para exclusão lógica sem no entanto removêlo fisicamente 5 Retirar da Lixeira Desmarca os contatos excluídos logicamente recuperando suas informações 6 Esvaziar Lixeira Elimina fisicamente os registros de contatos marcados como apagados Descrição dos campos de dados a serem armazenados no arquivo de dados Nome Uma string com no máximo 30 caracteres Chave de busca Endereço Uma string com no máximo 50 caracteres Telefone Uma string com no máximo 15 caracteres Apagado Um booleano que indica se o registro está ou não apagado Na lixeira 3 Descrição dos campos de dados no arquivo de índice chave Nome posição posição dentro do arquivo onde o registro correspondente se encontra 4 Indexação Quando o programa inicia o arquivo de índice deve ser lido para a memória e deve ser montada a árvore B Qualquer operação deverá primeiro localizar o registro na árvore B e então de posse da posição do registro desejado dentro do arquivo devese realizar a operação desejada Se for uma inclusão esta será feita sempre ao final do arquivo de dados Alterações serão feitas sempre na posição indicada pelo índice na árvore B Remoções lógicas apenas marcam o registro como apagado Remoções físicas implicam a reconstrução do índice inteiro Alterações de chaves nomes implicam a reconstrução da arvore B em memória Quando houver mudança nos índices esta deverá ser refletida no arquivo de índices Página 2 Problema 2 Implementação de um sistema de manipulação e visualização de Grafos 15 pts Deverá ser implementado um sistema de manipulação e visualização de grafos orientado por menus que realize as seguintes operações sobre grafos AbrirSalvar grafo deve permitir abrirsalvar um arquivo texto com as informações referentes ao grafo e a partir destas informações montar o grafo em memória 1 pts Inserir vértice Deve realizar a inserção de um novo vértice no grafo 1 pts Inserir Aresta Deve realizar a inserção de uma aresta no grafo entre vértices já existentes 1 pts Remover vértice Deve realizar a remoção de um vértice removendo também todas as arestas conectadas a ele 1 pts Remover aresta Deve remover uma aresta do grafo sem no entanto remover qualquer vértice ligado a mesma 1 pts Goodman Componentes Conexos deve calcular o número de componentes conexos do grafo e exibindo esta informação 1 pts Grafo Euleriano Verificar se um grafo é Euleriano ou não e exibir esta informação 1 pts Fleury Ciclo Euleriano Se o grafo for Euleriano encontrar o ciclo euleriano utilizando o Algoritmo de Fleury a partir de um nó informado 2 pts Busca em Profundidade Deve realizar uma busca em profundidade no grafo e imprimir o trajeto encontrado sequência de arestas percorridas a partir de um nó informado 2 pts Página 3 Busca em Largura Deve realizar uma busca em largura no grafo e imprimir o trajeto encontrado sequência de arestas percorridas a partir de um nó informado 2 pts Dijkstra Caminho de custo mínimo Deve realizar o cálculo do caminho de menor custo entre um vértice de origem e um vértice de destino informado exibindo a trajetória calculada 2 pts Poderá ser utilizada qualquer forma de representação para os vértices e arestas Os vértices deverão ter as seguintes informações associadas a Coordenadas x y posição espacial do vértice na tela b Rótulo uma string que identifica o vértice As arestas deverão ter as seguintes informações associadas a rótulo uma string que identifica a aresta b custo representa o custo de se percorrer a aresta p ex distância em Km OBS Após a realização de cada operação o sistema deverá imprimir a lista de arestas do grafo resultante atual include iostream include fstream include vector include queue include stack include algorithm include limits using namespace std struct Edge int from int to string label int cost struct Vertex int x int y string label vectorEdge edges class Graph public Graph void loadFromFilestring filename ifstream filefilename if fileisopen cout Não foi possível abrir o arquivo endl return verticesclear int n file n for int i 0 i n i Vertex v file vx vy vlabel verticespushbackv int m file m for int i 0 i m i Edge e file efrom eto elabel ecost verticesefromedgespushbacke verticesetoedgespushbacketo efrom elabel ecost fileclose void openAndSaveGraphstring filename loadFromFilefilename saveToFilefilename cout Grafo aberto e salvo com sucesso endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl void saveToFilestring filename ofstream filefilename if fileisopen cout Não foi possível abrir o arquivo endl return file verticessize endl for Vertex v vertices file vx vy vlabel endl int m 0 for Vertex v vertices m vedgessize m 2 file m endl for Vertex v vertices for Edge e vedges if efrom eto file efrom eto elabel ecost endl fileclose void insertVertexint x int y string label Vertex v x y label verticespushbackv cout Vértice inserido com sucesso endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl void insertEdgeint from int to string label int cost Edge e from to label cost verticesfromedgespushbacke verticestoedgespushbackto from label cost cout Aresta inserida com sucesso endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl void removeVertexint index for Edge e verticesindexedges for int i 0 i verticesetoedgessize i if verticesetoedgesito index verticesetoedgeseraseverticesetoedgesbegin i break verticeseraseverticesbegin index for Vertex v vertices for Edge e vedges if efrom index efrom if eto index eto cout Vértice removido com sucesso endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl void removeEdgeint from int to for int i 0 i verticesfromedgessize i if verticesfromedgesito to verticesfromedgeseraseverticesfromedgesbegin i break for int i 0 i verticestoedgessize i if verticestoedgesito from verticestoedgeseraseverticestoedgesbegin i break cout Aresta removida com sucesso endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl int countConnectedComponents vectorbool visitedverticessize false int count 0 for int i 0 i verticessize i if visitedi count dfsi visited cout Número de componentes conectados count endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl return count bool isEulerian vectorbool visitedverticessize false dfs0 visited for int i 0 i verticessize i if visitedi cout O grafo não é euleriano endl return false for Vertex v vertices if vedgessize 2 1 cout O grafo não é euleriano endl return false cout O grafo é euleriano endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl return true vectorint findEulerianCycleint start vectorint cycle stackint st vectorvectorEdge edgesverticessize for int i 0 i verticessize i edgesi verticesiedges stpushstart while stempty int v sttop if edgesvempty cyclepushbackv stpop else Edge e edgesvback edgesvpopback for int i 0 i edgesetosize i if edgesetoito v edgesetoeraseedgesetobegin i break stpusheto reversecyclebegin cycleend cout O ciclo euleriano é for int v cycle cout v cout endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl return cycle void depthFirstSearchint start vectorbool visitedverticessize false dfsstart visited cout endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl void breadthFirstSearchint start vectorbool visitedverticessize false queueint q visitedstart true qpushstart while qempty int v qfront qpop cout v for Edge e verticesvedges if visitedeto visitedeto true qpusheto cout endl cout Lista de arestas do grafo atualizado endl for Vertex v vertices for Edge e vedges if efrom eto cout efrom eto elabel ecost endl void dijkstraint start int end vectorint distverticessize numericlimitsintmax vectorint prevverticessize 1 priorityqueuepairint int vectorpairint int greaterpairint int pq diststart 0 pqpush0 start while pqempty int v pqtopsecond pqpop for Edge e verticesvedges if disteto distv ecost disteto distv ecost preveto v pqpushdisteto eto if distend numericlimitsintmax cout Não existe caminho entre os vértices start e end endl return vectorint path for int v end v 1 v prevv pathpushbackv reversepathbegin pathend cout Caminho de menor custo entre os vértices start e end for int v path coutv coutendl coutLista de arestas do grafo atualizadoendl forVertexvvertices forEdgeevedges ifefrometo coutefrom eto elabel ecostendl private vectorVertex vertices void dfsint v vectorbool visited visitedv true for Edge e verticesvedges if visitedeto dfseto visited int main Graph g while true cout endl cout 1 AbrirSalvar grafo endl cout 2 Inserir vértice endl cout 3 Inserir aresta endl cout 4 Remover vértice endl cout 5 Remover aresta endl cout 6 Calcular componentes conexos endl cout 7 Verificar se é Euleriano endl cout 8 Encontrar ciclo Euleriano endl cout 9 Busca em profundidade endl cout 10 Busca em largura endl cout 11 Caminho de menor custo Dijkstra endl cout 0 Sair endl int op cin op if op 0 break if op 1 string filename cout Insira o nome do arquivo cin filename gopenAndSaveGraphfilename else if op 2 int x y string label cout Insira a coordenada x do vértice cin x cout Insira a coordenada y do vértice cin y cout Insira o rótulo do vértice cin label ginsertVertexx y label else if op 3 int from to cost string label cout Insira o índice do vértice de origem cin from cout Insira o índice do vértice de destino cin to cout Insira o rótulo da aresta cin label cout Insira o custo da aresta cin cost ginsertEdgefrom to label cost else if op 4 int index cout Insira o índice do vértice a ser removido cin index gremoveVertexindex else if op 5 int from to cout Insira o índice do vértice de origem da aresta a ser removida cin from cout Insira o índice do vértice de destino da aresta a ser removida cin to gremoveEdgefrom to else if op 6 gcountConnectedComponents else if op 7 gisEulerian else if op 8 int start coutInsira o índice do vértice inicial cinstart vectorint cycle gfindEulerianCyclestart forint v cycle coutv coutendl else ifop9 int start coutInsira o índice do vértice inicial cinstart gdepthFirstSearchstart coutendl else ifop10 int start coutInsira o índice do vértice inicial cinstart gbreadthFirstSearchstart coutendl else ifop11 int start end coutInsira o índice do vértice inicial cinstart coutInsira o índice do vértice final cinend gdijkstrastartend return 0 include iostream include fstream include string include vector include algorithm struct Contato stdstring nome stdstring endereco stdstring telefone bool apagado class BinarySearchTree private struct Node Contato contato Node left Node right Nodeconst Contato contato contatocontato leftnullptr rightnullptr Node root void destroyTreeNode node if node destroyTreenodeleft destroyTreenoderight delete node void insertNode node const Contato contato if node node new Nodecontato return if contatonome nodecontatonome insertnodeleft contato else if contatonome nodecontatonome insertnoderight contato Node findNode node const stdstring nome const if node nodecontatonome nome return node if nome nodecontatonome return findnodeleft nome else return findnoderight nome Node findParentNode node const stdstring nome const if node nodeleft nodeleftcontatonome nome noderight noderightcontatonome nome return node if nome nodecontatonome return findParentnodeleft nome else return findParentnoderight nome void removeNode node const stdstring nome Node toRemove findnode nome if toRemove return Node parent findParentnode nome if toRemoveleft toRemoveright if parent Removing root when there are no children node nullptr else if parentleft toRemove parentleft nullptr else parentright nullptr delete toRemove else if toRemoveleft toRemoveright Node child toRemoveleft toRemoveleft toRemoveright if parent Removing root when there is one child node child else if parentleft toRemove parentleft child else parentright child delete toRemove else Node successor findSuccessortoRemoveright toRemovecontato successorcontato removetoRemoveright successorcontatonome Node findSuccessorNode node const while nodeleft node nodeleft return node void inOrderTraversalNode node stdvectorContato result const if node inOrderTraversalnodeleft result resultpushbacknodecontato inOrderTraversalnoderight result public BinarySearchTree rootnullptr BinarySearchTree destroyTreeroot void insertconst Contato contato insertroot contato Contato findconst stdstring nome const Node node findroot nome return node nodecontato nullptr void removeconst stdstring nome removeroot nome void inOrderTraversalstdvectorContato result const inOrderTraversalroot result class Agenda public Agendaconst stdstring arqDados const stdstring arqIndice arqDadosarqDados arqIndicearqIndice carregarDados void incluirContatoconst Contato contato arvoreinsertcontato salvarDados void alterarContatoconst stdstring nome const Contato novoContato Contato contato arvorefindnome if contato contato novoContato salvarDados void listarContatos const stdvectorContato contatos arvoreinOrderTraversalcontatos for const auto contato contatos stdcout contatonome contatoendereco contatotelefone if contatoapagado stdcout Contato na lixeira stdcout void enviarParaLixeiraconst stdstring nome Contato contato arvorefindnome if contato contatoapagado true salvarDados void retirarDaLixeiraconst stdstring nome Contato contato arvorefindnome if contato contatoapagado false salvarDados void esvaziarLixeira stdvectorContato contatos arvoreinOrderTraversalcontatos for const auto contato contatos if contatoapagado arvoreremovecontatonome salvarDados private BinarySearchTree arvore stdstring arqDados stdstring arqIndice void carregarDados stdifstream arqarqDados if arqisopen while arqeof Contato contato getlinearq contatonome getlinearq contatoendereco getlinearq contatotelefone arq contatoapagado arqignore if arqeof arvoreinsertcontato arqclose void salvarDados const stdofstream arqarqDados stdvectorContato contatos arvoreinOrderTraversalcontatos for const auto contato contatos arq contatonome arq contatoendereco arq contatotelefone arq contatoapagado arqclose int main Agenda agendadadostxt indicetxt while true stdcout Escolha uma opção stdcout 1 Incluir novo contato stdcout 2 Alterar dados de um contato stdcout 3 Listar contatos stdcout 4 Enviar para lixeira stdcout 5 Retirar da lixeira stdcout 6 Esvaziar lixeira stdcout 0 Sair int opcao stdcin opcao switch opcao case 1 Contato contato stdcout Nome stdcinignore getlinestdcin contatonome stdcout Endereço getlinestdcin contatoendereco stdcout Telefone getlinestdcin contatotelefone contatoapagado false agendaincluirContatocontato break case 2 stdstring nome stdcout Nome do contato a ser alterado stdcinignore getlinestdcin nome Contato novoContato stdcout Novo nome getlinestdcin novoContatonome stdcout Novo endereço getlinestdcin novoContatoendereco stdcout Novo telefone getlinestdcin novoContatotelefone novoContatoapagado false agendaalterarContatonome novoContato break case 3 agendalistarContatos break case 4 stdstring nome stdcout Nome do contato a ser enviado para a lixeira stdcinignore getlinestdcin nome agendaenviarParaLixeiranome break case 5 stdstring nome stdcout Nome do contato a ser retirado da lixeira stdcinignore getlinestdcin nome agendaretirarDaLixeiranome break case 6 agendaesvaziarLixeira break case 0 return 0 default stdcout Opção inválida