Current version : AGX-3.4.8
What is AutoGraphiX?
AGX-1 1997-2000
AutoGraphiX (AGX) is a computer system designed to help researchers in graph theory. The main purpose of AGX is to search for extremal graphs, i.e., graphs minimizing of maximizing a graph invariant (or a function of graph invariants, which could also be considered as an invariant). From this main capability, some information on the extremal graphs could be extracted and conjectures may be generated automatically or found by the researcher. The first version of AGX was developed between 1997 and 2001 during G. Caporossi’s Ph.D. thesis. It was strictly based upon invariants.
AGX-2 2001-2009
In the second version (developed between 2001 and 2009), matrices and vectors were also handled by the system, allowing the definition of new invariants by the user, without the need of compiling the software again. The third version whose development started from 2011 is conceived to be easier to use for the end user, but nevertheless allows the matrix and vector manipulation to allow custom definition of invariants. The whole code was rewritten and the structure of the software is completely new. The optimization parameters settings are now completely automated in order to simplify the task of the user. Compared to the previous versions, AGX now has some constraints predefined, which avoids some of the most common misuses of the previous versions. Indeed, in AGX-1 or AGX-2, bounding the maximum degree needed to be achieved through 5 to 10 constraints to be efficient in practice. These special constraints also needed to be constructed in a special manner that supposed that the user was an expert in combinatorial optimization. Bounding the maximum degree or the diameter of a graph is now achieved by simply clicking a dedicated button.
AGX-III 2015-current
The interface and the optimizer were completely rebuilt from scratch, making the software easier to use and more intuitive. Among the improvements, the most important one is certainly the native support for vertex-based optimization. This feature involves a native multiobjective optimization module which was devellopped also uses some machine learning techniques to help the optimizer. For instance, it is now easier to run AGX for regular graphs. The use of predetermined constraints allows the choice of appropriate optimization routines that could not be used in the general case. For example, when searching for some regular graph, AGX-III first searches for an example of regular graph (of the chosen degree), and then only uses transformations that keep this property. The new way to proceed does not only avoid wasting time by attempting to apply some transformations that cannot help, but it allows also the use of more sophisticated transformations that could not be considered in the general case. Some transformations considered for special cases in AGX-III involve 5 vertices, which could not be possible in general. Still among the the improvements, AGX-III is built to handle 2 objectives, either to find Pareto optimal solutions, or by setting one main criterion and a second one to use in case of ties. The use of secondary criterion helps when optimizing a function with little possible values (for example, the diameter is difficult to handle because one must often significantly change a graph to see its diameter decrease). In the previous versions of AGX, this trick was achieved by the user who had to include the secondary criterion in the main one by multiplying it with a very small factor. Constraints are now managed by lexicographic order. In previous versions, they were simply considered in the main objective by the mean of some penalty coefficient. Some numerical problems were likely to occur in case of multiple constraints. It is no more the case. All these changes involve a different implementation and the multiobjective optimization is made possible with the new implementation, which was simply not possible before. In multiobjective mode, the improving criterion is based upon domination of a solution over another. To improve the quality of the multiobjective optimization, AGX does not store the current solution as it was the case for the previous versions, but a set of solutions which could be viewed as the current Pareto frontier.