UNIVERSIDADE FEDERAL DO PARANÁ
SETOR DE CIÊNCIAS EXATAS
DEPARTAMENTO DE INFORMÁTICA
BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO
PYGRAPH – Plataforma para execução remota de algoritmos sobre grafos
CURITIBA
2013
RENAN MAZZI LUCIZANO
RICARDO ALEXANDRE SOARES BARBOSA
PYGRAPH – Plataforma para execução remota de algoritmos sobre grafos
Trabalho de graduação apresentado como
requisito parcial à obtenção de grau de
Bacharel em Ciência da Computação.
Orientador: André Luiz Pires Guedes.
Departamento de Informática, UFPR.
CURITIBA
2013
SUMÁRIO
1 INTRODUÇÃO ...................................................................................................................7
1.1 OBJETIVO ............................................................................................................................. 7
2 FUNDAMENTOS TEÓRICOS ................................................................................................9
2.1 PYTHON ............................................................................................................................... 9
2.1.1 Conhecendo a linguagem ............................................................................................. 9
2.1.2 Potencial do Phyton nos Sistemas WEB ..................................................................... 10
2.2 XML.................................................................................................................................... 11
2.3 WebServices ...................................................................................................................... 12
2.4 O Protocolo XML-RPC ........................................................................................................ 14
2.5 Grafos ................................................................................................................................ 15
3 O PYGRAPH .................................................................................................................... 19
3.1 Organização do Sistema .................................................................................................... 20
3.2 Formato Padrão de Entrada e Saída ............................................................................... 22
3.3 Recursos do Sistema ......................................................................................................... 24
3.3.1 Obter Lista de Algoritmos do Servidor ....................................................................... 24
3.3.2 Obter Informações de um Algoritmo Específico ........................................................ 25
3.3.3 Executar um Algoritmo sobre um Grafo .................................................................... 25
3.3.4 Recuperar o Resultado de uma Execução .................................................................. 27
3.3.5 Obter informações de horário local do servidor ........................................................ 27
3.3.6 Outras funções Importantes ...................................................................................... 28
3.4 Cadastrar Novos Algoritmos no Sistema ........................................................................... 29
3.5 Algoritmos implementados no servidor............................................................................ 30
4 CLIENTES ........................................................................................................................ 32
5 CONCLUSÃO ................................................................................................................... 38
6 REFERÊNCIAS .................................................................................................................. 40
LISTA DE FIGURAS
Figura 1 – Arquitetura do sistema ................................................................................................. 8
Figura 2 – Exemplo de código XML ............................................................................................. 12
Figura 3 – Visão geral de um WebService ................................................................................... 13
Figura 4 – Exemplo de um grafo ................................................................................................. 15
Figura 5 – Exemplo de um grafo simples .................................................................................... 16
Figura 6 – Exemplo de um grafo completo ................................................................................. 16
Figura 7 - Exemplo de um grafo vazio ......................................................................................... 17
Figura 8 – Exemplo de um grafo trivial ....................................................................................... 17
Figura 9 - Exemplo de um grafo regular ...................................................................................... 18
Figura 10 – A arquitetura do PYGRAPH ....................................................................................... 19
Figura 11 – Organização do sistema............................................................................................ 20
Figura 12 - Exemplo de XML aceito pelo PYGRAPH .................................................................... 23
Figura 13 – Grafo gerado pelo XML da figura 3.3 ....................................................................... 23
Figura 14 – Cliente PYTHON para solicitar lista de algoritmos do servidor ................................ 32
Figura 15 – Saída padrão após execução do código da figura 4.1 .............................................. 32
Figura 16 - Cliente PYTHON para solicitar informações de um algoritmo do servidor ............... 33
Figura 17 - Saída padrão após execução do código da figura 4.3 ............................................... 33
Figura 18 - Cliente PYTHON para solicitar a execução de um algoritmo no servidor ................. 33
Figura 19 - Cliente PYTHON para solicitar o resultado de uma execução já realizada ............... 34
Figura 20 - Cliente PYTHON para solicitar a execução de múltiplos procedimentos .................. 35
Figura 21 – Exemplo de método no servidor com documentação DOCSTRING ......................... 35
Figura 22 - Cliente PYTHON para solicitar os comentários DOCSTRING dos métodos cadastrados
no servidor .................................................................................................................................. 35
Figura 23 - Saída padrão após execução do código da figura 4.8 ............................................... 36
Figura 24 – Exemplo de código XML a ser convertido pelo GRAPHVIZ ....................................... 36
Figura 25 – Código XML da figura 4.10 convertido para linguagem .DOT .................................. 37
Figura 26 – Grafo resultante da conversão do XML da figura 4.10 pelo GRAPHVIZ ................... 37
LISTA DE TABELAS
Tabela 1 – Especificação para obter lista de algoritmos do servidor .......................................... 24
Tabela 2 – Informações de retorno ao solicitar lista de algoritmos do servidor ........................ 24
Tabela 3 – Especificação para obter informações sobre um algoritmo ...................................... 25
Tabela 4 – Informações de retorno ao solicitar descrição de um algoritmo .............................. 25
Tabela 5 – Especificação para solicitar a execução de um algoritmo ......................................... 26
Tabela 6 – Informações de retorno ao solicitar a execução de um algoritmo............................ 26
Tabela 7 – Especificação para solicitar o resultado de uma execução ....................................... 27
Tabela 8 – Informações de retorno ao solicitar o resultado de uma execução .......................... 27
Tabela 9 – Especificação para solicitar informações do horário local do servidor ..................... 27
Tabela 10 – Informações de retorno ao solicitar o horário local do servidor ............................. 28
7
1 INTRODUÇÃO
Desde o artigo publicado por Leonhard Euler em 1736 acerca do problema das
pontes de Konigsberg, considerado o primeiro resultado da Teoria dos Grafos [14],
este importante ramo da Matemática, que estuda a relação entre os elementos de um
conjunto, tem sido explorado significativamente em todas as áreas do conhecimento.
Atualmente muitos problemas podem ser representados através do grafo, como
a busca pelo menor trajeto entre um conjunto de cidades ou mesmo o roteamento de
pacotes em uma rede de computadores. O fato da maioria desses problemas
possuírem uma motivação algorítmica e em sua maior parte com um alto grau de
complexidade na qual a modelagem através do grafo possa facilitar o seu estudo, faz
crescer cada vez mais o interesse da Ciência da Computação por esta área.
O elevado grau de complexidade que muitas vezes acompanham problemas
envolvendo grafos geralmente evidencia a escassez de recurso local e centralizado
para a busca de uma solução em um tempo viável, tornando a necessidade de
distribuição e paralelização de trabalho quase que uma obrigatoriedade para este
processo. Motivado pelo cenário acima citado, propomos ao longo deste documento a
utilização do conceito de WebService unido à Teoria dos Grafos para colaborar com o
processo de pesquisa e estudos nesta área.
1.1 OBJETIVO
O presente trabalho tem como objetivo descrever a arquitetura e estudar o
desenvolvimento da ferramenta PYGRAPH, capaz de executar remotamente os mais
variados tipos de algoritmos relacionados à Teoria dos Grafos.
O PYGRAPH será desenvolvido utilizando o conceito de WebService, podendo
ser integrado a qualquer sistema já existente de forma prática e rápida independente
da linguagem ou plataforma em que estes sistemas estão implementados.
A Figura 1 ilustra a arquitetura do sistema, auxiliando no entendimento do
PYGRAPH. Em resumo, o cliente faz uma requisição que trafega através da Internet
8
até encontrar o servidor, que em seguida processa a requisição e retorna a mensagem
com o resultado da execução solicitada pelo cliente.
Figura 1 – Arquitetura do sistema
9
2 FUNDAMENTOS TEÓRICOS
2.1 PYTHON
2.1.1 Conhecendo a linguagem
A linguagem de programação Python foi criada por Guido van Rossum no fim
da década de 1980 e meados da década de 1990. É uma linguagem de múltiplos
paradigmas - orientada a objetos e estruturada, interpretada, com tipagem dinâmica e
multiplataforma. Ainda, é considerada de alto nível por se distanciar dos códigos de
máquina e se aproximar da linguagem humana, com um elevado grau de abstração
[15].
Apesar de não ser especificado formalmente em sua totalidade, o Python
possui uma sintaxe bastante clara e concisa capaz de combinar sua biblioteca padrão
com vários frameworks desenvolvidos por terceiros. Pode ser descrita como uma
linguagem muito simples, intuitiva e poderosa, em que prevalece o esforço do
programador sobre o esforço computacional, ou seja, podemos dizer que prioriza a
legibilidade sobre a velocidade de execução.
Atualmente o Python está disponível nas mais diversas plataformas, como o
MacOS, UNIX, Windows e até celulares e tablets. Para sistemas operacionais que não
suportam a linguagem nativamente basta que estes possuam um compilador C
compatível que o Python será gerado a partir do código fonte utilizando um
interpretador (e.g. CPython), escrito em linguagem C. Desta forma, o código fonte será
traduzido pelo interpretador para o formato bytecode, que é multiplataforma e poderá
ser executado e distribuído sem o fonte original [15].
Algumas das vantagens do Python que contribuíram para o triunfo da
linguagem são:
•
Tem uma sintaxe simples e clara que compõe blocos de código
limpos e legíveis, demarcados pela identação Python;
•
Possui uma biblioteca padrão completa que ainda pode ser
combinada com vários frameworks desenvolvidos por terceiros;
10
•
Linguagem com tipagem dinâmica e ao mesmo tempo
fortemente tipada;
•
Disponibiliza o tratamento de exceções;
•
Possui licença livre aprovada pela OSI e compatível com GPL
que prevê que binários possam ser distribuídos sem a
necessidade de fornecer o código fonte junto.
2.1.2 Potencial do Phyton nos Sistemas WEB
A evolução da tecnologia, de um modo geral, no mundo atual aumentou
significativamente o número de computadores ligados à Internet, e consequentemente,
o número de usuários navegando na rede mundial. Tal evolução fez com que a
interação do usuário com as páginas WEB migrasse das solicitações por conteúdos
estáticos para as interações mais completas, onde o usuário fornece informações ao
servidor que, após processá-las, retorna o conteúdo desejado ao usuário. Isto fez com
que a Internet deixasse de ser apenas um grande repositório de informações e
propagandas para abrigar sistemas de informações mais complexos, de um modo
geral. Desde o momento em que os sistemas de informação puderam ser abrigados
na Internet, esta tecnologia passou a otimizar processos e agregar valor aos produtos
de diversas organizações, ao passo que permitiu a sua utilização para realizar
processamento de dados, permitir a conexão à distância, simplificou rotinas
administrativas, entre outras melhorias.
Como os sistemas de informação são escritos em esquemas de códigos fontes
e estes dependem da linguagem de programação a ser utilizada, a escolha de qual
tecnologia a ser utilizada para este desenvolvimento passou a ser um ponto muito
importante do processo. Diversos cenários tendem a influenciar esta decisão, como a
complexidade que a linguagem exige para integração com outros sistemas ou mesmo
a necessidade de mudanças de layout e design de forma rápida e ágil. Em
contrapartida, há quem prefira a segurança e robustez à agilidade acima citada, entre
outros.
Neste cenário, o Python ganha força a cada dia dentro das organizações que
procuram robustez e produtividade, gerando redução no custo da manutenção de
programas e encorajando os mais diversos nichos de desenvolvedores com a sua
11
ampla gama de bibliotecas e módulos prontos que facilitam tarefas como a conexão
com sistemas legados, desenvolvimento de WebServices, construção de protótipos
que facilmente são convertidos em aplicações, etc. Somado a isso, o fato desta
linguagem ser conhecida como clara em termos de legibilidade, ser bastante modular
e possuir código aberto faz com que diversas empresas como a Nokia, Philips ou
mesmo o Google, que a utiliza em muitos projetos internos, encorajem ainda mais o
seu uso.
Além do exposto acima, o desenvolvimento WEB com Python também é
apoiado por diversas plataformas, como o Mod_Python, o Zope, o TurboGears e o
Django [15] que no geral proporcionam um rápido desenvolvimento de aplicações com
alto índice de modularização e reutilização de código.
2.2 XML
O termo XML, do inglês Extensible Markup Language, é uma recomendação
feita pela W3C para gerar linguagens de marcação, assim como o HTML, permitindo a
criação de documentos organizados hierarquicamente com a principal finalidade de
compartilhar informações facilmente através da Internet. Entre as principais vantagens
desta linguagem podemos destacar o fato dela ser extensível e auto documentada, ou
seja, o usuário poderá criar os seus próprios termos de marcação (“tags”) sem violar
as características e definições da linguagem [2].
O XML surgiu na década de 1990, de uma iniciativa do consórcio W3C, com o
intuito de unir a flexibilidade do já consagrado SGML e a simplicidade do HTML,
reunindo alguns princípios como: possibilidade de criar marcadores sem limitações,
simplicidade e legibilidade tanto para humanos como para computadores, possibilitar a
criação de definições para validação da estrutura do documento (como o DTD ou o
XML SCHEMA) além de ser formal e conciso no modo de processar e armazenar as
informações [5].
Desde
o
seu
surgimento,
em
um
ambiente
que
proporciona
aos
desenvolvedores e empresas em geral a possibilidade de criação de diversos formatos
proprietários, a aceitação do XML cresce a cada dia. Atualmente, podemos destacar o
uso desta linguagem de marcação nas seguintes aplicações: transferências de dados
12
entre sistemas de informações, codificação e padronização de documentos e
integração entre sistemas WEB de diferentes plataformas [1].
A Figura 2 apresenta um exemplo simples da sintaxe do XML, onde é possível
reconhecer as principais características da linguagem tais como o conceito de
marcadores, hierarquia e padronização.
Figura 2 – Exemplo de código XML
A simplicidade da sintaxe e o grande poder de portabilidade foram
determinantes na escolha do XML como o padrão de transferência de dados no
sistema proposto por este documento. Veremos como será este uso mais adiante.
2.3 WebServices
A popularização da internet e demais tecnologias tem proporcionado e ao
mesmo tempo gerado uma necessidade cada vez maior de troca de informações entre
as pessoas, empresas e sistemas de informação em geral. Foi neste cenário que
surgiu uma solução chamada de WebService, tecnologia que permite a comunicação
entre sistemas de plataformas distintas fornecendo os mais diversos serviços na rede
global [9].
O surgimento dos serviços via WEB abriu uma grande gama de possibilidades
para os empreendedores e desenvolvedores ao passo que permite a troca de
13
informações entre sistemas de plataformas diferentes [11], escritos em linguagens
distintas que posteriormente serão traduzidas para um formato padrão além de
proporcionar uma comunicação automatizada e ao mesmo tempo segura, pois não
necessita da intervenção humana para ser realizada. No geral, eles não fornecem uma
interface gráfica e sim apenas uma interface de entrada e saída de dados.
Outra característica importante a ser observada com o advento desta
tecnologia é a possibilidade de dividir o sistema em módulos proporcionando uma
forma de computação distribuída, permitindo aos desenvolvedores facilidades de
manutenção e upgrade de tecnologia dentro dos diversos módulos do sistema desde
que cada um respeite o formato padrão de comunicação.
A arquitetura de um WebService é simples, composta por dois personagens: o
produtor de serviços – entidade responsável por desenvolver o serviço em um formato
padrão e registrá-lo na rede através de um URI (Uniform Resource Identifier), ou seja,
um identificador para o recurso recém publicado para que os usuários possam utilizálo; e o consumidor de serviços – responsável por utilizar as ferramentas
disponibilizadas pelo produtor [10]. A dinâmica de funcionamento pode ser observada
na Figura 3:
Figura 3 – Visão geral de um WebService
14
Algumas tecnologias se destacam na arquitetura do WebService, como o
protocolo de transporte de dados, o padrão de formatação de dados e o protocolo de
encapsulamento de dados [9]:
•
Os protocolos de transporte de dados mais utilizados atualmente são o HTTP
para conexões normais e o HTTPS para conexões seguras;
•
O padrão de formatação de dados mais utilizado atualmente é o XML, que
também pode ser substituído por JSON, YAML e Properties, entre outros;
•
O protocolo de encapsulamento mais utilizado atualmente é o SOAP, que
também pode ser substituído por CORBA, XML-RPC, REST, entre outros.
2.4 O Protocolo XML-RPC
O RPC (Remote Procedure Calls) é um protocolo ou tecnologia que permite a
comunicação entre processos possibilitando um programa de computador chamar uma
rotina que será executada em outro espaço de endereçamento, geralmente em um
acesso remoto. Desta forma, o XML-RPC, criado por Dave Winer em 1998, nada mais
é do que o próprio protocolo RPC codificado em XML e utilizando o protocolo HTTP
para transporte de mensagens. Ele é mais enxuto que outras implementações como o
RMI, CORBA ou o SOAP [8], além de ser mais adequado e flexível no tipo de
operações e chamadas de métodos adotadas pelo PYGRAPH.
O funcionamento do XML-RPC é muito simples, nele o cliente envia uma
requisição HTTP codificada em XML ao servidor solicitando a execução de algum
procedimento que após a execução retorna o conteúdo também codificado em XML ao
cliente. Esta sistemática de funcionamento permite que o cliente consuma os recursos
fornecidos pelo servidor sem se preocupar com a tecnologia utilizada na
implementação destes. Por exemplo, podemos ter uma versão do servidor em Java e
do cliente em PHP realizando uma comunicação entre si.
Em cada chamada de execução que o cliente realiza no servidor vários
parâmetros de entrada podem ser enviados, mas apenas um será retornado. No
entanto, os tipos de parâmetros disponíveis permitem que vários valores sejam
aninhados em uma estrutura, fazendo com que a restrição no número de parâmetros
de retorno possa ser superada facilmente.
15
2.5 Grafos
Os grafos podem ser definidos como uma representação entre as relações dos
elementos de dados de um certo conjunto. A definição formal de um grafo G=(V,A) [12]
pode ser observada abaixo:
V - conjunto não vazio de vértices do grafo;
A - conjunto de pares não ordenados a=(x,y), sendo x e y pertencentes a V,
que representam as arestas do grafo.
Representação Gráfica
Tipicamente o grafo é representado como um conjunto de pontos (vértices)
interligados por um conjunto de retas (arestas) [14], como mostra a Figura 4:
Figura 4 – Exemplo de um grafo
16
Alguns tipos especiais de grafos
•
Grafo simples: é um grafo com no máximo uma aresta entre cada par de
vértices distintos e sem a presença de laços, ou seja, arestas que ligam um
vértice a ele mesmo [14]. Este tipo de grafo pode ser não-direcionado, como
mostrado na Figura 5, ou direcionado, em que cada aresta possui um indicador
que representa o seu sentido.
Figura 5 – Exemplo de um grafo simples
•
Grafo completo: é o grafo simples em que, para cada vértice do grafo, existe
uma aresta conectando este vértice a cada um dos demais [14]. A Figura 6
apresenta um exemplo de um grafo completo:
Figura 6 – Exemplo de um grafo completo
17
•
Grafo vazio: é o grafo cujo conjunto de arestas é vazio [14]. A Figura 7
apresenta um exemplo de um grafo vazio:
Figura 7 - Exemplo de um grafo vazio
•
Grafo trivial: é o grafo que possui apenas um vértice e nenhuma aresta [14]. A
Figura 8 apresenta um exemplo de um grafo trivial:
Figura 8 – Exemplo de um grafo trivial
18
•
Grafo regular: é um grafo em que todos os vértices têm o mesmo grau, ou seja,
o número de arestas incidentes para com o vértice, com os laços contados
duas vezes [14]. A Figura 9 apresenta um grafo regular:
Figura 9 - Exemplo de um grafo regular
19
3 O PYGRAPH
Após esta breve introdução de conceitos, estamos aptos a nos aprofundar
ainda mais na arquitetura do sistema proposto por este trabalho, o PYGRAPH.
Em resumo, o sistema trata-se de um WebService desenvolvido em linguagem
PYTHON, comunicação realizada através do protocolo XML-RPC e utilização do
formato XML para padronizar a entrada e saída de dados. O objetivo deste sistema é
viabilizar a execução de algoritmos sobre GRAFOS de forma remota através da WEB
sem que os sistemas clientes precisem preocupar-se com a plataforma ou linguagem
em que o servidor está escrito, preocupando-se apenas em enviar e receber conteúdo
no formato indicado e protocolo estabelecido pelo servidor.
A Figura 10 apresenta uma ilustração das interações geradas com o sistema
PYGRAPH:
Figura 10 – A arquitetura do PYGRAPH
20
3.1 Organização do Sistema
A estrutura de pastas do sistema após a implementação no servidor é
mostrada na Figura 11:
Figura 11 – Organização do sistema
Descrição do conteúdo:
•
SERVER – Diretório responsável por armazenar todos os arquivos necessários
para execução do Webservice.
o server.py – É o arquivo onde o código-fonte do WebService está
localizado, é ele quem inicia o serviço na rede.
o readme.txt – Este arquivo explica como executar o Webservice,
tornando-o apto a receber requisições dos clientes.
o RESULTS – Diretório que irá armazenar os resultados das execuções
realizadas no servidor, todos em formato XML. Este diretório foi
utilizado para fornecer a de persistência de dados ao usuário, que
21
poderá visualizar o resultado de uma execução já realizada a qualquer
momento.
o ALGORITHM – Diretório que irá armazenar todos os algoritmos
cadastrados no servidor.
Algorithmlist.txt – É o arquivo responsável por armazenar o
nome dos algoritmos e os seus respectivos códigos. Este
arquivo funciona apenas como uma lista simples, ele não irá
armazenar qualquer descrição ou código fonte do algoritmo
PASTAS
NOMEADAS
COM
O
IDENTIFICADOR
DO
ALGORITMO (1, 2, 3, etc..) – Diretórios responsáveis por
armazenar todos os dados relativo ao algoritmo em questão,
incluindo
arquivos
executáveis
e
arquivos
de
inclusão
necessários para a execução.
• run.py – É obrigatório e deve ser criado no momento da
adição do algoritmo ao servidor. Este é o arquivo
invocado pelo servidor para execução do algoritmo
selecionado, ele recebe como entrada os parâmetros
especificados e obrigatoriamente exibe o resultado da
execução na saída padrão, que posteriormente será
capturado pelo processo que o invocou. Apesar de ser
desenvolvido em PYTHON, através deste arquivo o
desenvolvedor poderá solicitar a execução de algoritmos
escritos em inúmeras linguagens através da biblioteca
SUBPROCESS, capaz de executar comandos externos
(SHELL).
• info.txt – Este arquivo é obrigatório e deve ser criado no
momento da adição do algoritmo ao servidor. É ele que
irá armazenar a especificação de execução do algoritmo
e uma breve descrição a respeito do mesmo.
• FONTS – Diretório auxiliar que irá armazenar os códigos
fontes do algoritmo a que esta pasta está associada.
22
3.2 Formato
Padrão de Entrada e Saída
O codificador escolhido para padronizar a entrada e saída de dados no
PYGRAPH foi o formato XML, por ser um dos padrões mais difundidos no mundo para
este tipo de uso e possuir vantagens como ser extensível e auto-documentado [6].
O arquivo deve estar formatado de acordo com a seguinte especificação:
Codificação - UTF-8
TAG <data> - todo o conteúdo deve estar dentro deste marcador, que inclusive
poderá abrigar vários grafos de uma só vez.
TAG <graph> - cada marcador como este irá delimitar o conteúdo de um grafo dentro
do arquivo XML.
TAG <node> - cada marcador como este irá delimitar o conteúdo referente a certo
vértice do grafo além de conter as propriedades (atributos) desse vértice, como: cor,
forma, tamanho, entre outros. Os atributos de cada nó podem ser adicionados ou
editados de acordo com as necessidades e especificações do algoritmo que será
executado no servidor.
TAG <edge> - sempre associado ao marcador <node>, ele irá conter as propriedades
(atributos) de uma aresta ligada ao vértice a que este marcador está associado. Note
que apesar de cada aresta estar escrita duas vezes no exemplo da Figura 12 para
facilitar o entendimento da relação entre os vértices, não é necessário escrevê-la em
duplicidade na entrada que será fornecida ao sistema.
TAG <value> - pode estar associado ao marcador <node> ou ao marcador <edge>,
desempenhando as seguintes funções:
•
Quando associado ao marcador <node> - irá armazenar o valor do nó.
•
Quando associado ao marcador <edge> - irá armazenar o valor do nó
adjacente ao nó que o marcador pai está associado.
23
Um exemplo de arquivo XML compatível com a especificação acima pode ser
visto na Figura 12.
Figura 12 - Exemplo de XML aceito pelo PYGRAPH
O XML acima irá gerar o grafo apresentado na Figura 13:
Figura 13 – Grafo gerado pelo XML da figura 3.3
24
Como podemos observar no exemplo da figura 12, o formato XML facilita
bastante a representação de um grafo tornando-se um arquivo de fácil manipulação
pelo computador e de certa forma legível para os seres humanos.
3.3 Recursos do Sistema
A primeira versão do PYGRAPH disponibiliza dentro do seu núcleo (server.py)
as funções descritas a seguir.
3.3.1 Obter Lista de Algoritmos do Servidor
Este recurso tem como objetivo informar ao usuário a lista de nomes e códigos
de todos os algoritmos que estão implementados no servidor. É com este código que o
usuário irá identificar o algoritmo que deseja executar sobre um ou mais grafos
fornecidos como parâmetro.
Método de consumo deste recurso:
Nome do Método
Parâmetros
algorithmList()
Nenhum
Tabela 1 – Especificação para obter lista de algoritmos do servidor
Resposta fornecida pelo servidor:
Retorno
algorithmList
String com o código e o
nome de cada algoritmo
cadastrado no servidor,
separados linha a linha.
Tabela 2 – Informações de retorno ao solicitar lista de algoritmos do servidor
25
3.3.2 Obter Informações de um Algoritmo Específico
Este recurso tem como objetivo informar ao usuário as características de um
algoritmo cadastrado no servidor. Através deste método o usuário irá receber uma
breve descrição além de todas as informações necessárias para solicitar a execução
do mesmo fornecendo os parâmetros corretos.
Método de consumo deste recurso:
Nome do Método
Parâmetros
algorithmInfo()
algorithmId
Número inteiro corresponde ao
identificador do algoritmo.
Tabela 3 – Especificação para obter informações sobre um algoritmo
Resposta fornecida pelo servidor:
Retorno
algorithmDescription
String
com
toda
a
especificação de execução do
algoritmo além de uma breve
descrição a seu respeito.
Tabela 4 – Informações de retorno ao solicitar descrição de um algoritmo
3.3.3 Executar um Algoritmo sobre um Grafo
Este recurso tem como objetivo executar um algoritmo em uma entrada
fornecida pelo cliente.
Este é o método mais importante do sistema e consequentemente quem mais
recebeu atenção durante o processo de desenvolvimento do sistema. Uma das
dificuldades encontradas aqui foi que toda a estrutura de armazenamento e execução
dos algoritmos localizados no servidor precisou ser desenvolvida a parte, ao contrário
de soluções implementadas em outras linguagens como o PHP e framework .NET em
que o servidor de hospedagem fica responsável por criar (ou reconhecer) a estrutura
de pasta dos arquivos dentro do servidor. Outro fator que podemos destacar foi o fato
de termos adotado a facilidade de adição de novos algoritmos como o mais importante
princípio durante o desenvolvimento deste método, algo que em parte foi facilitado
26
pelo método SUBPROCESS do PYTHON e sua função de chamadas de comandos
externos à linguagem, permitindo que novos algoritmos sejam desenvolvidos em
qualquer linguagem compatível com a plataforma em que o sistema está hospedado.
Método de consumo deste recurso:
Nome do Método
Parâmetros
algorithmExecute ()
algorithmId
Número inteiro corresponde ao
identificador do algoritmo a ser
executado.
paramsList
Lista
com
os
parâmetros
necessários para execução do
algoritmo
pelo
servidor
(incluindo o grafo em XML). As
informações a respeito dos
parâmetros necessários podem
ser obtidas através do método
algorithmInfo.
Tabela 5 – Especificação para solicitar a execução de um algoritmo
Resposta fornecida pelo servidor:
Retorno
executionId
Número
inteiro
com
o
identificador da execução que
acabou de ser realizada no
servidor.
executionResult
String com o XML resultante da
execução do algoritmo.
Tabela 6 – Informações de retorno ao solicitar a execução de um algoritmo
27
3.3.4 Recuperar o Resultado de uma Execução
Este recurso tem como objetivo retornar ao cliente o resultado (XML) de uma
execução realizada previamente no servidor. Isto irá criar uma persistência de dados
que pode ser muito interessante em casos como queda da rede durante uma
execução ou caso o usuário deseje acessar o resultado em locais diferentes sem ter
que esperar a execução novamente.
Método de consumo deste recurso:
Nome do Método
Parâmetros
resultReturn()
executionId
Número
inteiro
com
o
identificador de uma execução
realizada previamente.
Tabela 7 – Especificação para solicitar o resultado de uma execução
Resposta fornecida pelo servidor:
Retorno da Função
executionResult
String
contendo
o
XML
correspondente ao resultado
da execução.
Tabela 8 – Informações de retorno ao solicitar o resultado de uma execução
3.3.5 Obter informações de horário local do servidor
Este recurso pode ser utilizado pelos clientes como função auxiliar dentro do
processo de execução de outros algoritmos. Este recurso pode ser utilizado para a
medição de desempenho entre diferentes execuções ou algoritmos, por exemplo.
Método de consumo deste recurso:
Nome do Método
Parâmetros
currentTime ()
Nenhum
Tabela 9 – Especificação para solicitar informações do horário local do servidor
28
Resposta fornecida pelo servidor:
Retorno
timeNow
String contendo a data e hora
local do servidor no formato
DD-MM-YYYY HH:MM:SS
Tabela 10 – Informações de retorno ao solicitar o horário local do servidor
3.3.6 Outras funções Importantes
Algumas outras funções importantes são fornecidas pela própria linguagem em
que o sistema foi desenvolvido em conjunto com o protocolo utilizado para a
comunicação entra o cliente e o servidor. Abaixo listamos algumas destas funções.
Chamada de múltiplos procedimentos
O usuário poderá solicitar a execução de vários algoritmos (ou qualquer outro
método do servidor) de uma só vez recebendo os resultados em apenas uma resposta
do servidor. Isso pode gerar uma série de vantagens como a diminuição da
concorrência e congestionamento do servidor além da diminuição do trafego da rede.
Visualizar DOCSTRING dos métodos
O PYTHON fornece uma espécie de documentação automática dos métodos e
classes. Para utilizar essa função basta que o desenvolvedor do Webservice coloque
os comentários entre uma sequência de três aspas duplas. Para visualizar os
comentários de um método, o usuário responsável pelo sistema cliente deverá utilizar
o comando system.methodeHelp() passando como parâmetro o nome do método.
Visualizar nome de todos os métodos do servidor
O PYTHON também disponibiliza uma função para o cliente obter o nome de
todos os métodos cadastrados no servidor, a system.listMethods(). O retorno da
função será uma lista com o nome de cada método do servidor.
29
3.4 Cadastrar Novos Algoritmos no Sistema
Como dito anteriormente, a facilidade de adição de novos algoritmos ao
servidor
foi
considerado
um
dos
princípios
mais
importantes
durante
o
desenvolvimento do sistema. Vamos agora conhecer como realizar esse processo de
forma simples e rápida.
Para cadastrar um novo algoritmo, o usuário deve ter em mente que o
desenvolvimento pode ser feito em qualquer linguagem de programação desde que o
programa seja executado através da linha de comando SHELL. Desta forma, ele irá
salvar todo o conteúdo necessário dentro do servidor e este conteúdo será invocado
através da linguagem PYTHON.
Descrição do processo por etapas:
•
Abrir o arquivo algorithmList.txt dentro do diretório ALGORITHM;
•
Editar o arquivo criando uma linha ao final do arquivo com o código e nome do
algoritmo, separados por hífen (Ex: 1 – Busca em Largura).
•
Criar uma pasta com o identificador do algoritmo dentro do diretório
ALGORITHM;
•
Dentro da pasta recém criada, criar o arquivo info.txt, responsável por conter as
especificações necessárias para a execução do algoritmo além de uma breve
descrição a respeito do mesmo.
•
Ainda dentro deste mesmo diretório, criar o arquivo run.py que será
responsável por realizar a execução do algoritmo. Este arquivo será invocado
pelo processo servidor recebendo como entrada os parâmetros especificados
no arquivo info.txt e deverá exibir o resultado da execução (XML) na saída
padrão do sistema. Fica totalmente a critério do usuário a escolha da
linguagem de programação em que o sistema será desenvolvido, já que o
arquivo PYTHON poderá executar comandos externos como mostrado no
trecho de código da imagem abaixo:
•
Ainda dentro deste mesmo diretório, criar a pasta FONTS em que deverão ser
armazenados os códigos fontes do algoritmo recém cadastrado no servidor.
30
Após a realização dos passos descritos acima, todos os sistemas clientes serão
capazes de solicitar a execução do novo algoritmo.
3.5 Algoritmos implementados no servidor
Para exemplificar a facilidade de uso do sistema PYGRAPH, foram
disponibilizados dois algoritmos no servidor:
•
Algoritmo de Busca em Largura – É um algoritmo exaustivo de busca em
grafos que após a execução todos os vértices e arestas do grafo terão sido
visitados. O processo de busca tem início no vértice raiz e se expande a todos
os vértices vizinhos, ou seja, vértices com distância 1 do nó raiz.
Posteriormente, o processo de busca irá explorar todos os vizinhos dos
vértices visitados no passo anterior, ou seja, todos os vértices com distância
dois do nó raiz. O processo continua até que o alvo da busca seja encontrado
[19]. Para garantir que um nó não seja visitado mais de uma vez, o algoritmo
utiliza uma estrutura de dados do tipo fila.
Identificação do algoritmo no servidor: 1
Lista de parâmetros de entrada: Vértice de origem, vértice de destino, grafo no
padrão XML estabelecido.
Saída: Identificador da execução e grafo resultante no padrão XML.
•
Algoritmo de Dijkstra – concebido pelo holandês Edsger Dijkstra em 1956, é um
dos mais famosos algoritmos para cálculo da distância mínima entre vértices
de um grafo com arestas de custo não negativo. Semelhante ao algoritmo de
busca em largura, porém com estratégia gulosa, o algoritmo de Dijkstra
considera uma estimativa inicial C de menores caminhos a partir de um vértice
inicial V. A cada passo da execução busca-se nos vizinhos dos vértices
pertencentes a C o que possui menor distância em relação a V, adicionando-o
a C. O processo é repetido até que todos os vértices alcançáveis por V façam
parte do conjunto C [20].
Identificação do algoritmo no servidor: 2
31
Lista de parâmetros de entrada: Vértice de origem, vértice de destino, grafo no
padrão XML estabelecido.
Saída: Identificador da execução e grafo resultante no padrão XML.
32
4 CLIENTES
O sistema cliente é o motivo da existência dos diversos WebServices
publicados na internet já que eles são os responsáveis por consumir os recursos
disponibilizados por cada serviço deste.
Neste tópico iremos apresentar alguns exemplos de sistemas clientes,
desenvolvidos em PYTHON, consumindo alguns dos principais recursos fornecidos
pelo servidor.
Cliente 1:
Função – Obter a lista de algoritmos cadastrados no servidor.
Código fonte:
Figura 14 – Cliente PYTHON para solicitar lista de algoritmos do servidor
Exemplo de saída padrão:
Figura 15 – Saída padrão após execução do código da figura 4.1
33
Cliente 2:
Função – Obter a descrição de algum algoritmo específico cadastrado no
servidor.
Código fonte:
Figura 16 - Cliente PYTHON para solicitar informações de um algoritmo do servidor
Exemplo de saída padrão:
Figura 17 - Saída padrão após execução do código da figura 4.3
Cliente 3:
Função – Solicitar a execução de algum algoritmo cadastrado no servidor.
Código fonte:
Figura 18 - Cliente PYTHON para solicitar a execução de um algoritmo no servidor
34
Exemplo de saída padrão:
A saída do cliente será o arquivo de nome <id da execução> e extensão XML.
Cliente 4:
Função – Resgatar o resultado de alguma execução realizada previamente no
servidor.
Código fonte:
Figura 19 - Cliente PYTHON para solicitar o resultado de uma execução já realizada
Exemplo de saída padrão:
Como no exemplo acima, a saída do cliente será o arquivo de nome <id da execução>
e extensão XML.
Cliente 5:
Função – Realizar vários procedimentos fazendo uma única chamada ao
servidor e recebendo uma única resposta.
35
Código fonte:
Figura 20 - Cliente PYTHON para solicitar a execução de múltiplos procedimentos
Exemplo de saída padrão:
A saída deste cliente será uma lista na variável result com todas as informações
retornadas pelos três procedimentos executados pelo comando multirequest.
Cliente 6:
Função – Obter os comentários de desenvolvimento de um determinado
método.
Código fonte:
Figura 21 – Exemplo de método no servidor com documentação DOCSTRING
Figura 22 - Cliente PYTHON para solicitar os comentários DOCSTRING dos métodos
cadastrados no servidor
36
Exemplo de saída padrão:
Figura 23 - Saída padrão após execução do código da figura 4.8
Ferramenta Auxiliar - GRAPHVIZ:
Função – Como o retorno de todas as execuções de algoritmo realizadas no
servidor possui o formato XML, desenvolvemos nos sistemas clientes uma ferramenta
auxiliar capaz de converter o arquivo de retorno em uma imagem JPEG, facilitando a
conferência do resultado por parte do usuário. Para realizar esta conversão foi
utilizada a ferramenta GRAPHVIZ, que recebe como entrada o arquivo XML convertido
em linguagem .DOT e o transforma na imagem do grafo resultante. Abaixo um
exemplo da utilização desta ferramenta.
A Figura 24 apresenta o XML de entrada:
Figura 24 – Exemplo de código XML a ser convertido pelo GRAPHVIZ
37
A Figura 25 apresenta o arquivo .DOT resultante do XML:
Figura 25 – Código XML da figura 4.10 convertido para linguagem .DOT
A Figura 26 apresenta o resultado final da conversão:
Figura 26 – Grafo resultante da conversão do XML da figura 4.10 pelo GRAPHVIZ
38
5 CONCLUSÃO
Através do desenvolvimento do sistema proposto por este documento, o
PYGRAPH, conseguimos consolidar muitos dos conhecimentos adquiridos ao longo
do curso além de nos deparamos com novos conceitos acerca do desenvolvimento de
ferramentas para WEB.
O Python provou ser uma linguagem muito robusta, de fácil aprendizado e com
um enorme grupo de seguidores ao redor do mundo, capazes de desenvolver e
compartilhar as mais diversas ferramentas proporcionando um desenvolvimento de
aplicações cada vez mais prático e rápido.
Nas pesquisas realizadas para construirmos a arquitetura do sistema, nos
deparamos com a ausência quase completa de ferramentas como esta na Internet,
fato este que nos motivou ainda mais durante o desenvolvimento, pois acreditamos
que a disponibilização de uma ferramenta acesso remoto para execução dos mais
complexos algoritmos da Teoria dos Grafos pode ser de grande valia para os usuários
ao redor de mundo.
Reunimos também algumas sugestões para trabalhos futuros visando ampliar a
estrutura e as funcionalidades do PYGRAPH, como:
•
Validação do XML – Implementar a validação do arquivo de entrada fornecido
pelo usuário implica em economizar a utilização de recursos de forma
desnecessária no servidor, como uma busca por uma solução inexistente em
um XML que está mal formado. A validação também poderia ser empregada na
saída fornecida pelo algoritmo, prevenindo o envio de uma solução incompleta
ao usuário que solicitou a requisição.
•
Remoção do arquivo RUN.py – Adotado como ponto inicial de cada execução
no servidor, a presença obrigatória do arquivo run.py pode ser eliminada
facilmente através da utilização dos comandos SHELL para execução dos
algoritmos. Para isso, basta que no momento de cadastro do algoritmo seja
armazenada a linha de comando necessária para a execução.
•
Servidor Distribuído – Na arquitetura do PYGRAPH é perfeitamente possível
integrar um módulo cliente dentro do Webservice, desta forma podemos criar
um servidor com a função apenas de gerenciar as requisições dos clientes e
39
solicitar a execução dos algoritmos em outros servidores remotos, podendo
fazer também um balanço de carga e diminuindo a carga empregada no
Webservice pela execução de algoritmos locais.
40
6 REFERÊNCIAS
[1] Objectivos e Possíveis Usos do XML. Disponível
em:<http://omundodaprogramacao.com/objectivos-e-possiveis-usos-do-xml/>. Acesso
em: 21 dez. 2012.
[2] Pereira, Ana Paula. O que é XML? Disponível
em:<http://www.tecmundo.com.br/programacao/1762-o-que-e-xml-.htm>. Acesso em:
21 dez. 2012.
[3] Definição conceitual do XML. Disponível
em:<http://www.gta.ufrj.br/grad/00_1/miguel/link5.htm>. Acesso em: 21 dez. 2012.
[4] Significado de XML. Disponível em:<http://www.significados.com.br/xml/>. Acesso
em: 23 dez. 2012.
[5] WIKIPEDIA. XML. Disponível em:<http://pt.wikipedia.org/wiki/XML>. Acesso em: 23
dez. 2012.
[6] Macoratti, José Carlos. XML – Introdução e conceitos básicos. Disponível
em:<http://www.macoratti.net/xml.htm>. Acesso em: 10 jan. 2013.
[7] Python XML-RPC. Disponível em:
<http://wmagician.wordpress.com/2010/07/23/python-xml-rpc/.>. Acesso em: 10 jan.
2013.
[8] Spanhol, Fábio Alexandre. XML-RPC: Tópicos Introdutórios. Disponível
em:<http://www.slideshare.net/_photon_/xmlrpc-13067431>. Acesso em: 16 jan. 2013.
[9] WIKIPEDIA. Web service. Disponível
em:<http://pt.wikipedia.org/wiki/Web_service>. Acesso em: 16 jan. 2013.
[10] Reckziegel, Maurício. Entendendo os WebServices. Disponível
em:<http://imasters.com.br/artigo/4245/web-services/entendendo-os-webservices/>.
Acesso em: 20 jan. 2013.
41
[11] O que é Web Service? Disponível
em:<http://www.oficinadanet.com.br/artigo/447/o_que_e_web_service>. Acesso em:
20 jan. 2013.
[12] WIKIPEDIA. Grafo. Disponível em:<http://pt.wikipedia.org/wiki/Grafo>. Acesso em:
22 jan. 2013.
[13] Conceito Básicos da Teoria de Grafos. Disponível
em:<http://www.inf.ufsc.br/grafos/definicoes/definicao.html>. Acesso em: 25 jan. 2013.
[14] WIKIPEDIA. Teoria dos grafos. Disponível
em:<http://pt.wikipedia.org/wiki/Teoria_dos_grafos>. Acesso em: 25 jan. 2013.
[15] WIKIPEDIA. Python. Disponível em:<http://pt.wikipedia.org/wiki/Python>. Acesso
em: 25 jan. 2013.
[16] WIKIPEDIA. XML-RPC. Disponível em:<http://pt.wikipedia.org/wiki/XML-RPC>.
Acesso em: 10 fev. 2013.
[17] Winer, Dave. XML-RPC Specification. Disponível
em:<http://xmlrpc.scripting.com/spec.html>. Acesso em: 10 fev. 2013.
[18] Garcia, Luís Fernando Fortes. RPC - Remote Procedure Call. Disponível
em:<http://penta.ufrgs.br/rc952/trab1/rpc.html>. Acesso em: 12 fev. 2013.
[19] WIKIPEDIA. Busca em Largura. Disponível
em:<http://pt.wikipedia.org/wiki/Busca_em_largura>. Acesso em: 28 fev. 2013.
[20] WIKIPEDIA. Algoritmo de Dijkstra. Disponível
em:<http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra>. Acesso em: 28 fev. 2013.