Skip to content

Instantly share code, notes, and snippets.

@douglasb78

douglasb78/metodo_pert_cpm.c

Last active July 3, 2024 06:30
Show Gist options
  • Save douglasb78/d1e411d7a1ff9a0a8c25f7cdbe4291ba to your computer and use it in GitHub Desktop.
Save douglasb78/d1e411d7a1ff9a0a8c25f7cdbe4291ba to your computer and use it in GitHub Desktop.
Download ZIP
TDE 4 - Cálculo de duração de projeto pelo método PERT/CPM
Raw
metodo_pert_cpm.c
/*
Faça um programa que leia de um arquivo entrada.txt um conjunto de tarefas com suas identificação, duração e dependências, e calcule a duração mínima do projeto, bem como as atividades que fazem parte do caminho crítico usando o método PERT/CPM.
O arquivo consiste de uma série de atividades, uma linha por atividade, contendo a identificação da tarefa (uma letra entre 'a' e 'z'), sua duração, e a lista de atividades das quais ela depende, conforme o exemplo abaixo.
*/
#include <stdio.h>
#include <string.h> // memset
#define tarefa_es(i) custos[0][i] // early start
#define tarefa_ef(i) custos[1][i] // early finish
#define tarefa_ls(i) custos[2][i] // late start
#define tarefa_lf(i) custos[3][i] // late finish
#define INFINITY 10000
int pegar_duracao(int matriz_adj[26][26], int v){
int duracao = 0;
for(int i=0; i<26; i++){
if(matriz_adj[i][v]){
duracao = matriz_adj[i][v];
break;
}
}
return duracao;
}
void remover_duplicatas(int matriz_adj[26][26], int qntd_tarefas, int ligados_inicio[26]){
int conexoes_a[26], conexoes_b[26];
for(int a=1; a<qntd_tarefas; a++){
for(int b=1; b<qntd_tarefas; b++){
if(a==b) continue;
if(ligados_inicio[a] || ligados_inicio[b]) continue;
memset(conexoes_a, 0, sizeof(int) * 26);
memset(conexoes_b, 0, sizeof(int) * 26);
for(int i=0; i<qntd_tarefas; i++){
if(matriz_adj[i][a]) conexoes_a[i] = 1;
if(matriz_adj[i][b]) conexoes_b[i] = 1;
}
if(memcmp(conexoes_a, conexoes_b, sizeof(int) * 26) == 0){
printf("%c e %c iguais, removendo duplicata.\n", a+'A'-1, b+'A'-1);
for(int i=0; i<qntd_tarefas; i++){
matriz_adj[i][b] = 0;
}
}
}
}
}
void forward_pass(int matriz_adj[26][26], int custos[4][26], int v, int custo, int *vf){
if(custo < tarefa_es(v)) return;
tarefa_es(v) = custo;
tarefa_ef(v) = custo + pegar_duracao(matriz_adj, v);
printf("[%c] es:%d ef:%d (duracao:%d) (v:%d)\n", v+'A'-1, tarefa_es(v), tarefa_ef(v), pegar_duracao(matriz_adj, v), v);
int flag = 1;
for(int i=0; i<26; i++){
if(matriz_adj[v][i]){
flag = 0;
forward_pass(matriz_adj, custos, i, tarefa_ef(v), vf);
}
}
if(flag)
*vf = v;
}
void backward_pass(int matriz_adj[26][26], int custos[4][26], int v, int custo_neg, int *vi){
if(custo_neg == -1) tarefa_lf(v) = tarefa_ef(v); // último vértice
if(custo_neg > tarefa_lf(v)) return;
if(custo_neg != -1)
tarefa_lf(v) = custo_neg;
tarefa_ls(v) = tarefa_lf(v)-pegar_duracao(matriz_adj, v);
printf("[%c] ls:%d lf:%d (duracao:%d) (v:%d)\n", v+'A'-1, tarefa_ls(v), tarefa_lf(v), pegar_duracao(matriz_adj, v), v);
int flag = 1;
for(int i=0; i<26; i++){
if(matriz_adj[i][v]){
flag = 0;
backward_pass(matriz_adj, custos, i, tarefa_ls(v), vi);
}
}
if(flag)
*vi = v;
}
int calcular_cpm(int matriz_adj[26][26], int qntd_tarefas){
int vf = -1, vi=-1;
int soma = 0;
int custos[4][26];
memset(custos, INFINITY, sizeof(int)*4*26); // até o final
memset(custos, -1, sizeof(int)*2*26); // até a metade
printf("** fazendo forward pass **\n");
forward_pass(matriz_adj, custos, 0, 0, &vf);
printf("vertice final: %c (%d)\n\n", vf+'A'-1, vf);
printf("** fazendo backwards pass **\n");
backward_pass(matriz_adj, custos, vf, -1, &vi);
printf("vertice inicial: %c (%d)\n\n", vi+'A'-1, vi);
printf("** calculando cpm **\n");
for(int i=0; i<=qntd_tarefas; i++){
if(tarefa_ef(i) == tarefa_lf(i)){
soma += pegar_duracao(matriz_adj, i);
printf("ef:%d lf:%d duracao: %d\n", tarefa_ef(i), tarefa_lf(i), pegar_duracao(matriz_adj, i));
}
}
printf("CPM: %d\n", soma);
}
int main(){
int matriz_adj[26][26] = {0};
int ligados_inicio[26] = {0};
int qntd_tarefas = 0;
// https://imgur.com/cnSy7gZ
FILE *file_ptr = NULL;
file_ptr = fopen("entrada.txt", "r");
if(file_ptr == NULL) return -1;
// enquanto as linhas iniciarem com um caractere:
int aux;
int tarefa = -1, duracao = 0, flag = 1;
printf("** fazendo leitura **\n");
while(aux != EOF){
aux = fgetc(file_ptr);
// não ler nova linha, espaços e vírgula
if(aux != '\n' && aux != ' ' && aux != ','){
// se a letra da tarefa não foi lida:
if(tarefa == -1){
if(aux >= 'A' && aux <= 'Z') tarefa = aux - 'A'+1; // A=1 ... Z:26
else if(aux >= 'a' && aux <= 'z') tarefa = aux - 'a'+1; // a=1 ... z:26
printf("\ntarefa: %c\n", aux);
qntd_tarefas += 1;
} else if (tarefa){ // se a tarefa já foi lida, ler a duração:
// se é dígito (a duração pode ter N dígitos)
if(aux >= '0' && aux <= '9'){
duracao = (duracao * 10) + (aux-'0');
printf("duracao: %d\n", duracao);
} else if(aux >= 'A' && aux <= 'Z'){
printf("dependencia: %c->%c\n", aux, tarefa+'A'-1);
matriz_adj[aux-'A'+1][tarefa] = duracao;
flag = 0;
} else if (aux >= 'a' && aux <= 'z'){
printf("dependencia: %c->%c\n", aux, tarefa+'a'-1);
matriz_adj[aux-'a'+1][tarefa] = duracao;
flag = 0;
}
}
}
// limpar as variáveis auxiliares ao receber uma nova linha:
if(aux == '\n'){
if(flag){ // se não tiver predecessor
ligados_inicio[tarefa] = 1;
matriz_adj[0][tarefa] = duracao;
}
tarefa = -1;
duracao = 0;
flag=1;
}
}
printf("\n** fim **\n");
remover_duplicatas(matriz_adj, qntd_tarefas, ligados_inicio);
calcular_cpm(matriz_adj, qntd_tarefas);
return 0;
}
/*
entrada.txt
a,7
b,5
c,9,a
d,11,c
e,6,b
f,4,c,e
g,3,d
h,8,f
i,6,g,h
j,6,g,h
k,7,i,j
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment