Terceiro projeto da matéria de Teoria e Aplicação de Grafos (TAG) do semestre de 2017/1. O sistema irá resolver o "famoso" problema de emparelhamento estável.
Como orientação foi proposto a leitura do artigo (Abraham, Irving & Manlove, 2007) para seguir o problema de alocação de estudante-projeto, porém, aplicado para professor-escola.
Para executar este programa basta executar os seguintes comandos no terminal:
$ bash run_all.sh
Este comando acima compila o programa utilizando o Makefile e já o executa em seguida. Caso queira só executar o programa sem necessariamente compilar novamente, executar o seguinte comando:
$ ./main
Este programa foi testado no sistema operacional macOS Sierra
, versão 10.12
. A linguagem de programação utilizada para implementar todo o projeto foi C++11
.
Este programa utiliza o arquivo cod_hab.txt
e cod-hab_schools.txt
para criar um grafo de professores que gostariam de trabalhar em certas escolas, e o requerimento de cada escola em relação a professores que gostariam de contratar . É gerado um estrutura abstrata de grafo bidirecionado e bipartido para representar ambos os professores e as escolas. Ao total são 50 escolas que querem contratar até 2 professores e 100 professores, que tem preferência de 5 escolas.
Cada professor pode ter de 1 a 3 habilitações de conteúdos, e cada escola pode preferir contratar professores que contenham habilitações de 1, 2 ou 3. Este sistema é ótimo no ponto de vista do professor, ou seja, nenhum professor é alocado fora de uma escola que ele não tenha desejo de trabalhar.
O programa realiza as seguintes funcionalidades a partir do menu principal:
-
Opção 1 : Mostra o emparelhamento estável entre os grupos de professores e escolas, com base nas preferências dos professores.
-
Opção 2 : Mostra o Grafo Completo
-
Opção 3 : Mostra uma tela de ajuda, relatando informações básicas sobre o programa.
-
Opção 4 : Permite sair do programa.
- Recebe dois arquivos de texto,
cod-hab.txt
que contém informações das escolas e suas preferencias,cod-hab_schools.txt
contendo informações dos professores e suas preferencias de escolas; - Cria-se um vértice, contendo os seguintes elementos:
- Entidade (professor, ou escola),
- Código,
- Numero de habilitações,
- Preferencias;
- Faz o devido tratamento dos códigos dos vértices para inserção no grafo;
- Cria-se as listas de preferências com os códigos atualizados;
- Realiza o emparelhamento estável ótimo para os professores;
- Mostra a interface do usuário no terminal;
- Espera receber alguma ação do usuário;
- Executa a ação requisitada e volta para o menu inicial até que o usuário não queira mais utilizar o sistema (pressionando o número 4 do teclado na tela principal para sair do programa).
-
Dayanne Fernandes da Cunha
- Matrícula: 13/0107191
- E-mail: [email protected]
- GitHub: Dayof
-
Renato Avellar Nobre
- Matrícula: 15/0146698
- E-mail: [email protected]
- GitHub: Skalwalker