Desenvolvendo uma Análise para os Megaprojetos

Desenvolvendo uma Análise para os Megaprojetos Gabriel Dias Schmoeller, Patrick Thiago Bard 1

Faculdade de Informática (FACIN) Pontifícia Universidade Católica do Rio Grande do Sul (PUCRS) 24 de junho de 2013 {gabriel.schmoeller,patrick.bard}@acad.pucrs.br

Resumo. Este artigo apresenta os algoritmos desenvolvidos para solucionar o segundo trabalho proposto na disciplina de Algoritmos e Programação III, no primeiro semestre de 2013. Desenvolvemos uma maneira para apresentar o custo final de um projeto, e inclusive demonstra-la graficamente, utilizado o recurso do Graphviz. Foi utilizado uma estrutura de Grafos, porém com determinadas modificação, sendo a complexidade no caso médio O(n).

1. Introdução De um modo geral, o problema consiste em apresentar o custo final de um projeto. Tal projeto, pode possuir diversas atividades, com custos diferentes e em quantidades diferentes. De modo que uma atividade além de seu custo próprio, pode necessitar de uma outra atividade determinado número de vezes.

2. Abordagem Desenvolvida 2.1. Introdução Apresentamos aqui as primeiras ideias para resolução do trabalho proposto. 2.2. Descrição O programa proposto a ser feito, tem uma complexidade simples num contexto geral. E ele não precisa de maiores explicações além de saber calcular o custo das atividades, sabendo que uma atividade A pode depender de outras (determinado número de vezes), e que as outras podem necessitar do custo total de A. E assim, saber o custo total de um projeto, sabendo o custo da atividade de mais alto nível (também chamada aqui de fonte), que necessita de outras, mas nenhuma depende dela. Por essa descrição já é possível notar algumas características que nos ajudaram no ato da implementação. Uma delas é a visível facilidade que seria implementar um método recursivo para calcular o custo total de uma atividade, já que o processo de calcular se repete da mesma maneira, tanto para atividade fonte, como para atividades sem dependências de outras. Outra característica notável é a similaridade com o conceito de grafos, com a única diferença de que é obrigatória ter apenas um nodo fonte, algo que de certa forma facilita a implementação, por possuir um ponto de partida acessível. Deste modo desde os primeiros esboços de ideias para desenvolver esse projeto, utilizamos o conceito de grafos. Porém, já de início, analisamos as implementações padrões da estrutura de grafos, e concluímos que poderíamos usufruir mais recursos dela se desenvolvemos uma própria. Num geral, a estrutura que usamos para armazenar as informações está contida em mapas.

3. Casos de Teste 3.1. Introdução Apresentamos aqui, os resultados que obtivemos, assim como o porque confiamos nos valores obtidos. 3.2. Resultados iniciais e comparações 3.2.1. 1o caso Primeiro, executamos um teste simples, afim de que qualquer pessoa pudesse calcular mentalmente as ligações, de modo que pudéssemos ver se o algoritmo gerava a saída esperada. Utilizando a entrada à esquerda, foi possível gerar a saída com o GraphViz: 3 NAL 2 TUM 2 GGW 2 3 NAL TUM 1 NAL GGW 2 TUM GGW 1 Após gerado a saída, analisamos suas características, conforme listadas: • Existem apenas três nodos, e três ligações. • Todos os nodos possuem custo próprio $2. • Apenas a ligação de NAL para CGW possui aresta de peso 2, sendo as outras com peso 1. • Custo total de NAL é $10 porque este custo se caracteriza como: Seu custo próprio $2 + duas vezes o custo de CGW que também é $2, mais o custo de TUM que é $4, porque soma o seu custo próprio de $2 mais o custo de CGW. 2 + (2 ∗ 2) + (2 + 2) = 10 O modelo visual acompanha corretamente a entrada fornecida em texto e todas suas característica estão corretas seguindo as noções definidas no enunciado do trabalho. Assim podemos confirmar que esta saída foi gerada corretamente. 3.2.2. 2o caso Continuando este tipo de teste. Refizemos um caso que já sabíamos a saída esperada, o exemplo fornecido junto com o enunciado. Utilizamos ele como um caso de teste, por possuir uma complexidade um pouco maior do que modelos muito simples como o anterior, mas ainda sim, complexo suficiente para podermos verificar a atuação do algoritmo em vários casos, como múltiplas dependências e nodos sumidouros. O fato de já possuirmos a resposta esperada nos garante uma segurança maior ao comparar os resultados. A esquerda, se encontra a entrada textual fornecida. No centro, a saída esperada, fornecida no enunciado. E a direita, se apresenta a saída visual baseada nos cálculos feitos pelo nosso algoritmo, gerada via GraphViz.

10 NAL 3 TUM 4 GGW 9 SQD 10 YUY 15 QMR 17 FPK 16 GMZ 15 WNJ 12 MCX 3 13 GMZ WNJ 3 YUY FPK 9 NAL QMR 8 NAL SQD 1 SQD YUY 1 MCX YUY 4 GMZ MCX 9 GGW QMR 9 GGW SQD 7 MCX FPK 3 GMZ TUM 6 GMZ NAL 1 TUM GGW 2 Neste caso de teste é fácil notar que a saída gerada está dentro do que esperávamos. O resultado final do projeto foi de $22706, o mesmo valor de resultado que o exemplo do enunciado apresenta. Apesar de ser possível notar algumas diferenças comparando a saída do GraphViz, elas possuem a mesma topologia, portanto isto não torna o modelo errado, já que a ordem dos nodos não faz diferença mas sim suas arestas, pesos e valores. Comparando com o exemplo original, os nodos apenas estão agrupados praticamente espelhados. 3.3. GraphViz As saídas para os casos de testes presentes neste artigo foram desenvolvidas usando a ferramenta GraphViz. Ele se torna muito útil por receber uma entrada simples de texto, e por gerenciar automaticamente onde deve se situar a posição de cada nodo de acordo com suas ligação, gerando saídas já organizadas. Para facilitar ainda mais o uso desta ferramenta, usamos o método Java Runtime.getRuntime().exec(), que resumidamente, invoca o uso de um executável externo (GraphViz no caso), e o parâmetro representa o comando necessário a ser executado no executável: -Tsvg -o O algoritmo gera um arquivo .dot (formato reconhecido pelo GraphViz), e executando o comando acima, gera um arquivo de imagem vetorial .svg. O padrão utilizado no arquivo .dot, segue estas características:

digraph { -> ; -> ; ... -> ; } Onde: • : Representa o nome do Grafo a ser criado (por padrão, "G"). • : Representa as características de um nodo, sendo formadas por $ $ • : Representa o valor da ligação do nodo da esquerda ao da direita [ label = ] As entradas textuais reais utilizadas para gerar a saída dos dois primeiros casos de teste são apresentadas abaixo: Caso 1 digraph G{ "TUM $2 $4-> "GGW $2 $2"[ label="1"]; "NAL $2 $10-> "GGW $2 $2"[ label="2"]; "NAL $2 $10-> "TUM $2 $4"[ label="1"]; } Caso 2 digraph G{ "YUY $15 $159-> "FPK $16 $16"[ label="9"]; "GGW $9 $1345-> "SQD $10 $169"[ label="7"]; "GGW $9 $1345-> "QMR $17 $17"[ label="9"]; "MCX $3 $687-> "YUY $15 $159"[ label="4"]; "MCX $3 $687-> "FPK $16 $16"[ label="3"]; "SQD $10 $169-> "YUY $15 $159"[ label="1"]; "TUM $4 $2694-> "GGW $9 $1345"[ label="2"]; "NAL $3 $308-> "SQD $10 $169"[ label="1"]; "NAL $3 $308-> "QMR $17 $17"[ label="8"]; "GMZ $15 $22706-> "WNJ $12 $12"[ label="3"]; "GMZ $15 $22706-> "MCX $3 $687"[ label="9"]; "GMZ $15 $22706-> "NAL $3 $308"[ label="1"]; "GMZ $15 $22706-> "TUM $4 $2694"[ label="6"]; } 3.4. Demais Casos de Teste Após analisarmos os dois primeiro casos de teste mais simples, e verificarmos que o algoritmo que desenvolvemos produzia as saídas conforme o esperado com o resultado final correto, avançamos para casos mais complexos. Nos próximos casos de teste apresentados, utilizaremos os exemplos fornecidos na página da disciplina como base. Os próximos grafos a serem apresentados possuem complexidade muito maior, portanto não apresentaremos suas entradas textuais devido ao fato de que o tamanho da entrada é proporcional à sua complexidade.

3.4.1. 3o caso Caso de teste baseado no arquivo ex1

Tabela 1. Informações do 3o caso de teste

Resultado Final 560123827178 Quantidade de nodos 40 Quantidade de Arestas 109 Tempo de Execução 108ms Tempo de Renderização 140ms

3.4.2. 4o caso Caso de teste baseado no arquivo ex2

Tabela 2. Informações do 4o caso de teste

Resultado Final 28947426541 Quantidade de nodos 40 Quantidade de Arestas 105 Tempo de Execução 100ms Tempo de Renderização 152ms

3.4.3. 5o caso Caso de teste baseado no arquivo ex3

Tabela 3. Informações do 5o caso de teste

Resultado Final 11416727425 Quantidade de nodos 40 Quantidade de Arestas 106 Tempo de Execução 87ms Tempo de Renderização 110ms

3.4.4. 6o caso

Caso de teste baseado no arquivo ex4

Tabela 4. Informações do 6o caso de teste

Resultado Final 25383189053 Quantidade de nodos 40 Quantidade de Arestas 103 Tempo de Execução 90ms Tempo de Renderização 125ms

3.4.5. 7o caso Caso de teste baseado no arquivo ex5

Tabela 5. Informações do 7o caso de teste

Resultado Final 179772695372 Quantidade de nodos 40 Quantidade de Arestas 109 Tempo de Execução 105ms Tempo de Renderização 164ms

3.4.6. 8o caso Caso de teste baseado no arquivo ex6

Tabela 6. Informações do 8o caso de teste

Resultado Final 207031229463 Quantidade de nodos 40 Quantidade de Arestas 107 Tempo de Execução 92ms Tempo de Renderização 123ms

3.4.7. 9o caso Caso de teste baseado no arquivo ex8

Tabela 7. Informações do 9o caso de teste

Resultado Final 8454210463937 Quantidade de nodos 40 Quantidade de Arestas 102 Tempo de Execução 103ms Tempo de Renderização 148ms

4. Algoritmo 4.1. Introdução Aqui apresentamos o pseudo-código das principais partes do algoritmo desenvolvido. 4.2. Pseudo-código classe NeoGraph { vertice novo Dicionario (); arestas novo Dicionario(); addNodo(String chave, Generico elemento){ se(vertice contemChave = ) lancar nova Excecao (Nome da chave ja existe) vertice coloca(chave na lista: elemento) origemDestino = novo Objeto OriginsTargets arestas coloca(chave na lista: origemDestino) } addAresta(String de, String para, inteiro peso){ se(vertice naoContemChave = ) lancar nova Excecao( nao existe) se(vertice naoContemChave = para) lancar nova Excecao( nao existe) arestas.get(para).getOrigens().coloca(de, peso) arestas.get(de).getDestinos().coloca(para, peso) } Generico getVertice(String chave){ se(vertice naoContemChave = ) lancar nova Excecao( nao existe) retorna vertice.get(chave) } getPeso(String de, String para){ retorna arestas.get(de).getOrigens().get(para) } Dicionario getFontes(){ retorno = novo Dicionario() para cada aresta em arestas { se(aresta.getValor().origens.estaVazio()) retorno.coloca(aresta.getChave(), vertice.get(aresta.getChave())) } retorna retorno } String toString() { retorna "NeoGraph{ + vertice.toString() + + arestas.toString()+ }" } classe interna OriginsTargets{ Dicionario origens

Dicionario destinos OriginsTargets(){ this.origens = novo Dicionario() this.destinos = novo Dicionario() } String toString() { retorna "OriginsTargets{ + + origens.toString() + + destinos.toString() + }" } } } classe ProjetoEncoder { getGraph(File entrada){ retorna getGraph(new Scanner(entrada) } long calculaTotal(NeoGraph grafo){ long total = 0 para cada n em grafo.getFontes(){ total = calculaTotal(grafo, grafo.getDestinos( n.getChave())) +n.getValor() } retorna total } long calculaTotal(NeoGraph grafo, Mapa vertices){ long total = 0 se(vertices for diferente de null) para cada vertice em vertices{ total += (calculaTotal(grafo, grafo.getDestinos(vertice.getChave())) +grafo.getVertice(vertice.getChave())) *vertice.getValor() Sistema.ImprimeNovaLinha( vertice.getChave() + total) } retorna total } } }

5. Complexidade do Algoritmo Como o algoritmo basicamente percorre seguindo as ligações, podemos dizer que seu caso médio é O(n), sendo n o número de ligações. Porém não podemos definir um pior caso, pois não podemos nos basear apenas na quantidade de ligações ou nodos, já que dependendo do caso, mesmo tendo poucas ligações ou nodos ele poderia ter muitos cálculos repetidos.

6. Conclusão Apesar do trabalho proposto aparentar possuir uma certa complexidade, podemos ver que ele pode ser facilmente resolvido, e que usufruir as características que citamos no inicio, fácil adequação a recursividade e característica de estrutura de grafos nos ajudou muito. Mesmo com os valores de certa forma exorbitantes de alguns exemplos apresentados, o cálculo em si é processado de forma simples. Podemos notar também que não foi tão simples definir um pior caso para o algoritmo, mas de um modo geral se comportou com um tempo de resposta rápido com um caso médio O(n).