§1  EP2  UMA SOLUCAO PARA O EP2 1

1. Uma solucao para o EP2. Esta é uma implementação em de um algoritmo de escalonamento simples. O propósito é resolver o EP2. Nós nos baseamos firmemente no programa , de ordenação topológica.

Observação (de sempre). A versão do que estamos usando neste programa não mescla muito bem com o português: um projeto interessante seria encontrar uma solução simples para este problema.

2. Aqui está a estrutura geral do nosso programa .

⟨ Inclusão de arquivos sobre as bibliotecas 3 ⟩

⟨ Declaração de tipos 5 ⟩

⟨ Variáveis globais 4 ⟩

⟨ O programa principal 6 ⟩

3. Precisamos incluir os arquivos para as funções de entrada e saída e para as funções de alocação de memória. ⟨ Inclusão de arquivos sobre as bibliotecas 3 ⟩ ≡ #include /∗ para as funções de entrada e saída ∗/ #include /∗ para calloc( ), malloc( ), e free( ) ∗/

This code is used in section 2.

4. Usaremos a variável status para passar ao sistema operacional informação sobre o sucesso, ou não, da execução deste programa. A variável nome do prog é usada para guardar o nome do programa (como em ). #define 0 /∗ valor de status quando tudo correu bem ∗/ #define erro nos dados 1 /∗ valor de status quando os dados de entrada foram inconsistentes ∗/

#define erro na leitura de arquivo 2

/∗ valor de status para quando ocorre erro na leitura da entrada ∗/

#define erro na alocacao de memoria 3

/∗ valor de status para quando ocorre erro na alocação de memória ∗/

#define erro no numero de rodadas 4 /∗ esperemos que isto nunca aconteca ∗/ ⟨ Variáveis globais 4 ⟩ ≡

int status = ; /∗ inicialmente nada aconteceu de errado ∗/

char ∗nome do prog ; /∗ o nome deste programa ∗/

char ∗nome do arq ; /∗ nome do arquivo de dados, caso não seja o stdin ∗/ FILE ∗arquivo = Λ; /∗ ponteiro para arquivo de dados (se diferente de stdin) ∗/

This code is used in section 2.

2  UMA SOLUCAO PARA O EP2  EP2 §5

5. Os elementos da ordem parcial serão representados por estruturas. Tais estruturas (do tipo struct elemento) terão os campos id , g entr , topo suc, prox fila, e anterior . O campo id é simplesmente um inteiro que identifica o elemento. O campo g entr é um inteiro, que contará o número de arcos que terminam neste elemento em cada instante.

Queremos montar uma partição dos elementos da entrada em rodadas. A primeira rodada é constituída dos elementos que têm g entr = 0, i.e., as fontes. Removemos então todos os elementos desta primeira rodada (e também os arcos que emanam deles). Tal remoção cria novas fontes, e a segunda rodada é constituída destas novas fontes. Prosseguimos analogamente até esgotarmos a entrada.

Como no algoritmo de ordenação topológica, manteremos, para cada x, uma lista de estruturas que representam os elementos para os quais x manda um arco. Estas estruturas serão do tipo struct sucessor . A lista correspondente ao elemento x começa na estrutura x topo suc. O campo prox suc de uma estrutura do tipo struct sucessor , que é declarado como um ponteiro para struct sucessor , será usado para implementar esta lista. O campo id de uma estrutura do tipo struct sucessor aponta para o elemento da ordem parcial que ele representa (mais precisamente, para a estrutura do tipo struct elemento que representa o elemento).

O campo prox fila dos struct elemento será usado para implementar uma fila que conterá as fontes, i.e., os elementos com g entr = 0. O campo anterior destas estruturas, que será um ponteiro para struct elemento, será usado para se construir seqüências de elementos que formam “cadeias de dependência completa” (os elementos de cada uma destas seqüências dependem um do outro, em uma ordem linear). Se o nosso programa devolve uma decomposição da entrada em k rodadas, então devemos também devolver uma tal seqüência com k elementos.

Montaremos uma lista de listas para representar a solução final. A k-ésima lista desta lista conterá os elementos que constituem a k-ésima rodada. Usaremos o campo prox na rodada para implementar as listas que representam as rodadas. Aqui vamos tentar ser econômicos, e definiremos prox na rodada sendo uma macro que vale prox fila (lembre-se da observação sobre “leitores astutos” de ).

Finalmente, usaremos as estruturas struct lista para montar a lista das listas das rodadas.

#define prox na rodada prox fila

⟨ Declaração de tipos 5 ⟩ ≡

struct elemento { int id ; int g entr ; struct sucessor ∗topo suc; struct elemento ∗prox fila; struct elemento ∗anterior ;

};

struct sucessor { struct elemento ∗id ; struct sucessor ∗prox suc;

};

struct lista { struct elemento ∗comeco; struct lista ∗prox lista;

};

This code is used in section 2.

6. A função main tem a seguinte cara. ⟨ O programa principal 6 ⟩ ≡

main(argc, argv )

int argc; /∗ o número argumentos na linha de comando ∗/

char ∗∗argv ; /∗ um vetor de strings, contendo os argumentos ∗/ { ⟨ Variáveis locais a main 12 ⟩

nome do prog = argv [0]; ⟨ Interprete a linha de comando 7 ⟩; ⟨ Leia os dados de entrada 8 ⟩; ⟨ Encontre uma decomposição em rodadas 13 ⟩; ⟨ Imprima a decomposição encontrada 23 ⟩; ⟨ Imprima uma seqüência de elementos interdependentes 25 ⟩; exit (status );

}

This code is used in section 2.

7. O usuário pode fornecer os dados de entrada de duas formas. A mais simples é através do stdin. Entretanto, podemos também fornecer um nome de arquivo na linha de comando (o primeiro argumento fornecido será interpretado como o nome do arquivo).

#define

⟨ Interprete a linha de comando 7 ⟩ ≡

if (argc > 1) { /∗ o usuário forneceu pelo menos um argumento ∗/ nome do arq = argv [1]; arquivo = fopen(nome do arq , ); if (arquivo ≡ Λ) {

status = erro na leitura de arquivo;

fprintf (stderr , ␣ ␣ ␣ ␣ ␣ ␣ , nome do prog , nome do arq ); exit (status );

} } /∗ caso contrário, a entrada virá no stdin. Neste caso, arquivo = Λ ∗/

This code is used in section 6.

8. Agora que já sabemos de onde virá a entrada, precisamos lê-la. Assumimos que o número de elementos n da ordem parcial vem na primeira linha do arquivo de entrada. Nas linhas seguintes, assumimos que vêm os pares (i, j), um par por linha; o par (i, j) representa a relação i ≺ j. No arquivo, assumimos que o par (i, j) é representado por dois inteiros separados por espaços. ⟨ Leia os dados de entrada 8 ⟩ ≡

{ int scanf args ; /∗ o número de argumentos de scanf que foram entendidos com sucesso ∗/ if (arquivo) scanf args = fscanf (arquivo, , &n); else scanf args = scanf ( , &n); if (scanf args < 1) {

status = erro nos dados ;

fprintf (stderr , ␣ ␣ ␣ ␣ ␣ ␣ ␣ , nome do prog ); exit (status );

} ⟨ Aloque e inicialize memória para as n estruturas 9 ⟩; ⟨ Leia as relações fornecidas 10 ⟩; if (arquivo) fclose(arquivo);

}

This code is used in section 6.

9. Fazemos aqui a alocação de memória para as n estruturas que vão representar os elementos da ordem parcial. Uma outra opção seria o uso de um vetor de entradas, com algum grande. ⟨ Aloque e inicialize memória para as n estruturas 9 ⟩ ≡

{ int k; struct elemento ∗ptr ; els = (struct elemento ∗) calloc(n, sizeof (struct elemento)); if (els ≡ Λ) { /∗ faltou memória... ∗/

status = erro na alocacao de memoria; fprintf (stderr , ␣ ␣ , nome do prog ); exit (status );

} for (ptr = els , k = 1; ptr < els + n; ptr^{++}, k^{++}) {

ptr id = k; ptr g entr = 0; ptr topo suc = Λ; ptr prox fila = ptr anterior = Λ;

} }

This code is used in section 8.

10. Agora precisamos ler os vários pares (i, j) a serem lidos. Para tanto, lemos dois inteiros por vez, e quando não conseguimos ler um par de inteiros assumimos que o arquivo terminou. ⟨ Leia as relações fornecidas 10 ⟩ ≡

{ int i, j; /∗ os elementos lidos ∗/ int scanf args ; /∗ o número de argumentos de scanf que foram entendidos com sucesso ∗/ int ha pares para ler = 1; /∗ variável booleana para controle da leitura dos pares ∗/ while (ha pares para ler ) {

if (arquivo) scanf args = fscanf (arquivo, ␣ , &i, &j); else scanf args = scanf ( ␣ , &i, &j); if (scanf args < 2) ha pares para ler = 0; else ⟨ Insira o par (i, j) em nossa estrutura de dados 11 ⟩;

} }

This code is used in section 8.

11. Queremos agora registrar em nossa estrutura de dados que temos i ≺ j. #define el (k) (els + k − 1) ⟨ Insira o par (i, j) em nossa estrutura de dados 11 ⟩ ≡

{ struct sucessor ∗ptr ; ptr = (struct sucessor ∗) malloc(sizeof (struct sucessor)); if (ptr ≡ Λ) { /∗ faltou memória... ∗/ status = erro na alocacao de memoria; fprintf (stderr , ␣ ␣ , nome do prog ); exit (status );

}

ptr id = el (j);

el (j) g entr^{++}; /∗ incrementamos o contador de arcos de entrada para j ∗/ ptr prox suc = el (i) topo suc; el (i) topo suc = ptr ; /∗ inserimos o elemento j na lista de sucessores de i ∗/

}

This code is used in section 10.

12. Comecemos agora com o algoritmos propriamente dito. No que segue, chamamos de fontes os elementos que já não recebem nenhum arco ou, para ser mais preciso, aqueles elementos cujos “ancestrais” foram todos já classificados em alguma rodada anterior. Manteremos o conjunto de fontes em uma fila. O começo da fila será apontada por comeco e o término por fim. ⟨ Variáveis locais a main 12 ⟩ ≡

struct elemento ∗comeco, ∗fim;

See also sections 14, 20, and 26. This code is used in section 6.

13. O algoritmo em si está nesta parágrafo. ⟨ Encontre uma decomposição em rodadas 13 ⟩ ≡

⟨ Inicialize a lista das listas das rodadas 15 ⟩; ⟨ Inicialize a fila de fontes 22 ⟩; ⟨ Monte as listas que representam as rodadas 16 ⟩; ⟨ Verifique se classificamos todos os elementos 21 ⟩;

This code is used in section 6.

14. A lista das listas das rodadas será na verdade uma fila, pois queremos que as rodadas sejam acrescentadas no fim da lista, para que a ordem das rodadas seja “crescente.” O início e fim desta fila serão apontados por primeira rodada e rodada mais recente. Manteremos também um contador n rodadas com o número de rodadas que já temos. ⟨ Variáveis locais a main 12 ⟩ +≡

struct lista ∗primeira rodada;

struct lista ∗rodada mais recente;

int n rodadas = 0;

15. ⟨ Inicialize a lista das listas das rodadas 15 ⟩ ≡ primeira rodada = rodada mais recente = Λ;

This code is used in section 13.

16. ⟨ Monte as listas que representam as rodadas 16 ⟩ ≡

while (comeco) { /∗ enquanto a fila das fontes não estiver vazia… ∗/ n rodadas^{++}; ⟨ Coloque todos os elementos da fila de fontes na fila das rodadas 17 ⟩; ⟨ Percorra a lista desta nova rodada e acerte os g entr e a fila de fontes 18 ⟩;

}

This code is used in section 13.

17. ⟨ Coloque todos os elementos da fila de fontes na fila das rodadas 17 ⟩ ≡

{ struct lista ∗ptr ; ptr = (struct lista ∗) malloc(sizeof (struct lista)); ptr comeco = comeco; ptr prox lista = Λ; if (rodada mais recente ≡ Λ) primeira rodada = rodada mais recente = ptr ; else {

rodada mais recente prox lista = ptr ;

rodada mais recente = ptr ; } comeco = fim = Λ; /∗ a fila de fontes está vazia agora ∗/

}

This code is used in section 16.

18. ⟨ Percorra a lista desta nova rodada e acerte os g entr e a fila de fontes 18 ⟩ ≡

{ struct elemento ∗ptr elemento; struct sucessor ∗ptr suc, ∗ptr aux ; ptr elemento = rodada mais recente comeco; while (ptr elemento) {

ptr suc = ptr elemento topo suc;

while (ptr suc) { if (^{−}ptr suc id g entr ≡ 0) ⟨ Processe a nova fonte ptr suc id 19 ⟩; ptr aux = ptr suc; ptr suc = ptr suc prox suc; free(ptr aux );

}

n proc^{++};

ptr elemento = ptr elemento prox na rodada; }

}

This code is used in section 16.

19. Quando descobrimos que um elemento x se tornou uma fonte, devemos inseri-lo na fila das fontes e também acertar x anterior , que passa a apontar para o elemento que mandava para x o último arco que ele recebia. ⟨ Processe a nova fonte ptr suc id 19 ⟩ ≡

{ ptr suc id prox fila = Λ; if (fim ≡ Λ) comeco = fim = ptr suc id ; else {

fim prox fila = ptr suc id ; fim = ptr suc id ;

}

ptr suc id anterior = ptr elemento; }

This code is used in section 18.

20. Queremos verificar, ao término da execução do algoritmo, se classificamos todos os n elementos em rodadas. Para tanto, mantemos um contador que conta o número de elementos que são classificados em rodadas. ⟨ Variáveis locais a main 12 ⟩ +≡

int n proc = 0;

21. ⟨ Verifique se classificamos todos os elementos 21 ⟩ ≡

if (n proc < n) {

fprintf (stderr ,  ␣    ␣   ␣     ␣   ␣        ␣  ␣  , nome do prog );
printf (  ␣    ␣ ␣       ␣        ␣  );

⟨ Imprima as rodadas 24 ⟩; status = erro nos dados ; exit (status );

}

This code is used in section 13.

22. Antes de começar o algoritmo, devemos encontrar e inserir todas as fontes na lista de fontes. ⟨ Inicialize a fila de fontes 22 ⟩ ≡

{ int k; comeco = fim = Λ; for (k = 1; k ≤ n; k^{++}) if (el (k) g entr ≡ 0)

if (comeco ≡ Λ) /∗ fila vazia ∗/

fim = comeco = el (k); else { /∗ fila não está vazia ∗/

fim prox fila = el (k); fim = el (k);

} }

This code is used in section 13.

23. ⟨ Imprima a decomposição encontrada 23 ⟩ ≡

  printf (  ␣           ␣   ␣       ␣  ␣     ␣        ␣ ␣    ␣  );

⟨ Imprima as rodadas 24 ⟩;

This code is used in section 6.

24. ⟨ Imprima as rodadas 24 ⟩ ≡

{ struct lista ∗ptr lista; struct elemento ∗ptr elemento; int k; for (k = 1, ptr lista = primeira rodada; ptr lista; k^{++}, ptr lista = ptr lista prox lista) {

printf ( ␣ , k);

for (ptr elemento = ptr lista comeco; ptr elemento; ptr elemento = ptr elemento prox na rodada)

printf ( ␣ , ptr elemento id ); printf ( );

} }

This code is used in sections 21 and 23.

25. Se listamos a seqüência de elementos que começa com um elemento que pertence à ultima rodada, digamos x, seguida de x anterior , seguida de x anterior anterior etc, encontraremos uma seqüência de elementos que demonstram que o número de rodadas em que decompusemos a entrada é ótima, i.e., não poderíamos ter decomposto em menos rodadas. Um pequeno detalhe é que, na verdade, fica mais intuitivo imprimirmos uma seqüência com descrita acima na ordem reversa. ⟨ Imprima uma seqüência de elementos interdependentes 25 ⟩ ≡

{ struct elemento ∗ptr elemento; struct elemento ∗topo = Λ; struct elemento ∗ptr aux = Λ; int k = 0; ptr elemento = rodada mais recente comeco; while (ptr elemento) {

ptr aux = ptr elemento;

ptr elemento = ptr elemento anterior ;

ptr aux anterior = topo;

topo = ptr aux ;

k^{++}; } printf ( ␣ ␣ ␣ ␣ ␣ ␣ ␣ , k); for ( ; topo; topo = topo anterior ) printf ( ␣ , topo id ); printf ( ); if (k ≠ n rodadas ) {

status = erro no numero de rodadas ;

fprintf (stderr , ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ,

nome do prog ); exit (status );

} }

This code is used in section 6.

26. ⟨ Variáveis locais a main 12 ⟩ +≡ int n; /∗ número de elementos na ordem parcial ∗/ struct elemento ∗els ; /∗ ponteiro para os elementos ∗/

§27  EP2  INDICE 9

27. Indice. Aqui está uma lista de identificadores que são usados, com indicação de onde eles aparecem. As entradas sublinhadas indicam onde eles aparecem.

anterior : \underline{5}, 9, 19, 25. argc: \underline{6}, 7. argv : \underline{6}, 7. arquivo: \underline{4}, 7, 8, 10. calloc: 3, 9. comeco: \underline{5}, \underline{12}, 16, 17, 18, 19, 22, 24, 25. el : \underline{11}, 22. elemento: \underline{5}, 9, 12, 18, 24, 25, 26. els : 9, 11, \underline{26}. erro na alocacao de memoria: \underline{4}, 9, 11. erro na leitura de arquivo: \underline{4}, 7. erro no numero de rodadas : \underline{4}, 25. erro nos dados : \underline{4}, 8, 21. exit : 6, 7, 8, 9, 11, 21, 25. fclose: 8. fim: \underline{12}, 17, 19, 22. fopen: 7. fprintf : 7, 8, 9, 11, 21, 25. free: 3, 18. fscanf : 8, 10. g entr : \underline{5}, 9, 11, 18, 22. ha pares para ler : \underline{10}. i: \underline{10}. id : \underline{5}, 9, 11, 18, 19, 24, 25. j: \underline{10}. k: \underline{9}, \underline{22}, \underline{24}, \underline{25}. lista: \underline{5}, 14, 17, 24. main: \underline{6}. malloc: 3, 11, 17. n: \underline{26}. n proc: 18, \underline{20}, 21. n rodadas : \underline{14}, 16, 25. : 9. nome do arq : \underline{4}, 7. nome do prog : \underline{4}, 6, 7, 8, 9, 11, 21, 25. : \underline{4}. primeira rodada: \underline{14}, 15, 17, 24. printf : 21, 23, 24, 25. prox fila: \underline{5}, 9, 19, 22. prox lista: \underline{5}, 17, 24. prox na rodada: \underline{5}, 18, 24. prox suc: \underline{5}, 11, 18. ptr : \underline{9}, \underline{11}, \underline{17}. ptr aux : \underline{18}, \underline{25}. ptr elemento: \underline{18}, 19, \underline{24}, \underline{25}. ptr lista: \underline{24}. ptr suc: \underline{18}, 19. : \underline{7}. rodada mais recente: \underline{14}, 15, 17, 18, 25. scanf : 8, 10. scanf args : \underline{8}, \underline{10}. status : \underline{4}, 6, 7, 8, 9, 11, 21, 25. stderr : 7, 8, 9, 11, 21, 25. stdin: 4, 7. sucessor: \underline{5}, 11, 18. topo: \underline{25}. topo suc: \underline{5}, 9, 11, 18.

⟨ Aloque e inicialize memória para as n estruturas 9 ⟩ Used in section 8. ⟨ Coloque todos os elementos da fila de fontes na fila das rodadas 17 ⟩ Used in section 16. ⟨ Declaração de tipos 5 ⟩ Used in section 2. ⟨ Encontre uma decomposição em rodadas 13 ⟩ Used in section 6. ⟨ Imprima a decomposição encontrada 23 ⟩ Used in section 6.

⟨ Imprima as rodadas 24 ⟩ Used in sections 21 and 23.

⟨ Imprima uma seqüência de elementos interdependentes 25 ⟩ Used in section 6. ⟨ Inclusão de arquivos sobre as bibliotecas 3 ⟩ Used in section 2. ⟨ Inicialize a fila de fontes 22 ⟩ Used in section 13. ⟨ Inicialize a lista das listas das rodadas 15 ⟩ Used in section 13. ⟨ Insira o par (i, j) em nossa estrutura de dados 11 ⟩ Used in section 10. ⟨ Interprete a linha de comando 7 ⟩ Used in section 6. ⟨ Leia as relações fornecidas 10 ⟩ Used in section 8. ⟨ Leia os dados de entrada 8 ⟩ Used in section 6. ⟨ Monte as listas que representam as rodadas 16 ⟩ Used in section 13. ⟨ O programa principal 6 ⟩ Used in section 2. ⟨ Percorra a lista desta nova rodada e acerte os g entr e a fila de fontes 18 ⟩ Used in section 16. ⟨ Processe a nova fonte ptr suc id 19 ⟩ Used in section 18. ⟨ Variáveis globais 4 ⟩ Used in section 2.

⟨ Variáveis locais a main 12, 14, 20, 26 ⟩ Used in section 6.

⟨ Verifique se classificamos todos os elementos 21 ⟩ Used in section 13.