igraph_error_t igraph_cliques(const igraph_t *graph, igraph_vector_int_list_t *res,
                   igraph_integer_t min_size, igraph_integer_t max_size);

Cliques are fully connected subgraphs of a graph.

If you are only interested in the size of the largest clique in the graph, use igraph_clique_number() instead.

The current implementation of this function uses version 1.21 of the Cliquer library by Sampo Niskanen and Patric R. J. Östergård, http://users.aalto.fi/~pat/cliquer.html

Arguments: 

Returns: 

See also: 

Time complexity: Exponential

#include <igraph.h>
#include <stdlib.h>

int compare_vectors(const igraph_vector_int_t *v1, const igraph_vector_int_t *v2) {
    igraph_integer_t s1, s2, i;

    s1 = igraph_vector_int_size(v1);
    s2 = igraph_vector_int_size(v2);
    if (s1 < s2) {
        return -1;
    }
    if (s1 > s2) {
        return 1;
    }
    for (i = 0; i < s1; ++i) {
        if (VECTOR(*v1)[i] < VECTOR(*v2)[i]) {
            return -1;
        }
        if (VECTOR(*v1)[i] > VECTOR(*v2)[i]) {
            return 1;
        }
    }
    return 0;
}

/* Takes a pointer vector of vectors. Sorts each vector, then sorts the pointer vector */
void canonicalize_list(igraph_vector_int_list_t *list) {
    igraph_integer_t len = igraph_vector_int_list_size(list);
    for (igraph_integer_t i = 0; i < len; ++i) {
        igraph_vector_int_sort(igraph_vector_int_list_get_ptr(list, i));
    }
    igraph_vector_int_list_sort(list, &compare_vectors);
}

struct userdata {
    igraph_integer_t i;
    igraph_vector_int_list_t *list;
};

igraph_error_t handler(const igraph_vector_int_t *clique, void *arg) {
    struct userdata *ud;
    igraph_bool_t cont;

    ud = (struct userdata *) arg;
    cont = 1; /* true */

    if (compare_vectors(clique, igraph_vector_int_list_get_ptr(ud->list, ud->i)) != 0) {
        printf("igraph_cliques() and igraph_cliques_callback() give different results.\n");
        cont = 0; /* false */
    }

    ud->i += 1;

    return cont ? IGRAPH_SUCCESS : IGRAPH_STOP;
}

void test_callback(const igraph_t *graph) {
    igraph_vector_int_list_t list;
    struct userdata ud;

    igraph_vector_int_list_init(&list, 0);
    igraph_cliques(graph, &list, 0, 0);

    ud.i = 0;
    ud.list = &list;

    igraph_cliques_callback(graph, 0, 0, &handler, (void *) &ud);

    igraph_vector_int_list_destroy(&list);
}


int main(void) {

    igraph_t g;
    igraph_vector_int_list_t result;
    igraph_es_t es;
    igraph_integer_t omega;
    igraph_integer_t i, j, n;
    const int params[] = {4, -1, 2, 2, 0, 0, -1, -1};

    igraph_set_warning_handler(igraph_warning_handler_ignore);

    igraph_vector_int_list_init(&result, 0);
    igraph_full(&g, 6, 0, 0);
    igraph_es_pairs_small(&es, 0, 0, 1, 0, 2, 3, 5, -1);
    igraph_delete_edges(&g, es);
    igraph_es_destroy(&es);

    for (j = 0; j < sizeof(params) / (2 * sizeof(params[0])); j++) {
        if (params[2 * j + 1] != 0) {
            igraph_cliques(&g, &result, params[2 * j], params[2 * j + 1]);
        } else {
            igraph_largest_cliques(&g, &result);
        }
        n = igraph_vector_int_list_size(&result);
        printf("%" IGRAPH_PRId " cliques found\n", n);
        canonicalize_list(&result);
        for (i = 0; i < n; i++) {
            igraph_vector_int_t* v = igraph_vector_int_list_get_ptr(&result, i);
            igraph_vector_int_print(v);
        }
    }

    igraph_clique_number(&g, &omega);
    printf("omega=%" IGRAPH_PRId "\n", omega);

    test_callback(&g);

    igraph_destroy(&g);

    igraph_kary_tree(&g, 5, 2, IGRAPH_TREE_OUT);
    igraph_cliques(&g, &result, 5, 5);
    if (igraph_vector_int_list_size(&result) != 0) {
        return 1;
    }

    igraph_destroy(&g);
    igraph_vector_int_list_destroy(&result);

    return 0;
}

igraph_error_t igraph_clique_size_hist(const igraph_t *graph, igraph_vector_t *hist,
                            igraph_integer_t min_size, igraph_integer_t max_size);

Cliques are fully connected subgraphs of a graph.

The current implementation of this function uses version 1.21 of the Cliquer library by Sampo Niskanen and Patric R. J. Östergård, http://users.aalto.fi/~pat/cliquer.html

Arguments: 

Returns: 

See also: 

Time complexity: Exponential

igraph_error_t igraph_cliques_callback(const igraph_t *graph,
                            igraph_integer_t min_size, igraph_integer_t max_size,
                            igraph_clique_handler_t *cliquehandler_fn, void *arg);

Cliques are fully connected subgraphs of a graph. This function enumerates all cliques within the given size range and calls cliquehandler_fn for each of them. The cliques are passed to the callback function as a pointer to an igraph_vector_int_t. Destroying and freeing this vector is left up to the user. Use igraph_vector_int_destroy() to destroy it first, then free it using igraph_free().

The current implementation of this function uses version 1.21 of the Cliquer library by Sampo Niskanen and Patric R. J. Östergård, http://users.aalto.fi/~pat/cliquer.html

Arguments: 

Returns: 

See also: 

Time complexity: Exponential

typedef igraph_error_t igraph_clique_handler_t(const igraph_vector_int_t *clique, void *arg);

Callback type, called when a clique was found. See the details at the documentation of igraph_cliques_callback().

Arguments: 

Returns: 

igraph_error_t igraph_largest_cliques(const igraph_t *graph, igraph_vector_int_list_t *res);

A clique is largest (quite intuitively) if there is no other clique in the graph which contains more vertices.

Note that this is not necessarily the same as a maximal clique, i.e. the largest cliques are always maximal but a maximal clique is not always largest.

The current implementation of this function searches for maximal cliques using igraph_maximal_cliques_callback() and drops those that are not the largest.

The implementation of this function changed between igraph 0.5 and 0.6, so the order of the cliques and the order of vertices within the cliques will almost surely be different between these two versions.

Arguments: 

Returns: 

See also: 

Time complexity: O(3^(|V|/3)) worst case.

igraph_error_t igraph_maximal_cliques(
    const igraph_t *graph, igraph_vector_int_list_t *res,
    igraph_integer_t min_size, igraph_integer_t max_size
);

A maximal clique is a clique which can't be extended any more by adding a new vertex to it.

If you are only interested in the size of the largest clique in the graph, use igraph_clique_number() instead.

The current implementation uses a modified Bron-Kerbosch algorithm to find the maximal cliques, see: David Eppstein, Maarten Löffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation, Lecture Notes in Computer Science Volume 6506, 2010, pp 403-414.

The implementation of this function changed between igraph 0.5 and 0.6 and also between 0.6 and 0.7, so the order of the cliques and the order of vertices within the cliques will almost surely be different between these three versions.

Arguments: 

Returns: 

See also: 

Time complexity: O(d(n-d)3^(d/3)) worst case, d is the degeneracy of the graph, this is typically small for sparse graphs.

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_list_t cliques;
    igraph_integer_t no;

    igraph_small(&g, 9, IGRAPH_UNDIRECTED,
                 0,1, 0,2, 1,2, 2,3, 3,4, 3, 5, 4,5, 5,6, 6,7, -1);
    igraph_vector_int_list_init(&cliques, 0);
    igraph_maximal_cliques(&g, &cliques, /*min_size=*/ 0,
                           /*max_size=*/ 0 /*no limit*/);
    igraph_maximal_cliques_count(&g, &no, /*min_size=*/ 0,
                                 /*max_size=*/ 0 /*no limit*/);

    if (no != igraph_vector_int_list_size(&cliques)) {
        return 1;
    }

    for (igraph_integer_t i = 0; i < igraph_vector_int_list_size(&cliques); i++) {
        igraph_vector_int_t *v = igraph_vector_int_list_get_ptr(&cliques, i);
        igraph_vector_int_print(v);
    }

    igraph_vector_int_list_destroy(&cliques);
    igraph_destroy(&g);

    return 0;
}

igraph_error_t igraph_maximal_cliques_count(const igraph_t *graph,
                                 igraph_integer_t *res,
                                 igraph_integer_t min_size,
                                 igraph_integer_t max_size);

The current implementation uses a modified Bron-Kerbosch algorithm to find the maximal cliques, see: David Eppstein, Maarten Löffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation, Lecture Notes in Computer Science Volume 6506, 2010, pp 403-414.

Arguments: 

Returns: 

See also: 

Time complexity: O(d(n-d)3^(d/3)) worst case, d is the degeneracy of the graph, this is typically small for sparse graphs.

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_list_t cliques;
    igraph_integer_t no;

    igraph_small(&g, 9, IGRAPH_UNDIRECTED,
                 0,1, 0,2, 1,2, 2,3, 3,4, 3, 5, 4,5, 5,6, 6,7, -1);
    igraph_vector_int_list_init(&cliques, 0);
    igraph_maximal_cliques(&g, &cliques, /*min_size=*/ 0,
                           /*max_size=*/ 0 /*no limit*/);
    igraph_maximal_cliques_count(&g, &no, /*min_size=*/ 0,
                                 /*max_size=*/ 0 /*no limit*/);

    if (no != igraph_vector_int_list_size(&cliques)) {
        return 1;
    }

    for (igraph_integer_t i = 0; i < igraph_vector_int_list_size(&cliques); i++) {
        igraph_vector_int_t *v = igraph_vector_int_list_get_ptr(&cliques, i);
        igraph_vector_int_print(v);
    }

    igraph_vector_int_list_destroy(&cliques);
    igraph_destroy(&g);

    return 0;
}

igraph_error_t igraph_maximal_cliques_file(const igraph_t *graph,
                                FILE *outfile,
                                igraph_integer_t min_size,
                                igraph_integer_t max_size);

This function enumerates all maximal cliques and writes them to file.

Edge directions are ignored.

Arguments: 

Returns: 

See also: 

Time complexity: O(d(n-d)3^(d/3)) worst case, d is the degeneracy of the graph, this is typically small for sparse graphs.*

igraph_error_t igraph_maximal_cliques_subset(
    const igraph_t *graph, const igraph_vector_int_t *subset,
    igraph_vector_int_list_t *res, igraph_integer_t *no,
    FILE *outfile, igraph_integer_t min_size, igraph_integer_t max_size
);

This function enumerates all maximal cliques for a subset of initial vertices and writes them to file.

Edge directions are ignored.

Arguments: 

Returns: 

See also: 

Time complexity: O(d(n-d)3^(d/3)) worst case, d is the degeneracy of the graph, this is typically small for sparse graphs.

igraph_error_t igraph_maximal_cliques_hist(const igraph_t *graph,
                                igraph_vector_t *hist,
                                igraph_integer_t min_size,
                                igraph_integer_t max_size);

This function counts how many maximal cliques of each size are present in the graph. Size-1 maximal cliques are simply isolated vertices.

Edge directions are ignored.

Arguments: 

Returns: 

See also: 

Time complexity: O(d(n-d)3^(d/3)) worst case, d is the degeneracy of the graph, this is typically small for sparse graphs.

igraph_error_t igraph_maximal_cliques_callback(const igraph_t *graph,
                                    igraph_clique_handler_t *cliquehandler_fn, void *arg,
                                    igraph_integer_t min_size, igraph_integer_t max_size);

This function enumerates all maximal cliques within the given size range and calls cliquehandler_fn for each of them. The cliques are passed to the callback function as a pointer to an igraph_vector_int_t. The vector is owned by the maximal clique search routine so users are expected to make a copy of the vector using igraph_vector_int_init_copy() if they want to hold on to it.

Edge directions are ignored.

Arguments: 

Returns: 

See also: 

Time complexity: O(d(n-d)3^(d/3)) worst case, d is the degeneracy of the graph, this is typically small for sparse graphs.

igraph_error_t igraph_clique_number(const igraph_t *graph, igraph_integer_t *no);

The clique number of a graph is the size of the largest clique.

The current implementation of this function searches for maximal cliques using igraph_maximal_cliques_callback() and keeps track of the size of the largest clique that was found.

Arguments: 

Returns: 

See also: 

Time complexity: O(3^(|V|/3)) worst case.

igraph_error_t igraph_weighted_cliques(const igraph_t *graph,
                            const igraph_vector_t *vertex_weights, igraph_vector_int_list_t *res,
                            igraph_real_t min_weight, igraph_real_t max_weight, igraph_bool_t maximal);

Cliques are fully connected subgraphs of a graph. The weight of a clique is the sum of the weights of individual vertices within the clique.

Only positive integer vertex weights are supported.

The current implementation of this function uses version 1.21 of the Cliquer library by Sampo Niskanen and Patric R. J. Östergård, http://users.aalto.fi/~pat/cliquer.html

Arguments: 

Returns: 

See also: 

Time complexity: Exponential

igraph_error_t igraph_largest_weighted_cliques(const igraph_t *graph,
                                    const igraph_vector_t *vertex_weights, igraph_vector_int_list_t *res);

The weight of a clique is the sum of the weights of its vertices. This function finds the clique(s) having the largest weight in the graph.

Only positive integer vertex weights are supported.

The current implementation of this function uses version 1.21 of the Cliquer library by Sampo Niskanen and Patric R. J. Östergård, http://users.aalto.fi/~pat/cliquer.html

Arguments: 

Returns: 

See also: 

Time complexity: TODO

igraph_error_t igraph_weighted_clique_number(const igraph_t *graph,
                                  const igraph_vector_t *vertex_weights, igraph_real_t *res);

The weight of a clique is the sum of the weights of its vertices. This function finds the weight of the largest weight clique.

Only positive integer vertex weights are supported.

The current implementation of this function uses version 1.21 of the Cliquer library by Sampo Niskanen and Patric R. J. Östergård, http://users.aalto.fi/~pat/cliquer.html

Arguments: 

Returns: 

See also: 

Time complexity: TODO

igraph_error_t igraph_independent_vertex_sets(const igraph_t *graph,
                                   igraph_vector_int_list_t *res,
                                   igraph_integer_t min_size,
                                   igraph_integer_t max_size);

A vertex set is considered independent if there are no edges between them.

If you are interested in the size of the largest independent vertex set, use igraph_independence_number() instead.

The current implementation was ported to igraph from the Very Nauty Graph Library by Keith Briggs and uses the algorithm from the paper S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505--517, 1977.

Arguments: 

Returns: 

See also: 

Time complexity: TODO

#include <igraph.h>
#include <stdlib.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_list_t result;
    igraph_integer_t i, j, n;
    igraph_integer_t alpha;
    const int params[] = {4, -1, 2, 2, 0, 0, -1, -1};

    igraph_set_warning_handler(igraph_warning_handler_ignore);
    igraph_vector_int_list_init(&result, 0);

    igraph_kary_tree(&g, 5, 2, IGRAPH_TREE_OUT);
    for (j = 0; j < sizeof(params) / (2 * sizeof(params[0])); j++) {
        if (params[2 * j + 1] != 0) {
            igraph_independent_vertex_sets(&g, &result, params[2 * j], params[2 * j + 1]);
        } else {
            igraph_largest_independent_vertex_sets(&g, &result);
        }
        n = igraph_vector_int_list_size(&result);
        printf("%" IGRAPH_PRId " independent sets found\n", n);
        for (i = 0; i < n; i++) {
            igraph_vector_int_print(igraph_vector_int_list_get_ptr(&result, i));
        }
    }
    igraph_destroy(&g);

    igraph_kary_tree(&g, 10, 2, IGRAPH_TREE_OUT);
    igraph_maximal_independent_vertex_sets(&g, &result);
    n = igraph_vector_int_list_size(&result);
    printf("%" IGRAPH_PRId " maximal independent sets found\n", n);
    for (i = 0; i < n; i++) {
        igraph_vector_int_print(igraph_vector_int_list_get_ptr(&result, i));
    }

    igraph_independence_number(&g, &alpha);
    printf("alpha=%" IGRAPH_PRId "\n", alpha);

    igraph_destroy(&g);

    igraph_vector_int_list_destroy(&result);

    return 0;
}

igraph_error_t igraph_largest_independent_vertex_sets(const igraph_t *graph,
        igraph_vector_int_list_t *res);

An independent vertex set is largest if there is no other independent vertex set with more vertices in the graph.

The current implementation was ported to igraph from the Very Nauty Graph Library by Keith Briggs and uses the algorithm from the paper S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505--517, 1977.

Arguments: 

Returns: 

See also: 

Time complexity: TODO

igraph_error_t igraph_maximal_independent_vertex_sets(const igraph_t *graph,
        igraph_vector_int_list_t *res);

A maximal independent vertex set is an independent vertex set which can't be extended any more by adding a new vertex to it.

The algorithm used here is based on the following paper: S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505--517, 1977.

The implementation was originally written by Kevin O'Neill and modified by K M Briggs in the Very Nauty Graph Library. I simply re-wrote it to use igraph's data structures.

If you are interested in the size of the largest independent vertex set, use igraph_independence_number() instead.

Arguments: 

Returns: 

See also: 

Time complexity: TODO.

igraph_error_t igraph_independence_number(const igraph_t *graph, igraph_integer_t *no);

The independence number of a graph is the cardinality of the largest independent vertex set.

The current implementation was ported to igraph from the Very Nauty Graph Library by Keith Briggs and uses the algorithm from the paper S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505--517, 1977.

Arguments: 

Returns: 

See also: 

Time complexity: TODO.