Matching for Windows

Program to find the maximum matching of graphs.

I wanted to do a simple graphical interface to exemplify maximum matching of graphs. Than, I started implementing this small program. It can load a file that complies with a specific format and that contains the structure of a graph. After the graph is loaded than the program can drawn the graph on a window. The position of each vertex is defined on a random way. Once the graph is drawn than the Maximum Matching algorithm can be executed. The code that I used was the exact same code that I created for my Master's degree dissertation. The only difference is that it is running on only a single processor. Unfortunately I lost the source code of this program. I remember that formatted my hard disk and I didn't find the source code among my backups.

Picture: Initial window of the matching program.

When the user executes the program than a window will appear. The user can open a file containing the graph information. To load a file the user has to select "File", "Open" and select a file containing a graph. Among the files of the program I include five graphs. Each graph is in a specific file: "Graph 1.grf", "Graph 2.grf", etc. These files are actually common text files. They can be renamed with extension ".txt" and open it on a common text editor. The format of the file is simple. It consists of an initial line containing the letter "p" followed by the number of vertices and of the number of edges. Each edge should be in the lines right after the first line. The letter "a" does the indication of an edge. It than follows the number of the origin vertex and the number of the target-vertex. The vertices numbering start by number 1.

Picture: Execution of the maximum matching on a loaded graph.

When the graph is loaded, the user can show the graph on a graphical representation by selecting the menu options "Show" and "Graph." To execute the Maximum Matching the user has to select "Run" and "Matching". The edges belonging to the maximum matching will be drawn in blue. The size of this window can modified and the vertices alignment can be altered by choosing the menu options "Options", "Alignment" and than "Fixed" for fixed alignment and "Window" for alignment based on the size of the window. To close this window the user can select the option "Action" and than "Return." I didn't implement a help window. If the user selects the "Help" option than he will find only the "About" option. This option only hows the name of the application and my name.

Picture: The size of the graph is limited to the size of the memory.

Among the program files I also include a program to generate of simple complete graphs called "complete.exe". I made this program to do simple tests. To execute the program it is necessary to call the program passing the number of vertices wanted. The configuration of the edges will be done in such a way that all of the vertices are connected by an edge. The generated graph is shown on the screen. To generate a file it is necessary to redirect the output to a file, example: "complete 5 > graph.grf".