Project for the application of the Prim's Algorithm in the Algorithm and Data Structures course of the Information Systems (SI) at the Center for Informatics (CIN) - UFPE.

Firstly, please ensure that you have met the following requirements (specific instructions for running in VSCode):

• You have installed the python plugin
• You have installed the anaconda terminal plugin
• You have installed the pandas library using the following command:

pip install pandas

• You have installed the pygame library using the following command:

pip install pygame

• You have installed the Gephi software on your machine, in the following path (only necessary for visualizing the final minimum spanning tree):

C:\Program Files

• Modify the path to the Gephi executable in the Main.py file if necessary
• When Gephi initializes, some configurations will still be required. You can observe them from Figure 4 to 7

(back to top)

In 2050, it was a challenging period for humanity. An unknown virus emerged, triggering a new global pandemic. Modern science and medicine were in a race against time to find a cure for this invisible threat spreading across entire continents. After the collaboration of various research centers, a crucial discovery was made: there was a specific gene that, when combined with other properties, could be used to create the cure. And this genetic key was hidden near the almost extinct mangrove regions in the state of Pernambuco, Brazil.
To find the required human gene, scientists had to collect various samples detailing the correlation between genes and the degree of infection to which they were exposed. But there was an additional challenge: they had to find the most resistant sample, the one that could withstand virus mutations and become the basis for the cure.
To achieve this, scientists applied the Prim algorithm, a powerful minimum spanning tree tool. This allowed them to efficiently and effectively explore the vast array of collected samples, identifying crucial patterns and connections in their quest for the gene of hope.
Finally, after countless tries, sample collections, and days of intensive study, the foundational gene for the cure was found. With the discovery in hand, scientists could begin working on the solution. It was a complex and time-consuming process, but hope was rekindled. Gradually, the cure began to be distributed worldwide, and the pandemic came to an end.

(back to top)

The database used in this work was the SC-CC (Biological Networks), which contains information about functional associations between genes, including edge weights. To manipulate the database, the file was transformed into CSV format, and the data was separated into: Gene 1 (vertex 1), Gene 2 (vertex 2), and Degree of Infection (weight).

(back to top)

Prim's Algorithm - Minimum Spanning Tree

Stages:

1. Database Processing and Graph Creation;
2. Prim Algorithm Creation and Calculation Systems;
3. Graph Visualization and Graphic Interface;
4. Readme and Project Report.

• Pandas: We utilized the pandas library for reading the CSV database, converting the file into a DataFrame, and exploring each item within the DataFrame to create the graph.

• Pygame: We used the Pygame library for sound addition.

• Random: We employed the random library to generate random numbers during calculations for deaths.

• Tkinter: We applied the tkinter library to create user graphical user interfaces (GUIs).

Link to the repository:

https://github.com/luiz-linkezio/Algoritmo_PRIM-Algoritmo_e_Estrutura_de_Dados-SI-CIN-UFPE-2023.1  

(back to top)

The program uses the selected database in CSV format and converts it into a graph to find the minimum spanning tree through the Prim's Algorithm. The chosen database needed to be transformable into a connected, weighted, and undirected graph to ensure error-free processing.
Consequently, after processing the CSV file and forming the minimum spanning tree, the program calculates the number of pandemic deaths (total and per day) during the search process and how long it took to find the foundational gene for the cure. Following these results, the program provides a visualization of the minimum spanning tree graph using the Gephi software.

(back to top)

(back to top)

Dayane Lima - [email protected]
Luiz Henrique - [email protected]

(back to top)

Projeto de aplicação do Algoritmo de Prim da cadeira de Algoritmo e Estrutura de Dados do curso de Sistemas de Informação (SI) do Centro de Informática (CIN) - UFPE.

Antes de começar, verifique se você atendeu aos seguintes requisitos (instruções específicas para rodar no VSCode):

• Você instalou o puglin python
• Você instalou o puglin anaconda terminal
• Você instalou a biblioteca pandas através da seguinte chamada:

pip install pandas

• Você instalou a biblioteca pygame através da seguinte chamada:

pip install pygame

• Você instalou o software Gephi na sua máquina, no caminho (necessário apenas para conseguir visualizar árvore geradora mínima final):

C:\Arquivos de Programas

• Mude o caminho para o executável do Gephi no Main.py do código, se necessário
• Quando for aberto o Gephi, ainda serão necessárias algumas configurações. Você pode observá-las da Figura 4 a 7

(voltar ao topo)

Era o ano de 2050, um período desafiador para a humanidade. Um vírus desconhecido, surgiu desencadeando uma nova pandemia global. A ciência e a medicina modernas estavam em uma corrida contra o tempo para encontrar uma cura para essa ameaça invisível que se espalhava por continentes inteiros. Após a união de diversos centros de pesquisa, foi feita uma descoberta crucial: havia um gene específico que, quando combinado com outras propriedades, poderia ser utilizado para criar a cura. E essa chave genética, estava escondida próxima às regiões de manguezais, quase extintas, no Estado de Pernambuco, no Brasil.
Para encontrar o gene humano necessário, os cientistas teriam que coletar diversas amostras detalhando a correlação entre os genes e o grau de infecção ao qual estavam expostos. Mas havia um desafio adicional: eles tinham que encontrar a amostra mais resistente, aquela que poderia resistir às mutações do vírus e se tornar a base para a cura.
Para isso, os cientistas aplicaram o algoritmo de Prim, uma ferramenta poderosa de árvore geradora mínima. Isso lhes permitiu explorar a vasta gama de amostras coletadas de forma eficiente e eficaz, identificando padrões e conexões cruciais em sua busca pelo gene da esperança.
Finalmente, depois de inúmeras tentativas e erros, coletas de amostras e dias inteiros de estudo, foi encontrado o gene base para a cura. Com a descoberta em mãos, os cientistas puderam começar a trabalhar na produção da solução. Era um processo complexo e demorado, mas a esperança renasceu. Progressivamente, a cura começou a ser distribuída pelo mundo, e a pandemia foi cessada.

(voltar ao topo)

A base de dados utilizada neste trabalho foi a SC-CC (Biological Networks) que possui as informações das associações funcionais entre genes, contendo o peso nas arestas. Para a manipulação da base, foi transformado o arquivo para CSV e feito a separação dos dados em: Gene 1 (vértice 1), gene 2 (vértice 2) e Grau de Infecção (peso).

(voltar ao topo)

Algoritmo de Prim - Árvore geradora mínima

Etapas:

1. Tratamento do Banco de Dados e criação de Grafo;
2. Criação do Algoritmo de Prim e sistemas de cálculos;
3. Visualização do Grafo e Interface Gráfica;
4. Readme e Relatório do Projeto.

• Pandas: Utilizamos a biblioteca pandas para leitura do banco de dados em CSV, transformação do arquivo em DataFrame e exploração de cada item do DataFrame para criação de grafo.

• Pygame: Fizemos uso da biblioteca pygame para adição de som.

• Random: Usamos a biblioteca random para gerar números aleatórios durante os cálculos de óbitos.

• Tkinter: Aplicamos a biblioteca tkinter para criar interfaces gráficas de usuário (GUI).

Link para o repositório:

https://github.com/luiz-linkezio/Algoritmo_PRIM-Algoritmo_e_Estrutura_de_Dados-SI-CIN-UFPE-2023.1  

(voltar ao topo)

O programa utiliza o banco de dados escolhido em formato CSV e o transforma em um grafo para encontrar a árvore geradora mínima por meio do Algoritmo de Prim. O banco selecionado necessitava poder ser transformado em um grafo conectado, com peso e não direcionado para que a busca ocorresse sem erros.
Dessa forma, após o tratamento do arquivo CSV e formulação da árvore geradora mínima, é realizado o cálculo da quantidade de óbitos da pandemia (total e por dia) durante o processo de busca e quanto tempo levou para encontrar o gene base para formulação da cura. Após esses resultados, o programa apresenta uma visualização do grafo da árvore geradora mínima através do software Gephi.

(voltar ao topo)

(voltar ao topo)

Dayane Lima - [email protected]
Luiz Henrique - [email protected]

(voltar ao topo)