Program carried out in the academic field. It is one of my best works and of which I’m most proud.

Introduction

What is a graph?

A graph is a set of vertices intercommunicated by edges (as in the cover image). They are useful for represent certain types of problems, ej: Travelling salesman problem.

What is a graph colored?

Each vertex is assigned a color, with the condition that there are not 2 or more vertex that are connected by any edge and have the same color.

graphic example

A trivial coloring for a graph would be to assign a different color to each vertex.

example of graph with trivial coloring

What is a proper coloring graph?

A proper coloring graph, is a coloring of a graph, with the added condition that use the minor numbers of colors possible.

We will call χ (Chi) the minimum number of colors necessary to generate a proper coloring of the graph.

the same graphic example, with proper coloring. χ = 3


It turns out that, except for particular cases, there is no (fast) polynomial algorithm to generate a proper coloring of a Graph. Because of this we are going to use a heuristic, that is, a function that approximates the value of χ. This function will be to use Greedy algorithm multiple times, which depends on the initial ordering of the vertices.


Design

This program was designed from the beginning to handle larges graphs, of the order of millions of vertices and tens of millions of edges, and use Greedy a thousand times! Therefore, to support such magnitudes, it was necessary to constantly think about efficiency throughout the development process.

If you are not very careful you could develop a program that takes days or even months to finish!

graphic description


Conclusion

For more specific information and how to use it, see the source code here.