Matching for DOS

Program to find the maximum matching of graphs.

I implemented this graphical interface on DOS environment to have an idea of the complexity of each graph that used to test my matching implementations. This program can load a file with a specific format that contains the structure of a graph. Right after loading the graph the program draws the drawn on the VGA graphic screen of DOS operating system. The position of each vertex is defined randomly. After the graph is drawn the maximum matching algorithm can be executed by pressing the space key. The code that I used to generate the maximum matching is the same that I created on my master's degree dissertation, but executing on only a single processor.

Picture: A simple graph.

Along with the source code I include the graph generators that I used on my master's degree dissertation. The first generator is called "Cubes". This generator produces three-dimensional graphs with randomly generated edges. To create graphs of this type just call: cube seed cols lins deep extra prob. Where:

• seed - Seed for the random number generator.

• cols - Number of columns.

• lins - Number of rows.

• deep -Depth in layers.

• extra -Number of edges.

• prob -Probability of the existence of an edge [0-100].

Picture: Edges belonging to the maximum matching are painted on green.

The generator "Groups" generates graphs with ring of sub-groups. The graphs are generated with groups whose edges are randomly linked and these groups are linked to each other forming a ring. To generate graphs of this type the user can call: groups seed grps grps_verts arest_lig numb_esp_arest prob. Where:

• seed - Seed for the random numbers generator.

• grps - Number of groups.

• grps_verts - Number of vertexes on each group.

• arest_lig - Number of edges linking the groups.

• numb_esp_arest - expected Number of edges on each vertex.

• prob - Probability of the edge existence [1-100].

Picture: Example of a complex graph.

The generator "Net" generates bi-dimensional graphs and the edges are generated randomly. To generate graphas of this type the user can call: net seed lin col ext prob.

• seed - Seed for the random number generator.

• lin - Number of rows.

• col - Number of columns.

• ext - Number of edges.

• prob - Probability of the existence of each edge [0-100].

The generator "Shuffle" reads a graph file and it shuffles their edges. It expects to find a file called "GRF" in the same directory. He reads this file, it shuffles the edges and than writes the graph on the top of the previous file. To shuffle a graph the user can rename a file to "GRF" and than call: shuffle seed. Where:

• seed - Seed of the the random number generator.