2. Independent Vertex Sets

2.1. igraph_independent_vertex_sets — Find all independent vertex sets in a graph
2.2. igraph_largest_independent_vertex_sets — Finds the largest independent vertex set(s) in a graph.
2.3. igraph_maximal_independent_vertex_sets — Find all maximal independent vertex sets of a graph
2.4. igraph_independence_number — Find the independence number of the graph

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.3.  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>

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