igraph Reference Manual

For using the igraph C library

Chapter 15. Cliques and Independent Vertex Sets

These functions calculate various graph properties related to cliques and independent vertex sets.

1. Cliques

1.1. igraph_cliques — Find all or some cliques in a graph

int igraph_cliques(const igraph_t *graph, igraph_vector_ptr_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 searches for maximal independent vertex sets (see igraph_maximal_independent_vertex_sets()) in the complementer graph using the algorithm published in: 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: 

graph:

The input graph.

res:

Pointer to a pointer vector, the result will be stored here, ie. res will contain pointers to igraph_vector_t objects which contain the indices of vertices involved in a clique. The pointer vector will be resized if needed but note that the objects in the pointer vector will not be freed.

min_size:

Integer giving the minimum size of the cliques to be returned. If negative or zero, no lower bound will be used.

max_size:

Integer giving the maximum size of the cliques to be returned. If negative or zero, no upper bound will be used.

Returns: 

Error code.

See also: 

Time complexity: TODO

Example 15.1.  File examples/simple/igraph_cliques.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

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

void print_vector(igraph_vector_t *v) {
  long int i, n=igraph_vector_size(v);
  for (i=0; i<n; i++) {
    printf(" %li", (long int) VECTOR(*v)[i]);
  }
  printf("\n");
}

void warning_handler_ignore(const char* reason,const char* file,int line,int e) {
}

int main() {
  
  igraph_t g;
  igraph_vector_ptr_t result;
  igraph_es_t es;
  igraph_integer_t omega;
  long int i, j, n;
  const int params[] = {4, -1, 2, 2, 0, 0, -1, -1};
 
  igraph_set_warning_handler(warning_handler_ignore);

  igraph_vector_ptr_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_ptr_size(&result);
    printf("%ld cliques found\n", (long)n);
    for (i=0; i<n; i++) {
      igraph_vector_t* v;
      v=igraph_vector_ptr_e(&result,i);
      print_vector((igraph_vector_t*)v);
      igraph_vector_destroy(v);
      free(v);
    }
  }
   
  igraph_clique_number(&g, &omega);
  printf("omega=%ld\n", (long)omega);

  igraph_destroy(&g);

  igraph_tree(&g, 5, 2, IGRAPH_TREE_OUT);
  igraph_cliques(&g, &result, 5, 5);
  if (igraph_vector_ptr_size(&result) != 0) return 1;

  igraph_destroy(&g);
  igraph_vector_ptr_destroy(&result);

  return 0;
}


1.2. igraph_largest_cliques — Finds the largest clique(s) in a graph.

int igraph_largest_cliques(const igraph_t *graph, igraph_vector_ptr_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, ie. 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() 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: 

graph:

The input graph.

res:

Pointer to an initialized pointer vector, the result will be stored here. It will be resized as needed. Note that vertices of a clique may be returned in arbitrary order.

Returns: 

Error code.

See also: 

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

1.3. igraph_maximal_cliques — Find all maximal cliques of a graph

int igraph_maximal_cliques(const igraph_t *graph, 
			   igraph_vector_ptr_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: 

graph:

The input graph.

res:

Pointer to a pointer vector, the result will be stored here, ie. res will contain pointers to igraph_vector_t objects which contain the indices of vertices involved in a clique. The pointer vector will be resized if needed but note that the objects in the pointer vector will not be freed. Note that vertices of a clique may be returned in arbitrary order.

min_size:

Integer giving the minimum size of the cliques to be returned. If negative or zero, no lower bound will be used.

max_size:

Integer giving the maximum size of the cliques to be returned. If negative or zero, no upper bound will be used.

Returns: 

Error code.

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.

Example 15.2.  File examples/simple/igraph_maximal_cliques.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

#define NODES 1000
#define CLIQUE_SIZE 10
#define NO_CLIQUES 10
#define INT(a) (igraph_rng_get_integer(igraph_rng_default(), 0, (a)))

int permutation(igraph_vector_t *vec) {
  int i, r, tmp;
  for (i=0; i<CLIQUE_SIZE; i++) {
    r=INT(NODES-1);
    tmp=VECTOR(*vec)[i];
    VECTOR(*vec)[i]=VECTOR(*vec)[r];
    VECTOR(*vec)[r]=tmp;
  }
  return 0;
}

int sort_cmp(const void *a, const void *b) {
  const igraph_vector_t **da = (const igraph_vector_t **) a;
  const igraph_vector_t **db = (const igraph_vector_t **) b;
  int i, alen=igraph_vector_size(*da), blen=igraph_vector_size(*db);
  if (alen != blen) { return (alen < blen) - (alen > blen); }
  for (i=0; i<alen; i++) {
    int ea=VECTOR(**da)[i], eb=VECTOR(**db)[i];
    if (ea != eb) { return (ea > eb) - (ea < eb); }
  }
  return 0;
}

void sort_cliques(igraph_vector_ptr_t *cliques) {
  int i, n=igraph_vector_ptr_size(cliques);
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(*cliques)[i];
    igraph_vector_sort(v);
  }
  igraph_qsort(VECTOR(*cliques), (size_t) n,
	       sizeof(igraph_vector_t *), sort_cmp);
}

void print_and_destroy_cliques(igraph_vector_ptr_t *cliques) {
  int i;
  sort_cliques(cliques);
  for (i=0; i<igraph_vector_ptr_size(cliques); i++) {
    igraph_vector_t *v=VECTOR(*cliques)[i];
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
  }
}

int main() {
  
  igraph_t g, g2, cli;
  igraph_vector_t perm;
  igraph_vector_ptr_t cliques;
  igraph_integer_t no;
  int i;

  igraph_rng_seed(igraph_rng_default(), 42);
  
  /* Create a graph that has a random component, plus a number of 
     relatively small cliques */
  
  igraph_vector_init_seq(&perm, 0, NODES-1);
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, NODES, NODES, 
        /*directed=*/ 0, /*loops=*/ 0);
  igraph_full(&cli, CLIQUE_SIZE, /*directed=*/ 0, /*loops=*/ 0);

  for (i=0; i<NO_CLIQUES; i++) {
    /* Permute vertices of g */
    permutation(&perm);
    igraph_permute_vertices(&g, &g2, &perm);
    igraph_destroy(&g);
    g=g2;
    
    /* Add a clique */
    igraph_union(&g2, &g, &cli, /*edge_map1=*/ 0, /*edge_map2=*/ 0);
    igraph_destroy(&g);
    g=g2;
  }
  igraph_simplify(&g, /*multiple=*/ 1, /*loop=*/ 0, /*edge_comb=*/ 0);
  
  igraph_vector_destroy(&perm);
  igraph_destroy(&cli);
  
  /* Find the maximal cliques */
  
  igraph_vector_ptr_init(&cliques, 0);
  igraph_maximal_cliques(&g, &cliques, /*min_size=*/ 3,
       /*max_size=*/ 0 /*no limit*/);
  igraph_maximal_cliques_count(&g, &no, /*min_size=*/ 3, 
       /*max_size=*/ 0 /*no limit*/);

  if (no != igraph_vector_ptr_size(&cliques)) { return 1; }
  
  /* Print and destroy them */

  print_and_destroy_cliques(&cliques);
  
  /* Clean up */

  igraph_vector_ptr_destroy(&cliques);
  igraph_destroy(&g);

  /* Build a triangle with a loop (thanks to Emmanuel Navarro) */

  igraph_small(&g, 3, IGRAPH_UNDIRECTED, 0, 1, 1, 2, 2, 0, 0, 0, -1);

  /* Find the maximal cliques */

  igraph_vector_ptr_init(&cliques, 0);
  igraph_maximal_cliques(&g, &cliques, /*min_size=*/ 3,
    /*max_size=*/ 0 /*no limit*/);
  igraph_maximal_cliques_count(&g, &no, /*min_size=*/ 3, 
       /*max_size=*/ 0 /*no limit*/);

  if (no != igraph_vector_ptr_size(&cliques)) { return 2; }

  /* Print and destroy them */

  print_and_destroy_cliques(&cliques);
  
  /* Clean up */

  igraph_vector_ptr_destroy(&cliques);
  igraph_destroy(&g);

  return 0;
}


1.4. igraph_maximal_cliques_count — Count the number of maximal cliques in a graph

int 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: 

graph:

The input graph.

res:

Pointer to a pointer vector, the result will be stored here, ie. res will contain pointers to igraph_vector_t objects which contain the indices of vertices involved in a clique. The pointer vector will be resized if needed but note that the objects in the pointer vector will not be freed. Note that vertices of a clique may be returned in arbitrary order.

min_size:

Integer giving the minimum size of the cliques to be returned. If negative or zero, no lower bound will be used.

max_size:

Integer giving the maximum size of the cliques to be returned. If negative or zero, no upper bound will be used.

Returns: 

Error code.

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.

Example 15.3.  File examples/simple/igraph_maximal_cliques.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2010-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#include <igraph.h>

#define NODES 1000
#define CLIQUE_SIZE 10
#define NO_CLIQUES 10
#define INT(a) (igraph_rng_get_integer(igraph_rng_default(), 0, (a)))

int permutation(igraph_vector_t *vec) {
  int i, r, tmp;
  for (i=0; i<CLIQUE_SIZE; i++) {
    r=INT(NODES-1);
    tmp=VECTOR(*vec)[i];
    VECTOR(*vec)[i]=VECTOR(*vec)[r];
    VECTOR(*vec)[r]=tmp;
  }
  return 0;
}

int sort_cmp(const void *a, const void *b) {
  const igraph_vector_t **da = (const igraph_vector_t **) a;
  const igraph_vector_t **db = (const igraph_vector_t **) b;
  int i, alen=igraph_vector_size(*da), blen=igraph_vector_size(*db);
  if (alen != blen) { return (alen < blen) - (alen > blen); }
  for (i=0; i<alen; i++) {
    int ea=VECTOR(**da)[i], eb=VECTOR(**db)[i];
    if (ea != eb) { return (ea > eb) - (ea < eb); }
  }
  return 0;
}

void sort_cliques(igraph_vector_ptr_t *cliques) {
  int i, n=igraph_vector_ptr_size(cliques);
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(*cliques)[i];
    igraph_vector_sort(v);
  }
  igraph_qsort(VECTOR(*cliques), (size_t) n,
	       sizeof(igraph_vector_t *), sort_cmp);
}

void print_and_destroy_cliques(igraph_vector_ptr_t *cliques) {
  int i;
  sort_cliques(cliques);
  for (i=0; i<igraph_vector_ptr_size(cliques); i++) {
    igraph_vector_t *v=VECTOR(*cliques)[i];
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
  }
}

int main() {
  
  igraph_t g, g2, cli;
  igraph_vector_t perm;
  igraph_vector_ptr_t cliques;
  igraph_integer_t no;
  int i;

  igraph_rng_seed(igraph_rng_default(), 42);
  
  /* Create a graph that has a random component, plus a number of 
     relatively small cliques */
  
  igraph_vector_init_seq(&perm, 0, NODES-1);
  igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNM, NODES, NODES, 
        /*directed=*/ 0, /*loops=*/ 0);
  igraph_full(&cli, CLIQUE_SIZE, /*directed=*/ 0, /*loops=*/ 0);

  for (i=0; i<NO_CLIQUES; i++) {
    /* Permute vertices of g */
    permutation(&perm);
    igraph_permute_vertices(&g, &g2, &perm);
    igraph_destroy(&g);
    g=g2;
    
    /* Add a clique */
    igraph_union(&g2, &g, &cli, /*edge_map1=*/ 0, /*edge_map2=*/ 0);
    igraph_destroy(&g);
    g=g2;
  }
  igraph_simplify(&g, /*multiple=*/ 1, /*loop=*/ 0, /*edge_comb=*/ 0);
  
  igraph_vector_destroy(&perm);
  igraph_destroy(&cli);
  
  /* Find the maximal cliques */
  
  igraph_vector_ptr_init(&cliques, 0);
  igraph_maximal_cliques(&g, &cliques, /*min_size=*/ 3,
       /*max_size=*/ 0 /*no limit*/);
  igraph_maximal_cliques_count(&g, &no, /*min_size=*/ 3, 
       /*max_size=*/ 0 /*no limit*/);

  if (no != igraph_vector_ptr_size(&cliques)) { return 1; }
  
  /* Print and destroy them */

  print_and_destroy_cliques(&cliques);
  
  /* Clean up */

  igraph_vector_ptr_destroy(&cliques);
  igraph_destroy(&g);

  /* Build a triangle with a loop (thanks to Emmanuel Navarro) */

  igraph_small(&g, 3, IGRAPH_UNDIRECTED, 0, 1, 1, 2, 2, 0, 0, 0, -1);

  /* Find the maximal cliques */

  igraph_vector_ptr_init(&cliques, 0);
  igraph_maximal_cliques(&g, &cliques, /*min_size=*/ 3,
    /*max_size=*/ 0 /*no limit*/);
  igraph_maximal_cliques_count(&g, &no, /*min_size=*/ 3, 
       /*max_size=*/ 0 /*no limit*/);

  if (no != igraph_vector_ptr_size(&cliques)) { return 2; }

  /* Print and destroy them */

  print_and_destroy_cliques(&cliques);
  
  /* Clean up */

  igraph_vector_ptr_destroy(&cliques);
  igraph_destroy(&g);

  return 0;
}


1.5. igraph_clique_number — Find the clique number of the graph

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

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

Arguments: 

graph:

The input graph.

no:

The clique number will be returned to the igraph_integer_t pointed by this variable.

Returns: 

Error code.

See also: 

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

2. Independent Vertex Sets

2.1. igraph_independent_vertex_sets — Find all independent vertex sets in a graph

int igraph_independent_vertex_sets(const igraph_t *graph,
				   igraph_vector_ptr_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: 

graph:

The input graph.

res:

Pointer to a pointer vector, the result will be stored here, ie. res will contain pointers to igraph_vector_t objects which contain the indices of vertices involved in an independent vertex set. The pointer vector will be resized if needed but note that the objects in the pointer vector will not be freed.

min_size:

Integer giving the minimum size of the sets to be returned. If negative or zero, no lower bound will be used.

max_size:

Integer giving the maximum size of the sets to be returned. If negative or zero, no upper bound will be used.

Returns: 

Error code.

See also: 

Time complexity: TODO

Example 15.4.  File examples/simple/igraph_independent_sets.c

/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2006-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard st, Cambridge MA, 02139 USA
   
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

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

void print_vector(igraph_vector_t *v) {
  long int i, n=igraph_vector_size(v);
  for (i=0; i<n; i++) {
    printf(" %li", (long int) VECTOR(*v)[i]);
  }
  printf("\n");
}

void warning_handler_ignore(const char* reason,const char* file,int line,int e) {
}

int main() {
  
  igraph_t g;
  igraph_vector_ptr_t result;
  long int i, j, n;
  igraph_integer_t alpha;
  const int params[] = {4, -1, 2, 2, 0, 0, -1, -1};
  
  igraph_set_warning_handler(warning_handler_ignore);
  igraph_vector_ptr_init(&result, 0);

  igraph_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_ptr_size(&result);
    printf("%ld independent sets found\n", (long)n);
    for (i=0; i<n; i++) {
      igraph_vector_t* v;
      v=igraph_vector_ptr_e(&result,i);
      print_vector((igraph_vector_t*)v);
      igraph_vector_destroy(v);
      free(v);
    }
  }
  igraph_destroy(&g);

  igraph_tree(&g, 10, 2, IGRAPH_TREE_OUT);
  igraph_maximal_independent_vertex_sets(&g, &result);
  n = igraph_vector_ptr_size(&result);
  printf("%ld maximal independent sets found\n", (long)n);
  for (i=0; i<n; i++) {
    igraph_vector_t* v;
    v=igraph_vector_ptr_e(&result,i);
    print_vector((igraph_vector_t*)v);
    igraph_vector_destroy(v);
    free(v);
  }
  igraph_vector_ptr_destroy(&result);

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

  igraph_destroy(&g);

  return 0;
}


2.2. igraph_largest_independent_vertex_sets — Finds the largest independent vertex set(s) in a graph.

int igraph_largest_independent_vertex_sets(const igraph_t *graph,
					   igraph_vector_ptr_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: 

graph:

The input graph.

res:

Pointer to a pointer vector, the result will be stored here. It will be resized as needed.

Returns: 

Error code.

See also: 

Time complexity: TODO

2.3. igraph_maximal_independent_vertex_sets — Find all maximal independent vertex sets of a graph

int igraph_maximal_independent_vertex_sets(const igraph_t *graph,
					   igraph_vector_ptr_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: 

graph:

The input graph.

res:

Pointer to a pointer vector, the result will be stored here, ie. res will contain pointers to igraph_vector_t objects which contain the indices of vertices involved in an independent vertex set. The pointer vector will be resized if needed but note that the objects in the pointer vector will not be freed.

Returns: 

Error code.

See also: 

Time complexity: TODO.

2.4. igraph_independence_number — Find the independence number of the graph

int 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: 

graph:

The input graph.

no:

The independence number will be returned to the igraph_integer_t pointed by this variable.

Returns: 

Error code.

See also: 

Time complexity: TODO.