igraph Reference Manual

For using the igraph C library

Chapter 26. Graph Operators

1. Union and intersection

1.1. igraph_disjoint_union — Creates the union of two disjoint graphs

int igraph_disjoint_union(igraph_t *res, const igraph_t *left, 
			  const igraph_t *right);

First the vertices of the second graph will be relabeled with new vertex ids to have two disjoint sets of vertex ids, then the union of the two graphs will be formed. If the two graphs have |V1| and |V2| vertices and |E1| and |E2| edges respectively then the new graph will have |V1|+|V2| vertices and |E1|+|E2| edges.

Both graphs need to have the same directedness, ie. either both directed or both undirected.

The current version of this function cannot handle graph, vertex and edge attributes, they will be lost.

Arguments: 

res:

Pointer to an uninitialized graph object, the result will stored here.

left:

The first graph.

right:

The second graph.

Returns: 

Error code.

See also: 

igraph_disjoint_union_many() for creating the disjoint union of more than two graphs, igraph_union() for non-disjoint union.

Time complexity: O(|V1|+|V2|+|E1|+|E2|).

Example 26.1.  File examples/simple/igraph_disjoint_union.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, l=igraph_vector_size(v);
  for (i=0; i<l; i++) {
    printf(" %li", (long int) VECTOR(*v)[i]);
  }
  printf("\n");
}

int main() {
  
  igraph_t left, right, uni;
  igraph_vector_t v;
  igraph_vector_ptr_t glist;
  long int i;

  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,2, 2,3, -1);
  igraph_create(&left, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,2, 2,4, -1); 
  igraph_create(&right, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_disjoint_union(&uni, &left, &right);
  igraph_vector_init(&v, 0);
  igraph_get_edgelist(&uni, &v, 0);
  igraph_vector_sort(&v);
  print_vector(&v);
  
  igraph_vector_destroy(&v);
  igraph_destroy(&left);
  igraph_destroy(&right);
  igraph_destroy(&uni);

  /* Empty graph list */
  igraph_vector_ptr_init(&glist, 0);
  igraph_disjoint_union_many(&uni, &glist);
  if (!igraph_is_directed(&uni) || igraph_vcount(&uni) != 0) {
    return 1;
  }
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);

  /* Non-empty graph list */
  igraph_vector_ptr_init(&glist, 10); 
  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    VECTOR(glist)[i]=calloc(1, sizeof(igraph_t));
    igraph_vector_init_int_end(&v, -1, 0,1, 1,0, -1);
    igraph_create(VECTOR(glist)[i], &v, 0, IGRAPH_DIRECTED);    
    igraph_vector_destroy(&v);
  }

  igraph_disjoint_union_many(&uni, &glist);
  igraph_vector_init(&v, 0);
  igraph_get_edgelist(&uni, &v, 0);
  igraph_vector_sort(&v);
  print_vector(&v);
  igraph_vector_destroy(&v);

  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    igraph_destroy(VECTOR(glist)[i]);
    free(VECTOR(glist)[i]);
  }
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);

  return 0;
}


1.2. igraph_disjoint_union_many — The disjint union of many graphs.

int igraph_disjoint_union_many(igraph_t *res, 
			       const igraph_vector_ptr_t *graphs);

First the vertices in the graphs will be relabeled with new vertex ids to have pairwise disjoint vertex id sets and then the union of the graphs is formed. The number of vertices and edges in the result is the total number of vertices and edges in the graphs.

Both graphs need to have the same directedness, ie. either both directed or both undirected.

The current version of this function cannot handle graph, vertex and edge attributes, they will be lost.

Arguments: 

res:

Pointer to an uninitialized graph object, the result of the operation will be stored here.

graphs:

Pointer vector, contains pointers to initialized graph objects.

Returns: 

Error code.

See also: 

igraph_disjoint_union() for an easier syntax if you have only two graphs, igraph_union_many() for non-disjoint union.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the result.

1.3. igraph_union — Calculates the union of two graphs.

int igraph_union(igraph_t *res, 
		 const igraph_t *left, const igraph_t *right, 
		 igraph_vector_t *edge_map1, igraph_vector_t *edge_map2);

The number of vertices in the result is that of the larger graph from the two arguments. The result graph contains edges which are present in at least one of the operand graphs.

Arguments: 

res:

Pointer to an uninitialized graph object, the result will be stored here.

left:

The first graph.

right:

The second graph.

edge_map1:

Pointer to an initialized vector or a null pointer. If not a null pointer, it will contain a mapping from the edges of the first argument graph (left) to the edges of the result graph.

edge_map2:

The same as edge_map1, but for the second graph, right.

Returns: 

Error code.

See also: 

igraph_union_many() for the union of many graphs, igraph_intersection() and igraph_difference() for other operators.

Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| the number of edges in the result graph.

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

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

int print_free_vector_ptr(igraph_vector_ptr_t *v) {  
  long int i, l=igraph_vector_ptr_size(v);
  printf("---\n");
  for (i=0; i<l; i++) {
    print_vector(VECTOR(*v)[i]);
  }
  printf("===\n");
  return 0;
}

int main() {
  
  igraph_t left, right, uni;
  igraph_vector_t v;
  igraph_vector_ptr_t glist;
  igraph_vector_t edge_map1, edge_map2;
  igraph_vector_ptr_t edgemaps;
  long int i;  

  igraph_vector_init(&edge_map1, 0);
  igraph_vector_init(&edge_map2, 0);

  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,2, 2,3, -1);
  igraph_create(&left, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,2, 2,4, -1); 
  igraph_create(&right, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_union(&uni, &left, &right, &edge_map1, &edge_map2);
  igraph_write_graph_edgelist(&uni, stdout);
  igraph_vector_print(&edge_map1);
  igraph_vector_print(&edge_map2);  

  igraph_destroy(&uni);
  igraph_destroy(&left);
  igraph_destroy(&right);
  igraph_vector_destroy(&edge_map1);
  igraph_vector_destroy(&edge_map2);

  /* Empty graph list */  
  igraph_vector_ptr_init(&glist, 0);
  igraph_vector_ptr_init(&edgemaps, 0);
  igraph_union_many(&uni, &glist, &edgemaps);
  if (!igraph_is_directed(&uni) || igraph_vcount(&uni) != 0) {
    return 1;
  }
  print_free_vector_ptr(&edgemaps);
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);  

  /* Non-empty graph list */
  igraph_vector_ptr_init(&glist, 10); 
  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    VECTOR(glist)[i]=calloc(1, sizeof(igraph_t));
    igraph_vector_init_int_end(&v, -1, 0,1, 1,0, -1);
    igraph_create(VECTOR(glist)[i], &v, 0, IGRAPH_DIRECTED);    
    igraph_vector_destroy(&v);
  }

  igraph_union_many(&uni, &glist, &edgemaps);
  igraph_write_graph_edgelist(&uni, stdout);

  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    igraph_destroy(VECTOR(glist)[i]);
    free(VECTOR(glist)[i]);
  }
  print_free_vector_ptr(&edgemaps);
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);  

  /* Another non-empty graph list */
  igraph_vector_ptr_init(&glist, 10); 
  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    VECTOR(glist)[i]=calloc(1, sizeof(igraph_t));
    igraph_vector_init_int_end(&v, -1, i,i+1, 1,0, -1);
    igraph_create(VECTOR(glist)[i], &v, 0, IGRAPH_DIRECTED);    
    igraph_vector_destroy(&v);
  }

  igraph_union_many(&uni, &glist, &edgemaps);
  igraph_write_graph_edgelist(&uni, stdout);

  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    igraph_destroy(VECTOR(glist)[i]);
    free(VECTOR(glist)[i]);
  }
  print_free_vector_ptr(&edgemaps);
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);  
  
  /* Undirected graph list*/
  igraph_vector_ptr_init(&glist, 10); 
  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    VECTOR(glist)[i]=calloc(1, sizeof(igraph_t));
    igraph_vector_init_int_end(&v, -1, i,i+1, 1,0, -1);
    igraph_create(VECTOR(glist)[i], &v, 0, IGRAPH_UNDIRECTED);    
    igraph_vector_destroy(&v);
  }

  igraph_union_many(&uni, &glist, &edgemaps);
  igraph_write_graph_edgelist(&uni, stdout);

  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    igraph_destroy(VECTOR(glist)[i]);
    free(VECTOR(glist)[i]);
  }
  print_free_vector_ptr(&edgemaps);
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);  

  igraph_vector_ptr_destroy(&edgemaps);
  
  return 0;
}


1.4. igraph_union_many — Creates the union of many graphs.

int igraph_union_many(igraph_t *res, const igraph_vector_ptr_t *graphs, 
		      igraph_vector_ptr_t *edgemaps);

The result graph will contain as many vertices as the largest graph among the arguments does, and an edge will be included in it if it is part of at least one operand graph.

The directedness of the operand graphs must be the same.

Arguments: 

res:

Pointer to an uninitialized graph object, this will contain the result.

graphs:

Pointer vector, contains pointers to the operands of the union operator, graph objects of course.

edgemaps:

If not a null pointer, then it must be an initialized pointer vector and the mappings of edges from the graphs to the result graph will be stored here, in the same order as graphs. Each mapping is stored in a separate igraph_vector_t object.

Returns: 

Error code.

See also: 

igraph_union() for the union of two graphs, igraph_intersection_many(), igraph_intersection() and igraph_difference for other operators.

Time complexity: O(|V|+|E|), |V| is the number of vertices in largest graph and |E| is the number of edges in the result graph.

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

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

int print_free_vector_ptr(igraph_vector_ptr_t *v) {  
  long int i, l=igraph_vector_ptr_size(v);
  printf("---\n");
  for (i=0; i<l; i++) {
    print_vector(VECTOR(*v)[i]);
  }
  printf("===\n");
  return 0;
}

int main() {
  
  igraph_t left, right, uni;
  igraph_vector_t v;
  igraph_vector_ptr_t glist;
  igraph_vector_t edge_map1, edge_map2;
  igraph_vector_ptr_t edgemaps;
  long int i;  

  igraph_vector_init(&edge_map1, 0);
  igraph_vector_init(&edge_map2, 0);

  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,2, 2,3, -1);
  igraph_create(&left, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,2, 2,4, -1); 
  igraph_create(&right, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_union(&uni, &left, &right, &edge_map1, &edge_map2);
  igraph_write_graph_edgelist(&uni, stdout);
  igraph_vector_print(&edge_map1);
  igraph_vector_print(&edge_map2);  

  igraph_destroy(&uni);
  igraph_destroy(&left);
  igraph_destroy(&right);
  igraph_vector_destroy(&edge_map1);
  igraph_vector_destroy(&edge_map2);

  /* Empty graph list */  
  igraph_vector_ptr_init(&glist, 0);
  igraph_vector_ptr_init(&edgemaps, 0);
  igraph_union_many(&uni, &glist, &edgemaps);
  if (!igraph_is_directed(&uni) || igraph_vcount(&uni) != 0) {
    return 1;
  }
  print_free_vector_ptr(&edgemaps);
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);  

  /* Non-empty graph list */
  igraph_vector_ptr_init(&glist, 10); 
  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    VECTOR(glist)[i]=calloc(1, sizeof(igraph_t));
    igraph_vector_init_int_end(&v, -1, 0,1, 1,0, -1);
    igraph_create(VECTOR(glist)[i], &v, 0, IGRAPH_DIRECTED);    
    igraph_vector_destroy(&v);
  }

  igraph_union_many(&uni, &glist, &edgemaps);
  igraph_write_graph_edgelist(&uni, stdout);

  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    igraph_destroy(VECTOR(glist)[i]);
    free(VECTOR(glist)[i]);
  }
  print_free_vector_ptr(&edgemaps);
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);  

  /* Another non-empty graph list */
  igraph_vector_ptr_init(&glist, 10); 
  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    VECTOR(glist)[i]=calloc(1, sizeof(igraph_t));
    igraph_vector_init_int_end(&v, -1, i,i+1, 1,0, -1);
    igraph_create(VECTOR(glist)[i], &v, 0, IGRAPH_DIRECTED);    
    igraph_vector_destroy(&v);
  }

  igraph_union_many(&uni, &glist, &edgemaps);
  igraph_write_graph_edgelist(&uni, stdout);

  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    igraph_destroy(VECTOR(glist)[i]);
    free(VECTOR(glist)[i]);
  }
  print_free_vector_ptr(&edgemaps);
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);  
  
  /* Undirected graph list*/
  igraph_vector_ptr_init(&glist, 10); 
  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    VECTOR(glist)[i]=calloc(1, sizeof(igraph_t));
    igraph_vector_init_int_end(&v, -1, i,i+1, 1,0, -1);
    igraph_create(VECTOR(glist)[i], &v, 0, IGRAPH_UNDIRECTED);    
    igraph_vector_destroy(&v);
  }

  igraph_union_many(&uni, &glist, &edgemaps);
  igraph_write_graph_edgelist(&uni, stdout);

  for (i=0; i<igraph_vector_ptr_size(&glist); i++) {
    igraph_destroy(VECTOR(glist)[i]);
    free(VECTOR(glist)[i]);
  }
  print_free_vector_ptr(&edgemaps);
  igraph_vector_ptr_destroy(&glist);
  igraph_destroy(&uni);  

  igraph_vector_ptr_destroy(&edgemaps);
  
  return 0;
}


1.5. igraph_intersection — Collect the common edges from two graphs.

int igraph_intersection(igraph_t *res,
			const igraph_t *left, const igraph_t *right, 
			igraph_vector_t *edge_map1, 
			igraph_vector_t *edge_map2);

The result graph contains only edges present both in the first and the second graph. The number of vertices in the result graph is the same as the larger from the two arguments.

Arguments: 

res:

Pointer to an uninitialized graph object. This will contain the result of the operation.

left:

The first operand, a graph object.

right:

The second operand, a graph object.

edge_map1:

Null pointer, or an initialized igraph_vector_t. If the latter, then a mapping from the edges of the result graph, to the edges of the left input graph is stored here.

edge_map2:

Null pointer, or an igraph_vector_t. The same as edge_map1, but for the right input graph.

Returns: 

Error code.

See also: 

igraph_intersection_many() to calculate the intersection of many graphs at once, igraph_union(), igraph_difference() for other operators.

Time complexity: O(|V|+|E|), |V| is the number of nodes, |E| is the number of edges in the smaller graph of the two. (The one containing less vertices is considered smaller.)

Example 26.4.  File examples/simple/igraph_intersection.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>

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

int main() {

  igraph_t left, right, isec;
  igraph_vector_t v;
  igraph_vector_ptr_t glist;
  igraph_t g1, g2, g3;
  igraph_vector_t edge_map1, edge_map2;

  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,3, -1);
  igraph_create(&left, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);

  igraph_vector_init_int_end(&v, -1, 1,0, 5,4, 1,2, 3,2, -1);
  igraph_create(&right, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);

  igraph_vector_init(&edge_map1, 0);
  igraph_vector_init(&edge_map2, 0);
  
  igraph_intersection(&isec, &left, &right, &edge_map1, &edge_map2);
  igraph_vector_init(&v, 0);
  igraph_get_edgelist(&isec, &v, 0);
  printf("---\n");
  print_vector(&v);
  print_vector(&edge_map1);
  print_vector(&edge_map2);
  printf("---\n");
  igraph_vector_destroy(&v);
  igraph_destroy(&left);
  igraph_destroy(&right);
  igraph_destroy(&isec);
  igraph_vector_destroy(&edge_map1);
  igraph_vector_destroy(&edge_map2);

  /* empty graph list */
  igraph_vector_ptr_init(&glist, 0);
  igraph_intersection_many(&isec, &glist, 0);
  if (igraph_vcount(&isec) != 0 || !igraph_is_directed(&isec)) {
    return 1;
  }
  igraph_destroy(&isec);
  igraph_vector_ptr_destroy(&glist);

  /* graph list with an empty graph */
  igraph_vector_ptr_init(&glist, 3);
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,3, -1);
  igraph_create(&g1, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,3, -1);
  igraph_create(&g2, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  igraph_empty(&g3, 10, IGRAPH_DIRECTED);

  VECTOR(glist)[0]=&g1;
  VECTOR(glist)[1]=&g2;
  VECTOR(glist)[2]=&g3;
  igraph_intersection_many(&isec, &glist, 0);
  if (igraph_ecount(&isec) != 0 || igraph_vcount(&isec) != 10) {
    return 2;
  }
  igraph_destroy(&g1);
  igraph_destroy(&g2);
  igraph_destroy(&g3);
  igraph_destroy(&isec);
  igraph_vector_ptr_destroy(&glist);
  
  /* "proper" graph list */
  igraph_vector_ptr_init(&glist, 3);
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,3, -1);
  igraph_create(&g1, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 2,3, 3,2, 4,5, 6,5, -1);
  igraph_create(&g2, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  igraph_vector_init_int_end(&v, -1, 2,3, 1,0, 1,2, 3,2, 4,5, 6,5, 2,3, -1);
  igraph_create(&g3, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  VECTOR(glist)[0]=&g1;
  VECTOR(glist)[1]=&g2;
  VECTOR(glist)[2]=&g3;
  igraph_intersection_many(&isec, &glist, 0);
  igraph_write_graph_edgelist(&isec, stdout);
  igraph_destroy(&g1);
  igraph_destroy(&g2);
  igraph_destroy(&g3);
  igraph_destroy(&isec);
  igraph_vector_ptr_destroy(&glist);

  return 0;
}


1.6. igraph_intersection_many — The intersection of more than two graphs.

int igraph_intersection_many(igraph_t *res, 
			     const igraph_vector_ptr_t *graphs, 
			     igraph_vector_ptr_t *edgemaps);

This function calculates the intersection of the graphs stored in the graphs argument. Only those edges will be included in the result graph which are part of every graph in graphs.

The number of vertices in the result graph will be the maximum number of vertices in the argument graphs.

Arguments: 

res:

Pointer to an uninitialized graph object, the result of the operation will be stored here.

graphs:

Pointer vector, contains pointers to graphs objects, the operands of the intersection operator.

edgemaps:

If not a null pointer, then it must be an initialized pointer vector and the mappings of edges from the graphs to the result graph will be stored here, in the same order as graphs. Each mapping is stored in a separate igraph_vector_t object. For the edges that are not in the intersection, -1 is stored.

Returns: 

Error code.

See also: 

igraph_intersection() for the intersection of two graphs, igraph_union_many(), igraph_union() and igraph_difference() for other operators.

Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| is the number of edges in the smallest graph (ie. the graph having the less vertices).

2. Other set-like operators

2.1. igraph_difference — Calculate the difference of two graphs

int igraph_difference(igraph_t *res, 
		      const igraph_t *orig, const igraph_t *sub);

The number of vertices in the result is the number of vertices in the original graph, ie. the left, first operand. In the results graph only edges will be included from orig which are not present in sub.

Arguments: 

res:

Pointer to an uninitialized graph object, the result will be stored here.

orig:

The left operand of the operator, a graph object.

sub:

The right operand of the operator, a graph object.

Returns: 

Error code.

See also: 

igraph_intersection() and igraph_union() for other operators.

Time complexity: O(|V|+|E|), |V| is the number vertices in the smaller graph, |E| is the number of edges in the result graph.

Example 26.5.  File examples/simple/igraph_difference.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>

int main() {
  
  igraph_t orig, sub, diff;
  igraph_vector_t v;

  /* Subtract from itself */
  printf("subtract itself\n");
  igraph_vector_init_int_end(&v, -1, 0,1,1,2,2,1,4,5, -1);
  igraph_create(&orig, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_difference(&diff, &orig, &orig);
  igraph_write_graph_edgelist(&diff, stdout);
  if (igraph_ecount(&diff) != 0 ||
      igraph_vcount(&diff) != igraph_vcount(&orig)) {
    return 1;
  }
  
  igraph_destroy(&orig);
  igraph_destroy(&diff);

  /* Same for undirected graph */
  printf("subtract itself, undirected\n");
  igraph_vector_init_int_end(&v, -1, 0,1,1,2,2,1,4,5, -1);
  igraph_create(&orig, &v, 0, IGRAPH_UNDIRECTED);
  igraph_vector_destroy(&v);

  igraph_vector_init_int_end(&v, -1, 1,0,1,2,2,1,4,5, -1);
  igraph_create(&sub, &v, 0, IGRAPH_UNDIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_difference(&diff, &orig, &sub);
  igraph_write_graph_edgelist(&diff, stdout);
  if (igraph_ecount(&diff) != 0 ||
      igraph_vcount(&diff) != igraph_vcount(&orig)) {
    return 2;
  }
  
  igraph_destroy(&orig);
  igraph_destroy(&sub);
  igraph_destroy(&diff);
  
  /* Subtract the empty graph */
  printf("subtract empty\n");
  igraph_vector_init_int_end(&v, -1, 0,1,1,2,2,1,4,5, -1);
  igraph_create(&orig, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);

  igraph_empty(&sub, 3, IGRAPH_DIRECTED);
  igraph_difference(&diff, &orig, &sub);
  igraph_write_graph_edgelist(&diff, stdout);
  if (igraph_ecount(&diff) != igraph_ecount(&orig) ||
      igraph_vcount(&diff) != igraph_vcount(&orig)) {
    return 3;
  }

  igraph_destroy(&orig);
  igraph_destroy(&sub);
  igraph_destroy(&diff);

  /* A `real' example */
  printf("real example\n");
  igraph_vector_init_int_end(&v, -1, 0,1,1,2,2,1,4,5,8,9, -1);
  igraph_create(&orig, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);

  igraph_vector_init_int_end(&v, -1, 0,1,5,4,2,1,6,7, -1);
  igraph_create(&sub, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_difference(&diff, &orig, &sub);
  igraph_write_graph_edgelist(&diff, stdout);

  igraph_destroy(&diff);
  igraph_destroy(&orig);
  igraph_destroy(&sub);  

  /* undirected version */
  printf("real example, undirected\n");
  igraph_vector_init_int_end(&v, -1, 0,1,1,2,2,1,4,5,8,9,8,10,8,13,8,11,8,12, -1);
  igraph_create(&orig, &v, 0, IGRAPH_UNDIRECTED);
  igraph_vector_destroy(&v);

  igraph_vector_init_int_end(&v, -1, 0,1,5,4,2,1,6,7,8,10,8,13, -1);
  igraph_create(&sub, &v, 0, IGRAPH_UNDIRECTED);
  igraph_vector_destroy(&v);

  igraph_difference(&diff, &orig, &sub);
  igraph_write_graph_edgelist(&diff, stdout);

  igraph_destroy(&diff);
  igraph_destroy(&orig);
  igraph_destroy(&sub);  
  
  return 0;
}


2.2. igraph_complementer — Create the complementer of a graph

int igraph_complementer(igraph_t *res, const igraph_t *graph, 
			igraph_bool_t loops);

The complementer graph means that all edges which are not part of the original graph will be included in the result.

Arguments: 

res:

Pointer to an uninitialized graph object.

graph:

The original graph.

loops:

Whether to add loop edges to the complementer graph.

Returns: 

Error code.

See also: 

Time complexity: O(|V|+|E1|+|E2|), |V| is the number of vertices in the graph, |E1| is the number of edges in the original and |E2| in the complementer graph.

Example 26.6.  File examples/simple/igraph_complementer.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>

int main() {
  
  igraph_t g1, g2;
  
  /* complementer of the empty graph */
  igraph_empty(&g1, 5, IGRAPH_DIRECTED);
  igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
  igraph_write_graph_edgelist(&g2, stdout);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  printf("---\n");

  /* the same without loops */
  igraph_empty(&g1, 5, IGRAPH_DIRECTED);
  igraph_complementer(&g2, &g1, IGRAPH_NO_LOOPS);
  igraph_write_graph_edgelist(&g2, stdout);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  printf("---\n");
  
  /* complementer of the full graph */
  igraph_full(&g1, 5, IGRAPH_DIRECTED, IGRAPH_LOOPS);
  igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
  if (igraph_ecount(&g2) != 0) {
    return 1;
  }
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  printf("---\n");

  /* complementer of the full graph, results loops only */
  igraph_full(&g1, 5, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
  igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
  igraph_write_graph_edgelist(&g2, stdout);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  printf("---\n");

  /**************
   * undirected *
   *************/

  /* complementer of the empty graph */
  igraph_empty(&g1, 5, IGRAPH_UNDIRECTED);
  igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
  igraph_write_graph_edgelist(&g2, stdout);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  printf("---\n");

  /* the same without loops */
  igraph_empty(&g1, 5, IGRAPH_UNDIRECTED);
  igraph_complementer(&g2, &g1, IGRAPH_NO_LOOPS);
  igraph_write_graph_edgelist(&g2, stdout);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  printf("---\n");
  
  /* complementer of the full graph */
  igraph_full(&g1, 5, IGRAPH_UNDIRECTED, IGRAPH_LOOPS);
  igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
  if (igraph_ecount(&g2) != 0) {
    return 1;
  }
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  printf("---\n");

  /* complementer of the full graph, results loops only */
  igraph_full(&g1, 5, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
  igraph_complementer(&g2, &g1, IGRAPH_LOOPS);
  igraph_write_graph_edgelist(&g2, stdout);
  igraph_destroy(&g1);
  igraph_destroy(&g2);
  
  return 0;
}


2.3. igraph_compose — Calculates the composition of two graphs

int igraph_compose(igraph_t *res, const igraph_t *g1, const igraph_t *g2,
		   igraph_vector_t *edge_map1, igraph_vector_t *edge_map2);

The composition of graphs contains the same number of vertices as the bigger graph of the two operands. It contains an (i,j) edge if and only if there is a k vertex, such that the first graphs contains an (i,k) edge and the second graph a (k,j) edge.

This is of course exactly the composition of two binary relations.

Two two graphs must have the same directedness, otherwise the function returns with an error message. Note that for undirected graphs the two relations are by definition symmetric.

Arguments: 

res:

Pointer to an uninitialized graph object, the result will be stored here.

g1:

The firs operand, a graph object.

g2:

The second operand, another graph object.

edge_map1:

If not a null pointer, then it must be a pointer to an initialized vector, and a mapping from the edges of the result graph to the edges of the first graph is stored here.

edge_map1:

If not a null pointer, then it must be a pointer to an initialized vector, and a mapping from the edges of the result graph to the edges of the second graph is stored here.

Returns: 

Error code.

Time complexity: O(|V|*d1*d2), |V| is the number of vertices in the first graph, d1 and d2 the average degree in the first and second graphs.

Example 26.7.  File examples/simple/igraph_compose.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>

int main() {

  igraph_t g1, g2, res;
  igraph_vector_t v;
  igraph_vector_t map1, map2;

  igraph_vector_init(&map1, 0);
  igraph_vector_init(&map2, 0);

  /* composition with the empty graph */
  igraph_empty(&g1, 5, IGRAPH_DIRECTED);
  igraph_full(&g2, 5, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);
  igraph_compose(&res, &g1, &g2, &map1, &map2);
  if (igraph_ecount(&res) != 0) { 
    return 1;
  }
  if (igraph_vector_size(&map1) != 0 || igraph_vector_size(&map2) != 0) {
    return 11;
  }
  igraph_destroy(&res);
  igraph_compose(&res, &g2, &g1, &map1, &map2);
  if (igraph_ecount(&res) != 0) { 
    return 2;
  }
  if (igraph_vector_size(&map1) != 0 || igraph_vector_size(&map2) != 0) {
    return 12;
  }
  igraph_destroy(&res);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  /* same but undirected */
  igraph_empty(&g1, 5, IGRAPH_UNDIRECTED);
  igraph_full(&g2, 5, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);
  igraph_compose(&res, &g1, &g2, &map1, &map2);
  if (igraph_ecount(&res) != 0) { 
    return 1;
  }
  if (igraph_vector_size(&map1) != 0 || igraph_vector_size(&map2) != 0) {
    return 11;
  }
  igraph_destroy(&res);
  igraph_compose(&res, &g2, &g1, &map1, &map2);
  if (igraph_ecount(&res) != 0) { 
    return 2;
  }
  if (igraph_vector_size(&map1) != 0 || igraph_vector_size(&map2) != 0) {
    return 12;
  }
  igraph_destroy(&res);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  /* proper directed graph */
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 5,6, -1);
  igraph_create(&g1, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);

  igraph_vector_init_int_end(&v, -1, 0,1, 2,4, 5,6, -1);
  igraph_create(&g2, &v, 0, IGRAPH_DIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_compose(&res, &g1, &g2, &map1, &map2);
  igraph_write_graph_edgelist(&res, stdout);
  igraph_vector_print(&map1);
  igraph_vector_print(&map2);
  igraph_destroy(&res);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  /* undirected graph */
  igraph_vector_init_int_end(&v, -1, 0,1, 1,2, 5,6, -1);
  igraph_create(&g1, &v, 0, IGRAPH_UNDIRECTED);
  igraph_vector_destroy(&v);

  igraph_vector_init_int_end(&v, -1, 0,1, 0,4, 5,6, -1);
  igraph_create(&g2, &v, 0, IGRAPH_UNDIRECTED);
  igraph_vector_destroy(&v);
  
  igraph_compose(&res, &g1, &g2, &map1, &map2);
  igraph_write_graph_edgelist(&res, stdout);
  igraph_vector_print(&map1);
  igraph_vector_print(&map2);
  igraph_destroy(&res);
  igraph_destroy(&g1);
  igraph_destroy(&g2);

  igraph_vector_destroy(&map2);
  igraph_vector_destroy(&map1);

  return 0;
}