Emparelhamento Windows

Programa para achar o emparelhamento máximo de grafos.

Eu queria fazer uma interface gráfica simples para exemplificar emparelhamentos máximos em gráficos. Para isto, comecei a fazer este pequeno programa. Nele se 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 numa janela. A posição de cada vértice é feita randomicamente. Uma vez o grafo desenhado, pode-se executar o algoritmo de emparelhamento máximo. O código que usei foi o mesmo que criei para a minha dissertação de mestrado, só que rodando somente em um processador. Infelizmente eu perdi o código fonte deste programa. Me lembro que formatei o meu disco rígido e não encontrei o código fonte dentro das cópias de segurança que tinha feito. Realmente, foi uma pena.

Figura: Janela inicial do programa de emparelhamento.

Ao executar a aplicação aparecerá uma janela onde se pode pedir para ler arquivo contendo um grafo. Para isto, basta selecionar "File", "Open" e em seguida selecionar um arquivo contendo um grafo. Junto do arquivo do programa eu inclui cinco grafos. Cada grafo se encontra num arquivo: "Graph 1.grf", "Graph 2.grf", etc. Estes arquivos possuem um texto comum. Caso queira ver o conteúdo basta renomear para extensão ".txt" e abrir num editor comum. O formato do arquivo é simples. Ele consite numa linha inicial contendo a letra "p" seguida do número de vértices e do número de arestas. Cada aresta deve estar nas linhas logo abaixo. A indicação da aresta é feita pela letra "a" seguida do número do vértice-origem e o número vértice-destino. Os vértices possuem numeração iniciando em 1.

Figura: Execução do programa de emparelhamento máximo sobre um grafo carregado.

Quando o grafo for carregado, pode-se mostrar sua representação gráfica selecionando as opções de menu "Show" e "Graph". Para executar o emparelhamento máximo basta selecionar "Run" e em seguida "Matching". As arestas pertencentes ao emparelhamento serão desenhadas em azul. Esta janela pode ser redimensionada e o alinhamento das arestas do grafo pode ser alterado escolhendo as opções de menu "Options", "Alignment" e em seguida "Fixed" para alinhamento fixo e "Window" para alinhamento baseado no tamanho da janela. Para fechar esta janela basta selecionar a opção "Action" e "Return". Eu não implementei uma janela de ajuda propriamente dita. Ao se selecionar a opção "Help" se encontrará somente a opção "About", o qual traz o título da aplicação e o meu nome.

Figura: O tamanho do grafo a ser apresentado é limitado ao tamanho da memória.

Junto da programa eu também inclui um programa gerador de grafo completo simples chamado "complete.exe". Eu fiz este programa para fazer testes. Para executar o programa basta chamá-lo passando o número de vértices desejados. A configuração das aresta será feita de tal forma que todos os vértices sejam conectados por uma aresta. O grafo gerado é mostrado na tela. Para gerar um arquivo será necessário redirecionar a saída para um arquivo, exemplo: "complete 5 > graph.grf".