Emparelhamento DOS

Programa para achar o emparelhamento máximo de grafos.

Eu implementei esta interface gráfica em DOS para ter uma pequena idéia da complexidade de cada grafo que usava para testar os meu programa de emparelhamento. Este programa pode carregar um arquivo num formato específico que contém a estrutura de um grafo. Em seguida, pode-se requisitar que este grafo seja desenhado na tela gráfica VGA do sistema operacional DOS. A posição de cada vértice é definida randomicamente. Uma vez o grafo desenhado, pode-se executar o algoritmo de emparelhamento máximo apenas apertando a tecla de espaço. O código que usei foi o mesmo que criei para a minha dissertação de mestrado, só que rodando somente em um processador.

Figura: Desenho de um grafo simples.

Junto dos arquivos de emparelhamento eu inclui os geradores que usei na implementação que fiz durante a minha dissertação de mestrado. O primeiro gerador é chamado de "Cube". Este gerador produz grafos em grade tridimensional com algumas arestas colocadas aleatoriamente. Para gerar este tipo de grafo basta chamar: cube seed cols lins deep extra prob. Onde:

• seed - Semente para a randomizacao.

• cols - Número de colunas.

• lins - Número de linhas.

• deep - Profundidade em camadas.

• extra - Número de arestas colocadas aleatoriamente.

• prob - Probabilidade da existência de uma aresta [0-100].

Figura: Arestas pertencentes ao emparelhamento máximo são pintadas de verde.

O gerador "Groups" gera grafos constrói grafos em anel de sub-grupos. Os grafos são gerados com grupos cujas arestas são ligadas aleatoriamente e estes grupos são ligados entre si formando um anel. Para gerar grafos deste tipo basta chamar: groups seed grps grps_verts arest_lig numb_esp_arest prob. Onde:

• seed - Semente para o gerador de números aleatórios.

• grps - Número de grupos desejados.

• grps_verts - Número de vértices de cada grupo.

• arest_lig - Número de arestas que ligaram dois grupos entre si.

• numb_esp_arest - Número de arestas esperado em cada vértice.

• prob - Probabilidade da existência de aresta [1-100].

Figura: Exemplo de um grafo complexo.

O gerador "Net" gera grafos em grade bidimensional com arestas colocadas aleatoriamente. Para gerar grafos deste tipo basta chamar: net seed lin col ext prob.

• seed - Semente para o gerador de números aleatórios.

• lin - Número de linhas.

• col - Número de colunas.

• ext - Número de arestas que serão colocadas aleatoriamente.

• prob - Probabilidade da existência de cada aresta [0-100].

O gerador "Shuffle" lê um arquivo de grafo e embaralha suas arestas. Ele espera encontrar um arquivo chamado "GRF" no mesmo diretório. Ele lê este arquivo, embaralha as arestas e grava o arquivo em cima do anterior. Para embaralhar um grafo, basta renomear o arquivo para "GRF" e chamar: shuffle seed. Onde:

• seed - Semente do gerador de números randômicos.