Advertisement
Guest User

Untitled

a guest
May 20th, 2019
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.70 KB | None | 0 0
  1. #include <stdio.h>
  2. #include "grafos2.h"
  3. #include "queue.h"
  4. #include "string.h"
  5.  
  6.  
  7. //variaveis globais
  8. static int nTasks;
  9. static int v_f;
  10. static int durMin = -1;
  11. static int grauE[MAXVERTS];
  12. static int grauS[MAXVERTS];
  13. static int _ES[MAXVERTS];
  14. static int _LF[MAXVERTS];
  15. static int _LS[MAXVERTS];
  16. static int _FT[MAXVERTS];
  17. static int _FL[MAXVERTS];
  18. static int prec[MAXVERTS];
  19. static int dur[MAXVERTS];
  20. static int trab[MAXVERTS];
  21.  
  22. //concluida
  23. GRAFO * ler_construir_grafo(){
  24. GRAFO *g;
  25. int n_tarefa , nTrab,n_preced;
  26. int duration, i, j, y;
  27. //printf("Enter number of tasks\n");
  28. scanf("%d", &nTasks);
  29. //int array[20];
  30. g = new_graph(nTasks+2);
  31. for(i=1;i<=nTasks;i++){
  32. //printf("Enter Task\n");
  33. scanf("%d", &n_tarefa);
  34. //printf("Enter number of precedents\n");
  35. scanf("%d", &n_preced);
  36.  
  37. //array com precedencias
  38. int array[20], j=0;
  39. while(j<n_preced){
  40. //printf("precedente\n");
  41. scanf("%d", &array[j]);
  42. j++;
  43. }
  44. //printf("duração e numero de trablhadores\n");
  45. scanf("%d %d", &duration, &nTrab);
  46. dur[n_tarefa] = duration;
  47. trab[n_tarefa] = nTrab;
  48. if(n_preced == 0)
  49. insert_new_arc(n_tarefa,nTasks+1, duration, nTrab,g); // no nTasks+1 e o fim do projeto
  50. for(y=0;y<j;y++)
  51. insert_new_arc(n_tarefa, array[y], duration, nTrab, g);
  52. }
  53.  
  54. //instanciar arrays de grau de entrada e de saida
  55. for(i=0;i<=nTasks+1;i++){
  56. _ES[i]=0;
  57. _LS[i]=0;
  58. _FT[i]=0;
  59. _FL[i]=0;
  60. prec[i]=-99;
  61. grauE[i]=0;
  62. grauS[i]=0;
  63. }
  64. for(i=1;i<=nTasks;i++){
  65. for(j=1;j<=nTasks;j++)
  66. if(find_arc(i,j,g)!=NULL){
  67. grauE[j]=grauE[j]+1;
  68. grauS[i]=grauS[i]+1;
  69. }
  70. if( grauE[i] == 0 )
  71. insert_new_arc(0, i, 0, 0, g);
  72. if( grauS[i] == 0)
  73. insert_new_arc(i, 0, 0, 0, g);
  74. printf("dur[%d] = %d\n",i, dur[i]);
  75. }
  76.  
  77. return g;
  78. }
  79.  
  80.  
  81. //concluida
  82. void earl_star(GRAFO *g){
  83. int i,j,k=0;
  84. QUEUE *q = mk_empty_queue(nTasks);
  85. v_f = 0;
  86. BOOL a = FALSE;
  87. int v, max_trabalhadores_activos = 0;
  88. ARCO* arc ;
  89. int grE[nTasks+1];
  90. //tarefas iniciais (sem precedentes)
  91. for(i=1;i<=nTasks;i++){
  92. //printf("grauE[%d]=%d | grauS[%d]=%d\n",i,grauE[i],i,grauS[i]);
  93. grE[i] = grauE[i];
  94. if(grauE[i] == 0)
  95. enqueue(i,q);
  96. }
  97.  
  98. //algoritmo ES
  99. while(a != TRUE){
  100. v = dequeue(q);
  101. //printf("tarefa %d\n",v);
  102. ARCO* adj = ADJS_NO(v,g);
  103. if( durMin < _ES[v] + dur[v]){
  104. durMin = _ES[v] + dur[v];
  105. v_f = v;
  106. }
  107. while(adj!=NULL){
  108. //printf("entrei\n");
  109. int w = EXTREMO_FINAL(adj);
  110. if(_ES[w] < _ES[v] + VALOR1_ARCO(adj)){
  111. _ES[w] = _ES[v] + VALOR1_ARCO(adj);
  112. prec[w] = v;
  113. }
  114. grE[w] = grE[w]-1;
  115. if(grE[w] == 0)
  116. enqueue(w,q);
  117. adj = PROX_ADJ(adj);
  118. }
  119. a = queue_is_empty(q);
  120. }
  121. /*
  122. for(i=1;i<=nTasks+1;i++)
  123. printf("\tprec[%d] = %d ES[%d] = %d\n",i,prec[i],i,_ES[i]);
  124. */ printf("duracao minima do projeto: %d \n",_ES[nTasks+1]);
  125. }
  126.  
  127. GRAFO * transposto(GRAFO *g){
  128. GRAFO *gt = new_graph(nTasks+1);
  129. int i;
  130.  
  131. for(i=0;i<=nTasks;i++){
  132. ARCO *adj = ADJS_NO(i,g);
  133. while(adj!=NULL){
  134. int w = EXTREMO_FINAL(adj);
  135. insert_new_arc(w,i,dur[i], trab[i], gt);
  136. adj = PROX_ADJ(adj);
  137. }
  138. }
  139. return gt;
  140. }
  141.  
  142. void lates_fini(GRAFO* g){
  143. int i, j, w;
  144. QUEUE * q = mk_empty_queue(nTasks);
  145. BOOL a = FALSE;
  146.  
  147. for(i=1;i<=nTasks;i++){
  148. _LF[i]= _ES[nTasks+1];
  149. //printf("grauS[%d]= %d\n", i, grauS[i]);
  150. if(grauS[i] == 0)
  151. enqueue(i,q);
  152. }
  153. printf("um!\n");
  154. while(a!=TRUE) {
  155. int v = dequeue(q);
  156. printf("valor de v %d - ", v);
  157. ARCO * adjs = ADJS_NO(v,g);
  158. while(adjs!=NULL){
  159. int w = EXTREMO_FINAL(adjs);
  160. //printf("valor de w %d\n", w);
  161. if(_LF[w] > _LF[v] - dur[v])
  162. _LF[w] = _LF[v] - dur[v];
  163.  
  164. grauS[w] = grauS[w]-1;
  165. if(grauS[w]==0)
  166. enqueue(w,q);
  167. adjs = PROX_ADJ(adjs);
  168. }
  169. a = queue_is_empty(q);
  170. }
  171. for(i=1;i<=nTasks;i++)
  172. printf("LF[%d] = %d\n",i,_LF[i]);
  173.  
  174. }
  175.  
  176. //concluida
  177. void escreveCaminho(int v_final){
  178. int j=0, i=1, k = 0;
  179. int* caminho = (int *) malloc(nTasks * sizeof(int));
  180. for(i=0; i<nTasks;i++)
  181. caminho[i] = 0;
  182.  
  183. caminho[0] = v_final;
  184. while( prec[v_final] != -99 ) {
  185. caminho[++k] = prec[v_final];
  186. v_final = prec[v_final];
  187. }
  188.  
  189. printf("---CAMINHO---\n");
  190. printf("%d", caminho[k]);
  191. for(i=k-1; i>=0; i--)
  192. printf(" - %d", caminho[i]);
  193. printf("\n");
  194. }
  195.  
  196. // PERGUNTA 1.2 concluida
  197. int trabalhadores_necessarios_ES(GRAFO *g) {
  198. int i,j,max = 0, cont;
  199. int events_matrix[nTasks+1][MAXVERTS];
  200. for(i=0;i<=nTasks;i++)
  201. for(j=0;j<MAXVERTS;j++)
  202. events_matrix[i][j] = 0;
  203.  
  204. for(i=1; i<=nTasks;i++){
  205. //printf("entrei %d\n",i);
  206. ARCO* adj = ADJS_NO(i,g);
  207.  
  208. for(j=_ES[i]; j < _ES[i] + VALOR1_ARCO(adj);j++){
  209. events_matrix[i][j]= VALOR2_ARCO(adj);
  210. //printf("---events_matrix[%d][%d] = %d\n", i, j, events_matrix[i][j]);
  211. }
  212. }
  213.  
  214. for(j=0;j<MAXVERTS;j++){
  215. cont = 0;
  216. for(i=1;i<=nTasks;i++){
  217. cont += events_matrix[i][j];
  218. //printf("---events_matrix[%d][%d] = %d\n", i, j, events_matrix[i][j]);
  219. }
  220.  
  221. //printf("cont=%d\n",cont);
  222. if (max < cont)
  223. max = cont;
  224. }
  225. return max;
  226. }
  227.  
  228. int min_trabalhadores(GRAFO* g){
  229.  
  230.  
  231. return 0;
  232. }
  233.  
  234. int main(){
  235. GRAFO *g = ler_construir_grafo();//concluida
  236. earl_star(g);
  237. escreveCaminho(prec[nTasks+1]);
  238. int t = trabalhadores_necessarios_ES(g);
  239. int mint = min_trabalhadores(g);
  240. GRAFO *gt = transposto(g);
  241. lates_fini(gt);
  242.  
  243. printf("TRABALHADORES : %d\n",t);
  244. printf("Minimo de TRABALHADORES: %d\n", mint);
  245.  
  246. printf("Num vertices %d\n", NUM_VERTICES(g));
  247. printf("Num arcos %d\n", NUM_ARCOS(g));
  248. return 0;
  249. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement