EvolutionaryGraphs

This repository contains the source code of an evolutionary algorithm designed to search for regular $K_3$-irregular graphs. The project combines graph theory, evolutionary computation, and practical heuristics, and supports customization of mutation, fitness, and selection mechanisms.

This project is a part of the paper. If you use this code in your research, please cite the following paper:
A. Hak, S. Kozerenko and A. Serdiuk "Regular $K_3$-Irregular Graphs".
Preprint: arXiv:2507.18776.

Overview

A $K_3$-degree (triangle-degree) of a vertex $v$ of a graph $G$ is the number of subgraphs $K_3$ of $G$ that vertex $v$ belongs to. A graph is called $K_3$-irregular if all its vertices have (pairwise) distinct triangle-degrees.

We implement an evolutionary algorithm to search for regular $K_3$-irregular graphs. The algorithm explores the graph space using various mutation operators and elitist selection strategies, guided by a fitness function based on triangle degrees.

The code is written in C++ using the Boost Graph Library

Folder structure

• EvolutionaryGraphs/ — Main source code and project files;
• Found Regular K3-Irregular Graphs/ – Graphs discovered by the algorithm;
• EvolutionaryGraphs — Visual Studio solution file;
• LICENSE — MIT license;
• README.md — this file.

Requirements

• C++17 or later
• Boost Graph Library download

Tested with: Visual Studio 2022, Boost 1.82.0, C++17 (C++20)

Build Instructions

0. Make sure you have Visual Studio with C++ installed and Boost Graph Lib downloaded. Only header-only parts of Boost are required (e.g., Boost Graph Library). No separate compilation or linking of Boost libraries is needed.
1. Clone this repository.
2. Open EvolutionaryGraphs.sln in Visual Studio.
3. Make sure the Boost path is configured properly:
   • Right click on project in VS -> Go to properties
   • On the left panel, go to: Configuration properties -> C\C++ -> General
   • Put the path to boost directory into AdditionalIncludeDirectories: (For me it looks like: C:\boost\boost_1_82_0); Note: pay attention to Configuration and Platform settings selected at the top. I recommend adding this path for all settings at once.
   • Save settings and close them. Note: See the next section for code documentation to get to know how to setup algorithm parameters.
4. Build and run the project.

Configuration and Parameters

Main algorithm loop

Full algorithm loop goes as follows:

1. Initialization: Generate an initial population of graphs and evaluate their fitness.
2. Stopping criterion: If a regular $K_3$-irregular graph is found, terminate the algorithm; otherwise, proceed to the next step.
3. Multi-offspring mutations: For each individual in the current population, generate $m$ mutated offspring by independently applying mutation.
4. Fitness evaluation: Compute the $K_3$-degree of every vertex and evaluate the fitness of each candidate graph.
5. Selection: From the enlarged pool of $mN$ candidates (optionally including some individuals from the previous generation), select the best $N$ individuals to form the next generation. The process then continues from step~2.

General Settings — Settings.h

• POPULATION_SIZE — The size of the population (used in initialization starting population and in selection parameter);
• POPULATION_PREV_SAVE_SIZE — The number of best individuals to directly carry over from the pre-mutation population into the pool of candidates for selection;
• MaxIter — Stop algorithm if exceed this number of iterations.
• freqWriteToFile — After each such number of iterations, the full population will be logged into the file (when division remainder is zero: iteration % freqWriteToFile = 0);
• setting_string — String with settings to be logged at the top of run log;
• LOG_FOLDER — Folder to create log file in;
• FileName — Log file name;
• FULL_PATH — Full path to log file.

Regular irregular configs — RegIrregConfig.h

• REGULARITY — The regularity to search;
• V — the order of the graph, used for generating the initial population.

Mutation configs — MutationConfig.h

Note MutationProperty has parameter ancestors_count — this is how many mutated individuals are generated from each graph. Also, the second parameter modifies some mutations. For example, you can specify into how many verices an edge is subdivided for the SUB_DIVIDE_EDGE mutation, or how many vertices are added for the ADD_LEAF_PATH mutation.

• ADD_EDGE — two vertices are selected randomly. Then if they are adjacent, nothing happens. If they are not, an edge between them is added. This mutation has a parameter subdivedN, it makes vertices connected not directly but through a path (equivalent to connecting and subdividing the newly created edge with subdivedN vertices);
• SUB_DIVIDE_EDGE — an edge is selected randomly and subdivided with vertices. The number of vertices is determined by the vertN parameter, which has a default value 1;
• ADD_LEAF_PATH — A vertex is selected randomly and a path of length pathLen is glued to it;
• REMOVE_VERTEX, REMOVE_EDGE — a vertex/edge is selected randomly, then we check if its removal does not break the connectedness of the graph (vertex is not an articulation point, edge is not a bridge). And then the element is removed. Inside a function there is a threshold on the number of vertices/edges to not perform this operation on small graphs;
• REMOVE_VERTEX_HARD, REMOVE_EDGE_HARD — stronger versions of previous mutations. The removal is performed even if the graph becomes disconnected. After that, for each pair of connected components, a random edge is added to connect them;
• ADD_REGVERTEX — adds a new vertex to a graph, while keeping it regular. For odd regularities, 2 vertices are added;
• TRY_REMOVE_REG_VERTEX — Picks a vertex at random, removes it and tries to sew its neighborhood and keep the graph regular. If it is impossible, does nothing. Note: implemented only for even regularities.
• REMOVE_REG_VERTEX — The same as TRY_REMOVE_REG_VERTEX, but if it fails, picks another random vertex and tries to do the same. Caution: may cause an infinite loop, but in practice does not;
• FLIP_2_EDGES — Edge switching mutation. Picks 2 vertices at random and 2 vertices from their neighborhoods (also at random), check if 2-edge switch can be performed (remove $ab$, $cd$ edges and $ac$, $bd$ edges) and performs it if so, otherwise keeps picking vertices at random. Caution: may cause an infinite loop, but in practice does not;

Fitness configs — FitnessConfig.h

Fitness Config has a parameter score that is a weight applied to this function. Each part of the fitness function must return a value from the interval [0,1]. Then each is multiplied by score and summed tovards the total score.

• REGULAR — Returns the proportion of vertices having a degree equal to REGULARITY;
• K3IRREGULAR — Counts the number of equal pairs of $K_3$-degrees.

Note: when FitnessConfig is created, do not forget to update its max score it is used in stop condition.

Selection configs — SelectionConfig.h

Parameter nSelect is the number of individuals being selected;

• ELITARY — Elitist Selection;
• WHEEL_RWS — Roulette Wheel Selection;
• WHEEL_SUS — Stochastic Universal Sampling;
• TOURNAMENT — Tournament Selection, also has the parameter tournamentSize.

Output Format

Run logs

Examples of logs during runs can be found in Logs folder. When you run the program created file with name FileName in folder LOG_FOLDER. These parameters are defined in Settings.h.

The general evolutionary algorithm parameters of the run are logged (population size, fitness config, mutation config, selection config, etc.).

After that, the best Individual of the iteration is logged into the file along with its fitness and average fitness of generation.

The parameter freqWriteToFile determines when the whole generation is logged into the file.

If the run is successful (individual of maximum fitness is encountered), the algorithm logs this individual into the file along with a congratulatory message. After that, the whole population is also saved into the file.

Found Graph information in .txt format

In order to print info about found regular $K_3$-irregular graph, the function printRegGraphCharacteristics is used. This info is saved in the Found Regular K3-Irregular Graphs folder.

Note: our files contain info about algorithm parameters and Iteration counter used in the successful runs, they were copied by hand from the run log.

The graph is printed in different formats: Input — duplicated the input given. This is the adjacency list: a list of lists, where each element corresponds a vertex, and contains its adjacent vertices.

Then, the order and the size of the graph is printed, followed by Adjacency lists (suitable to tikz latex). This is a more readable form of the adjacency list, each vertex's adjacencies are printed on a new line. The syntax (curly braces and slash) is suitable for drawing graph in tikz.

Next, a $K_3$-degrees remapped version is printed Adjacencies of K_3 degrees: now each vertex id corresponds to its $K_3$-degree. This remapping ids are only present here, the following prints use the default ids (not corresponding to $K_3$-degrees).

The next is All edges format — just all pairs of adjacent vertices are printed.

After that, we have the Adjacency Matrix format — just a matrix with 0's and 1's representing the adjacency relation.

After the Fitness is printed, it is usually 200, that is, 100 points for being regular and another 100 points for being $K_3$-irregular. Note that regularity is checked according to REGULARITY parameter defined in RegIrregConfig.h.

In the end, we have a list of K_3 degrees printed in the order of vertex ids (starting from 0). Additionally, we have the sorted list of $K_3$-degrees just to see the range more clearly (the min/max and gaps between them).

Source Code Structure

• main.cpp — entry point to the program;
• Logs — Folder where the logs are saved;

Graphs

• CommonGraphs.h — Generate common graphs (only $K_n$ and regular graphs; for now)
• GraphUtils.h — Some utility functions to work with graph;
• Regullarity.h — Function to work with regularities and irregularities of graphs (like computing $K_3$-degrees)
• TypeTraits.h — Types defined here (mostly graph types);

Evolutionary Algorithm

• GeneticTypeTraits.h — Types of Chromosome and Population defined here;
• GeneticAlgoritm.h — General loop of evolutionary algorithm
• Population.h — Init population using Small World Generator;
• Fitness.h, Selection.h, Mutation.h — Defined Fitness, Selection and Mutation functions respectively;
• PrintGeneticUtils.h — Utility functions to print logs about population;

  Configs

  • Settings.h — General parameters of the algorithm configured here (like population size, log folder, and frequency of logs);
  • RegIrregConfig.h — Configs for regularity parameters here (like regularity, order). Also, our typical setups for fitness, selection and mutation configs are here;
  • FitnessConfig.h, SelectionConfig.h, MutationConfig.h — Configure function to use in each phase, their parameters and weights;

Utils

• BoostExamples.h — example of code with boost graph lib. Was used to learn BGL;
• ColorConsole.h — Utility to print colored text to console;
• PrintUtils.h — Utility functions for printing;
• Utils.h — General utility functions;
• Tests.h — Function to print info (test graph properties) about graphs defined here. Also some test cases were written when exploring BGL;

License

This project is licensed under the MIT License.

Some useful links:

Boost getting started for Windows

Boost graph lib documentation

The basics of using the boost graph library YouTube