Skip to content

Home

Jump to bottom
Laura edited this page Nov 27, 2018 · 18 revisions

A ser feito até 04/12:

  • Olhar memory leaks com valgrind
  • Mergear branch for_kruskal
  • Fazer main.cpp para o usuário poder usar a biblioteca
  • Fazer a documentação de como usar a biblioteca

Divisão de tarefas:

  • Documentação - Laura
  • Grafo dirigido: - Caio
  • Grafo nao dirigido - Pedro, Laura e Henrique
  • Arvore: - Henrique
  • DAG - Henrique
  • Testes:
    • DAG - Pedro
    • Grafo Dirigido - Caio e Henrique
    • Grafo Nao Dirigido - Pedro e Laura
    • Arvore - Henrique

Foram criados testes para os seguintes arquivos src:

  • dag.cpp
  • directed_graph.cpp
  • edges.cpp
  • exceptions.cpp
  • interface_base.cpp
  • interface_directed.cpp
  • interface_undirected.cpp
  • tree.cpp
  • undirected_graph.cpp

Sobre o trabalho:

  • Criar nomes de variáveis mais acessíveis;
  • Traduzir o código para inglês;
  • Criar um Makefile;
  • Criar uma lista de propriedades a serem implementadas;
  • Subdividir o trabalho;
  • Geração de grafos randomicos;
  • Implementar a função ajuda;
  • Criar a classe Grafo Não-Direcionado;
  • Criar a classe Árvore;
  • Decidir sobre o armazenamento de resultados de queries;
  • Estudar sobre testes;
  • Documentação.

Grafos - Classe Base:

  • Construtor e destrutor de classe;
  • Gets e setters básicos;
  • Verifica grau do vértice;
  • Verifica a ordem do grafo;
  • Verifica o tamanho do grafo;
  • Verifica se é um grafo completo;
  • Verifica se é um grafo regular;
  • Verifica se é um grafo bipartido;
  • Encontra o menor caminha entre dois vértices;
    • Implementar o Dijkstra;
    • Implementar o Bellman Ford;
  • Verifica se um grafo é um tour euleriano;
  • Verifica se um grafo é subgrafo do outro.

Grafos Dirigidos - Subclasse:

  • Construtor e destrutor da classe;
  • Gets e setters básicos;
  • Verificadores do grau de entrada e saída de um vértice;
  • Verica se o grafo é conexo;
    • Implementar a DFS;
    • Implementar o Kosaraju ou Tarjan;
    • Retornar um novo grafo usando os componentes conexos como vértices -- Sempre uma DAG, interessante para ordenação topológica;
  • Verifica se possui algum ciclo;
  • Retornar sua Ordenação Topológica, se existir;
  • Get do componente conexo ao qual o vértices pertence;
  • Retornar o grafo não-dirigido referente ao grafo original;
  • Verifica se o grafo é reflexivo;
  • Verifica se o grafo é irreflexivo;
  • Verifica se o grafo é simétrico;
  • Verifica se o grafo é assimétrico;
  • Verifica se o grafo é anti-simétrico;
  • Verifica se o grafo é transitivo;

Grafos Não-Dirigidos - Subclasse:

  • Construtor e destrutor da classe;
  • Gets e setters básicos;
  • Verifica se o grafo é conexo;
  • Verifica se possui algum ciclo;
  • Retornar a MSP;
    • Implementar Union-Find;
    • Implementar Kruskal;
  • Verifica se é árvore;
  • Trazer a função de grafo euleriano pra este módulo;
  • Verifica se o grafo é Euleriano;
  • Verifica se o grafo é Bipartido.

Árvore - Subsubclasse:

  • Vamos fazer.

DAG - Subsubclasse

  • Vamos fazer.

Referências:

Clone this wiki locally