igraph Reference Manual

For using the igraph C library

Chapter 21. Vertex separators

1. igraph_is_separator — Decides whether the removal of a set of vertices disconnects the graph

int igraph_is_separator(const igraph_t *graph, 
			const igraph_vs_t candidate,
			igraph_bool_t *res);

Arguments: 

graph:

The input graph. It may be directed, but edge directions are ignored.

condidate:

The candidate separator. It must not contain all vertices.

res:

Pointer to a boolean variable, the result is stored here.

Returns: 

Error code.

Time complexity: O(|V|+|E|), linear in the number vertices and edges.

Example 21.1.  File examples/simple/igraph_is_separator.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>
#include <stdio.h>

#define FAIL(msg, error) do { printf(msg "\n") ; return error; } while (0)

int main() {
  
  igraph_t graph;
  igraph_vector_t sep;
  igraph_bool_t result;

  /* Simple star graph, remove the center */
  igraph_star(&graph, 10, IGRAPH_STAR_UNDIRECTED, 0);
  igraph_is_separator(&graph, igraph_vss_1(0), &result);
  if (!result) FAIL("Center of star graph failed.", 1);

  /* Same graph, but another vertex */
  igraph_is_separator(&graph, igraph_vss_1(6), &result);
  if (result) FAIL("Non-center of star graph failed.", 2);
  igraph_destroy(&graph);

  /* Karate club */
  igraph_famous(&graph, "zachary");
  igraph_vector_init(&sep, 0);
  igraph_vector_push_back(&sep, 32);
  igraph_vector_push_back(&sep, 33);
  igraph_is_separator(&graph, igraph_vss_vector(&sep), &result);
  if (!result) FAIL("Karate network (32,33) failed", 3);

  igraph_vector_resize(&sep, 5);
  VECTOR(sep)[0]=8;
  VECTOR(sep)[1]=9;
  VECTOR(sep)[2]=19;
  VECTOR(sep)[3]=30;
  VECTOR(sep)[4]=31;
  igraph_is_separator(&graph, igraph_vss_vector(&sep), &result);
  if (result) FAIL("Karate network (8,9,19,30,31) failed", 4);

  igraph_destroy(&graph);
  igraph_vector_destroy(&sep);

  return 0;
}


2. igraph_is_minimal_separator — Decides whether a set of vertices is a minimal separator

int igraph_is_minimal_separator(const igraph_t *graph,
				const igraph_vs_t candidate, 
				igraph_bool_t *res);

A set of vertices is a minimal separator, if the removal of the vertices disconnects the graph, and this is not true for any subset of the set.

This implementation first checks that the given candidate is a separator, by calling igraph_is_separator(). If it is a separator, then it checks that each subset of size n-1, where n is the size of the candidate, is not a separator.

Arguments: 

graph:

The input graph. It may be directed, but edge directions are ignored.

candidate:

Pointer to a vector of long integers, the candidate minimal separator.

res:

Pointer to a boolean variable, the result is stored here.

Returns: 

Error code.

Time complexity: O(n(|V|+|E|)), |V| is the number of vertices, |E| is the number of edges, n is the number vertices in the candidate separator.

Example 21.2.  File examples/simple/igraph_is_minimal_separator.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>
#include <stdio.h>

#define FAIL(msg, error) do { printf(msg "\n") ; return error; } while (0)

int main() {
  
  igraph_t graph;
  igraph_vector_t sep;
  igraph_bool_t result;

  /* Simple star graph, remove the center */
  igraph_star(&graph, 10, IGRAPH_STAR_UNDIRECTED, 0);
  igraph_is_minimal_separator(&graph, igraph_vss_1(0), &result);
  if (!result) FAIL("Center of star graph failed.", 1);

  /* Same graph, but another vertex */
  igraph_is_minimal_separator(&graph, igraph_vss_1(6), &result);
  if (result) FAIL("Non-center of star graph failed.", 2);
  igraph_destroy(&graph);

  /* Karate club */
  igraph_famous(&graph, "zachary");
  igraph_vector_init(&sep, 0);
  igraph_vector_push_back(&sep, 32);
  igraph_vector_push_back(&sep, 33);
  igraph_is_minimal_separator(&graph, igraph_vss_vector(&sep), &result);
  if (!result) FAIL("Karate network (32,33) failed", 3);

  igraph_vector_resize(&sep, 5);
  VECTOR(sep)[0]=8;
  VECTOR(sep)[1]=9;
  VECTOR(sep)[2]=19;
  VECTOR(sep)[3]=30;
  VECTOR(sep)[4]=31;
  igraph_is_minimal_separator(&graph, igraph_vss_vector(&sep), &result);
  if (result) FAIL("Karate network (8,9,19,30,31) failed", 4);

  igraph_destroy(&graph);
  igraph_vector_destroy(&sep);

  return 0;
}


3. igraph_all_minimal_st_separators — List all vertex sets that are minimal (s,t) separators for some s and t

int igraph_all_minimal_st_separators(const igraph_t *graph, 
				     igraph_vector_ptr_t *separators);

This function lists all vertex sets that are minimal (s,t) separators for some (s,t) vertex pair.

See more about the implemented algorithm in Anne Berry, Jean-Paul Bordat and Olivier Cogis: Generating All the Minimal Separators of a Graph, In: Peter Widmayer, Gabriele Neyer and Stephan Eidenbenz (editors): Graph-theoretic concepts in computer science, 1665, 167--172, 1999. Springer.

Arguments: 

graph:

The input graph. It may be directed, but edge directions are ignored.

separators:

An initialized pointer vector, the separators are stored here. It is a list of pointers to igraph_vector_t objects. Each vector will contain the ids of the vertices in the separator. To free all memory allocated for separators, you need call igraph_vector_destroy() and then igraph_free() on each element, before destroying the pointer vector itself.

Returns: 

Error code.

Time complexity: O(n|V|^3), |V| is the number of vertices, n is the number of separators.

Example 21.3.  File examples/simple/igraph_minimal_separators.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>
#include <stdio.h>

int main() {
  
  igraph_t graph;
  igraph_vector_ptr_t separators;
  long int i, n;
  
  igraph_famous(&graph, "zachary");
  igraph_vector_ptr_init(&separators, 0);
  igraph_all_minimal_st_separators(&graph, &separators);

  n=igraph_vector_ptr_size(&separators);
  for (i=0; i<n; i++) {
    igraph_bool_t res;
    igraph_vector_t *sep=VECTOR(separators)[i];
    igraph_is_separator(&graph, igraph_vss_vector(sep), &res);
    if (!res) { 
      printf("Vertex set %li is not a separator!\n", i);
      igraph_vector_print(sep);
      return 1;
    }
  }

  igraph_destroy(&graph);
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(separators)[i];
    igraph_vector_destroy(v);
    igraph_Free(v);
  }
  igraph_vector_ptr_destroy(&separators);
  
  return 0;
}


4. igraph_minimum_size_separators — Find all minimum size separating vertex sets

int igraph_minimum_size_separators(const igraph_t *graph,
				   igraph_vector_ptr_t *separators);

This function lists all separator vertex sets of minimum size. A vertex set is a separator if its removal disconnects the graph.

The implementation is based on the following paper: Arkady Kanevsky: Finding all minimum-size separating vertex sets in a graph, Networks 23, 533--541, 1993.

Arguments: 

graph:

The input graph, it may be directed, but edge directions will be ignored.

separators:

An initialized pointer vector, the separators are stored here. It is a list of pointers to igraph_vector_t objects. Each vector will contain the ids of the vertices in the separator. To free all memory allocated for separators, you need call igraph_vector_destroy() and then igraph_free() on each element, before destroying the pointer vector itself.

Returns: 

Error code.

Time complexity: TODO.

Example 21.4.  File examples/simple/igraph_minimum_size_separators.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>

int print_and_destroy(igraph_vector_ptr_t *ptr) {
  long int i, n=igraph_vector_ptr_size(ptr);
  for (i=0; i<n; i++) {
    igraph_vector_t *v=VECTOR(*ptr)[i];
    igraph_vector_print(v);
    igraph_vector_destroy(v);
    igraph_free(v);
  }
  igraph_vector_ptr_destroy(ptr);
  return 0;
}

int main() {
  igraph_t g, g2;
  igraph_vector_ptr_t sep;
  igraph_vs_t vs;
  
  igraph_small(&g, 7, IGRAPH_UNDIRECTED,
	       1,0, 2,0, 3,0, 4,0, 5,0, 6,0,
	       -1);
  igraph_vector_ptr_init(&sep, 0);
  igraph_minimum_size_separators(&g, &sep);
  print_and_destroy(&sep);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 5, IGRAPH_UNDIRECTED,
	       0,3, 1,3, 2,3,
	       0,4, 1,4, 2,4,
	       -1);
  igraph_vector_ptr_init(&sep, 0);
  igraph_minimum_size_separators(&g, &sep);
  print_and_destroy(&sep);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 5, IGRAPH_UNDIRECTED,
	       2,0, 3,0, 4,0,
	       2,1, 3,1, 4,1,
	       -1);
  igraph_vector_ptr_init(&sep, 0);
  igraph_minimum_size_separators(&g, &sep);
  print_and_destroy(&sep);
  igraph_destroy(&g);

  /* ----------------------------------------------------------- */

  igraph_small(&g, 10, IGRAPH_UNDIRECTED,
	       0,2, 0,3, 1,2, 1,3, 5,2, 5,3, 6,2, 6,3, 
	       7,2, 7,3, 8,2, 8,3, 9,2, 9,3,
	       2,4, 4,3,
	       -1);
  igraph_vector_ptr_init(&sep, 0);
  igraph_minimum_size_separators(&g, &sep);
  print_and_destroy(&sep);
  igraph_destroy(&g);  

  /* ----------------------------------------------------------- */

  igraph_full(&g, 4, IGRAPH_UNDIRECTED, /*loops=*/ 0);
  igraph_vector_ptr_init(&sep, 0);
  igraph_minimum_size_separators(&g, &sep);
  print_and_destroy(&sep);
  igraph_destroy(&g);  

  /* ----------------------------------------------------------- */

  igraph_small(&g, 23, IGRAPH_UNDIRECTED,
	       0,1, 0,2, 0,3, 0,4, 0,5,
	       1,2, 1,3, 1,4, 1,6,
	       2,3, 2,5, 2,6,
	       3,4, 3,5, 3,6,
	       4,5, 4,6, 4,20,
	       5,6, 
	       6,7, 6,10, 6,13, 6,18,
	       7,8, 7,10, 7,13,
	       8,9,
	       9,11, 9,12,
	       10,11, 10,13,
	       11,15,
	       12,15,
	       13,14,
	       14,15,
	       16,17, 16,18, 16,19,
	       17,19, 17,20,
	       18,19, 18,21, 18,22,
	       19,20,
	       20,21, 20,22,
	       21,22,
	       -1);

  igraph_vector_ptr_init(&sep, 0);
  igraph_minimum_size_separators(&g, &sep);
  printf("Orig:\n"); print_and_destroy(&sep);

  igraph_vector_ptr_init(&sep, 0);
  igraph_vs_vector_small(&vs, 0,1,2,3,4,5,6, 16,17,18,19,20,21,22, -1);
  igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO);
  igraph_minimum_size_separators(&g2, &sep);
  printf("1-7,17-23:\n"); print_and_destroy(&sep);
  igraph_vs_destroy(&vs);
  igraph_destroy(&g2);
  
  igraph_vector_ptr_init(&sep, 0);
  igraph_vs_vector_small(&vs, 6,7,8,9,10,11,12,13,14,15, -1);
  igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO);
  igraph_minimum_size_separators(&g2, &sep);
  printf("7-16:\n"); print_and_destroy(&sep);
  igraph_vs_destroy(&vs);
  igraph_destroy(&g2);
  
  igraph_vector_ptr_init(&sep, 0);
  igraph_vs_vector_small(&vs, 16,17,18,19,20,21,22, -1);
  igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO);
  igraph_minimum_size_separators(&g2, &sep);
  printf("17-23:\n"); print_and_destroy(&sep);
  igraph_vs_destroy(&vs);
  igraph_destroy(&g2);
  
  igraph_vector_ptr_init(&sep, 0);
  igraph_vs_vector_small(&vs, 6,7,10,13, -1);
  igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO);
  igraph_minimum_size_separators(&g2, &sep);
  printf("7,8,11,14:\n"); print_and_destroy(&sep);
  igraph_vs_destroy(&vs);
  igraph_destroy(&g2);

  igraph_vector_ptr_init(&sep, 0);
  igraph_vs_vector_small(&vs, 0,1,2,3,4,5,6, -1);
  igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO);
  igraph_minimum_size_separators(&g2, &sep);
  printf("1-7:\n"); print_and_destroy(&sep);
  igraph_vs_destroy(&vs);
  igraph_destroy(&g2);  

  igraph_destroy(&g);  

  return 0;
}