igraph Reference Manual

For using the igraph C library

Search the manual:

Chapter 17. Graph Coloring

1. igraph_vertex_coloring_greedy — Computes a vertex coloring using a greedy algorithm.

int igraph_vertex_coloring_greedy(const igraph_t *graph, igraph_vector_int_t *colors, igraph_coloring_greedy_t heuristic);

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.

Vertices are colored one by one, choosing the smallest color index that differs from that of already colored neighbors. Colors are represented with non-negative integers 0, 1, 2, ...

Arguments: 

graph:

The input graph.

colors:

Pointer to an initialized integer vector. The vertex colors will be stored here.

heuristic:

The vertex ordering heuristic to use during greedy coloring. See igraph_coloring_greedy_t

Returns: 

Error code.

Example 17.1.  File examples/simple/igraph_coloring.c

#include <igraph.h>
#include <assert.h>

int main() {
    igraph_t graph;
    igraph_vector_int_t colors;

    igraph_rng_seed(igraph_rng_default(), 42);

    igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNM, 1000, 10000, /* directed = */ 0, /* loops = */ 0);

    igraph_vector_int_init(&colors, 0);

    igraph_vertex_coloring_greedy(&graph, &colors, IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS);

    /* verify that the colouring is valid: */
    {
        long i;
        long no_of_edges = igraph_ecount(&graph);
        for (i = 0; i < no_of_edges; ++i) {
            assert( VECTOR(colors)[ IGRAPH_FROM(&graph, i) ] != VECTOR(colors)[ IGRAPH_TO(&graph, i) ]  );
        }
    }

    igraph_vector_int_destroy(&colors);
    igraph_destroy(&graph);

    return 0;
}


2. igraph_coloring_greedy_t — Ordering heuristics for igraph_vertex_coloring_greedy

typedef enum {
    IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS = 0
} igraph_coloring_greedy_t;

Values: 

IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS:

Choose vertex with largest number of already colored neighbors.