igraph Reference Manual

For using the igraph C library

Chapter 18. Graph coloring

1. igraph_vertex_coloring_greedy — Computes a vertex coloring using a greedy algorithm.
2. igraph_coloring_greedy_t — Ordering heuristics for greedy 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 18.1. File examples/simple/igraph_coloring.c

#include <igraph.h>

int main() {
    igraph_t graph;
    igraph_vector_int_t colors;

    /* Setting a seed makes the result of erdos_renyi_game deterministic. */
    igraph_rng_seed(igraph_rng_default(), 42);

    /* IGRAPH_UNDIRECTED and IGRAPH_NO_LOOPS are both equivalent to 0/FALSE, but
       communicate intent better in this context. */
    igraph_erdos_renyi_game(&graph, IGRAPH_ERDOS_RENYI_GNM, 1000, 10000, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);

    /* As with all igraph functions, the vector in which the result is returned must
       be initialized in advance. */
    igraph_vector_int_init(&colors, 0);
    igraph_vertex_coloring_greedy(&graph, &colors, IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS);

    /* Verify that the colouring is valid, i.e. no two adjacent vertices have the same colour. */
    {
        long int i;
        /* Store the edge count to avoid the overhead from igraph_ecount in the for loop. */
        long int 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 %ld and %ld are adjacent but have the same color.\n",
                       (long) IGRAPH_FROM(&graph, i), (long) IGRAPH_TO(&graph, i));
                abort();
            }
        }
    }

    /* Destroy data structure when we are done. */
    igraph_vector_int_destroy(&colors);
    igraph_destroy(&graph);

    return 0;
}

2. `igraph_coloring_greedy_t` — Ordering heuristics for greedy graph coloring.

typedef enum {
    IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS = 0
} igraph_coloring_greedy_t;

Ordering heuristics for igraph_vertex_coloring_greedy().

Values:

IGRAPH_COLORING_GREEDY_COLORED_NEIGHBORS:

Choose vertex with largest number of already colored neighbors.

igraph Reference Manual

Chapter 18. Graph coloring

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

2. igraph_coloring_greedy_t — Ordering heuristics for greedy graph coloring.

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

2. `igraph_coloring_greedy_t` — Ordering heuristics for greedy graph coloring.