igraph · professorcode1 · Nov 2, 2022 · Nov 4, 2022 · Jun 4, 2023 · Jul 7, 2024
diff --git a/examples/simple/igraph_coloring.c b/examples/simple/igraph_coloring.c
@@ -31,6 +31,23 @@ int main(void) {
         }
     }
 
+    igraph_vertex_coloring_AntColony(&graph, &colors, 1.0, 5.0, 0.9, 100, 9, 0.6, 0 , true,true );
+
+    /* Verify that the colouring is valid, i.e. no two adjacent vertices have the same colour. */
+    {
+        igraph_integer_t i;
+        /* Store the edge count to avoid the overhead from igraph_ecount in the for loop. */
+        igraph_integer_t no_of_edges = igraph_ecount(&graph);
+        for (i = 0; i < no_of_edges; ++i) {
+            if ( VECTOR(colors)[ IGRAPH_FROM(&graph, i) ] == VECTOR(colors)[ IGRAPH_TO(&graph, i) ]  ) {
+                printf("Inconsistent coloring! Vertices %" IGRAPH_PRId " and %" IGRAPH_PRId " are adjacent but have the same color.\n",
+                       IGRAPH_FROM(&graph, i), IGRAPH_TO(&graph, i));
+                abort();
+            }
+        }
+    }
+
+
     /* Destroy data structure when we are done. */
     igraph_vector_int_destroy(&colors);
     igraph_destroy(&graph);

diff --git a/include/igraph_coloring.h b/include/igraph_coloring.h
@@ -48,8 +48,14 @@ typedef enum {
     IGRAPH_COLORING_GREEDY_DSATUR = 1
 } igraph_coloring_greedy_t;
 
+
 IGRAPH_EXPORT igraph_error_t igraph_vertex_coloring_greedy(const igraph_t *graph, igraph_vector_int_t *colors, igraph_coloring_greedy_t heuristic);
 
+IGRAPH_EXPORT igraph_error_t igraph_vertex_coloring_AntColony(const igraph_t *graph, igraph_vector_int_t *colors,igraph_real_t alpha, igraph_real_t beta,
+    igraph_real_t rho, igraph_integer_t maxIters, igraph_integer_t tabuRangeUp, igraph_real_t tabuFactor, igraph_integer_t k_end , igraph_bool_t firstVariationFlag,
+    igraph_bool_t secondVariationFlag );
+
+
 __END_DECLS
 
 #endif /* IGRAPH_COLORING_H */
diff --git a/src/misc/coloring.c b/src/misc/coloring.c
@@ -306,3 +306,142 @@
         IGRAPH_ERROR("Invalid heuristic for greedy vertex coloring.", IGRAPH_EINVAL);
     }
 }
+
+static igraph_integer_t DSatur_node_selection(const igraph_t *graph,igraph_vector_int_t *colors, igraph_vector_int_t * saturation_degree, igraph_integer_t vc){
+    igraph_integer_t mst_saurated_node = -1, max_saturation = -1, max_degree = -1;
+    for( igraph_integer_t node = 0 ; node < vc ; node++ ){
+        //finding an uncolored node with max (saturation degree ,  degree)
+        if( VECTOR(*colors)[node] == -1 ){
+            if( VECTOR(*saturation_degree)[node] > max_saturation ){
+                max_saturation = VECTOR(*saturation_degree)[node];
+                mst_saurated_node = node;
+            }
+            else if( VECTOR(*saturation_degree)[node] == max_saturation ){
+                igraph_integer_t degree;
+                igraph_degree_1(graph, &degree, node, IGRAPH_ALL, true);
+                if( degree > max_degree ){
+                    mst_saurated_node = node;
+                    max_degree = degree;
+                }
+            }
+        }
+    }
+    return mst_saurated_node;
+}
+
+static void update_saturation_degree(const igraph_t *graph, igraph_vector_int_t * saturation_degree,igraph_vector_int_t *neighbours){
+    igraph_integer_t nbr_cnt = igraph_vector_int_size(neighbours);
+    for( igraph_integer_t nmbr_indx = 0 ; nmbr_indx < nbr_cnt ; nmbr_indx++ ){
+        igraph_integer_t nbr = VECTOR(*neighbours)[nmbr_indx];
+        VECTOR(*saturation_degree)[ nbr ] += 1;
+    }
+}
+
+static igraph_error_t DSatur(const igraph_t *graph,igraph_vector_int_t *colors, igraph_vector_int_t * saturation_degree){
+    igraph_vector_int_fill(colors, -1); //-1 as a color means uncolored
+    igraph_vector_int_fill(saturation_degree, 0);
+
+    igraph_integer_t vc = igraph_vcount(graph);
+    igraph_integer_t vertices_colored = 0;
+    igraph_vector_int_t neighbours;
+    igraph_vector_int_init(&neighbours, 0);
+    while( vertices_colored < vc ){
+        igraph_integer_t node_to_color = DSatur_node_selection(graph, colors, saturation_degree, vc);
+
+        IGRAPH_CHECK(igraph_neighbors(graph, &neighbours, node_to_color, IGRAPH_ALL ));
+        igraph_integer_t nbr_cnt = igraph_vector_int_size(&neighbours);
+        for( igraph_integer_t color = 0 ; color < vc ; color++ ){
+            igraph_bool_t viable_color = true;
+            for( igraph_integer_t nmbr_indx = 0 ; nmbr_indx < nbr_cnt ; nmbr_indx++ ){
+                igraph_integer_t nbr = VECTOR(neighbours)[nmbr_indx];
+                if( color == VECTOR(*colors)[nbr] ){
+                    viable_color = false;
+                    break;
+                }
+            }
+            if( viable_color ){
+                VECTOR(*colors)[ node_to_color ] = color;
+                break;
+            }
+        }
+        update_saturation_degree(graph, saturation_degree, &neighbours);
+
+        vertices_colored++;
+
+    }
+    return IGRAPH_SUCCESS;
+}
+
+// static igraph_error_t Color(const igraph_t *graph,igraph_vector_int_t *colors, igraph_vector_int_t * saturation_degree, igraph_matrix_int_t* ants,
+//     igraph_integer_t nmbr_colors){
+
+//         return IGRAPH_SUCCESS;
+// }
+
+/**
+ * \function igraph_vertex_coloring_antColony
+ * \brief Computes a vertex coloring using ant colony optimisation metaheuristic.
+ *
+ * </para><para>
+ * This function assigns a "color"—represented as a non-negative integer—to
+ * each vertex of the graph in such a way that neighboring vertices never have
+ * the same color. The obtained coloring is not necessarily minimal.
+ *
+ * </para><para>
+ * The coloring is performed using the ant-colony optimisation metaheuristic as described in the paper with slight variations
+ * A New Ant Algorithm for Graph Coloring - Alain Hertz, Nicolas Zufferey
+ * </para><para>
+ * The variations are
+ * 1) The sorting of the move is first done by how much it would reduce conflicts, and then inplace by the fitness formula given in the paper
+ * 2) The selection of moves is not deterministic its probabalistic with the probability distribution being a normal distribution
+ * Both of these can be turned off (see parameters) to use the original algorithm
+ * \param graph The input graph.
+ * \param colors Pointer to an initialized integer vector. The vertex colors will be stored here.
+ * \param alpha real number which describes the greedy force when calculating move fitness. Paper suggests keeping this 1.0
+ * \param beta  real number which describes the trail force when calculating move fitness. Paper suggests keeping this 5.0
+ * \param rho evaporation constant which describes the trail being forgotten per iteration. Paper suggests keeping this at or close to 0.9
+ * \param maxIters number of iterations the ant colony loop will run for each color. Paper suggest to keep that at 1000. Setting this to 0 will
+ * will jus return the graph colored using the D-Satur algorithm and all checks for other parameters being valid will not run
+ * \param tabuRangeUp the lower bound on the maximum tabu tenure. Paper suggests keeping this 9
+ * \param tabuFactor the formula for tabu tenure of a move is given by random_int(0, tabuRange) + tabuFactor * NCV(s) where s is the current coloring
+ * and NVC is the number of conflicting vertices.
+ * \param k_end the number of colors which once achieved will make the algorithm return. Setting this to 0 will allow the algorithm to try and find the optimal coloring
+ * \param firstVariationFlag setting this to true will enable the first variatio, which has been observed to improve results
+ * \param secondVariationFlag setting this to true will enable second variation, which works well with the first variation.
+ * \return Error code.
+ *
+ * \example examples/simple/igraph_coloring.c
+ */
+igraph_error_t igraph_vertex_coloring_AntColony(const igraph_t *graph, igraph_vector_int_t *colors,igraph_real_t alpha, igraph_real_t beta,
+    igraph_real_t rho, igraph_integer_t maxIters, igraph_integer_t tabuRangeUp, igraph_real_t tabuFactor, igraph_integer_t k_end , igraph_bool_t firstVariationFlag,
+    igraph_bool_t secondVariationFlag ) {
+
+    igraph_integer_t vc = igraph_vcount(graph);
+    IGRAPH_CHECK(igraph_vector_int_resize(colors, vc));
+    if (vc <= 1) {
+        igraph_vector_int_fill(colors, 0);
+        return IGRAPH_SUCCESS;
+    }
+
+    igraph_vector_int_t saturation_degree;
+    IGRAPH_CHECK(igraph_vector_int_init(&saturation_degree, vc));
+    if( maxIters == 0 ){
+        IGRAPH_CHECK(DSatur(graph, colors, &saturation_degree));
+        return IGRAPH_SUCCESS;
+    }
+
+    if( rho < 0 || rho > 1 ){
+        IGRAPH_ERROR("Evaporation constant should be b/w 0 and 1", IGRAPH_EINVAL);
+    }
+    if( maxIters < 0 ){
+        IGRAPH_ERROR("maxIters should be greater than or equal to 0", IGRAPH_EINVAL);
+    }
+    if( tabuRangeUp < 0 ){
+        IGRAPH_ERROR("tabuRangeUp should be greater than or equal to 0", IGRAPH_EINVAL);
+    }
+    if( tabuFactor < 0.0 ){
+        IGRAPH_ERROR("tabuFactor should be greater than or equal to 0", IGRAPH_EINVAL);
+    }
+    IGRAPH_CHECK(DSatur(graph, colors, &saturation_degree));
+    return IGRAPH_SUCCESS;
+}