For using the igraph C library
The igraph library can handle directed andundirected graphs. The igraph graphs are multisetsof ordered (if directed) or unordered (if undirected) labeled pairs.The labels of the pairs plus the number of vertices always starts withzero and ends with the number of edges minus one. In addition to that,a table of metadata is also attached to every graph, its mostimportant entries being the number of vertices in the graph and whetherthe graph is directed or undirected.
Like the edges, the igraph vertices are alsolabeled by numbers between zero and the number of vertices minus one.So, to summarize, a directed graph can be imagined like this:
( vertices: 6, directed: yes, { (0,2), (2,2), (3,2), (3,3), (3,4), (3,4), (4,3), (4,1) } )Here the edges are ordered pairs or vertex ids, and the graph is a multisetof edges plus some metadata.
An undirected graph is like this:
( vertices: 6, directed: no, { (0,2), (2,2), (2,3), (3,3), (3,4), (3,4), (3,4), (1,4) } )Here, an edge is an unordered pair of two vertex IDs. A graph is a multisetof edges plus metadata, just like in the directed case.
It is possible to convert between directed and undirected graphs,see theigraph_to_directed()andigraph_to_undirected() functions.
igraph aims to robustly support multigraphs, i.e. graphs whichhave more than one edge between some pairs of vertices, as well asgraphs with self-loops. Most functions which do not support such graphswill check their input and issue an error if it is not valid. Thoserare functions which do not perform this check clearly indicate thisin their documentation. To eliminate multiple edges from a graph, you can useigraph_simplify().
igraph has a simple and consistent interface. Most functions checktheir input for validity and display an informative error messagewhen something goes wrong. In order to support this, the majority of functionsreturn an error code. In basic usage, this code can be ignored, as thedefault behaviour is to abort the program immediately upon error. Seethe section on error handling formore information on this topic.
Results are typically returned throughoutput arguments,i.e. pointers to a data structure into which the result will be written.In almost all cases, this data structure is expected to be pre-initialized.A few simple functions communicate their result directly through their returnvalue—these functions can never encounter an error.
igraph introduces a few aliases to standard C data types that are then usedthroughout the library. The most important of these types isigraph_integer_t, which is an alias to either a 32-bit or a 64-bitsigned integer, depending on whether igraph was compiledin 32-bit or 64-bit mode. The size ofigraph_integer_t alsoinfluences the maximum number of vertices that an igraph graph can representas the number of vertices is stored in a variable of typeigraph_integer_t.
Since the size of a variable of typeigraph_integer_t maychange depending on how igraph is compiled, you cannot simply use%d or%ld as a placeholder for igraph integers inprintf format strings. igraph provides theIGRAPH_PRId macro, which maps tod,ldorlld depending on the size ofigraph_integer_t, andyou must use this macro inprintf format strings to avoid compilerwarnings.
Similarly to howigraph_integer_t maps to the standard sizesigned integer in the library,igraph_uint_t maps to a 32-bit ora 64-bitunsigned integer. It is guaranteed that the size ofigraph_integer_t is the same as the size ofigraph_uint_t.igraph providesIGRAPH_PRIu as a format string placeholder forvariables of typeigraph_uint_t.
Real numbers (i.e. quantities that can potentially be fractional orinfinite) are represented with a type namedigraph_real_t. Currentlyigraph_real_t is always aliased todouble, but it isstill good practice to useigraph_real_t in your own code for sakeof consistency.
Boolean values are represented with a type namedigraph_bool_t.It tries to be as small as possible since it only needs to represent a truthvalue. For printing purposes, you can treat it as an integer and use%d in format strings as a placeholder for anigraph_bool_t.
Upper and lower limits ofigraph_integer_t andigraph_uint_t are provided by the constants namedIGRAPH_INTEGER_MIN,IGRAPH_INTEGER_MAX,IGRAPH_UINT_MIN andIGRAPH_UINT_MAX.
This is the very minimal API inigraph. All the otherfunctions use this minimal set for creating and manipulatinggraphs.
This is a very important principle since it makes possible toimplement other data representations by implementing only thisminimal set.
This section lists all the functions and macros that are consideredas part of the core API from the point of view of theusersof igraph. Some of these functions and macros have sensible defaultimplementations that simply call some other core function (e.g.,igraph_empty() callsigraph_empty_attrs() with a null attributetable pointer). If you wish to experiment with implementing an alternativedata type, the actual number of functions that you need to replace is loweras you can rely on the same default implementations in most cases.
igraph_empty — Creates an empty graph with some vertices and no edges.igraph_empty_attrs — Creates an empty graph with some vertices, no edges and some graph attributes.igraph_copy — Creates an exact (deep) copy of a graph.igraph_destroy — Frees the memory allocated for a graph object.igraph_error_t igraph_empty(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed);
The most basic constructor, all the other constructors should callthis to create a minimal graph object. Our use of the term "empty graph"in the above description should be distinguished from the mathematicaldefinition of the empty or null graph. Strictly speaking, the empty or nullgraph in graph theory is the graph with no vertices and no edges. Howeverby "empty graph" as used inigraph we mean a graph having zero or morevertices, but no edges.
Arguments:
| Pointer to a not-yet initialized graph object. | ||||
| The number of vertices in the graph, a non-negative integer number is expected. | ||||
| Boolean; whether the graph is directed or not. Supported values are:
|
Returns:
Error code: |
Time complexity: O(|V|) for a graph with|V| vertices (and no edges).
Example 4.1. Fileexamples/simple/creation.c
#include <igraph.h>#include <assert.h>intmain(void) { igraph_t graph; igraph_vector_int_t edges;/* Create a directed graph with no vertices or edges. */igraph_empty(&graph, 0, IGRAPH_DIRECTED);/* Add 5 vertices. Vertex IDs will range from 0 to 4, inclusive. */igraph_add_vertices(&graph, 5, NULL);/* Add 5 edges, specified as 5 consecutive pairs of vertex IDs * stored in an integer vector. */igraph_vector_int_init_int(&edges, 10, 0,1, 0,2, 3,1, 2,1, 0,4);igraph_add_edges(&graph, &edges, NULL);igraph_vector_int_destroy(&edges);/* Now the graph has 5 vertices and 5 edges. */assert(igraph_vcount(&graph) == 5);assert(igraph_ecount(&graph) == 5);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_empty_attrs(igraph_t *graph, igraph_integer_t n, igraph_bool_t directed, void *attr);
Use this instead ofigraph_empty() if you wish to add some graphattributes right after initialization. This function is currentlynot very interesting for the ordinary user. Just supply 0 here oruseigraph_empty().
This function does not set any vertex attributes. To create a graph which hasvertex attributes, call this function specifying 0 vertices, then useigraph_add_vertices() to add vertices and their attributes.
Arguments:
| Pointer to a not-yet initialized graph object. | ||||
| The number of vertices in the graph; a non-negative integer number is expected. | ||||
| Boolean; whether the graph is directed or not. Supported values are:
| ||||
| The graph attributes. Supply |
Returns:
Error code: |
See also:
|
Time complexity: O(|V|) for a graph with|V| vertices (and no edges).
igraph_error_t igraph_copy(igraph_t *to, const igraph_t *from);
This function deeply copies a graph object to create an exactreplica of it. The new replica should be destroyed by callingigraph_destroy() on it when not needed any more.
You can also create a shallow copy of a graph by simply using thestandard assignment operator, but be careful and donotdestroy a shallow replica. To avoid this mistake, creating shallowcopies is not recommended.
Arguments:
| Pointer to an uninitialized graph object. |
| Pointer to the graph object to copy. |
Returns:
Error code. |
Time complexity: O(|V|+|E|) for agraph with |V| vertices and|E| edges.
Example 4.2. Fileexamples/simple/igraph_copy.c
#include <igraph.h>intmain(void) { igraph_t g1, g2; igraph_vector_int_t v1, v2;igraph_vector_int_init(&v1, 8);VECTOR(v1)[0] = 0;VECTOR(v1)[1] = 1;VECTOR(v1)[2] = 1;VECTOR(v1)[3] = 2;VECTOR(v1)[4] = 2;VECTOR(v1)[5] = 3;VECTOR(v1)[6] = 2;VECTOR(v1)[7] = 2;igraph_create(&g1, &v1, 0, 0);igraph_copy(&g2, &g1);igraph_vector_int_init(&v2, 0);igraph_get_edgelist(&g2, &v2, 0);if (!igraph_vector_int_all_e(&v1, &v2)) {return 1; }igraph_vector_int_destroy(&v1);igraph_vector_int_destroy(&v2);igraph_destroy(&g1);igraph_destroy(&g2);return 0;}
void igraph_destroy(igraph_t *graph);
This function should be called for every graph object exactly once.
This function invalidates all iterators (of course), but theiterators of a graph should be destroyed before the graph itselfanyway.
Arguments:
| Pointer to the graph to free. |
Time complexity: operating system specific.
igraph_vcount — The number of vertices in a graph.igraph_ecount — The number of edges in a graph.igraph_is_directed — Is this a directed graph?igraph_edge — Returns the head and tail vertices of an edge.igraph_edges — Gives the head and tail vertices of a series of edges.IGRAPH_FROM — The source vertex of an edge.IGRAPH_TO — The target vertex of an edge.IGRAPH_OTHER — The other endpoint of an edge.igraph_get_eid — Get the edge ID from the endpoints of an edge.igraph_get_eids — Return edge IDs based on the adjacent vertices.igraph_get_all_eids_between — Returns all edge IDs between a pair of vertices.igraph_neighbors — Adjacent vertices to a vertex.igraph_incident — Gives the incident edges of a vertex.igraph_degree — The degree of some vertices in a graph.igraph_degree_1 — The degree of of a single vertex in the graph.igraph_integer_t igraph_vcount(const igraph_t *graph);
Arguments:
| The graph. |
Returns:
Number of vertices. |
Time complexity: O(1)
igraph_integer_t igraph_ecount(const igraph_t *graph);
Arguments:
| The graph. |
Returns:
Number of edges. |
Time complexity: O(1)
igraph_bool_t igraph_is_directed(const igraph_t *graph);
Arguments:
| The graph. |
Returns:
Boolean value, |
Time complexity: O(1)
Example 4.3. Fileexamples/simple/igraph_is_directed.c
#include <igraph.h>intmain(void) { igraph_t g;igraph_empty(&g, 0, 0);if (igraph_is_directed(&g)) {return 1; }igraph_destroy(&g);igraph_empty(&g, 0, 1);if (!igraph_is_directed(&g)) {return 2; }igraph_destroy(&g);return 0;}
igraph_error_t igraph_edge( const igraph_t *graph, igraph_integer_t eid, igraph_integer_t *from, igraph_integer_t *to);
Arguments:
| The graph object. |
| The edge ID. |
| Pointer to anigraph_integer_t. The tail (source) ofthe edge will be placed here. |
| Pointer to anigraph_integer_t. The head (target) of theedge will be placed here. |
Returns:
Error code. |
See also:
|
Added in version 0.2.
Time complexity: O(1).
igraph_error_t igraph_edges(const igraph_t *graph, igraph_es_t eids, igraph_vector_int_t *edges);
Arguments:
| The graph object. |
| Edge selector, the series of edges. |
| Pointer to an initialized vector. The start and endpoints of each edge will be placed here. |
Returns:
Error code. |
See also:
|
Time complexity: O(k) where k is the number of edges in the selector.
#define IGRAPH_FROM(graph,eid)
Faster thanigraph_edge(), but no error checking is done:eid is assumed to be valid.
Arguments:
| The graph. |
| The edge ID. |
Returns:
The source vertex of the edge. |
See also:
|
#define IGRAPH_TO(graph,eid)
Faster thanigraph_edge(), but no error checking is done:eid is assumed to be valid.
Arguments:
| The graph object. |
| The edge ID. |
Returns:
The target vertex of the edge. |
See also:
|
#define IGRAPH_OTHER(graph,eid,vid)
Typically used with undirected edges when one endpoint of the edge is known,and the other endpoint is needed. No error checking is done:eid andvid are assumed to be valid.
Arguments:
| The graph object. |
| The edge ID. |
| The vertex ID of one endpoint of an edge. |
Returns:
The other endpoint of the edge. |
See also:
|
igraph_error_t igraph_get_eid(const igraph_t *graph, igraph_integer_t *eid, igraph_integer_t from, igraph_integer_t to, igraph_bool_t directed, igraph_bool_t error);
For undirected graphsfrom andto are exchangeable.
Arguments:
| The graph object. |
| Pointer to an integer, the edge ID will be stored here. If |
| The starting point of the edge. |
| The end point of the edge. |
| Boolean, whether to search for directed edges in a directed graph. Ignored for undirected graphs. |
| Boolean, whether to report an error if the edge was not found. If it is false, then |
Returns:
Error code. |
See also:
|
Time complexity: O(log (d)), where d is smaller of the out-degreeoffrom and in-degree ofto ifdirected is true. Ifdirectedis false, then it is O(log(d)+log(d2)), where d is the same as before andd2 is the minimum of the out-degree ofto and the in-degree offrom.
Example 4.4. Fileexamples/simple/igraph_get_eid.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_integer_t eid; igraph_vector_int_t hist; igraph_integer_t i;/* DIRECTED */igraph_star(&g, 10, IGRAPH_STAR_OUT, 0);igraph_vector_int_init(&hist, 9);for (i = 1; i < 10; i++) {igraph_get_eid(&g, &eid, 0, i, IGRAPH_DIRECTED,/*error=*/ true);VECTOR(hist)[ eid ] = 1; }igraph_vector_int_print(&hist);igraph_vector_int_destroy(&hist);igraph_destroy(&g);/* UNDIRECTED */igraph_star(&g, 10, IGRAPH_STAR_UNDIRECTED, 0);igraph_vector_int_init(&hist, 9);for (i = 1; i < 10; i++) {igraph_get_eid(&g, &eid, 0, i, IGRAPH_UNDIRECTED,/*error=*/ true);VECTOR(hist)[ eid ] += 1;igraph_get_eid(&g, &eid, i, 0, IGRAPH_DIRECTED,/*error=*/ true);VECTOR(hist)[ eid ] += 1; }igraph_vector_int_print(&hist);igraph_vector_int_destroy(&hist);igraph_destroy(&g);return 0;}
Added in version 0.2.
igraph_error_t igraph_get_eids(const igraph_t *graph, igraph_vector_int_t *eids, const igraph_vector_int_t *pairs, igraph_bool_t directed, igraph_bool_t error);
The pairs of vertex IDs for which the edges are looked up are takenconsecutively from thepairs vector, i.e.VECTOR(pairs)[0]andVECTOR(pairs)[1] specify the first pair,VECTOR(pairs)[2] andVECTOR(pairs)[3] the secondpair, etc.
If you have a sequence of vertex IDs that describe apath on the graph,useigraph_expand_path_to_pairs() to convert them to a list of vertexpairs along the path.
If theerror argument is true, then it is an error to specify pairsof vertices that are not connected. Otherwise -1 is reported for vertex pairswithout at least one edge between them.
If there are multiple edges in the graph, then these are ignored;i.e. for a given pair of vertex IDs, igraph always returns the same edge ID,even if the pair appears multiple times inpairs.
Arguments:
| The input graph. |
| Pointer to an initialized vector, the result is stored here. It will be resized as needed. |
| Vector giving pairs of vertices to fetch the edges for. |
| Boolean, whether to consider edge directions in directed graphs. This is ignored for undirected graphs. |
| Boolean, whether it is an error to supply non-connected vertices. If false, then -1 is returned for non-connected pairs. |
Returns:
Error code. |
Time complexity: O(n log(d)), where n is the number of queriededges and d is the average degree of the vertices.
See also:
|
Example 4.5. Fileexamples/simple/igraph_get_eids.c
#include <igraph.h>#include <stdlib.h>voidprint_vector_int(igraph_vector_int_t *v, FILE *f) { igraph_integer_t i;for (i = 0; i <igraph_vector_int_size(v); i++) {fprintf(f, " %" IGRAPH_PRId,VECTOR(*v)[i]); }fprintf(f, "\n");}intmain(void) { igraph_t g; igraph_integer_t nodes = 100; igraph_integer_t edges = 1000; igraph_real_t p = 3.0 / nodes; igraph_integer_t runs = 10; igraph_integer_t r, e, ecount; igraph_vector_int_t eids, pairs, path;igraph_rng_seed(igraph_rng_default(), 42);/* make tests deterministic */igraph_vector_int_init(&pairs, edges * 2);igraph_vector_int_init(&path, 0);igraph_vector_int_init(&eids, 0);for (r = 0; r < runs; r++) {igraph_vector_int_resize(&pairs, edges * 2);igraph_vector_int_clear(&path);igraph_vector_int_clear(&eids);igraph_erdos_renyi_game_gnp(&g, nodes, p,/*directed=*/ 0,/*loops=*/ 0); ecount =igraph_ecount(&g);for (e = 0; e < edges; e++) { igraph_integer_t edge =RNG_INTEGER(0, ecount - 1);VECTOR(pairs)[2 * e] =IGRAPH_FROM(&g, edge);VECTOR(pairs)[2 * e + 1] =IGRAPH_TO(&g, edge); }igraph_get_eids(&g, &eids, &pairs,/* directed= */ 0,/*error=*/ 1);for (e = 0; e < edges; e++) { igraph_integer_t edge =VECTOR(eids)[e]; igraph_integer_t from1 =VECTOR(pairs)[2 * e]; igraph_integer_t to1 =VECTOR(pairs)[2 * e + 1]; igraph_integer_t from2 =IGRAPH_FROM(&g, edge); igraph_integer_t to2 =IGRAPH_TO(&g, edge); igraph_integer_t min1 = from1 < to1 ? from1 : to1; igraph_integer_t max1 = from1 < to1 ? to1 : from1; igraph_integer_t min2 = from2 < to2 ? from2 : to2; igraph_integer_t max2 = from2 < to2 ? to2 : from2;if (min1 != min2 || max1 != max2) {return 11; } }igraph_diameter(&g,/*res=*/ 0,/*from=*/ 0,/*to=*/ 0, &path, NULL, IGRAPH_UNDIRECTED,/*unconn=*/ 1);igraph_vector_int_update(&pairs, &path);igraph_expand_path_to_pairs(&pairs);igraph_get_eids(&g, &eids, &pairs, 0,/*error=*/ 1);for (e = 0; e <igraph_vector_int_size(&path) - 1; e++) { igraph_integer_t edge =VECTOR(eids)[e]; igraph_integer_t from1 =VECTOR(path)[e]; igraph_integer_t to1 =VECTOR(path)[e + 1]; igraph_integer_t from2 =IGRAPH_FROM(&g, edge); igraph_integer_t to2 =IGRAPH_TO(&g, edge); igraph_integer_t min1 = from1 < to1 ? from1 : to1; igraph_integer_t max1 = from1 < to1 ? to1 : from1; igraph_integer_t min2 = from2 < to2 ? from2 : to2; igraph_integer_t max2 = from2 < to2 ? to2 : from2;if (min1 != min2 || max1 != max2) {return 12; } }igraph_destroy(&g); }igraph_vector_int_destroy(&path);igraph_vector_int_destroy(&pairs);igraph_vector_int_destroy(&eids);return 0;}
igraph_error_t igraph_get_all_eids_between( const igraph_t *graph, igraph_vector_int_t *eids, igraph_integer_t source, igraph_integer_t target, igraph_bool_t directed);
For undirected graphssource andtarget are exchangeable.
Arguments:
| The input graph. |
| Pointer to an initialized vector, the result is stored here. It will be resized as needed. |
| The ID of the source vertex |
| The ID of the target vertex |
| Boolean, whether to consider edge directions in directed graphs. This is ignored for undirected graphs. |
Returns:
Error code. |
Time complexity: TODO
See also:
|
igraph_error_t igraph_neighbors(const igraph_t *graph, igraph_vector_int_t *neis, igraph_integer_t pnode, igraph_neimode_t mode);
Arguments:
| The graph to work on. |
| This vector will contain the result. The vector should be initialized beforehand and will be resized. Starting from igraph version 0.4 this vector is always sorted, the vertex IDs are in increasing order. If one neighbor is connected with multiple edges, the neighbor will be returned multiple times. |
| The id of the node for which the adjacent vertices are to be searched. |
| Defines the way adjacent vertices are searched in directed graphs. It can have the following values: |
Returns:
Error code: |
Time complexity: O(d),d is the numberof adjacent vertices to the queried vertex.
Example 4.6. Fileexamples/simple/igraph_neighbors.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_vector_int_t v;igraph_vector_int_init(&v, 0);igraph_small(&g, 4, IGRAPH_DIRECTED, 0,1, 1,2, 2,3, 2,2, -1);igraph_neighbors(&g, &v, 2, IGRAPH_OUT);igraph_vector_int_sort(&v);igraph_vector_int_print(&v);igraph_neighbors(&g, &v, 2, IGRAPH_IN);igraph_vector_int_sort(&v);igraph_vector_int_print(&v);igraph_neighbors(&g, &v, 2, IGRAPH_ALL);igraph_vector_int_sort(&v);igraph_vector_int_print(&v);igraph_vector_int_destroy(&v);igraph_destroy(&g);return 0;}
igraph_error_t igraph_incident(const igraph_t *graph, igraph_vector_int_t *eids, igraph_integer_t pnode, igraph_neimode_t mode);
Arguments:
| The graph object. |
| An initialized vector. It will be resizedto hold the result. |
| A vertex ID. |
| Specifies what kind of edges to include for directedgraphs. |
Returns:
Error code. |
Added in version 0.2.
Time complexity: O(d), the number of incident edges topnode.
igraph_error_t igraph_degree(const igraph_t *graph, igraph_vector_int_t *res, const igraph_vs_t vids, igraph_neimode_t mode, igraph_bool_t loops);
This function calculates the in-, out- or total degree of thespecified vertices.
This function returns the result as a vector ofigraph_integer_tvalues. In applications whereigraph_real_t is desired, useigraph_strength() withNULL weights.
Arguments:
| The graph. |
| Integer vector, this will contain the result. It should be initialized and will be resized to be the appropriate size. |
| Vertex selector, giving the vertex IDs of which the degree will be calculated. |
| Defines the type of the degree for directed graphs. Valid modes are: |
| Boolean, gives whether the self-loops should be counted. |
Returns:
Error code: |
Time complexity: O(v) ifloops istrue, andO(v*d) otherwise. v is the number ofvertices for which the degree will be calculated, andd is their (average) degree.
See also:
|
Example 4.7. Fileexamples/simple/igraph_degree.c
#include <igraph.h>igraph_bool_thandshaking_lemma(igraph_t *g, igraph_vector_int_t *v) {/* Consistency check of the handshaking lemma: * If d is the sum of all vertex degrees, then d = 2|E|. */returnigraph_vector_int_sum(v) == 2 *igraph_ecount(g);}intmain(void) { igraph_t g; igraph_vector_int_t v; igraph_vector_int_t seq; igraph_integer_t mdeg;/* Create graph */igraph_vector_int_init(&v, 8);igraph_small(&g, 4, IGRAPH_DIRECTED, 0,1, 1,2, 2,3, 2,2, -1);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_OUT, IGRAPH_NO_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_OUT, IGRAPH_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_IN, IGRAPH_NO_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_IN, IGRAPH_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);igraph_vector_int_print(&v);if (!handshaking_lemma(&g, &v)) {exit(3); }igraph_destroy(&g);igraph_small(&g, 4, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,3, 2,2, -1);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_OUT, IGRAPH_NO_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_OUT, IGRAPH_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_IN, IGRAPH_NO_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_IN, IGRAPH_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_ALL, IGRAPH_NO_LOOPS);igraph_vector_int_print(&v);igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);igraph_vector_int_print(&v);if (!handshaking_lemma(&g, &v)) {exit(4); }/* Degree of the same vertex multiple times */igraph_vector_int_init(&seq, 3);VECTOR(seq)[0] = 2;VECTOR(seq)[1] = 0;VECTOR(seq)[2] = 2;igraph_degree(&g, &v,igraph_vss_vector(&seq), IGRAPH_ALL, IGRAPH_LOOPS);igraph_vector_int_print(&v);igraph_destroy(&g);igraph_vector_int_destroy(&seq);/* Maximum degree */igraph_ring(&g, 10, IGRAPH_UNDIRECTED,/* mutual */ false,/* circular */ false);igraph_maxdegree(&g, &mdeg,igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);if (mdeg != 2) {exit(5); }igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);if (!handshaking_lemma(&g, &v)) {exit(6); }igraph_destroy(&g);igraph_full(&g, 10, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);igraph_maxdegree(&g, &mdeg,igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);if (mdeg != 9) {exit(7); }igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);if (!handshaking_lemma(&g, &v)) {exit(8); }igraph_destroy(&g);igraph_star(&g, 10, IGRAPH_STAR_OUT,/* center */ 0);igraph_maxdegree(&g, &mdeg,igraph_vss_all(), IGRAPH_OUT, IGRAPH_LOOPS);if (mdeg != 9) {exit(9); }igraph_maxdegree(&g, &mdeg,igraph_vss_all(), IGRAPH_IN, IGRAPH_LOOPS);if (mdeg != 1) {exit(10); }igraph_maxdegree(&g, &mdeg,igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);if (mdeg != 9) {exit(11); }igraph_degree(&g, &v,igraph_vss_all(), IGRAPH_ALL, IGRAPH_LOOPS);if (!handshaking_lemma(&g, &v)) {exit(12); }igraph_destroy(&g);igraph_vector_int_destroy(&v);return 0;}
igraph_error_t igraph_degree_1(const igraph_t *graph, igraph_integer_t *deg, igraph_integer_t vid, igraph_neimode_t mode, igraph_bool_t loops);
This function calculates the in-, out- or total degree of a single vertex.For a single vertex, it is more efficient than callingigraph_degree().
Arguments:
| The graph. |
| Pointer to the integer where the computed degree will be stored. |
| The vertex for which the degree will be calculated. |
| Defines the type of the degree for directed graphs. Valid modes are: |
| Boolean, gives whether the self-loops should be counted. |
Returns:
Error code. |
See also:
|
Time complexity: O(1) ifloops istrue, andO(d) otherwise, where d is the degree.
igraph_add_edge — Adds a single edge to a graph.igraph_add_edges — Adds edges to a graph object.igraph_add_vertices — Adds vertices to a graph.igraph_delete_edges — Removes edges from a graph.igraph_delete_vertices — Removes some vertices (with all their edges) from the graph.igraph_delete_vertices_idx — Removes some vertices (with all their edges) from the graph.igraph_error_t igraph_add_edge(igraph_t *graph, igraph_integer_t from, igraph_integer_t to);
For directed graphs the edge points fromfrom toto.
Note that if you want to add many edges to a big graph, then it isinefficient to add them one by one, it is better to collect them intoa vector and add all of them via a singleigraph_add_edges() call.
Arguments:
| The graph. |
| The id of the first vertex of the edge. |
| The id of the second vertex of the edge. |
Returns:
Error code. |
See also:
|
Time complexity: O(|V|+|E|), the number of edges plus the number ofvertices.
igraph_error_t igraph_add_edges(igraph_t *graph, const igraph_vector_int_t *edges, void *attr);
The edges are given in a vector, thefirst two elements define the first edge (the order isfrom,to for directedgraphs). The vectorshould contain even number of integer numbers between zero and thenumber of vertices in the graph minus one (inclusive). If you alsowant to add new vertices, calligraph_add_vertices() first.
Arguments:
| The graph to which the edges will be added. |
| The edges themselves. |
| The attributes of the new edges. You can supply a null pointer here if you do not need edge attributes. |
Returns:
Error code: |
This function invalidates all iterators.
Time complexity: O(|V|+|E|) where |V| is the number of vertices and|E| is the number of edges in thenew, extended graph.
Example 4.8. Fileexamples/simple/creation.c
#include <igraph.h>#include <assert.h>intmain(void) { igraph_t graph; igraph_vector_int_t edges;/* Create a directed graph with no vertices or edges. */igraph_empty(&graph, 0, IGRAPH_DIRECTED);/* Add 5 vertices. Vertex IDs will range from 0 to 4, inclusive. */igraph_add_vertices(&graph, 5, NULL);/* Add 5 edges, specified as 5 consecutive pairs of vertex IDs * stored in an integer vector. */igraph_vector_int_init_int(&edges, 10, 0,1, 0,2, 3,1, 2,1, 0,4);igraph_add_edges(&graph, &edges, NULL);igraph_vector_int_destroy(&edges);/* Now the graph has 5 vertices and 5 edges. */assert(igraph_vcount(&graph) == 5);assert(igraph_ecount(&graph) == 5);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_add_vertices(igraph_t *graph, igraph_integer_t nv, void *attr);
This function invalidates all iterators.
Arguments:
| The graph object to extend. |
| Non-negative integer specifying the number of vertices to add. |
| The attributes of the new vertices. You can supply a null pointer here if you do not need vertex attributes. |
Returns:
Error code: |
Time complexity: O(|V|) where |V| is the number of vertices in thenew,extended graph.
Example 4.9. Fileexamples/simple/creation.c
#include <igraph.h>#include <assert.h>intmain(void) { igraph_t graph; igraph_vector_int_t edges;/* Create a directed graph with no vertices or edges. */igraph_empty(&graph, 0, IGRAPH_DIRECTED);/* Add 5 vertices. Vertex IDs will range from 0 to 4, inclusive. */igraph_add_vertices(&graph, 5, NULL);/* Add 5 edges, specified as 5 consecutive pairs of vertex IDs * stored in an integer vector. */igraph_vector_int_init_int(&edges, 10, 0,1, 0,2, 3,1, 2,1, 0,4);igraph_add_edges(&graph, &edges, NULL);igraph_vector_int_destroy(&edges);/* Now the graph has 5 vertices and 5 edges. */assert(igraph_vcount(&graph) == 5);assert(igraph_ecount(&graph) == 5);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_delete_edges(igraph_t *graph, igraph_es_t edges);
The edges to remove are specified as an edge selector.
This function cannot remove vertices; vertices will be kept even if they loseall their edges.
This function invalidates all iterators.
Arguments:
| The graph to work on. |
| The edges to remove. |
Returns:
Error code. |
Time complexity: O(|V|+|E|) where |V| and |E| are the number of verticesand edges in theoriginal graph, respectively.
Example 4.10. Fileexamples/simple/igraph_delete_edges.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_es_t es;igraph_small(&g, 4, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,2, 2,3, -1);igraph_es_pairs_small(&es, IGRAPH_DIRECTED, 3, 2, -1);igraph_delete_edges(&g, es);if (igraph_ecount(&g) != 3) {return 1; }igraph_es_destroy(&es);igraph_destroy(&g);return 0;}
igraph_error_t igraph_delete_vertices(igraph_t *graph, const igraph_vs_t vertices);
This function changes the IDs of the vertices (except in some veryspecial cases, but these should not be relied on anyway).
This function invalidates all iterators.
Arguments:
| The graph to work on. |
| The IDs of the vertices to remove, in a vector. The vector may contain the same ID more than once. |
Returns:
Error code: |
Time complexity: O(|V|+|E|), |V| and |E| are the number of vertices andedges in the original graph.
Example 4.11. Fileexamples/simple/igraph_delete_vertices.c
#include <igraph.h>intmain(void) { igraph_t g;/* without edges */igraph_small(&g, 15, IGRAPH_UNDIRECTED, -1);igraph_delete_vertices(&g,igraph_vss_1(2));if (igraph_vcount(&g) != 14) {return 2; }igraph_destroy(&g);/* with edges */igraph_small(&g, 4, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,3, 2,2, -1);igraph_delete_vertices(&g,igraph_vss_1(2));if (igraph_vcount(&g) != 3) {return 3; }if (igraph_ecount(&g) != 1) {return 4; }igraph_destroy(&g);return 0;}
igraph_error_t igraph_delete_vertices_idx( igraph_t *graph, const igraph_vs_t vertices, igraph_vector_int_t *idx, igraph_vector_int_t *invidx);
This function changes the IDs of the vertices (except in some veryspecial cases, but these should not be relied on anyway). You can use theidx argument to obtain the mapping from old vertex IDs to the new ones,and thenewidx argument to obtain the reverse mapping.
This function invalidates all iterators.
Arguments:
| The graph to work on. |
| The IDs of the vertices to remove, in a vector. The vector may contain the same ID more than once. |
| An optional pointer to a vector that provides the mapping from the vertex IDsbefore the removal to the vertex IDsafter the removal,plus one. Zero is used to represent vertices that were removed during the operation. You can supply |
| An optional pointer to a vector that provides the mapping from the vertex IDsafter the removal to the vertex IDsbefore the removal. You can supply |
Returns:
Error code: |
Time complexity: O(|V|+|E|), |V| and |E| are the number of vertices andedges in the original graph.
Example 4.12. Fileexamples/simple/igraph_delete_vertices.c
#include <igraph.h>intmain(void) { igraph_t g;/* without edges */igraph_small(&g, 15, IGRAPH_UNDIRECTED, -1);igraph_delete_vertices(&g,igraph_vss_1(2));if (igraph_vcount(&g) != 14) {return 2; }igraph_destroy(&g);/* with edges */igraph_small(&g, 4, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,3, 2,2, -1);igraph_delete_vertices(&g,igraph_vss_1(2));if (igraph_vcount(&g) != 3) {return 3; }if (igraph_ecount(&g) != 1) {return 4; }igraph_destroy(&g);return 0;}
IGRAPH_VCOUNT_MAX — The maximum number of vertices supported in igraph graphs.IGRAPH_ECOUNT_MAX — The maximum number of edges supported in igraph graphs.igraph_expand_path_to_pairs — Helper function to convert a sequence of vertex IDs describing a path into a "pairs" vector.igraph_invalidate_cache — Invalidates the internal cache of an igraph graph.igraph_is_same_graph — Are two graphs identical as labelled graphs?#define IGRAPH_VCOUNT_MAX
The value of this constant is one less thanIGRAPH_INTEGER_MAX .When igraph is compiled in 32-bit mode, this means that you are limitedto 231 – 2 (about 2.1 billion) vertices. In64-bit mode, the limit is 263 – 2 so you are muchmore likely to hit out-of-memory issues due to other reasons before reachingthis limit.
#define IGRAPH_ECOUNT_MAX
The value of this constant is half ofIGRAPH_INTEGER_MAX .When igraph is compiled in 32-bit mode, this means that you are limitedto approximately 230 (about 1.07 billion)vertices. In 64-bit mode, the limit is approximately262 so you are much more likely to hitout-of-memory issues due to other reasons before reaching this limit.
igraph_error_t igraph_expand_path_to_pairs(igraph_vector_int_t* path);
This function is useful when you have a sequence of vertex IDs in a graph andyou would like to retrieve the IDs of the edges between them. The functionduplicates all but the first and the last elements in the vector, effectivelyconverting the path into a vector of vertex IDs that can be passed toigraph_get_eids().
Arguments:
| the input vector. It will be modified in-place and it will be resized as needed. When the vector contains less than two vertex IDs, it will be cleared. |
Returns:
Error code: |
void igraph_invalidate_cache(const igraph_t* graph);
igraph graphs cache some basic properties about themselves in an internaldata structure. This function invalidates the contents of the cache andforces a recalculation of the cached properties the next time they areneeded.
You should not need to call this function during normal usage; however, wemight ask you to call this function explicitly if we suspect that you arerunning into a bug in igraph's cache handling. A tell-tale sign of an invalidcache entry is that the result of a cached igraph function (such asigraph_is_dag() origraph_is_simple()) is different before andafter a cache invalidation.
Arguments:
| The graph whose cache is to be invalidated. |
Time complexity: O(1).
igraph_error_t igraph_is_same_graph(const igraph_t *graph1, const igraph_t *graph2, igraph_bool_t *res);
Two graphs are considered to be the same if they have the same vertex and edge sets.Graphs which are the same may have multiple different representations in igraph,hence the need for this function.
This function verifies that the two graphs have the same directedness, the samenumber of vertices, and that they contain precisely the same edges (regardless of their ordering)when written in terms of vertex indices. Graph attributes are not taken into account.
This concept is different from isomorphism. For example, the graphs0-1, 2-1 and1-2, 0-1 are considered the samebecause they only differ in the ordering of their edge lists and the orderingof vertices in an undirected edge. However, they are not the same as0-2, 1-2, even though they are isomorphic to it.Note that this latter graph contains the edge0-2while the former two do not — thus their edge sets differ.
Arguments:
| The first graph object. |
| The second graph object. |
| The result will be stored here. |
Returns:
Error code. |
Time complexity: O(E), the number of edges in the graphs.
See also:
|
| ← Chapter 3. Tutorial | Chapter 5. Error handling → |