For using the igraph C library
These functions usually calculate some structural property of a graph, like its diameter, the degree of the nodes, etc.
int igraph_are_connected(const igraph_t *graph,
igraph_integer_t v1, igraph_integer_t v2,
igraph_bool_t *res);
Arguments:
|
The graph object. |
|
The first vertex. |
|
The second vertex. |
|
Boolean, |
Returns:
The error code |
The function is of course symmetric for undirected graphs.
Time complexity: O( min(log(d1), log(d2)) ),
d1 is the (out-)degree of v1 and d2 is the (in-)degree of v2.
igraph_shortest_paths — The length of the shortest paths between vertices.igraph_shortest_paths_dijkstra — Weighted shortest path lengths between vertices.igraph_shortest_paths_bellman_ford — Weighted shortest path lengths between vertices, allowing negative weights.igraph_shortest_paths_johnson — Weighted shortest path lengths between vertices, using Johnson's algorithm.igraph_get_shortest_paths — Shortest paths from a vertex.igraph_get_shortest_path — Shortest path from one vertex to another one.igraph_get_shortest_paths_dijkstra — Weighted shortest paths from a vertex.igraph_get_shortest_path_dijkstra — Weighted shortest path from one vertex to another one.igraph_get_shortest_paths_bellman_ford — Weighted shortest paths from a vertex, allowing negative weights.igraph_get_shortest_path_bellman_ford — Weighted shortest path from one vertex to another one.igraph_get_all_shortest_paths — All shortest paths (geodesics) from a vertex.igraph_get_all_shortest_paths_dijkstra — All weighted shortest paths (geodesics) from a vertex.igraph_get_all_simple_paths — List all simple paths from one source.igraph_average_path_length — Calculates the average unweighted shortest path length between all vertex pairs.igraph_average_path_length_dijkstra — Calculates the average weighted shortest path length between all vertex pairs.igraph_path_length_hist — Create a histogram of all shortest path lengths.igraph_diameter — Calculates the diameter of a graph (longest geodesic).igraph_diameter_dijkstra — Calculates the weighted diameter of a graph using Dijkstra's algorithm.igraph_girth — The girth of a graph is the length of the shortest cycle in it.igraph_eccentricity — Eccentricity of some vertices.igraph_radius — Radius of a graph.
int igraph_shortest_paths(const igraph_t *graph, igraph_matrix_t *res,
const igraph_vs_t from, const igraph_vs_t to,
igraph_neimode_t mode);
Arguments:
|
The graph object. |
||||||
|
The result of the calculation, a matrix. A pointer to an
initialized matrix, to be more precise. The matrix will be
resized if needed. It will have the same
number of rows as the length of the |
||||||
|
The source vertices. |
||||||
|
The target vertices. It is not allowed to include a vertex twice or more. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
Returns:
|
Error code:
|
Time complexity: O(n(|V|+|E|)), n is the number of vertices to calculate, |V| and |E| are the number of vertices and edges in the graph.
See also:
|
int igraph_shortest_paths_dijkstra(const igraph_t *graph,
igraph_matrix_t *res,
const igraph_vs_t from,
const igraph_vs_t to,
const igraph_vector_t *weights,
igraph_neimode_t mode);
This function implements Dijkstra's algorithm to find the weighted shortest path lengths to all vertices from a single source. It is run independently for the given sources. It uses a binary heap for efficient implementation.
Arguments:
|
The input graph, can be directed. |
|
The result, a matrix. A pointer to an initialized matrix
should be passed here. The matrix will be resized as needed.
Each row contains the distances from a single source, to the
vertices given in the |
|
The source vertices. |
|
The target vertices. It is not allowed to include a vertex twice or more. |
|
The edge weights. All edge weights must be
non-negative for Dijkstra's algorithm to work. Additionally, no
edge weight may be NaN. If either case does not hold, an error
is returned. If this is a null pointer, then the unweighted
version, |
|
For directed graphs; whether to follow paths along edge
directions ( |
Returns:
Error code. |
Time complexity: O(s*|E|log|E|+|V|), where |V| is the number of vertices, |E| the number of edges and s the number of sources.
See also:
|
Example 13.1. File examples/simple/dijkstra.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2008-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 print_matrix(const igraph_matrix_t *m) { long int nrow = igraph_matrix_nrow(m); long int ncol = igraph_matrix_ncol(m); long int i, j; igraph_real_t val; for (i = 0; i < nrow; i++) { printf("%li:", i); for (j = 0; j < ncol; j++) { val = MATRIX(*m, i, j); if (igraph_is_inf(val)) { if (val < 0) { printf("-inf"); } else { printf(" inf"); } } else { printf(" %3.0f", val); } } printf("\n"); } return 0; } int main() { igraph_t g; igraph_vector_t weights; igraph_real_t weights_data[] = { 0, 2, 1, 0, 5, 2, 1, 1, 0, 2, 2, 8, 1, 1, 3, 1, 1, 4, 2, 1 }; igraph_matrix_t res; igraph_small(&g, 10, IGRAPH_DIRECTED, 0, 1, 0, 2, 0, 3, 1, 2, 1, 4, 1, 5, 2, 3, 2, 6, 3, 2, 3, 6, 4, 5, 4, 7, 5, 6, 5, 8, 5, 9, 7, 5, 7, 8, 8, 9, 5, 2, 2, 1, -1); igraph_vector_view(&weights, weights_data, sizeof(weights_data) / sizeof(igraph_real_t)); igraph_matrix_init(&res, 0, 0); igraph_shortest_paths_dijkstra(&g, &res, igraph_vss_all(), igraph_vss_all(), &weights, IGRAPH_OUT); print_matrix(&res); igraph_matrix_destroy(&res); igraph_destroy(&g); return 0; }
int igraph_shortest_paths_bellman_ford(const igraph_t *graph,
igraph_matrix_t *res,
const igraph_vs_t from,
const igraph_vs_t to,
const igraph_vector_t *weights,
igraph_neimode_t mode);
This function implements the Bellman-Ford algorithm to find the weighted
shortest paths to all vertices from a single source, allowing negative weights.
It is run independently for the given sources. If there are no negative
weights, you are better off with igraph_shortest_paths_dijkstra() .
Arguments:
|
The input graph, can be directed. |
|
The result, a matrix. A pointer to an initialized matrix
should be passed here, the matrix will be resized if needed.
Each row contains the distances from a single source, to all
vertices in the graph, in the order of vertex ids. For unreachable
vertices the matrix contains |
|
The source vertices. |
|
The target vertices. It is not allowed to include a vertex twice or more. |
|
The edge weights. There mustn't be any closed loop in
the graph that has a negative total weight (since this would allow
us to decrease the weight of any path containing at least a single
vertex of this loop infinitely). Additionally, no edge weight may
be NaN. If either case does not hold, an error is returned. If this
is a null pointer, then the unweighted version,
|
|
For directed graphs; whether to follow paths along edge
directions ( |
Returns:
Error code. |
Time complexity: O(s*|E|*|V|), where |V| is the number of vertices, |E| the number of edges and s the number of sources.
See also:
|
Example 13.2. File examples/simple/bellman_ford.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2008-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 print_matrix(const igraph_matrix_t *m) { long int nrow = igraph_matrix_nrow(m); long int ncol = igraph_matrix_ncol(m); long int i, j; igraph_real_t val; for (i = 0; i < nrow; i++) { printf("%li:", i); for (j = 0; j < ncol; j++) { val = MATRIX(*m, i, j); if (igraph_is_inf(val)) { if (val < 0) { printf("-inf"); } else { printf(" inf"); } } else { printf(" %3.0f", val); } } printf("\n"); } return 0; } int main() { igraph_t g; igraph_vector_t weights; igraph_real_t weights_data_0[] = { 0, 2, 1, 0, 5, 2, 1, 1, 0, 2, 2, 8, 1, 1, 3, 1, 1, 4, 2, 1 }; igraph_real_t weights_data_1[] = { 6, 7, 8, -4, -2, -3, 9, 2, 7 }; igraph_real_t weights_data_2[] = { 6, 7, 2, -4, -2, -3, 9, 2, 7 }; igraph_matrix_t res; /* Graph with only positive weights */ igraph_small(&g, 10, IGRAPH_DIRECTED, 0, 1, 0, 2, 0, 3, 1, 2, 1, 4, 1, 5, 2, 3, 2, 6, 3, 2, 3, 6, 4, 5, 4, 7, 5, 6, 5, 8, 5, 9, 7, 5, 7, 8, 8, 9, 5, 2, 2, 1, -1); igraph_vector_view(&weights, weights_data_0, sizeof(weights_data_0) / sizeof(igraph_real_t)); igraph_matrix_init(&res, 0, 0); igraph_shortest_paths_bellman_ford(&g, &res, igraph_vss_all(), igraph_vss_all(), &weights, IGRAPH_OUT); print_matrix(&res); igraph_matrix_destroy(&res); igraph_destroy(&g); printf("\n"); /***************************************/ /* Graph with negative weights */ igraph_small(&g, 5, IGRAPH_DIRECTED, 0, 1, 0, 3, 1, 3, 1, 4, 2, 1, 3, 2, 3, 4, 4, 0, 4, 2, -1); igraph_vector_view(&weights, weights_data_1, sizeof(weights_data_1) / sizeof(igraph_real_t)); igraph_matrix_init(&res, 0, 0); igraph_shortest_paths_bellman_ford(&g, &res, igraph_vss_all(), igraph_vss_all(), &weights, IGRAPH_OUT); print_matrix(&res); /***************************************/ /* Same graph with negative loop */ igraph_set_error_handler(igraph_error_handler_ignore); igraph_vector_view(&weights, weights_data_2, sizeof(weights_data_2) / sizeof(igraph_real_t)); if (igraph_shortest_paths_bellman_ford(&g, &res, igraph_vss_all(), igraph_vss_all(), &weights, IGRAPH_OUT) != IGRAPH_ENEGLOOP) { return 1; } igraph_matrix_destroy(&res); igraph_destroy(&g); if (!IGRAPH_FINALLY_STACK_EMPTY) { return 1; } return 0; }
int igraph_shortest_paths_johnson(const igraph_t *graph,
igraph_matrix_t *res,
const igraph_vs_t from,
const igraph_vs_t to,
const igraph_vector_t *weights);
See Wikipedia at http://en.wikipedia.org/wiki/Johnson's_algorithm for Johnson's algorithm. This algorithm works even if the graph contains negative edge weights, and it is worth using it if we calculate the shortest paths from many sources.
If no edge weights are supplied, then the unweighted
version, igraph_shortest_paths() is called.
If all the supplied edge weights are non-negative,
then Dijkstra's algorithm is used by calling
igraph_shortest_paths_dijkstra().
Arguments:
|
The input graph. If negative weights are present, it should be directed. |
|
Pointer to an initialized matrix, the result will be stored here, one line for each source vertex, one column for each target vertex. |
|
The source vertices. |
|
The target vertices. It is not allowed to include a vertex twice or more. |
|
Optional edge weights. If it is a null-pointer, then
the unweighted breadth-first search based |
Returns:
Error code. |
Time complexity: O(s|V|log|V|+|V||E|), |V| and |E| are the number of vertices and edges, s is the number of source vertices.
See also:
|
int igraph_get_shortest_paths(const igraph_t *graph,
igraph_vector_ptr_t *vertices,
igraph_vector_ptr_t *edges,
igraph_integer_t from, const igraph_vs_t to,
igraph_neimode_t mode,
igraph_vector_long_t *predecessors,
igraph_vector_long_t *inbound_edges);
If there is more than one geodesic between two vertices, this function gives only one of them.
Arguments:
|
The graph object. |
||||||
|
The result, the ids of the vertices along the paths. This is a pointer vector, each element points to a vector object. These should be initialized before passing them to the function, which will properly clear and/or resize them and fill the ids of the vertices along the geodesics from/to the vertices. Supply a null pointer here if you don't need these vectors. |
||||||
|
The result, the ids of the edges along the paths. This is a pointer vector, each element points to a vector object. These should be initialized before passing them to the function, which will properly clear and/or resize them and fill the ids of the vertices along the geodesics from/to the vertices. Supply a null pointer here if you don't need these vectors. |
||||||
|
The id of the vertex from/to which the geodesics are calculated. |
||||||
|
Vertex sequence with the ids of the vertices to/from which the shortest paths will be calculated. A vertex might be given multiple times. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
A pointer to an initialized igraph vector or null.
If not null, a vector containing the predecessor of each vertex in
the single source shortest path tree is returned here. The
predecessor of vertex i in the tree is the vertex from which vertex i
was reached. The predecessor of the start vertex (in the |
||||||
|
A pointer to an initialized igraph vector or null.
If not null, a vector containing the inbound edge of each vertex in
the single source shortest path tree is returned here. The
inbound edge of vertex i in the tree is the edge via which vertex i
was reached. The start vertex and vertices that were not reached
during the search will have -1 in the corresponding entry of the
vector. Note that the search terminates if all the vertices in
|
Returns:
|
Error code:
|
Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| the number of edges in the graph.
See also:
|
Example 13.3. File examples/simple/igraph_get_shortest_paths.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #include <stdlib.h> void print_vector(igraph_vector_t *v) { long int i, l = igraph_vector_size(v); for (i = 0; i < l; i++) { printf(" %li", (long int) VECTOR(*v)[i]); } printf("\n"); } int check_evecs(const igraph_t *graph, const igraph_vector_ptr_t *vecs, const igraph_vector_ptr_t *evecs, int error_code) { igraph_bool_t directed = igraph_is_directed(graph); long int i, n = igraph_vector_ptr_size(vecs); if (igraph_vector_ptr_size(evecs) != n) { exit(error_code + 1); } for (i = 0; i < n; i++) { igraph_vector_t *vvec = VECTOR(*vecs)[i]; igraph_vector_t *evec = VECTOR(*evecs)[i]; long int j, n2 = igraph_vector_size(evec); if (igraph_vector_size(vvec) == 0 && n2 == 0) { continue; } if (igraph_vector_size(vvec) != n2 + 1) { exit(error_code + 2); } for (j = 0; j < n2; j++) { long int edge = VECTOR(*evec)[j]; long int from = VECTOR(*vvec)[j]; long int to = VECTOR(*vvec)[j + 1]; if (directed) { if (from != IGRAPH_FROM(graph, edge) || to != IGRAPH_TO (graph, edge)) { exit(error_code); } } else { long int from2 = IGRAPH_FROM(graph, edge); long int to2 = IGRAPH_TO(graph, edge); long int min1 = from < to ? from : to; long int max1 = from < to ? to : from; long int min2 = from2 < to2 ? from2 : to2; long int max2 = from2 < to2 ? to2 : from2; if (min1 != min2 || max1 != max2) { exit(error_code + 3); } } } } return 0; } int main() { igraph_t g; igraph_vector_ptr_t vecs, evecs; igraph_vector_long_t pred, inbound; long int i; igraph_vs_t vs; igraph_ring(&g, 10, IGRAPH_DIRECTED, 0, 1); igraph_vector_ptr_init(&vecs, 5); igraph_vector_ptr_init(&evecs, 5); igraph_vector_long_init(&pred, 0); igraph_vector_long_init(&inbound, 0); for (i = 0; i < igraph_vector_ptr_size(&vecs); i++) { VECTOR(vecs)[i] = calloc(1, sizeof(igraph_vector_t)); igraph_vector_init(VECTOR(vecs)[i], 0); VECTOR(evecs)[i] = calloc(1, sizeof(igraph_vector_t)); igraph_vector_init(VECTOR(evecs)[i], 0); } igraph_vs_vector_small(&vs, 1, 3, 5, 2, 1, -1); igraph_get_shortest_paths(&g, &vecs, &evecs, 0, vs, IGRAPH_OUT, &pred, &inbound); check_evecs(&g, &vecs, &evecs, 10); for (i = 0; i < igraph_vector_ptr_size(&vecs); i++) { print_vector(VECTOR(vecs)[i]); igraph_vector_destroy(VECTOR(vecs)[i]); free(VECTOR(vecs)[i]); igraph_vector_destroy(VECTOR(evecs)[i]); free(VECTOR(evecs)[i]); } igraph_vector_long_print(&pred); igraph_vector_long_print(&inbound); igraph_vector_ptr_destroy(&vecs); igraph_vector_ptr_destroy(&evecs); igraph_vector_long_destroy(&pred); igraph_vector_long_destroy(&inbound); igraph_vs_destroy(&vs); igraph_destroy(&g); if (!IGRAPH_FINALLY_STACK_EMPTY) { return 1; } return 0; }
int igraph_get_shortest_path(const igraph_t *graph,
igraph_vector_t *vertices,
igraph_vector_t *edges,
igraph_integer_t from,
igraph_integer_t to,
igraph_neimode_t mode);
Calculates and returns a single unweighted shortest path from a given vertex to another one. If there are more than one shortest paths between the two vertices, then an arbitrary one is returned.
This function is a wrapper to igraph_get_shortest_paths(), for the special case when only one
target vertex is considered.
Arguments:
|
The input graph, it can be directed or undirected. Directed paths are considered in directed graphs. |
|
Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex ids along the path are stored here, including the source and target vertices. |
|
Pointer to an uninitialized vector or a null pointer. If not a null pointer, then the edge ids along the path are stored here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
|
A constant specifying how edge directions are
considered in directed graphs. Valid modes are:
|
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices and edges in the graph.
See also:
|
int igraph_get_shortest_paths_dijkstra(const igraph_t *graph,
igraph_vector_ptr_t *vertices,
igraph_vector_ptr_t *edges,
igraph_integer_t from,
igraph_vs_t to,
const igraph_vector_t *weights,
igraph_neimode_t mode,
igraph_vector_long_t *predecessors,
igraph_vector_long_t *inbound_edges);
If there is more than one path with the smallest weight between two vertices, this function gives only one of them.
Arguments:
|
The graph object. |
||||||
|
The result, the ids of the vertices along the paths.
This is a pointer vector, each element points to a vector
object. These should be initialized before passing them to
the function, which will properly clear and/or resize them
and fill the ids of the vertices along the geodesics from/to
the vertices. Supply a null pointer here if you don't need
these vectors. Normally, either this argument, or the |
||||||
|
The result, the ids of the edges along the paths.
This is a pointer vector, each element points to a vector
object. These should be initialized before passing them to
the function, which will properly clear and/or resize them
and fill the ids of the vertices along the geodesics from/to
the vertices. Supply a null pointer here if you don't need
these vectors. Normally, either this argument, or the |
||||||
|
The id of the vertex from/to which the geodesics are calculated. |
||||||
|
Vertex sequence with the ids of the vertices to/from which the shortest paths will be calculated. A vertex might be given multiple times. * |
||||||
|
The edge weights. All edge weights must be
non-negative for Dijkstra's algorithm to work. Additionally, no
edge weight may be NaN. If either case does not hold, an error
is returned. If this is a null pointer, then the unweighted
version, |
||||||
|
The type of shortest paths to be use for the calculation in directed graphs. Possible values:
|
||||||
|
A pointer to an initialized igraph vector or null.
If not null, a vector containing the predecessor of each vertex in
the single source shortest path tree is returned here. The
predecessor of vertex i in the tree is the vertex from which vertex i
was reached. The predecessor of the start vertex (in the |
||||||
|
A pointer to an initialized igraph vector or null.
If not null, a vector containing the inbound edge of each vertex in
the single source shortest path tree is returned here. The
inbound edge of vertex i in the tree is the edge via which vertex i
was reached. The start vertex and vertices that were not reached
during the search will have -1 in the corresponding entry of the
vector. Note that the search terminates if all the vertices in
|
Returns:
|
Error code:
|
Time complexity: O(|E|log|E|+|V|), where |V| is the number of vertices and |E| is the number of edges
See also:
|
Example 13.4. File examples/simple/igraph_get_shortest_paths_dijkstra.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #include <stdlib.h> void print_vector(igraph_vector_t *v) { long int i, l = igraph_vector_size(v); for (i = 0; i < l; i++) { printf(" %li", (long int) VECTOR(*v)[i]); } printf("\n"); } int check_evecs(const igraph_t *graph, const igraph_vector_ptr_t *vecs, const igraph_vector_ptr_t *evecs, int error_code) { igraph_bool_t directed = igraph_is_directed(graph); long int i, n = igraph_vector_ptr_size(vecs); if (igraph_vector_ptr_size(evecs) != n) { exit(error_code + 1); } for (i = 0; i < n; i++) { igraph_vector_t *vvec = VECTOR(*vecs)[i]; igraph_vector_t *evec = VECTOR(*evecs)[i]; long int j, n2 = igraph_vector_size(evec); if (igraph_vector_size(vvec) == 0 && n2 == 0) { continue; } if (igraph_vector_size(vvec) != n2 + 1) { exit(error_code + 2); } for (j = 0; j < n2; j++) { long int edge = VECTOR(*evec)[j]; long int from = VECTOR(*vvec)[j]; long int to = VECTOR(*vvec)[j + 1]; if (directed) { if (from != IGRAPH_FROM(graph, edge) || to != IGRAPH_TO (graph, edge)) { exit(error_code); } } else { long int from2 = IGRAPH_FROM(graph, edge); long int to2 = IGRAPH_TO(graph, edge); long int min1 = from < to ? from : to; long int max1 = from < to ? to : from; long int min2 = from2 < to2 ? from2 : to2; long int max2 = from2 < to2 ? to2 : from2; if (min1 != min2 || max1 != max2) { exit(error_code + 3); } } } } return 0; } int check_pred_inbound(const igraph_t* graph, const igraph_vector_long_t* pred, const igraph_vector_long_t* inbound, int start, int error_code) { long int i, n = igraph_vcount(graph); if (igraph_vector_long_size(pred) != n || igraph_vector_long_size(inbound) != n) { exit(error_code); } if (VECTOR(*pred)[start] != start || VECTOR(*inbound)[start] != -1) { exit(error_code + 1); } for (i = 0; i < n; i++) { if (VECTOR(*pred)[i] == -1) { if (VECTOR(*inbound)[i] != -1) { exit(error_code + 2); } } else if (VECTOR(*pred)[i] == i) { if (i != start) { exit(error_code + 3); } if (VECTOR(*inbound)[i] != -1) { exit(error_code + 4); } } else { long int eid = VECTOR(*inbound)[i]; long int u = IGRAPH_FROM(graph, eid), v = IGRAPH_TO(graph, eid); if (v != i && !igraph_is_directed(graph)) { long int dummy = u; u = v; v = dummy; } if (v != i) { exit(error_code + 5); } else if (u != VECTOR(*pred)[i]) { exit(error_code + 6); } } } return 0; } int main() { igraph_t g; igraph_vector_ptr_t vecs, evecs; igraph_vector_long_t pred, inbound; long int i; igraph_real_t weights[] = { 1, 2, 3, 4, 5, 1, 1, 1, 1, 1 }; igraph_real_t weights2[] = { 0, 2, 1, 0, 5, 2, 1, 1, 0, 2, 2, 8, 1, 1, 3, 1, 1, 4, 2, 1 }; igraph_vector_t weights_vec; igraph_vs_t vs; /* Simple ring graph without weights */ igraph_ring(&g, 10, IGRAPH_UNDIRECTED, 0, 1); igraph_vector_ptr_init(&vecs, 6); igraph_vector_ptr_init(&evecs, 6); igraph_vector_long_init(&pred, 0); igraph_vector_long_init(&inbound, 0); for (i = 0; i < igraph_vector_ptr_size(&vecs); i++) { VECTOR(vecs)[i] = calloc(1, sizeof(igraph_vector_t)); igraph_vector_init(VECTOR(vecs)[i], 0); VECTOR(evecs)[i] = calloc(1, sizeof(igraph_vector_t)); igraph_vector_init(VECTOR(evecs)[i], 0); } igraph_vs_vector_small(&vs, 0, 1, 3, 5, 2, 1, -1); igraph_get_shortest_paths_dijkstra(&g, /*vertices=*/ &vecs, /*edges=*/ &evecs, /*from=*/ 0, /*to=*/ vs, /*weights=*/ 0, /*mode=*/ IGRAPH_OUT, /*predecessors=*/ &pred, /*inbound_edges=*/ &inbound); check_evecs(&g, &vecs, &evecs, 10); check_pred_inbound(&g, &pred, &inbound, /* from= */ 0, 40); for (i = 0; i < igraph_vector_ptr_size(&vecs); i++) { print_vector(VECTOR(vecs)[i]); } /* Same ring, but with weights */ igraph_vector_view(&weights_vec, weights, sizeof(weights) / sizeof(igraph_real_t)); igraph_get_shortest_paths_dijkstra(&g, /*vertices=*/ &vecs, /*edges=*/ &evecs, /*from=*/ 0, /*to=*/ vs, &weights_vec, IGRAPH_OUT, /*predecessors=*/ &pred, /*inbound_edges=*/ &inbound); check_evecs(&g, &vecs, &evecs, 20); check_pred_inbound(&g, &pred, &inbound, /* from= */ 0, 50); for (i = 0; i < igraph_vector_ptr_size(&vecs); i++) { print_vector(VECTOR(vecs)[i]); } igraph_destroy(&g); /* More complicated example */ igraph_small(&g, 10, IGRAPH_DIRECTED, 0, 1, 0, 2, 0, 3, 1, 2, 1, 4, 1, 5, 2, 3, 2, 6, 3, 2, 3, 6, 4, 5, 4, 7, 5, 6, 5, 8, 5, 9, 7, 5, 7, 8, 8, 9, 5, 2, 2, 1, -1); igraph_vector_view(&weights_vec, weights2, sizeof(weights2) / sizeof(igraph_real_t)); igraph_get_shortest_paths_dijkstra(&g, /*vertices=*/ &vecs, /*edges=*/ &evecs, /*from=*/ 0, /*to=*/ vs, &weights_vec, IGRAPH_OUT, /*predecessors=*/ &pred, /*inbound_edges=*/ &inbound); check_evecs(&g, &vecs, &evecs, 30); check_pred_inbound(&g, &pred, &inbound, /* from= */ 0, 60); for (i = 0; i < igraph_vector_ptr_size(&vecs); i++) { print_vector(VECTOR(vecs)[i]); igraph_vector_destroy(VECTOR(vecs)[i]); free(VECTOR(vecs)[i]); igraph_vector_destroy(VECTOR(evecs)[i]); free(VECTOR(evecs)[i]); } igraph_vector_ptr_destroy(&vecs); igraph_vector_ptr_destroy(&evecs); igraph_vector_long_destroy(&pred); igraph_vector_long_destroy(&inbound); igraph_vs_destroy(&vs); igraph_destroy(&g); if (!IGRAPH_FINALLY_STACK_EMPTY) { return 1; } return 0; }
int igraph_get_shortest_path_dijkstra(const igraph_t *graph,
igraph_vector_t *vertices,
igraph_vector_t *edges,
igraph_integer_t from,
igraph_integer_t to,
const igraph_vector_t *weights,
igraph_neimode_t mode);
Calculates a single (positively) weighted shortest path from a single vertex to another one, using Dijkstra's algorithm.
This function is a special case (and a wrapper) to
igraph_get_shortest_paths_dijkstra().
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex ids along the path are stored here, including the source and target vertices. |
|
Pointer to an uninitialized vector or a null pointer. If not a null pointer, then the edge ids along the path are stored here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
|
The edge weights. All edge weights must be
non-negative for Dijkstra's algorithm to work. Additionally, no
edge weight may be NaN. If either case does not hold, an error
is returned. If this is a null pointer, then the unweighted
version, |
|
A constant specifying how edge directions are
considered in directed graphs. |
Returns:
Error code. |
Time complexity: O(|E|log|E|+|V|), |V| is the number of vertices, |E| is the number of edges in the graph.
See also:
|
int igraph_get_shortest_paths_bellman_ford(const igraph_t *graph,
igraph_vector_ptr_t *vertices,
igraph_vector_ptr_t *edges,
igraph_integer_t from,
igraph_vs_t to,
const igraph_vector_t *weights,
igraph_neimode_t mode,
igraph_vector_long_t *predecessors,
igraph_vector_long_t *inbound_edges);
This function calculates weighted shortest paths from or to a single vertex,
and allows negative weights. When there is more than one shortest path between
two vertices, only one of them is returned.
If there are no negative weights, you are better off with
igraph_get_shortest_paths_dijkstra() .
Arguments:
|
The input graph, can be directed. |
|
The result, the ids of the vertices along the paths.
This is a pointer vector, each element points to a vector
object. These should be initialized before passing them to
the function, which will properly clear and/or resize them
and fill the ids of the vertices along the geodesics from/to
the vertices. Supply a null pointer here if you don't need
these vectors. Normally, either this argument, or the |
|
The result, the ids of the edges along the paths.
This is a pointer vector, each element points to a vector
object. These should be initialized before passing them to
the function, which will properly clear and/or resize them
and fill the ids of the vertices along the geodesics from/to
the vertices. Supply a null pointer here if you don't need
these vectors. Normally, either this argument, or the |
|
The id of the vertex from/to which the geodesics are calculated. |
|
Vertex sequence with the ids of the vertices to/from which the shortest paths will be calculated. A vertex might be given multiple times. |
|
The edge weights. There mustn't be any closed loop in
the graph that has a negative total weight (since this would allow
us to decrease the weight of any path containing at least a single
vertex of this loop infinitely). If this is a null pointer, then the
unweighted version, |
|
For directed graphs; whether to follow paths along edge
directions ( |
|
A pointer to an initialized igraph vector or null.
If not null, a vector containing the predecessor of each vertex in
the single source shortest path tree is returned here. The
predecessor of vertex i in the tree is the vertex from which vertex i
was reached. The predecessor of the start vertex (in the |
|
A pointer to an initialized igraph vector or null.
If not null, a vector containing the inbound edge of each vertex in
the single source shortest path tree is returned here. The
inbound edge of vertex i in the tree is the edge via which vertex i
was reached. The start vertex and vertices that were not reached
during the search will have -1 in the corresponding entry of the
vector. Note that the search terminates if all the vertices in
|
Returns:
|
Error code:
|
Time complexity: O(|E|*|V|), where |V| is the number of vertices, |E| the number of edges.
See also:
|
int igraph_get_shortest_path_bellman_ford(const igraph_t *graph,
igraph_vector_t *vertices,
igraph_vector_t *edges,
igraph_integer_t from,
igraph_integer_t to,
const igraph_vector_t *weights,
igraph_neimode_t mode);
Calculates a single (positively) weighted shortest path from a single vertex to another one, using Bellman-Ford algorithm.
This function is a special case (and a wrapper) to
igraph_get_shortest_paths_bellman_ford().
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex ids along the path are stored here, including the source and target vertices. |
|
Pointer to an uninitialized vector or a null pointer. If not a null pointer, then the edge ids along the path are stored here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
|
The edge weights. There mustn't be any closed loop in the graph that has a negative total weight (since this would allow us to decrease the weight of any path containing at least a single vertex of this loop infinitely). If this is a null pointer, then the unweighted version is called. |
|
A constant specifying how edge directions are
considered in directed graphs. |
Returns:
Error code. |
Time complexity: O(|E|log|E|+|V|), |V| is the number of vertices, |E| is the number of edges in the graph.
See also:
|
int igraph_get_all_shortest_paths(const igraph_t *graph,
igraph_vector_ptr_t *res,
igraph_vector_t *nrgeo,
igraph_integer_t from, const igraph_vs_t to,
igraph_neimode_t mode);
When there is more than one shortest path between two vertices, all of them will be returned.
Arguments:
|
The graph object. |
||||||
|
Pointer to an initialized pointer vector, the result
will be stored here in |
||||||
|
Pointer to an initialized |
||||||
|
The id of the vertex from/to which the geodesics are calculated. |
||||||
|
Vertex sequence with the ids of the vertices to/from which the shortest paths will be calculated. A vertex might be given multiple times. |
||||||
|
The type of shortest paths to be use for the calculation in directed graphs. Possible values:
|
Returns:
|
Error code:
|
Added in version 0.2.
Time complexity: O(|V|+|E|) for most graphs, O(|V|^2) in the worst case.
int igraph_get_all_shortest_paths_dijkstra(const igraph_t *graph,
igraph_vector_ptr_t *res,
igraph_vector_t *nrgeo,
igraph_integer_t from, igraph_vs_t to,
const igraph_vector_t *weights,
igraph_neimode_t mode);
Arguments:
|
The graph object. |
||||||
|
Pointer to an initialized pointer vector, the result
will be stored here in igraph_vector_t objects. Each vector
object contains the vertices along a shortest path from |
||||||
|
Pointer to an initialized igraph_vector_t object or
NULL. If not NULL the number of shortest paths from |
||||||
|
The id of the vertex from/to which the geodesics are calculated. |
||||||
|
Vertex sequence with the ids of the vertices to/from which the shortest paths will be calculated. A vertex might be given multiple times. |
||||||
|
The edge weights. All edge weights must be
non-negative for Dijkstra's algorithm to work. Additionally, no
edge weight may be NaN. If either case does not hold, an error
is returned. If this is a null pointer, then the unweighted
version, |
||||||
|
The type of shortest paths to be use for the calculation in directed graphs. Possible values:
|
Returns:
|
Error code:
|
Time complexity: O(|E|log|E|+|V|), where |V| is the number of vertices and |E| is the number of edges
See also:
|
Example 13.5. File examples/simple/igraph_get_all_shortest_paths_dijkstra.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* 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> /* Compares two paths based on their last elements. If they are equal, proceeds * with the ones preceding these elements, until we find a difference. If one * of the vectors is a suffix of the other, the shorter vector gets ordered * first. */ int vector_tail_cmp(const void *path1, const void *path2) { const igraph_vector_t *vec1 = *(const igraph_vector_t**)path1; const igraph_vector_t *vec2 = *(const igraph_vector_t**)path2; size_t length1 = igraph_vector_size(vec1); size_t length2 = igraph_vector_size(vec2); int diff; while (length1 > 0 && length2 > 0) { length1--; length2--; diff = VECTOR(*vec1)[length1] - VECTOR(*vec2)[length2]; if (diff != 0) { return diff; } } if (length1 == 0 && length2 == 0) { return 0; } else if (length1 == 0) { return -1; } else { return 1; } } void check_nrgeo(const igraph_t *graph, igraph_vs_t vs, const igraph_vector_ptr_t *paths, const igraph_vector_t *nrgeo) { long int i, n; igraph_vector_t nrgeo2, *path; igraph_vit_t vit; n = igraph_vcount(graph); igraph_vector_init(&nrgeo2, n); if (igraph_vector_size(nrgeo) != n) { printf("nrgeo vector length must be %ld, was %ld", n, igraph_vector_size(nrgeo)); return; } n = igraph_vector_ptr_size(paths); for (i = 0; i < n; i++) { path = VECTOR(*paths)[i]; if (path == 0) { printf("Null path found in result vector at index %ld\n", i); return; } if (igraph_vector_size(path) == 0) { printf("Empty path found in result vector at index %ld\n", i); return; } VECTOR(nrgeo2)[(long int)igraph_vector_tail(path)] += 1; } igraph_vit_create(graph, vs, &vit); for (IGRAPH_VIT_RESET(vit); !IGRAPH_VIT_END(vit); IGRAPH_VIT_NEXT(vit)) { long int node = IGRAPH_VIT_GET(vit); if (VECTOR(*nrgeo)[node] - VECTOR(nrgeo2)[node]) { printf("nrgeo[%ld] invalid, observed = %ld, expected = %ld\n", node, (long int)VECTOR(*nrgeo)[node], (long int)VECTOR(nrgeo2)[node]); } } igraph_vit_destroy(&vit); igraph_vector_destroy(&nrgeo2); } int main() { igraph_t g; igraph_vector_ptr_t res; long int i; igraph_real_t weights[] = { 1, 2, 3, 4, 5, 1, 1, 1, 1, 1 }; igraph_real_t weights2[] = { 0, 2, 1, 0, 5, 2, 1, 1, 0, 2, 2, 8, 1, 1, 3, 1, 1, 4, 2, 1 }; igraph_real_t dim[] = { 4, 4 }; igraph_vector_t weights_vec, dim_vec, nrgeo; igraph_vs_t vs; igraph_vector_init(&nrgeo, 0); /* Simple ring graph without weights */ igraph_ring(&g, 10, IGRAPH_UNDIRECTED, 0, 1); igraph_vector_ptr_init(&res, 5); igraph_vs_vector_small(&vs, 1, 3, 4, 5, 2, 1, -1); igraph_get_all_shortest_paths_dijkstra( &g, /*res=*/ &res, /*nrgeo=*/ &nrgeo, /*from=*/ 0, /*to=*/ vs, /*weights=*/ NULL, /*mode=*/ IGRAPH_OUT); check_nrgeo(&g, vs, &res, &nrgeo); for (i = 0; i < igraph_vector_ptr_size(&res); i++) { igraph_vector_print(VECTOR(res)[i]); igraph_vector_destroy(VECTOR(res)[i]); igraph_free(VECTOR(res)[i]); VECTOR(res)[i] = 0; } /* Same ring, but with weights */ igraph_vector_view(&weights_vec, weights, sizeof(weights) / sizeof(igraph_real_t)); igraph_get_all_shortest_paths_dijkstra( &g, /*res=*/ &res, /*nrgeo=*/ &nrgeo, /*from=*/ 0, /*to=*/ vs, /*weights=*/ &weights_vec, /*mode=*/ IGRAPH_OUT); check_nrgeo(&g, vs, &res, &nrgeo); for (i = 0; i < igraph_vector_ptr_size(&res); i++) { igraph_vector_print(VECTOR(res)[i]); igraph_vector_destroy(VECTOR(res)[i]); igraph_free(VECTOR(res)[i]); VECTOR(res)[i] = 0; } igraph_destroy(&g); /* More complicated example */ igraph_small(&g, 10, IGRAPH_DIRECTED, 0, 1, 0, 2, 0, 3, 1, 2, 1, 4, 1, 5, 2, 3, 2, 6, 3, 2, 3, 6, 4, 5, 4, 7, 5, 6, 5, 8, 5, 9, 7, 5, 7, 8, 8, 9, 5, 2, 2, 1, -1); igraph_vector_view(&weights_vec, weights2, sizeof(weights2) / sizeof(igraph_real_t)); igraph_get_all_shortest_paths_dijkstra( &g, /*res=*/ &res, /*nrgeo=*/ &nrgeo, /*from=*/ 0, /*to=*/ vs, /*weights=*/ &weights_vec, /*mode=*/ IGRAPH_OUT); check_nrgeo(&g, vs, &res, &nrgeo); /* Sort the paths in a deterministic manner to avoid problems with * different qsort() implementations on different platforms */ igraph_vector_ptr_sort(&res, vector_tail_cmp); for (i = 0; i < igraph_vector_ptr_size(&res); i++) { igraph_vector_print(VECTOR(res)[i]); igraph_vector_destroy(VECTOR(res)[i]); igraph_free(VECTOR(res)[i]); VECTOR(res)[i] = 0; } igraph_vs_destroy(&vs); igraph_destroy(&g); /* Regular lattice with some heavyweight edges */ igraph_vector_view(&dim_vec, dim, sizeof(dim) / sizeof(igraph_real_t)); igraph_lattice(&g, &dim_vec, 1, 0, 0, 0); igraph_vs_vector_small(&vs, 3, 12, 15, -1); igraph_vector_init(&weights_vec, 24); igraph_vector_fill(&weights_vec, 1); VECTOR(weights_vec)[2] = 100; VECTOR(weights_vec)[8] = 100; /* 1-->2, 4-->8 */ igraph_get_all_shortest_paths_dijkstra( &g, /*res=*/ 0, /*nrgeo=*/ &nrgeo, /*from=*/ 0, /*to=*/ vs, /*weights=*/ &weights_vec, /*mode=*/ IGRAPH_OUT); igraph_vector_destroy(&weights_vec); igraph_vs_destroy(&vs); igraph_destroy(&g); printf("%ld ", (long int)VECTOR(nrgeo)[3]); printf("%ld ", (long int)VECTOR(nrgeo)[12]); printf("%ld\n", (long int)VECTOR(nrgeo)[15]); igraph_vector_ptr_destroy(&res); igraph_vector_destroy(&nrgeo); if (!IGRAPH_FINALLY_STACK_EMPTY) { return 1; } return 0; }
int igraph_get_all_simple_paths(const igraph_t *graph,
igraph_vector_int_t *res,
igraph_integer_t from,
const igraph_vs_t to,
igraph_integer_t cutoff,
igraph_neimode_t mode);
A path is simple if its vertices are unique, i.e. no vertex is visited more than once.
Note that potentially there are exponentially many paths between two vertices of a graph, and you may run out of memory when using this function, if your graph is lattice-like.
This function currently ignored multiple and loop edges.
Arguments:
|
The input graph. |
|
Initialized integer vector, all paths are returned here, separated by -1 markers. The paths are included in arbitrary order, as they are found. |
|
The start vertex. |
|
The target vertices. |
|
Maximum length of path that is considered. If negative, paths of all lengths are considered. |
|
The type of the paths to consider, it is ignored for undirected graphs. |
Returns:
Error code. |
Time complexity: O(n!) in the worst case, n is the number of vertices.
int igraph_average_path_length(const igraph_t *graph,
igraph_real_t *res, igraph_real_t *unconn_pairs,
igraph_bool_t directed, igraph_bool_t unconn);
If no vertex pairs can be included in the calculation, for example because the graph
has fewer than two vertices, or if the graph has no edges and unconn is set to TRUE,
NaN is returned.
Arguments:
|
The graph object. |
|
Pointer to a real number, this will contain the result. |
|
Pointer to a real number. If not a null pointer, the number of ordered vertex pairs where the second vertex is unreachable from the first one will be stored here. |
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
|
What to do if the graph is not connected. If
|
Returns:
Error code:
|
Time complexity: O(|V| |E|), the number of vertices times the number of edges.
See also:
|
Example 13.6. File examples/simple/igraph_average_path_length.c
#include <igraph.h> int main() { igraph_t graph; igraph_real_t result; /* Create a random preferential attachment graph. */ igraph_barabasi_game(&graph, 30, /*power=*/ 1, 30, 0, 0, /*A=*/ 1, IGRAPH_DIRECTED, IGRAPH_BARABASI_BAG, /*start_from=*/ 0); /* Compute the average shortest path length. */ igraph_average_path_length(&graph, &result, NULL, IGRAPH_UNDIRECTED, 1); printf("Average length of all-pairs shortest paths: %g\n", result); /* Destroy no-longer-needed objects. */ igraph_destroy(&graph); return 0; }
int igraph_average_path_length_dijkstra(const igraph_t *graph,
igraph_real_t *res, igraph_real_t *unconn_pairs,
const igraph_vector_t *weights,
igraph_bool_t directed, igraph_bool_t unconn);
If no vertex pairs can be included in the calculation, for example because the graph
has fewer than two vertices, or if the graph has no edges and unconn is set to TRUE,
NaN is returned.
All distinct ordered vertex pairs are taken into account.
Arguments:
|
The graph object. |
|
Pointer to a real number, this will contain the result. |
|
Pointer to a real number. If not a null pointer, the number of ordered vertex pairs where the second vertex is unreachable from the first one will be stored here. |
|
The edge weights. All edge weights must be
non-negative for Dijkstra's algorithm to work. Additionally, no
edge weight may be NaN. If either case does not hold, an error
is returned. If this is a null pointer, then the unweighted
version, |
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
|
If |
Returns:
|
Error code:
|
Time complexity: O(|V| |E| log|E| + |V|), where |V| is the number of vertices and |E| is the number of edges.
See also:
|
Example 13.7. File examples/simple/igraph_grg_game.c
#include <igraph.h> #include <math.h> int main() { igraph_t graph; igraph_vector_t x, y; igraph_vector_t weights; igraph_eit_t eit; igraph_real_t avg_dist; /* Set random seed for reproducible results */ igraph_rng_seed(igraph_rng_default(), 42); /* Create a random geometric graph and retrieve vertex coordinates */ igraph_vector_init(&x, 0); igraph_vector_init(&y, 0); igraph_grg_game(&graph, 200, 0.1, /* torus */ 0, &x, &y); /* Compute edge weights as geometric distance */ igraph_vector_init(&weights, igraph_ecount(&graph)); igraph_eit_create(&graph, igraph_ess_all(IGRAPH_EDGEORDER_ID), &eit); for (; ! IGRAPH_EIT_END(eit); IGRAPH_EIT_NEXT(eit)) { long int e = IGRAPH_EIT_GET(eit); long int u = IGRAPH_FROM(&graph, e); long int v = IGRAPH_TO(&graph, e); VECTOR(weights)[e] = hypot(VECTOR(x)[u] - VECTOR(x)[v], VECTOR(y)[u] - VECTOR(y)[v]); } igraph_eit_destroy(&eit); /* Compute average path length */ igraph_average_path_length_dijkstra(&graph, &avg_dist, NULL, &weights, IGRAPH_UNDIRECTED, /* unconn */ 1); printf("Average distance in the geometric graph: %g.\n", avg_dist); /* Destroy data structures when no longer needed */ igraph_vector_destroy(&weights); igraph_destroy(&graph); igraph_vector_destroy(&x); igraph_vector_destroy(&y); return 0; }
int igraph_path_length_hist(const igraph_t *graph, igraph_vector_t *res,
igraph_real_t *unconnected, igraph_bool_t directed);
This function calculates a histogram, by calculating the shortest path length between each pair of vertices. For directed graphs both directions might be considered and then every pair of vertices appears twice in the histogram.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the result is stored here. The first (i.e. zeroth) element contains the number of shortest paths of length 1, etc. The supplied vector is resized as needed. |
|
Pointer to a real number, the number of pairs for which the second vertex is not reachable from the first is stored here. |
|
Whether to consider directed paths in a directed graph (if not zero). This argument is ignored for undirected graphs. |
Returns:
Error code. |
Time complexity: O(|V||E|), the number of vertices times the number of edges.
See also:
int igraph_diameter(const igraph_t *graph, igraph_real_t *pres,
igraph_integer_t *pfrom, igraph_integer_t *pto,
igraph_vector_t *path,
igraph_bool_t directed, igraph_bool_t unconn);
The diameter of a graph is the length of the longest shortest path it has.
This function computes both the diameter, as well as the corresponding path.
The diameter of the null graph is considered be infinity by convention.
If the graph has no vertices, IGRAPH_NAN is returned.
Arguments:
|
The graph object. |
|
Pointer to a real number, if not |
|
Pointer to an integer, if not |
|
Pointer to an integer, if not |
|
Pointer to an initialized vector. If not |
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
|
What to do if the graph is not connected. If
|
Returns:
Error code:
|
Time complexity: O(|V||E|), the number of vertices times the number of edges.
See also:
Example 13.8. File examples/simple/igraph_diameter.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> void print_vector(igraph_vector_t *v) { long int i, n = igraph_vector_size(v); for (i = 0; i < n; i++) { printf(" %li", (long int) VECTOR(*v)[i]); } printf("\n"); } int main() { igraph_t g; igraph_real_t result; igraph_integer_t from, to; igraph_vector_t path; igraph_barabasi_game(&g, 30, /*power=*/ 1, 30, 0, 0, /*A=*/ 1, IGRAPH_DIRECTED, IGRAPH_BARABASI_BAG, /*start_from=*/ 0); igraph_diameter(&g, &result, 0, 0, 0, IGRAPH_UNDIRECTED, 1); /* printf("Diameter: %li\n", (long int) result); */ igraph_destroy(&g); igraph_ring(&g, 10, IGRAPH_DIRECTED, 0, 0); igraph_vector_init(&path, 0); igraph_diameter(&g, &result, &from, &to, &path, IGRAPH_DIRECTED, 1); printf("diameter: %li, from %li to %li\n", (long int) result, (long int) from, (long int) to); print_vector(&path); igraph_vector_destroy(&path); igraph_destroy(&g); return 0; }
int igraph_diameter_dijkstra(const igraph_t *graph,
const igraph_vector_t *weights,
igraph_real_t *pres,
igraph_integer_t *pfrom,
igraph_integer_t *pto,
igraph_vector_t *path,
igraph_bool_t directed,
igraph_bool_t unconn);
This function computes the weighted diameter of a graph.
If the graph has no vertices, IGRAPH_NAN is returned.
Arguments:
|
The input graph, can be directed or undirected. |
|
Pointer to a real number, if not |
|
Pointer to an integer, if not |
|
Pointer to an integer, if not |
|
Pointer to an initialized vector. If not |
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
|
What to do if the graph is not connected. If
|
Returns:
Error code. |
Time complexity: O(|V||E|*log|E|), |V| is the number of vertices, |E| is the number of edges.
See also:
int igraph_girth(const igraph_t *graph, igraph_integer_t *girth,
igraph_vector_t *circle);
The current implementation works for undirected graphs only, directed graphs are treated as undirected graphs. Self-loops and multiple edges are ignored.
For graphs that contain no cycles, and only for such graphs,
zero is returned. Note that in some applications, it is customary
to define the girth of acyclic graphs to be infinity. However, infinity
is not representable as an igraph_integer_t, therefore zero is used
for this case.
This implementation is based on Alon Itai and Michael Rodeh: Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory of computing , 1-10, 1977. The first implementation of this function was done by Keith Briggs, thanks Keith.
Arguments:
|
The input graph. |
|
Pointer to an integer, if not |
|
Pointer to an initialized vector, the vertex ids in
the shortest circle will be stored here. If |
Returns:
Error code. |
Time complexity: O((|V|+|E|)^2), |V| is the number of vertices, |E| is the number of edges in the general case. If the graph has no cycles at all then the function needs O(|V|+|E|) time to realize this and then it stops.
Example 13.9. File examples/simple/igraph_girth.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2007-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 main() { igraph_t g; igraph_integer_t girth; igraph_vector_t v; igraph_vector_t circle; igraph_real_t chord[] = { 0, 50 }; igraph_ring(&g, 100, IGRAPH_UNDIRECTED, 0, 1); igraph_vector_view(&v, chord, sizeof(chord) / sizeof(igraph_real_t)); igraph_add_edges(&g, &v, 0); igraph_girth(&g, &girth, 0); if (girth != 51) { return 1; } igraph_destroy(&g); /* Special case: null graph */ igraph_ring(&g, 0, IGRAPH_UNDIRECTED, 0, 1); igraph_vector_init(&circle, 1); VECTOR(circle)[0] = 2; igraph_girth(&g, &girth, &circle); if (girth != 0) { return 2; } if (igraph_vector_size(&circle) != 0) { return 3; } igraph_vector_destroy(&circle); igraph_destroy(&g); return 0; }
int igraph_eccentricity(const igraph_t *graph,
igraph_vector_t *res,
igraph_vs_t vids,
igraph_neimode_t mode);
The eccentricity of a vertex is calculated by measuring the shortest distance from (or to) the vertex, to (or from) all vertices in the graph, and taking the maximum.
This implementation ignores vertex pairs that are in different components. Isolated vertices have eccentricity zero.
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to an initialized vector, the result is stored here. |
|
The vertices for which the eccentricity is calculated. |
|
What kind of paths to consider for the calculation:
|
Returns:
Error code. |
Time complexity: O(v*(|V|+|E|)), where |V| is the number of vertices, |E| is the number of edges and v is the number of vertices for which eccentricity is calculated.
See also:
Example 13.10. File examples/simple/igraph_eccentricity.c
#include <igraph.h> int main() { igraph_t g; igraph_vector_t ecc; igraph_vector_init(&ecc, 0); igraph_star(&g, 10, IGRAPH_STAR_UNDIRECTED, 0); igraph_eccentricity(&g, &ecc, igraph_vss_all(), IGRAPH_OUT); igraph_vector_print(&ecc); igraph_destroy(&g); igraph_star(&g, 10, IGRAPH_STAR_OUT, 0); igraph_eccentricity(&g, &ecc, igraph_vss_all(), IGRAPH_ALL); igraph_vector_print(&ecc); igraph_destroy(&g); igraph_star(&g, 10, IGRAPH_STAR_OUT, 0); igraph_eccentricity(&g, &ecc, igraph_vss_all(), IGRAPH_OUT); igraph_vector_print(&ecc); igraph_destroy(&g); igraph_vector_destroy(&ecc); return 0; }
int igraph_radius(const igraph_t *graph, igraph_real_t *radius,
igraph_neimode_t mode);
The radius of a graph is the defined as the minimum eccentricity of
its vertices, see igraph_eccentricity().
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to a real variable, the result is stored here. |
|
What kind of paths to consider for the calculation:
|
Returns:
Error code. |
Time complexity: O(|V|(|V|+|E|)), where |V| is the number of vertices and |E| is the number of edges.
See also:
Example 13.11. File examples/simple/igraph_radius.c
/* -*- mode: C -*- */ /* vim:set ts=4 sts=4 sw=4 et: */ /* IGraph library. Copyright (C) 2011-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 g; igraph_real_t radius; igraph_star(&g, 10, IGRAPH_STAR_UNDIRECTED, 0); igraph_radius(&g, &radius, IGRAPH_OUT); if (radius != 1) { return 1; } igraph_destroy(&g); igraph_star(&g, 10, IGRAPH_STAR_OUT, 0); igraph_radius(&g, &radius, IGRAPH_ALL); if (radius != 1) { return 2; } igraph_destroy(&g); igraph_star(&g, 10, IGRAPH_STAR_OUT, 0); igraph_radius(&g, &radius, IGRAPH_OUT); if (radius != 0) { return 3; } igraph_destroy(&g); return 0; }
int igraph_global_efficiency(const igraph_t *graph, igraph_real_t *res,
const igraph_vector_t *weights,
igraph_bool_t directed);
The global efficiency of a network is defined as the average of inverse distances
between all pairs of vertices: E_g = 1/(N*(N-1)) sum_{i!=j} 1/d_ij,
where N is the number of vertices.
The inverse distance between pairs that are not reachable from each other is considered
to be zero. For graphs with fewer than 2 vertices, NaN is returned.
Reference: V. Latora and M. Marchiori, Efficient Behavior of Small-World Networks, Phys. Rev. Lett. 87, 198701 (2001). https://dx.doi.org/10.1103/PhysRevLett.87.198701
Arguments:
|
The graph object. |
|
Pointer to a real number, this will contain the result. |
|
The edge weights. All edge weights must be
non-negative for Dijkstra's algorithm to work. Additionally, no
edge weight may be NaN. If either case does not hold, an error
is returned. If this is a null pointer, then the unweighted
version, |
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
Returns:
|
Error code:
|
Time complexity: O(|V| |E| log|E| + |V|) for weighted graphs and O(|V| |E|) for unweighted ones. |V| denotes the number of vertices and |E| denotes the number of edges.
int igraph_local_efficiency(const igraph_t *graph, igraph_vector_t *res,
const igraph_vs_t vids,
const igraph_vector_t *weights,
igraph_bool_t directed, igraph_neimode_t mode);
The local efficiency of a network around a vertex is defined as follows: We remove the vertex and compute the distances (shortest path lengths) between its neighbours through the rest of the network. The local efficiency around the removed vertex is the average of the inverse of these distances.
The inverse distance between two vertices which are not reachable from each other is considered to be zero. The local efficiency around a vertex with fewer than two neighbours is taken to be zero by convention.
Reference: I. Vragović, E. Louis, and A. Díaz-Guilera, Efficiency of informational transfer in regular and complex networks, Phys. Rev. E 71, 1 (2005). http://dx.doi.org/10.1103/PhysRevE.71.036122
Arguments:
|
The graph object. |
||||||
|
Pointer to an initialized vector, this will contain the result. |
||||||
|
The vertices around which the local efficiency will be calculated. |
||||||
|
The edge weights. All edge weights must be
non-negative. Additionally, no edge weight may be NaN. If either
case does not hold, an error is returned. If this is a null
pointer, then the unweighted version,
|
||||||
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
||||||
|
How to determine the local neighborhood of each vertex in directed graphs. Ignored in undirected graphs.
|
Returns:
|
Error code:
|
Time complexity: O(|E|^2 log|E|) for weighted graphs and O(|E|^2) for unweighted ones. |E| denotes the number of edges.
See also:
int igraph_average_local_efficiency(const igraph_t *graph, igraph_real_t *res,
const igraph_vector_t *weights,
igraph_bool_t directed, igraph_neimode_t mode);
For the null graph, zero is returned by convention.
Arguments:
|
The graph object. |
||||||
|
Pointer to a real number, this will contain the result. |
||||||
|
The edge weights. They must be all non-negative. If a null pointer is given, all weights are assumed to be 1. |
||||||
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
||||||
|
How to determine the local neighborhood of each vertex in directed graphs. Ignored in undirected graphs.
|
Returns:
|
Error code:
|
Time complexity: O(|E|^2 log|E|) for weighted graphs and O(|E|^2) for unweighted ones. |E| denotes the number of edges.
See also:
int igraph_neighborhood_size(const igraph_t *graph, igraph_vector_t *res,
igraph_vs_t vids, igraph_integer_t order,
igraph_neimode_t mode,
igraph_integer_t mindist);
The neighborhood of a given order of a vertex includes all vertices which are closer to the vertex than the order. I.e., order 0 is always the vertex itself, order 1 is the vertex plus its immediate neighbors, order 2 is order 1 plus the immediate neighbors of the vertices in order 1, etc.
This function calculates the size of the neighborhood of the given order for the given vertices.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the result will be stored here. It will be resized as needed. |
|
The vertices for which the calculation is performed. |
|
Integer giving the order of the neighborhood. |
|
Specifies how to use the direction of the edges if a
directed graph is analyzed. For |
|
The minimum distance to include a vertex in the counting. Vertices reachable with a path shorter than this value are excluded. If this is one, then the starting vertex is not counted. If this is two, then its neighbors are not counted either, etc. |
Returns:
Error code. |
See also:
|
Time complexity: O(n*d*o), where n is the number vertices for which the calculation is performed, d is the average degree, o is the order.
int igraph_neighborhood(const igraph_t *graph, igraph_vector_ptr_t *res,
igraph_vs_t vids, igraph_integer_t order,
igraph_neimode_t mode, igraph_integer_t mindist);
The neighborhood of a given order of a vertex includes all vertices which are closer to the vertex than the order. I.e., order 0 is always the vertex itself, order 1 is the vertex plus its immediate neighbors, order 2 is order 1 plus the immediate neighbors of the vertices in order 1, etc.
This function calculates the vertices within the neighborhood of the specified vertices.
Arguments:
|
The input graph. |
|
An initialized pointer vector. Note that the objects
(pointers) in the vector will not be freed, but the pointer
vector will be resized as needed. The result of the calculation
will be stored here in |
|
The vertices for which the calculation is performed. |
|
Integer giving the order of the neighborhood. |
|
Specifies how to use the direction of the edges if a
directed graph is analyzed. For |
|
The minimum distance to include a vertex in the counting. Vertices reachable with a path shorter than this value are excluded. If this is one, then the starting vertex is not counted. If this is two, then its neighbors are not counted either, etc. |
Returns:
Error code. |
See also:
|
Time complexity: O(n*d*o), n is the number of vertices for which the calculation is performed, d is the average degree, o is the order.
int igraph_neighborhood_graphs(const igraph_t *graph, igraph_vector_ptr_t *res,
igraph_vs_t vids, igraph_integer_t order,
igraph_neimode_t mode,
igraph_integer_t mindist);
The neighborhood of a given order of a vertex includes all vertices which are closer to the vertex than the order. Ie. order 0 is always the vertex itself, order 1 is the vertex plus its immediate neighbors, order 2 is order 1 plus the immediate neighbors of the vertices in order 1, etc.
This function finds every vertex in the neighborhood of a given parameter vertex and creates the induced subgraph from these vertices.
The first version of this function was written by Vincent Matossian, thanks Vincent.
Arguments:
|
The input graph. |
|
Pointer to a pointer vector, the result will be stored
here, ie. |
|
The vertices for which the calculation is performed. |
|
Integer giving the order of the neighborhood. |
|
Specifies how to use the direction of the edges if a
directed graph is analyzed. For |
|
The minimum distance to include a vertex in the counting. Vertices reachable with a path shorter than this value are excluded. If this is one, then the starting vertex is not counted. If this is two, then its neighbors are not counted either, etc. |
Returns:
Error code. |
See also:
|
Time complexity: O(n*(|V|+|E|)), where n is the number vertices for which the calculation is performed, |V| and |E| are the number of vertices and edges in the original input graph.
The scan statistic is a summary of the locality statistics that is computed from the local neighborhood of each vertex. For details, see Priebe, C. E., Conroy, J. M., Marchette, D. J., Park, Y. (2005). Scan Statistics on Enron Graphs. Computational and Mathematical Organization Theory.
int igraph_local_scan_0(const igraph_t *graph, igraph_vector_t *res,
const igraph_vector_t *weights,
igraph_neimode_t mode);
K=0 scan-statistics is arbitrarily defined as the vertex degree for
unweighted, and the vertex strength for weighted graphs. See igraph_degree() and igraph_strength().
Arguments:
|
The input graph |
|
An initialized vector, the results are stored here. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
int igraph_local_scan_1_ecount(const igraph_t *graph, igraph_vector_t *res,
const igraph_vector_t *weights,
igraph_neimode_t mode);
Count the number of edges or the sum the edge weights in the 1-neighborhood of vertices.
Arguments:
|
The input graph |
|
An initialized vector, the results are stored here. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
int igraph_local_scan_k_ecount(const igraph_t *graph, int k,
igraph_vector_t *res,
const igraph_vector_t *weights,
igraph_neimode_t mode);
Arguments:
|
The input graph. |
|
The size of the neighborhood, non-negative integer.
The k=0 case is special, see |
|
An initialized vector, the results are stored here. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
int igraph_local_scan_0_them(const igraph_t *us, const igraph_t *them,
igraph_vector_t *res,
const igraph_vector_t *weights_them,
igraph_neimode_t mode);
K=0 scan-statistics is arbitrarily defined as the vertex degree for
unweighted, and the vertex strength for weighted graphs. See igraph_degree() and igraph_strength().
Arguments:
|
The input graph, to use to extract the neighborhoods. |
|
The input graph to use for the actually counting. |
|
An initialized vector, the results are stored here. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
int igraph_local_scan_1_ecount_them(const igraph_t *us, const igraph_t *them,
igraph_vector_t *res,
const igraph_vector_t *weights_them,
igraph_neimode_t mode);
Count the number of edges or the sum the edge weights in the 1-neighborhood of vertices.
Arguments:
|
The input graph to extract the neighborhoods. |
|
The input graph to perform the counting. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
See also:
|
int igraph_local_scan_k_ecount_them(const igraph_t *us, const igraph_t *them,
int k, igraph_vector_t *res,
const igraph_vector_t *weights_them,
igraph_neimode_t mode);
Count the number of edges or the sum the edge weights in the k-neighborhood of vertices.
Arguments:
|
The input graph to extract the neighborhoods. |
|
The input graph to perform the counting. |
|
The size of the neighborhood, non-negative integer.
The k=0 case is special, see |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
See also:
|
int igraph_local_scan_neighborhood_ecount(const igraph_t *graph,
igraph_vector_t *res,
const igraph_vector_t *weights,
const igraph_vector_ptr_t *neighborhoods);
Count the number of edges, or sum the edge weigths in neighborhoods given as a parameter.
Arguments:
|
The graph to perform the counting/summing in. |
|
Initialized vector, the result is stored here. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
List of |
Returns:
Error code. |
igraph_subcomponent — The vertices in the same component as a given vertex.igraph_clusters — Calculates the (weakly or strongly) connected components in a graph.igraph_is_connected — Decides whether the graph is (weakly or strongly) connected.igraph_decompose — Decompose a graph into connected components.igraph_decompose_destroy — Free the memory allocated by igraph_decompose().igraph_biconnected_components — Calculate biconnected componentsigraph_articulation_points — Find the articulation points in a graph.igraph_bridges — Find all bridges in a graph.
int igraph_subcomponent(const igraph_t *graph, igraph_vector_t *res, igraph_real_t vertex,
igraph_neimode_t mode);
Arguments:
|
The graph object. |
||||||
|
The result, vector with the ids of the vertices in the same component. |
||||||
|
The id of the vertex of which the component is searched. |
||||||
|
Type of the component for directed graphs, possible values:
|
Returns:
|
Error code:
|
Time complexity: O(|V|+|E|), |V| and |E| are the number of vertices and edges in the graph.
See also:
|
int igraph_clusters(const igraph_t *graph, igraph_vector_t *membership,
igraph_vector_t *csize, igraph_integer_t *no,
igraph_connectedness_t mode);
Arguments:
|
The graph object to analyze. |
|
First half of the result will be stored here. For
every vertex the id of its component is given. The vector
has to be preinitialized and will be resized. Alternatively
this argument can be |
|
The second half of the result. For every component it
gives its size, the order is defined by the component ids.
The vector has to be preinitialized and will be resized.
Alternatively this argument can be |
|
Pointer to an integer, if not |
|
For directed graph this specifies whether to calculate
weakly or strongly connected components. Possible values:
|
Returns:
Error code:
|
Time complexity: O(|V|+|E|), |V| and |E| are the number of vertices and edges in the graph.
int igraph_is_connected(const igraph_t *graph, igraph_bool_t *res,
igraph_connectedness_t mode);
A graph with zero vertices (i.e. the null graph) is not connected by definition. This behaviour changed in igraph 0.9; earlier versions assumed that the null graph is connected. See the following issue on Github for the argument that led us to change the definition: https://github.com/igraph/igraph/issues/1538
Arguments:
|
The graph object to analyze. |
|
Pointer to a logical variable, the result will be stored here. |
|
For a directed graph this specifies whether to calculate
weak or strong connectedness. Possible values:
|
Returns:
Error code:
|
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph.
int igraph_decompose(const igraph_t *graph, igraph_vector_ptr_t *components,
igraph_connectedness_t mode,
long int maxcompno, long int minelements);
Create separate graph for each component of a graph. Note that the vertex ids in the new graphs will be different than in the original graph. (Except if there is only one component in the original graph.)
Arguments:
|
The original graph. |
|
This pointer vector will contain pointers to the
subcomponent graphs. It should be initialized before calling this
function and will be resized to hold the graphs. Don't forget to
call |
|
Either |
|
The maximum number of components to return. The
first |
|
The minimum number of vertices a component
should contain in order to place it in the |
Returns:
Error code, |
Added in version 0.2.
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.
Example 13.12. File examples/simple/igraph_decompose.c
#include <igraph.h> #include <stdlib.h> void free_complist(igraph_vector_ptr_t *complist) { long int i; for (i = 0; i < igraph_vector_ptr_size(complist); i++) { igraph_destroy(VECTOR(*complist)[i]); igraph_free(VECTOR(*complist)[i]); } } int main() { igraph_t ring, g; igraph_vector_ptr_t complist; long int i; igraph_real_t edges[] = { 0, 1, 1, 2, 2, 0, 3, 4, 4, 5, 5, 6, 8, 9, 9, 10 }; igraph_vector_t v; /* A ring, a single component */ igraph_ring(&ring, 10, IGRAPH_UNDIRECTED, 0, 1); igraph_vector_ptr_init(&complist, 0); igraph_decompose(&ring, &complist, IGRAPH_WEAK, -1, 0); igraph_write_graph_edgelist(VECTOR(complist)[0], stdout); free_complist(&complist); igraph_destroy(&ring); /* Random graph with a giant component */ igraph_erdos_renyi_game(&g, IGRAPH_ERDOS_RENYI_GNP, 100, 4.0 / 100, IGRAPH_UNDIRECTED, 0); igraph_decompose(&g, &complist, IGRAPH_WEAK, -1, 20); if (igraph_vector_ptr_size(&complist) != 1) { return 1; } free_complist(&complist); igraph_destroy(&g); /* A toy graph, three components maximum, with at least 2 vertices each */ igraph_create(&g, igraph_vector_view(&v, edges, sizeof(edges) / sizeof(igraph_real_t)), 0, IGRAPH_DIRECTED); igraph_decompose(&g, &complist, IGRAPH_WEAK, 3, 2); for (i = 0; i < igraph_vector_ptr_size(&complist); i++) { igraph_write_graph_edgelist(VECTOR(complist)[i], stdout); } free_complist(&complist); igraph_destroy(&g); igraph_vector_ptr_destroy(&complist); return 0; }
igraph_decompose_destroy — Free the memory allocated by igraph_decompose().
void igraph_decompose_destroy(igraph_vector_ptr_t *complist);
Arguments:
|
The list of graph components, as returned by
|
Time complexity: O(c), c is the number of components.
int igraph_biconnected_components(const igraph_t *graph,
igraph_integer_t *no,
igraph_vector_ptr_t *tree_edges,
igraph_vector_ptr_t *component_edges,
igraph_vector_ptr_t *components,
igraph_vector_t *articulation_points);
A graph is biconnected if the removal of any single vertex (and its incident edges) does not disconnect it.
A biconnected component of a graph is a maximal biconnected subgraph of it. The biconnected components of a graph can be given by the partition of its edges: every edge is a member of exactly one biconnected component. Note that this is not true for vertices: the same vertex can be part of many biconnected components.
Somewhat arbitrarily, igraph does not consider components containing a single vertex only as being biconnected. Isolated vertices will not be part of any of the biconnected components.
Arguments:
|
The input graph. |
|
The number of biconnected components will be stored here. |
|
If not a NULL pointer, then the found components
are stored here, in a list of vectors. Every vector in the list
is a biconnected component, represented by its edges. More precisely,
a spanning tree of the biconnected component is returned.
Note you'll have to
destroy each vector first by calling |
|
If not a NULL pointer, then the edges of the
biconnected components are stored here, in the same form as for
|
|
If not a NULL pointer, then the vertices of the biconnected components are stored here, in the same format as for the previous two arguments. |
|
If not a NULL pointer, then the articulation points of the graph are stored in this vector. A vertex is an articulation point if its removal increases the number of (weakly) connected components in the graph. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices and
edges, but only if you do not calculate components and
component_edges. If you calculate components, then it is
quadratic in the number of vertices. If you calculate component_edges as well, then it is cubic in the number of
vertices.
See also:
Example 13.13. File examples/simple/igraph_biconnected_components.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 sort_and_print_vector(igraph_vector_t *v) { long int i, n = igraph_vector_size(v); igraph_vector_sort(v); for (i = 0; i < n; i++) { printf(" %li", (long int) VECTOR(*v)[i]); } printf("\n"); } void warning_handler_ignore(const char* reason, const char* file, int line, int e) { } int main() { igraph_t g; igraph_vector_ptr_t result; igraph_integer_t no; long int i; igraph_set_warning_handler(warning_handler_ignore); igraph_vector_ptr_init(&result, 0); igraph_small(&g, 7, 0, 0, 1, 1, 2, 2, 3, 3, 0, 2, 4, 4, 5, 2, 5, -1); igraph_biconnected_components(&g, &no, 0, 0, &result, 0); if (no != 2 || no != igraph_vector_ptr_size(&result)) { return 1; } for (i = 0; i < no; i++) { sort_and_print_vector((igraph_vector_t*)VECTOR(result)[i]); igraph_vector_destroy((igraph_vector_t*)VECTOR(result)[i]); igraph_free((igraph_vector_t*)VECTOR(result)[i]); } igraph_biconnected_components(&g, &no, 0, &result, 0, 0); if (no != 2 || no != igraph_vector_ptr_size(&result)) { return 2; } for (i = 0; i < no; i++) { sort_and_print_vector((igraph_vector_t*)VECTOR(result)[i]); igraph_vector_destroy((igraph_vector_t*)VECTOR(result)[i]); igraph_free((igraph_vector_t*)VECTOR(result)[i]); } igraph_biconnected_components(&g, &no, &result, 0, 0, 0); if (no != 2 || no != igraph_vector_ptr_size(&result)) { return 3; } for (i = 0; i < no; i++) { sort_and_print_vector((igraph_vector_t*)VECTOR(result)[i]); igraph_vector_destroy((igraph_vector_t*)VECTOR(result)[i]); igraph_free((igraph_vector_t*)VECTOR(result)[i]); } igraph_vector_ptr_destroy(&result); igraph_destroy(&g); return 0; }
int igraph_articulation_points(const igraph_t *graph,
igraph_vector_t *res);
A vertex is an articulation point if its removal increases the number of connected components in the graph.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the articulation points will be stored here. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices and edges.
See also:
int igraph_bridges(const igraph_t *graph, igraph_vector_t *bridges);
An edge is a bridge if its removal increases the number of (weakly) connected components in the graph.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the bridges will be stored here as edge indices. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices and edges.
See also:
igraph_is_graphical — Is there a graph with the given degree sequence?igraph_is_bigraphical — Is there a bipartite graph with the given bi-degree-sequence?igraph_is_degree_sequence — Determines whether a degree sequence is valid.igraph_is_graphical_degree_sequence — Determines whether a sequence of integers can be the degree sequence of some simple graph.
int igraph_is_graphical(const igraph_vector_t *out_degrees,
const igraph_vector_t *in_degrees,
const igraph_edge_type_sw_t allowed_edge_types,
igraph_bool_t *res);
Determines whether a sequence of integers can be the degree sequence of some graph. The classical concept of graphicality assumes simple graphs. This function can perform the check also when either self-loops, multi-edge, or both are allowed in the graph.
For simple undirected graphs, the Erdős-Gallai conditions are checked using the linear-time algorithm of Cloteaux. If both self-loops and multi-edges are allowed, it is sufficient to chek that that sum of degrees is even. If only multi-edges are allowed, but not self-loops, there is an additional condition that the sum of degrees be no smaller than twice the maximum degree. If at most one self-loop is allowed per vertex, but no multi-edges, a modified version of the Erdős-Gallai conditions are used (see Cairns & Mendan).
For simple directed graphs, the Fulkerson-Chen-Anstee theorem is used with the relaxation by Berger.
If both self-loops and multi-edges are allowed, then it is sufficient to check that the sum of
in- and out-degrees is the same. If only multi-edges are allowed, but not self loops, there is an
additional condition that the sum of out-degrees (or equivalently, in-degrees) is no smaller than
the maximum total degree. If single self-loops are allowed, but not multi-edges, the problem is equivalent
to realizability as a simple bipartite graph, thus the Gale-Ryser theorem can be used; see
igraph_is_bigraphical() for more information.
References:
P. Erdős and T. Gallai, Gráfok előírt fokú pontokkal, Matematikai Lapok 11, pp. 264–274 (1960). https://users.renyi.hu/~p_erdos/1961-05.pdf
Z Király, Recognizing graphic degree sequences and generating all realizations. TR-2011-11, Egerváry Research Group, H-1117, Budapest, Hungary. ISSN 1587-4451 (2012). http://bolyai.cs.elte.hu/egres/tr/egres-11-11.pdf
B. Cloteaux, Is This for Real? Fast Graphicality Testing, Comput. Sci. Eng. 17, 91 (2015). https://dx.doi.org/10.1109/MCSE.2015.125
A. Berger, A note on the characterization of digraphic sequences, Discrete Math. 314, 38 (2014). https://dx.doi.org/10.1016/j.disc.2013.09.010
G. Cairns and S. Mendan, Degree Sequence for Graphs with Loops (2013). https://arxiv.org/abs/1303.2145v1
Arguments:
|
A vector of integers specifying the degree sequence for undirected graphs or the out-degree sequence for directed graphs. |
||||||||
|
A vector of integers specifying the in-degree sequence for
directed graphs. For undirected graphs, it must be |
||||||||
|
The types of edges to allow in the graph:
|
||||||||
|
Pointer to a Boolean. The result will be stored here. |
Returns:
Error code. |
See also:
|
Time complexity: O(n^2) for simple directed graphs, O(n log n) for graphs with self-loops, and O(n) for all other cases, where n is the length of the degree sequence(s).
int igraph_is_bigraphical(const igraph_vector_t *degrees1,
const igraph_vector_t *degrees2,
const igraph_edge_type_sw_t allowed_edge_types,
igraph_bool_t *res);
Determines whether two sequences of integers can be the degree sequences of a bipartite graph. Such a pair of degree sequence is called bigraphical.
When multi-edges are allowed, it is sufficient to check that the sum of degrees is the same in the two partitions. For simple graphs, the Gale-Ryser theorem is used with Berger's relaxation.
References:
H. J. Ryser, Combinatorial Properties of Matrices of Zeros and Ones, Can. J. Math. 9, 371 (1957). https://dx.doi.org/10.4153/cjm-1957-044-3
D. Gale, A theorem on flows in networks, Pacific J. Math. 7, 1073 (1957). https://dx.doi.org/10.2140/pjm.1957.7.1073
A. Berger, A note on the characterization of digraphic sequences, Discrete Math. 314, 38 (2014). https://dx.doi.org/10.1016/j.disc.2013.09.010
Arguments:
|
A vector of integers specifying the degrees in the first partition |
||||
|
A vector of integers specifying the degrees in the second partition |
||||
|
The types of edges to allow in the graph:
|
||||
|
Pointer to a Boolean. The result will be stored here. |
Returns:
Error code. |
See also:
Time complexity: O(n log n) for simple graphs, O(n) for multigraphs, where n is the length of the larger degree sequence.
int igraph_is_degree_sequence(const igraph_vector_t *out_degrees,
const igraph_vector_t *in_degrees, igraph_bool_t *res);
Deprecated since version 0.9. Please do not use this function in new
code; use igraph_is_graphical()
instead.
A sequence of n integers is a valid degree sequence if there exists some
graph where the degree of the i-th vertex is equal to the i-th element of the
sequence. Note that the graph may contain multiple or loop edges; if you are
interested in whether the degrees of some simple graph may realize the
given sequence, use igraph_is_graphical_degree_sequence.
In particular, the function checks whether all the degrees are non-negative. For undirected graphs, it also checks whether the sum of degrees is even. For directed graphs, the function checks whether the lengths of the two degree vectors are equal and whether their sums are also equal. These are known sufficient and necessary conditions for a degree sequence to be valid.
Arguments:
|
an integer vector specifying the degree sequence for undirected graphs or the out-degree sequence for directed graphs. |
|
an integer vector specifying the in-degrees of the vertices for directed graphs. For undirected graphs, this must be null. |
|
pointer to a boolean variable, the result will be stored here |
Returns:
Error code. |
Time complexity: O(n), where n is the length of the degree sequence.
int igraph_is_graphical_degree_sequence(const igraph_vector_t *out_degrees,
const igraph_vector_t *in_degrees, igraph_bool_t *res);
Deprecated since version 0.9. Please do not use this function in new
code; use igraph_is_graphical()
instead.
References:
Hakimi SL: On the realizability of a set of integers as degrees of the vertices of a simple graph. J SIAM Appl Math 10:496-506, 1962.
PL Erdős, I Miklós and Z Toroczkai: A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs. The Electronic Journal of Combinatorics 17(1):R66, 2010. https://dx.doi.org/10.1017/S0963548317000499
Z Kiraly: Recognizing graphic degree sequences and generating all realizations. TR-2011-11, Egervary Research Group, H-1117, Budapest, Hungary. ISSN 1587-4451, 2012. https://www.cs.elte.hu/egres/tr/egres-11-11.pdf
Arguments:
|
an integer vector specifying the degree sequence for undirected graphs or the out-degree sequence for directed graphs. |
|
an integer vector specifying the in-degrees of the vertices for directed graphs. For undirected graphs, this must be null. |
|
pointer to a boolean variable, the result will be stored here |
Returns:
Error code. |
Time complexity: O(n log n) for undirected graphs, O(n^2) for directed graphs, where n is the length of the degree sequence.
igraph_closeness — Closeness centrality calculations for some vertices.igraph_harmonic_centrality — Harmonic centrality for some vertices.igraph_betweenness — Betweenness centrality of some vertices.igraph_edge_betweenness — Betweenness centrality of the edges.igraph_pagerank_algo_t — PageRank algorithm implementationigraph_pagerank — Calculates the Google PageRank for the specified vertices.igraph_personalized_pagerank — Calculates the personalized Google PageRank for the specified vertices.igraph_personalized_pagerank_vs — Calculates the personalized Google PageRank for the specified vertices.igraph_constraint — Burt's constraint scores.igraph_maxdegree — The maximum degree in a graph (or set of vertices).igraph_strength — Strength of the vertices, weighted vertex degree in other words.igraph_eigenvector_centrality — Eigenvector centrality of the verticesigraph_hub_score — Kleinberg's hub scores.igraph_authority_score — Kleinerg's authority scores.igraph_convergence_degree — Calculates the convergence degree of each edge in a graph.
int igraph_closeness(const igraph_t *graph, igraph_vector_t *res,
igraph_vector_t *reachable_count, igraph_bool_t *all_reachable,
const igraph_vs_t vids, igraph_neimode_t mode,
const igraph_vector_t *weights,
igraph_bool_t normalized);
The closeness centrality of a vertex measures how easily other vertices can be reached from it (or the other way: how easily it can be reached from the other vertices). It is defined as the inverse of the mean distance to (or from) all other vertices.
Closeness centrality is meaningful only for connected graphs.
If the graph is not connected, igraph computes the inverse of the
mean distance to (or from) all reachable vertices. In undirected
graphs, this is equivalent to computing the closeness separately in
each connected component. The optional all_reachable output
parameter is provided to help detect when the graph is disconnected.
While there is no universally adopted definition of closeness centrality
for disconnected graphs, there have been some attempts for generalizing
the concept to the disconnected case. One type of approach considers the mean distance
only to reachable vertices, then re-scales the obtained certrality score
by a factor that depends on the number of reachable vertices
(i.e. the size of the component in the undirected case).
To facilitate computing these generalizations of closeness centrality,
the number of reachable vertices (not including the starting vertex)
is returned in reachable_count.
In disconnected graphs, consider using the harmonic centrality,
computable using igraph_harmonic_centrality().
For isolated vertices, i.e. those having no associated paths, NaN is returned.
Arguments:
|
The graph object. |
||||||
|
The result of the computation, a vector containing the closeness centrality scores for the given vertices. |
||||||
|
If not |
||||||
|
Pointer to a Boolean. If not |
||||||
|
The vertices for which the closeness centrality will be computed. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
An optional vector containing edge weights for weighted closeness. No edge weight may be NaN. Supply a null pointer here for traditional, unweighted closeness. |
||||||
|
If true, the inverse of the mean distance to reachable vetices is returned. If false, the inverse of the sum of distances is returned. |
Returns:
|
Error code:
|
Time complexity: O(n|E|), n is the number of vertices for which the calculation is done and |E| is the number of edges in the graph.
See also:
Other centrality types: |
int igraph_harmonic_centrality(const igraph_t *graph, igraph_vector_t *res,
const igraph_vs_t vids, igraph_neimode_t mode,
const igraph_vector_t *weights,
igraph_bool_t normalized);
The harmonic centrality of a vertex is the mean inverse distance to all other vertices. The inverse distance to an unreachable vertex is considered to be zero.
References:
M. Marchiori and V. Latora, Harmony in the small-world, Physica A 285, pp. 539-546 (2000). https://doi.org/10.1016/S0378-4371%2800%2900311-3
Y. Rochat, Closeness Centrality Extended to Unconnected Graphs: the Harmonic Centrality Index, ASNA 2009. https://infoscience.epfl.ch/record/200525
S. Vigna and P. Boldi, Axioms for Centrality, Internet Mathematics 10, (2014). https://doi.org/10.1080/15427951.2013.865686
Arguments:
|
The graph object. |
||||||
|
The result of the computation, a vector containing the harmonic centrality scores for the given vertices. |
||||||
|
The vertices for which the harmonic centrality will be computed. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
An optional vector containing edge weights for
weighted harmonic centrality. No edge weight may be NaN.
If |
||||||
|
Boolean, whether to normalize the result. If true, the result is the mean inverse path length to other vertices, i.e. it is normalized by the number of vertices minus one. If false, the result is the sum of inverse path lengths to other vertices. |
Returns:
|
Error code:
|
Time complexity: O(n|E|), where n is the numberof vertices for which the calculation is done and |E| is the number of edges in the graph.
See also:
Other centrality types: |
int igraph_betweenness(const igraph_t *graph, igraph_vector_t *res,
const igraph_vs_t vids, igraph_bool_t directed,
const igraph_vector_t* weights);
The betweenness centrality of a vertex is the number of geodesics going through it. If there are more than one geodesic between two vertices, the value of these geodesics are weighted by one over the number of geodesics.
Arguments:
|
The graph object. |
|
The result of the computation, a vector containing the betweenness scores for the specified vertices. |
|
The vertices of which the betweenness centrality scores will be calculated. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional vector containing edge weights for calculating weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
Returns:
Error code:
|
Time complexity: O(|V||E|), |V| and |E| are the number of vertices and edges in the graph. Note that the time complexity is independent of the number of vertices for which the score is calculated.
See also:
Other centrality types: |
int igraph_edge_betweenness(const igraph_t *graph, igraph_vector_t *result,
igraph_bool_t directed,
const igraph_vector_t *weights);
The betweenness centrality of an edge is the number of geodesics going through it. If there are more than one geodesics between two vertices, the value of these geodesics are weighted by one over the number of geodesics.
Arguments:
|
The graph object. |
|
The result of the computation, vector containing the betweenness scores for the edges. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional weight vector for weighted edge betweenness. No edge weight may be NaN. Supply a null pointer here for the unweighted version. |
Returns:
Error code:
|
Time complexity: O(|V||E|), |V| and |E| are the number of vertices and edges in the graph.
See also:
Other centrality types: |
typedef enum {
IGRAPH_PAGERANK_ALGO_ARPACK = 1,
IGRAPH_PAGERANK_ALGO_PRPACK = 2
} igraph_pagerank_algo_t;
Algorithms to calculate PageRank.
Values:
|
Use the ARPACK library, this was the PageRank implementation in igraph from version 0.5, until version 0.7. |
|
Use the PRPACK library. Currently this implementation is recommended. |
int igraph_pagerank(const igraph_t *graph, igraph_pagerank_algo_t algo,
igraph_vector_t *vector,
igraph_real_t *value, const igraph_vs_t vids,
igraph_bool_t directed, igraph_real_t damping,
const igraph_vector_t *weights, igraph_arpack_options_t *options);
The PageRank centrality of a vertex is the fraction of time a
random walker traversing the graph would spend on that vertex.
The walker follows the out-edges with probabilities proportional
to their weights. Additionally, in each step, it restarts the walk
from a random vertex with probability 1 - damping.
If the random walker gets stuck in a sink vertex, it will also restart
from a random vertex.
The PageRank centrality is mainly useful for directed graphs. In undirected graphs it converges to trivial values proportional to degrees as the damping factor approaches 1.
Starting from version 0.9, igraph has two PageRank implementations,
and the user can choose between them. The first implementation is
IGRAPH_PAGERANK_ALGO_ARPACK, based on the ARPACK library. This
was the default before igraph version 0.7. The second and recommended
implementation is IGRAPH_PAGERANK_ALGO_PRPACK. This is using the
PRPACK package, see https://github.com/dgleich/prpack .
Note that the PageRank of a given vertex depends on the PageRank of all other vertices, so even if you want to calculate the PageRank for only some of the vertices, all of them must be calculated. Requesting the PageRank for only some of the vertices does not result in any performance increase at all.
References:
Sergey Brin and Larry Page: The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proceedings of the 7th World-Wide Web Conference, Brisbane, Australia, April 1998.
Arguments:
|
The graph object. |
|
The PageRank implementation to use. Possible values:
|
|
Pointer to an initialized vector, the result is stored here. It is resized as needed. |
|
Pointer to a real variable, the eigenvalue corresponding to the PageRank vector is stored here. It should be always exactly one. |
|
The vertex ids for which the PageRank is returned. |
|
Boolean, whether to consider the directedness of the edges. This is ignored for undirected graphs. |
|
The damping factor ("d" in the original paper). Must be a probability in the range [0, 1]. A commonly used value is 0.85. |
|
Optional edge weights. May be a |
|
Options for the ARPACK method. See |
Returns:
Error code:
|
Time complexity: depends on the input graph, usually it is O(|E|), the number of edges.
See also:
|
Example 13.14. File examples/simple/igraph_pagerank.c
#include <igraph.h> #include <float.h> int main() { igraph_t graph; igraph_vector_t pagerank; igraph_real_t value; /* Create a directed graph */ igraph_kautz(&graph, 2, 3); /* Initialize the vector where the results will be stored */ igraph_vector_init(&pagerank, 0); igraph_pagerank(&graph, IGRAPH_PAGERANK_ALGO_PRPACK, &pagerank, &value, igraph_vss_all(), IGRAPH_DIRECTED, /* damping */ 0.85, /* weights */ NULL, NULL /* not needed with PRPACK method */); /* Check that the eigenvalue is 1, as expected. */ if (fabs(value - 1.0) > 32*DBL_EPSILON) { fprintf(stderr, "PageRank failed to converge.\n"); return 1; } /* Output the result */ igraph_vector_print(&pagerank); /* Destroy data structure when no longer needed */ igraph_vector_destroy(&pagerank); igraph_destroy(&graph); return 0; }
int igraph_personalized_pagerank(const igraph_t *graph,
igraph_pagerank_algo_t algo, igraph_vector_t *vector,
igraph_real_t *value, const igraph_vs_t vids,
igraph_bool_t directed, igraph_real_t damping,
const igraph_vector_t *reset,
const igraph_vector_t *weights,
igraph_arpack_options_t *options);
The personalized PageRank is similar to the original PageRank measure, but
when the random walk is restarted, a new starting vertex is chosen non-uniformly,
according to the distribution specified in reset
(instead of the uniform distribution in the original PageRank measure).
The reset distribution is used both when restarting randomly with probability
1 - damping, and when the walker is forced to restart due to being
stuck in a sink vertex (a vertex with no outgoing edges).
Note that the personalized PageRank of a given vertex depends on the personalized PageRank of all other vertices, so even if you want to calculate the personalized PageRank for only some of the vertices, all of them must be calculated. Requesting the personalized PageRank for only some of the vertices does not result in any performance increase at all.
Arguments:
|
The graph object. |
|
The PageRank implementation to use. Possible values:
|
|
Pointer to an initialized vector, the result is stored here. It is resized as needed. |
|
Pointer to a real variable, the eigenvalue corresponding to the PageRank vector is stored here. It should be always exactly one. |
|
The vertex ids for which the PageRank is returned. |
|
Boolean, whether to consider the directedness of the edges. This is ignored for undirected graphs. |
|
The damping factor ("d" in the original paper). Must be a probability in the range [0, 1]. A commonly used value is 0.85. |
|
The probability distribution over the vertices used when
resetting the random walk. It is either a |
|
Optional edge weights. May be a |
|
Options for the ARPACK method. See |
Returns:
Error code:
|
Time complexity: depends on the input graph, usually it is O(|E|), the number of edges.
See also:
|
int igraph_personalized_pagerank_vs(const igraph_t *graph,
igraph_pagerank_algo_t algo, igraph_vector_t *vector,
igraph_real_t *value, const igraph_vs_t vids,
igraph_bool_t directed, igraph_real_t damping,
igraph_vs_t reset_vids,
const igraph_vector_t *weights,
igraph_arpack_options_t *options);
The personalized PageRank is similar to the original PageRank measure, but
when the random walk is restarted, a new starting vertex is chosen according to
a specified distribution.
This distribution is used both when restarting randomly with probability
1 - damping, and when the walker is forced to restart due to being
stuck in a sink vertex (a vertex with no outgoing edges).
This simplified interface takes a vertex sequence and resets the random walk to
one of the vertices in the specified vertex sequence, chosen uniformly. A typical
application of personalized PageRank is when the random walk is reset to the same
vertex every time - this can easily be achieved using igraph_vss_1() which
generates a vertex sequence containing only a single vertex.
Note that the personalized PageRank of a given vertex depends on the personalized PageRank of all other vertices, so even if you want to calculate the personalized PageRank for only some of the vertices, all of them must be calculated. Requesting the personalized PageRank for only some of the vertices does not result in any performance increase at all.
Arguments:
|
The graph object. |
|
The PageRank implementation to use. Possible values:
|
|
Pointer to an initialized vector, the result is stored here. It is resized as needed. |
|
Pointer to a real variable, the eigenvalue corresponding to the PageRank vector is stored here. It should be always exactly one. |
|
The vertex ids for which the PageRank is returned. |
|
Boolean, whether to consider the directedness of the edges. This is ignored for undirected graphs. |
|
The damping factor ("d" in the original paper). Must be a probability in the range [0, 1]. A commonly used value is 0.85. |
|
IDs of the vertices used when resetting the random walk. |
|
Optional edge weights, it is either a null pointer, then the edges are not weighted, or a vector of the same length as the number of edges. |
|
Options for the ARPACK method. See |
Returns:
Error code:
|
Time complexity: depends on the input graph, usually it is O(|E|), the number of edges.
See also:
|
int igraph_constraint(const igraph_t *graph, igraph_vector_t *res,
igraph_vs_t vids, const igraph_vector_t *weights);
This function calculates Burt's constraint scores for the given vertices, also known as structural holes.
Burt's constraint is higher if ego has less, or mutually stronger related (i.e. more redundant) contacts. Burt's measure of constraint, C[i], of vertex i's ego network V[i], is defined for directed and valued graphs,
C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in V[], j != i)
for a graph of order (i.e. number of vertices) N, where proportional tie strengths are defined as
p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i),
a[i,j] are elements of A and the latter being the graph adjacency matrix. For isolated vertices, constraint is undefined.
Burt, R.S. (2004). Structural holes and good ideas. American Journal of Sociology 110, 349-399.
The first R version of this function was contributed by Jeroen Bruggeman.
Arguments:
|
A graph object. |
|
Pointer to an initialized vector, the result will be stored here. The vector will be resized to have the appropriate size for holding the result. |
|
Vertex selector containing the vertices for which the constraint should be calculated. |
|
Vector giving the weights of the edges. If it is
|
Returns:
Error code. |
Time complexity: O(|V|+E|+n*d^2), n is the number of vertices for
which the constraint is calculated and d is the average degree, |V|
is the number of vertices, |E| the number of edges in the
graph. If the weights argument is NULL then the time complexity
is O(|V|+n*d^2).
int igraph_maxdegree(const igraph_t *graph, igraph_integer_t *res,
igraph_vs_t vids, igraph_neimode_t mode,
igraph_bool_t loops);
The largest in-, out- or total degree of the specified vertices is
calculated. If the graph has no vertices, or vids is empty,
0 is returned, as this is the smallest possible value for degrees.
Arguments:
|
The input graph. |
|
Pointer to an integer ( |
|
Vector giving the vertex IDs for which the maximum degree will be calculated. |
|
Defines the type of the degree.
|
|
Boolean, gives whether the self-loops should be counted. |
Returns:
Error code:
|
Time complexity: O(v) if loops is TRUE, and O(v*d) otherwise. v is the number of vertices for which the degree will be calculated, and d is their (average) degree.
int igraph_strength(const igraph_t *graph, igraph_vector_t *res,
const igraph_vs_t vids, igraph_neimode_t mode,
igraph_bool_t loops, const igraph_vector_t *weights);
In a weighted network the strength of a vertex is the sum of the weights of all incident edges. In a non-weighted network this is exactly the vertex degree.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the result is stored here. It will be resized as needed. |
|
The vertices for which the calculation is performed. |
|
Gives whether to count only outgoing ( |
|
A logical scalar, whether to count loop edges as well. |
|
A vector giving the edge weights. If this is a NULL
pointer, then |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number vertices and edges.
See also:
|
int igraph_eigenvector_centrality(const igraph_t *graph,
igraph_vector_t *vector,
igraph_real_t *value,
igraph_bool_t directed, igraph_bool_t scale,
const igraph_vector_t *weights,
igraph_arpack_options_t *options);
Eigenvector centrality is a measure of the importance of a node in a network. It assigns relative scores to all nodes in the network based on the principle that connections from high-scoring nodes contribute more to the score of the node in question than equal connections from low-scoring nodes. Specifically, the eigenvector centrality of each vertex is proportional to the sum of eigenvector centralities of its neighbors. In practice, the centralities are determined by calculating the eigenvector corresponding to the largest positive eigenvalue of the adjacency matrix. In the undirected case, this function considers the diagonal entries of the adjacency matrix to be twice the number of self-loops on the corresponding vertex.
The centrality scores returned by igraph can be normalized
(using the scale parameter) such that the largest eigenvector centrality
score is 1 (with one exception, see below).
In the directed case, the left eigenvector of the adjacency matrix is calculated. In other words, the centrality of a vertex is proportional to the sum of centralities of vertices pointing to it.
Eigenvector centrality is meaningful only for connected graphs. Graphs that are not connected should be decomposed into connected components, and the eigenvector centrality calculated for each separately. This function does not verify that the graph is connected. If it is not, in the undirected case the scores of all but one component will be zeros.
Also note that the adjacency matrix of a directed acyclic graph or the
adjacency matrix of an empty graph does not possess positive eigenvalues,
therefore the eigenvector centrality is not defined for these graphs.
igraph will return an eigenvalue of zero in such cases. The eigenvector
centralities will all be equal for an empty graph and will all be zeros
for a directed acyclic graph. Such pathological cases can be detected
by asking igraph to calculate the eigenvalue as well (using the value
parameter, see below) and checking whether the eigenvalue is very close
to zero.
Arguments:
|
The input graph. It may be directed. |
|
Pointer to an initialized vector, it will be resized as needed. The result of the computation is stored here. It can be a null pointer, then it is ignored. |
|
If not a null pointer, then the eigenvalue corresponding to the found eigenvector is stored here. |
|
Boolean scalar, whether to consider edge directions in a directed graph. It is ignored for undirected graphs. |
|
If not zero then the result will be scaled such that the absolute value of the maximum centrality is one. |
|
A null pointer (=no edge weights), or a vector giving the weights of the edges. The algorithm might result complex numbers is some weights are negative. In this case only the real part is reported. |
|
Options to ARPACK. See |
Returns:
Error code. |
Time complexity: depends on the input graph, usually it is O(|V|+|E|).
See also:
|
Example 13.15. File examples/simple/eigenvector_centrality.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2007-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 <math.h> int main() { igraph_t g; igraph_vector_t v, weights; long int i; igraph_real_t value; igraph_arpack_options_t options; igraph_star(&g, 100, IGRAPH_STAR_UNDIRECTED, 0); igraph_arpack_options_init(&options); igraph_vector_init(&v, 0); igraph_eigenvector_centrality(&g, &v, &value, /*directed=*/ 0, /*scale=*/1, /*weights=*/0, &options); if (options.info != 0) { return 1; } for (i = 0; i < igraph_vector_size(&v); i++) { printf(" %.4f", fabs(VECTOR(v)[i])); } printf("\n"); igraph_destroy(&g); /* Special cases: check for empty graph */ igraph_empty(&g, 10, 0); igraph_eigenvector_centrality(&g, &v, &value, 0, 0, 0, &options); if (value != 0.0) { return 1; } for (i = 0; i < igraph_vector_size(&v); i++) { printf(" %.2f", fabs(VECTOR(v)[i])); } printf("\n"); igraph_destroy(&g); /* Special cases: check for full graph, zero weights */ igraph_full(&g, 10, 0, 0); igraph_vector_init(&weights, 45); igraph_vector_fill(&weights, 0); igraph_eigenvector_centrality(&g, &v, &value, 0, 0, &weights, &options); igraph_vector_destroy(&weights); if (value != 0.0) { return 2; } for (i = 0; i < igraph_vector_size(&v); i++) { printf(" %.2f", fabs(VECTOR(v)[i])); } printf("\n"); igraph_destroy(&g); igraph_vector_destroy(&v); return 0; }
int igraph_hub_score(const igraph_t *graph, igraph_vector_t *vector,
igraph_real_t *value, igraph_bool_t scale,
const igraph_vector_t *weights,
igraph_arpack_options_t *options);
The hub scores of the vertices are defined as the principal
eigenvector of A*A^T, where A is the adjacency
matrix of the graph, A^T is its transposed.
See the following reference on the meaning of this score: J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
Arguments:
|
The input graph. Can be directed and undirected. |
|
Pointer to an initialized vector, the result is stored here. If a null pointer then it is ignored. |
|
If not a null pointer then the eigenvalue corresponding to the calculated eigenvector is stored here. |
|
If not zero then the result will be scaled such that the absolute value of the maximum centrality is one. |
|
A null pointer (=no edge weights), or a vector giving the weights of the edges. |
|
Options to ARPACK. See |
Returns:
Error code. |
Time complexity: depends on the input graph, usually it is O(|V|), the number of vertices.
See also:
|
int igraph_authority_score(const igraph_t *graph, igraph_vector_t *vector,
igraph_real_t *value, igraph_bool_t scale,
const igraph_vector_t *weights,
igraph_arpack_options_t *options);
The authority scores of the vertices are defined as the principal
eigenvector of A^T*A, where A is the adjacency
matrix of the graph, A^T is its transposed.
See the following reference on the meaning of this score: J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
Arguments:
|
The input graph. Can be directed and undirected. |
|
Pointer to an initialized vector, the result is stored here. If a null pointer then it is ignored. |
|
If not a null pointer then the eigenvalue corresponding to the calculated eigenvector is stored here. |
|
If not zero then the result will be scaled such that the absolute value of the maximum centrality is one. |
|
A null pointer (=no edge weights), or a vector giving the weights of the edges. |
|
Options to ARPACK. See |
Returns:
Error code. |
Time complexity: depends on the input graph, usually it is O(|V|), the number of vertices.
See also:
|
int igraph_convergence_degree(const igraph_t *graph, igraph_vector_t *result,
igraph_vector_t *ins, igraph_vector_t *outs);
Let us define the input set of an edge (i, j) as the set of vertices where the shortest paths passing through (i, j) originate, and similarly, let us defined the output set of an edge (i, j) as the set of vertices where the shortest paths passing through (i, j) terminate. The convergence degree of an edge is defined as the normalized value of the difference between the size of the input set and the output set, i.e. the difference of them divided by the sum of them. Convergence degrees are in the range (-1, 1); a positive value indicates that the edge is convergent since the shortest paths passing through it originate from a larger set and terminate in a smaller set, while a negative value indicates that the edge is divergent since the paths originate from a small set and terminate in a larger set.
Note that the convergence degree as defined above does not make sense in undirected graphs as there is no distinction between the input and output set. Therefore, for undirected graphs, the input and output sets of an edge are determined by orienting the edge arbitrarily while keeping the remaining edges undirected, and then taking the absolute value of the convergence degree.
Arguments:
|
The input graph, it can be either directed or undirected. |
|
Pointer to an initialized vector; the convergence degrees of
each edge will be stored here. May be |
|
Pointer to an initialized vector; the size of the input set of
each edge will be stored here. May be |
|
Pointer to an initialized vector; the size of the output set of
each edge will be stored here. May be |
Returns:
Error code. |
Time complexity: O(|V||E|), the number of vertices times the number of edges.
igraph_closeness_cutoff — Range limited closeness centrality.igraph_harmonic_centrality_cutoff — Range limited harmonic centrality.igraph_betweenness_cutoff — Range-limited betweenness centrality.igraph_edge_betweenness_cutoff — Range-limited betweenness centrality of the edges.
int igraph_closeness_cutoff(const igraph_t *graph, igraph_vector_t *res,
igraph_vector_t *reachable_count, igraph_bool_t *all_reachable,
const igraph_vs_t vids, igraph_neimode_t mode,
const igraph_vector_t *weights,
igraph_bool_t normalized,
igraph_real_t cutoff);
This function computes a range-limited version of closeness centrality by considering only those shortest paths whose length is no greater then the given cutoff value.
Arguments:
|
The graph object. |
||||||
|
The result of the computation, a vector containing the range-limited closeness centrality scores for the given vertices. |
||||||
|
If not |
||||||
|
Pointer to a Boolean. If not |
||||||
|
The vertices for which the range limited closeness centrality will be computed. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
An optional vector containing edge weights for weighted closeness. No edge weight may be NaN. Supply a null pointer here for traditional, unweighted closeness. |
||||||
|
If true, the inverse of the mean distance to vertices reachable within the cutoff is returned. If false, the inverse of the sum of distances is returned. |
||||||
|
The maximal length of paths that will be considered. If negative, the exact closeness will be calculated (no upper limit on path lengths). |
Returns:
|
Error code:
|
Time complexity: O(n|E|), n is the number of vertices for which the calculation is done and |E| is the number of edges in the graph.
See also:
|
int igraph_harmonic_centrality_cutoff(const igraph_t *graph, igraph_vector_t *res,
const igraph_vs_t vids, igraph_neimode_t mode,
const igraph_vector_t *weights,
igraph_bool_t normalized,
igraph_real_t cutoff);
This function computes the range limited version of harmonic centrality: only those shortest paths are considered whose length is not above the given cutoff. The inverse distance to vertices not reachable within the cutoff is considered to be zero.
Arguments:
|
The graph object. |
||||||
|
The result of the computation, a vector containing the range limited harmonic centrality scores for the given vertices. |
||||||
|
The vertices for which the harmonic centrality will be computed. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
An optional vector containing edge weights for
weighted harmonic centrality. No edge weight may be NaN.
If |
||||||
|
Boolean, whether to normalize the result. If true, the result is the mean inverse path length to other vertices. i.e. it is normalized by the number of vertices minus one. If false, the result is the sum of inverse path lengths to other vertices. |
||||||
|
The maximal length of paths that will be considered. The inverse distance to vertices that are not reachable within the cutoff path length is considered to be zero. Supply a negative value to compute the exact harmonic centrality, without any upper limit on the length of paths. |
Returns:
|
Error code:
|
Time complexity: O(n|E|), where n is the number of vertices for which the calculation is done and |E| is the number of edges in the graph.
See also:
Other centrality types: |
int igraph_betweenness_cutoff(const igraph_t *graph, igraph_vector_t *res,
const igraph_vs_t vids, igraph_bool_t directed,
const igraph_vector_t *weights, igraph_real_t cutoff);
This function computes a range-limited version of betweenness centrality by considering only those shortest paths whose length is no greater then the given cutoff value.
Arguments:
|
The graph object. |
|
The result of the computation, a vector containing the range-limited betweenness scores for the specified vertices. |
|
The vertices for which the range-limited betweenness centrality scores will be computed. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional vector containing edge weights for calculating weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
|
The maximal length of paths that will be considered. If negative, the exact betweenness will be calculated, and there will be no upper limit on path lengths. |
Returns:
Error code:
|
Time complexity: O(|V||E|), |V| and |E| are the number of vertices and edges in the graph. Note that the time complexity is independent of the number of vertices for which the score is calculated.
See also:
|
int igraph_edge_betweenness_cutoff(const igraph_t *graph, igraph_vector_t *result,
igraph_bool_t directed,
const igraph_vector_t *weights, igraph_real_t cutoff);
This function computes a range-limited version of edge betweenness centrality by considering only those shortest paths whose length is no greater then the given cutoff value.
Arguments:
|
The graph object. |
|
The result of the computation, vector containing the betweenness scores for the edges. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional weight vector for weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
|
The maximal length of paths that will be considered. If negative, the exact betweenness will be calculated (no upper limit on path lengths). |
Returns:
Error code:
|
Time complexity: O(|V||E|), |V| and |E| are the number of vertices and edges in the graph.
See also:
|
igraph_centralization — Calculate the centralization score from the node level scoresigraph_centralization_degree — Calculate vertex degree and graph centralizationigraph_centralization_betweenness — Calculate vertex betweenness and graph centralizationigraph_centralization_closeness — Calculate vertex closeness and graph centralizationigraph_centralization_eigenvector_centrality — Calculate eigenvector centrality scores and graph centralizationigraph_centralization_degree_tmax — Theoretical maximum for graph centralization based on degreeigraph_centralization_betweenness_tmax — Theoretical maximum for graph centralization based on betweennessigraph_centralization_closeness_tmax — Theoretical maximum for graph centralization based on closenessigraph_centralization_eigenvector_centrality_tmax — Theoretical maximum centralization for eigenvector centrality
igraph_real_t igraph_centralization(const igraph_vector_t *scores,
igraph_real_t theoretical_max,
igraph_bool_t normalized);
For a centrality score defined on the vertices of a graph, it is possible to define a graph level centralization index, by calculating the sum of the deviation from the maximum centrality score. Consequently, the higher the centralization index of the graph, the more centralized the structure is.
In order to make graphs of different sizes comparable, the centralization index is usually normalized to a number between zero and one, by dividing the (unnormalized) centralization score of the most centralized structure with the same number of vertices.
For most centrality indices the most centralized structure is the star graph, a single center connected to all other nodes in the network. There are some variation depending on whether the graph is directed or not, whether loop edges are allowed, etc.
This function simply calculates the graph level index, if the node level scores and the theoretical maximum are given. It is called by all the measure-specific centralization functions.
Arguments:
|
A vector containing the node-level centrality scores. |
|
The graph level centrality score of the most
centralized graph with the same number of vertices. Only used
if |
|
Boolean, whether to normalize the centralization by dividing the supplied theoretical maximum. |
Returns:
The graph level index. |
See also:
|
Time complexity: O(n), the length of the score vector.
Example 13.16. File examples/simple/centralization.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2009-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 <math.h> #define ALMOST_EQUALS(a, b) (fabs((a)-(b)) < 1e-8) int main() { igraph_t g; igraph_real_t cent; igraph_arpack_options_t arpack_options; /****************************/ /* in-star */ igraph_star(&g, 10, IGRAPH_STAR_IN, /*center=*/ 0); igraph_centralization_degree(&g, /*res=*/ 0, /*mode=*/ IGRAPH_IN, IGRAPH_NO_LOOPS, ¢, /*theoretical_max=*/ 0, /*normalized=*/ 1); if (cent != 1.0) { fprintf(stderr, "in-star, degree: %g\n", cent); return 1; } igraph_centralization_betweenness(&g, /*res=*/ 0, IGRAPH_UNDIRECTED, ¢, /*theoretical_max=*/ 0, /*normalized=*/ 1); if (cent != 1.0) { fprintf(stderr, "in-star, betweenness: %g\n", cent); return 2; } /* Skip closeness, as it is not well-defined for disconnected graphs such as an in-star. */ igraph_destroy(&g); /****************************/ /* out-star */ igraph_star(&g, 10, IGRAPH_STAR_OUT, /*center=*/ 0); igraph_centralization_degree(&g, /*res=*/ 0, /*mode=*/ IGRAPH_OUT, IGRAPH_NO_LOOPS, ¢, /*theoretical_max=*/ 0, /*normalized=*/ 1); if (cent != 1.0) { fprintf(stderr, "out-star, degree: %g\n", cent); return 11; } igraph_centralization_betweenness(&g, /*res=*/ 0, IGRAPH_UNDIRECTED, ¢, /*theoretical_max=*/ 0, /*normalized=*/ 1); if (cent != 1.0) { fprintf(stderr, "out-star, betweenness: %g\n", cent); return 12; } /* Skip closeness, as it is not well-defined for disconnected graphs such as an out-star. */ igraph_destroy(&g); /****************************/ /* undirected star */ igraph_star(&g, 10, IGRAPH_STAR_UNDIRECTED, /*center=*/ 0); igraph_centralization_degree(&g, /*res=*/ 0, /*mode=*/ IGRAPH_ALL, IGRAPH_NO_LOOPS, ¢, /*theoretical_max=*/ 0, /*normalized=*/ 1); if (cent != 1.0) { fprintf(stderr, "undirected star, degree: %g\n", cent); return 21; } igraph_centralization_betweenness(&g, /*res=*/ 0, IGRAPH_UNDIRECTED, ¢, /*theoretical_max=*/ 0, /*normalized=*/ 1); if (cent != 1.0) { fprintf(stderr, "undirected star, betweenness: %g\n", cent); return 22; } igraph_centralization_closeness(&g, /*res=*/ 0, IGRAPH_ALL, ¢, /*theoretical_max=*/ 0, /*normalization=*/ 1); if (!ALMOST_EQUALS(cent, 1.0)) { fprintf(stderr, "undirected star, closeness: %g\n", cent); return 23; } igraph_destroy(&g); /****************************/ /* single dyad */ igraph_small(&g, /*n=*/ 10, /*directed=*/ 0, 0, 1, -1); igraph_arpack_options_init(&arpack_options); igraph_centralization_eigenvector_centrality(&g, /*vector=*/ 0, /*value=*/ 0, /*directed=*/ 1, /*scale=*/ 1, &arpack_options, ¢, /*theoretical_max=*/ 0, /*normalization=*/ 1); if (!ALMOST_EQUALS(cent, 1.0)) { fprintf(stderr, "dyad, eigenvector centrality: %g\n", cent); return 24; } igraph_centralization_eigenvector_centrality(&g, /*vector=*/ 0, /*value=*/ 0, /*directed=*/ 1, /*scale=*/ 0, &arpack_options, ¢, /*theoretical_max=*/ 0, /*normalization=*/ 1); if (!ALMOST_EQUALS(cent, 1.0)) { fprintf(stderr, "dyad, eigenvector centrality, not scaled: %g\n", cent); return 25; } igraph_destroy(&g); return 0; }
int igraph_centralization_degree(const igraph_t *graph, igraph_vector_t *res,
igraph_neimode_t mode, igraph_bool_t loops,
igraph_real_t *centralization,
igraph_real_t *theoretical_max,
igraph_bool_t normalized);
This function calculates the degree of the vertices by passing its
arguments to igraph_degree(); and it calculates the graph
level centralization index based on the results by calling igraph_centralization().
Arguments:
|
The input graph. |
|
A vector if you need the node-level degree scores, or a null pointer otherwise. |
|
Constant the specifies the type of degree for directed
graphs. Possible values: |
|
Boolean, whether to consider loop edges when calculating the degree (and the centralization). |
|
Pointer to a real number, the centralization score is placed here. |
|
Pointer to real number or a null pointer. If not a null pointer, then the theoretical maximum graph centrality score for a graph with the same number vertices is stored here. |
|
Boolean, whether to calculate a normalized
centralization score. See |
Returns:
Error code. |
See also:
Time complexity: the complexity of igraph_degree() plus O(n),
the number of vertices queried, for calculating the centralization
score.
int igraph_centralization_betweenness(const igraph_t *graph,
igraph_vector_t *res,
igraph_bool_t directed,
igraph_real_t *centralization,
igraph_real_t *theoretical_max,
igraph_bool_t normalized);
This function calculates the betweenness centrality of the vertices
by passing its arguments to igraph_betweenness(); and it
calculates the graph level centralization index based on the
results by calling igraph_centralization().
Arguments:
|
The input graph. |
|
A vector if you need the node-level betweenness scores, or a null pointer otherwise. |
|
Boolean, whether to consider directed paths when calculating betweenness. |
|
Pointer to a real number, the centralization score is placed here. |
|
Pointer to real number or a null pointer. If not a null pointer, then the theoretical maximum graph centrality score for a graph with the same number vertices is stored here. |
|
Boolean, whether to calculate a normalized
centralization score. See |
Returns:
Error code. |
See also:
Time complexity: the complexity of igraph_betweenness() plus
O(n), the number of vertices queried, for calculating the
centralization score.
int igraph_centralization_closeness(const igraph_t *graph,
igraph_vector_t *res,
igraph_neimode_t mode,
igraph_real_t *centralization,
igraph_real_t *theoretical_max,
igraph_bool_t normalized);
This function calculates the closeness centrality of the vertices
by passing its arguments to igraph_closeness(); and it
calculates the graph level centralization index based on the
results by calling igraph_centralization().
Arguments:
|
The input graph. |
|
A vector if you need the node-level closeness scores, or a null pointer otherwise. |
|
Constant the specifies the type of closeness for directed
graphs. Possible values: |
|
Pointer to a real number, the centralization score is placed here. |
|
Pointer to real number or a null pointer. If not a null pointer, then the theoretical maximum graph centrality score for a graph with the same number vertices is stored here. |
|
Boolean, whether to calculate a normalized
centralization score. See |
Returns:
Error code. |
See also:
Time complexity: the complexity of igraph_closeness() plus
O(n), the number of vertices queried, for calculating the
centralization score.
int igraph_centralization_eigenvector_centrality(
const igraph_t *graph,
igraph_vector_t *vector,
igraph_real_t *value,
igraph_bool_t directed,
igraph_bool_t scale,
igraph_arpack_options_t *options,
igraph_real_t *centralization,
igraph_real_t *theoretical_max,
igraph_bool_t normalized);
This function calculates the eigenvector centrality of the vertices
by passing its arguments to igraph_eigenvector_centrality);
and it calculates the graph level centralization index based on the
results by calling igraph_centralization().
Arguments:
|
The input graph. |
|
A vector if you need the node-level eigenvector centrality scores, or a null pointer otherwise. |
|
If not a null pointer, then the leading eigenvalue is stored here. |
|
If not zero then the result will be scaled, such that the absolute value of the maximum centrality is one. |
|
Options to ARPACK. See |
|
Pointer to a real number, the centralization score is placed here. |
|
Pointer to real number or a null pointer. If not a null pointer, then the theoretical maximum graph centrality score for a graph with the same number vertices is stored here. |
|
Boolean, whether to calculate a normalized
centralization score. See |
Returns:
Error code. |
See also:
Time complexity: the complexity of igraph_eigenvector_centrality() plus O(|V|), the number of vertices
for the calculating the centralization.
int igraph_centralization_degree_tmax(const igraph_t *graph,
igraph_integer_t nodes,
igraph_neimode_t mode,
igraph_bool_t loops,
igraph_real_t *res);
This function returns the theoretical maximum graph centrality based on vertex degree.
There are two ways to call this function, the first is to supply a
graph as the graph argument, and then the number of
vertices is taken from this object, and its directedness is
considered as well. The nodes argument is ignored in
this case. The mode argument is also ignored if the
supplied graph is undirected.
The other way is to supply a null pointer as the graph
argument. In this case the nodes and mode
arguments are considered.
The most centralized structure is the star. More specifically, for undirected graphs it is the star, for directed graphs it is the in-star or the out-star.
Arguments:
|
A graph object or a null pointer, see the description above. |
|
The number of nodes. This is ignored if the
|
|
Constant, whether the calculation is based on in-degree
( |
|
Boolean scalar, whether to consider loop edges in the calculation. |
|
Pointer to a real variable, the result is stored here. |
Returns:
Error code. |
Time complexity: O(1).
See also:
int igraph_centralization_betweenness_tmax(const igraph_t *graph,
igraph_integer_t nodes,
igraph_bool_t directed,
igraph_real_t *res);
This function returns the theoretical maximum graph centrality based on vertex betweenness.
There are two ways to call this function, the first is to supply a
graph as the graph argument, and then the number of
vertices is taken from this object, and its directedness is
considered as well. The nodes argument is ignored in
this case. The directed argument is also ignored if the
supplied graph is undirected.
The other way is to supply a null pointer as the graph
argument. In this case the nodes and directed
arguments are considered.
The most centralized structure is the star.
Arguments:
|
A graph object or a null pointer, see the description above. |
|
The number of nodes. This is ignored if the
|
|
Boolean scalar, whether to use directed paths in
the betweenness calculation. This argument is ignored if
|
|
Pointer to a real variable, the result is stored here. |
Returns:
Error code. |
Time complexity: O(1).
See also:
int igraph_centralization_closeness_tmax(const igraph_t *graph,
igraph_integer_t nodes,
igraph_neimode_t mode,
igraph_real_t *res);
This function returns the theoretical maximum graph centrality based on vertex closeness.
There are two ways to call this function, the first is to supply a
graph as the graph argument, and then the number of
vertices is taken from this object, and its directedness is
considered as well. The nodes argument is ignored in
this case. The mode argument is also ignored if the
supplied graph is undirected.
The other way is to supply a null pointer as the graph
argument. In this case the nodes and mode
arguments are considered.
The most centralized structure is the star.
Arguments:
|
A graph object or a null pointer, see the description above. |
|
The number of nodes. This is ignored if the
|
|
Constant, specifies what kinf of distances to consider
to calculate closeness. See the |
|
Pointer to a real variable, the result is stored here. |
Returns:
Error code. |
Time complexity: O(1).
See also:
int igraph_centralization_eigenvector_centrality_tmax(
const igraph_t *graph,
igraph_integer_t nodes,
igraph_bool_t directed,
igraph_bool_t scale,
igraph_real_t *res);
This function returns the theoretical maximum graph centrality based on vertex eigenvector centrality.
There are two ways to call this function, the first is to supply a
graph as the graph argument, and then the number of
vertices is taken from this object, and its directedness is
considered as well. The nodes argument is ignored in
this case. The directed argument is also ignored if the
supplied graph is undirected.
The other way is to supply a null pointer as the graph
argument. In this case the nodes and directed
arguments are considered.
The most centralized directed structure is the in-star. The most centralized undirected structure is the graph with a single edge.
Arguments:
|
A graph object or a null pointer, see the description above. |
|
The number of nodes. This is ignored if the
|
|
Boolean scalar, whether to consider edge
directions. This argument is ignored if
|
|
Whether to rescale the node-level centrality scores to have a maximum of one. |
|
Pointer to a real variable, the result is stored here. |
Returns:
Error code. |
Time complexity: O(1).
See also:
igraph_bibcoupling — Bibliographic coupling.igraph_cocitation — Cocitation coupling.igraph_similarity_jaccard — Jaccard similarity coefficient for the given vertices.igraph_similarity_jaccard_pairs — Jaccard similarity coefficient for given vertex pairs.igraph_similarity_jaccard_es — Jaccard similarity coefficient for a given edge selector.igraph_similarity_dice — Dice similarity coefficient.igraph_similarity_dice_pairs — Dice similarity coefficient for given vertex pairs.igraph_similarity_dice_es — Dice similarity coefficient for a given edge selector.igraph_similarity_inverse_log_weighted — Vertex similarity based on the inverse logarithm of vertex degrees.
int igraph_bibcoupling(const igraph_t *graph, igraph_matrix_t *res,
const igraph_vs_t vids);
The bibliographic coupling of two vertices is the number
of other vertices they both cite, igraph_bibcoupling() calculates
this.
The bibliographic coupling score for each given vertex and all
other vertices in the graph will be calculated.
Arguments:
|
The graph object to analyze. |
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows is the same as the
number of vertex ids in |
|
The vertex ids of the vertices for which the calculation will be done. |
Returns:
Error code:
|
Time complexity: O(|V|d^2), |V| is the number of vertices in the graph, d is the (maximum) degree of the vertices in the graph.
See also:
Example 13.17. File examples/simple/igraph_cocitation.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2020 The igraph development team <igraph@igraph.org> 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, see <https://www.gnu.org/licenses/>. */ #include <igraph.h> #include <stdio.h> int main() { igraph_t graph; igraph_matrix_t matrix; /* Create a small test graph. */ igraph_small(&graph, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); /* As usual with igraph functions, the data structure in which the result will be returned must be initialized in advance. */ igraph_matrix_init(&matrix, 0, 0); igraph_bibcoupling(&graph, &matrix, igraph_vss_all()); printf("Bibliographic coupling matrix:\n"); igraph_matrix_print(&matrix); igraph_cocitation(&graph, &matrix, igraph_vss_all()); printf("\nCocitation matrix:\n"); igraph_matrix_print(&matrix); /* Destroy data structures when we are done with them. */ igraph_matrix_destroy(&matrix); igraph_destroy(&graph); return 0; }
int igraph_cocitation(const igraph_t *graph, igraph_matrix_t *res,
const igraph_vs_t vids);
Two vertices are cocited if there is another vertex citing both of
them. igraph_cocitation() simply counts how many times two vertices are
cocited.
The cocitation score for each given vertex and all other vertices
in the graph will be calculated.
Arguments:
|
The graph object to analyze. |
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows is the same as the
number of vertex ids in |
|
The vertex ids of the vertices for which the calculation will be done. |
Returns:
Error code:
|
Time complexity: O(|V|d^2), |V| is the number of vertices in the graph, d is the (maximum) degree of the vertices in the graph.
See also:
Example 13.18. File examples/simple/igraph_cocitation.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2020 The igraph development team <igraph@igraph.org> 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, see <https://www.gnu.org/licenses/>. */ #include <igraph.h> #include <stdio.h> int main() { igraph_t graph; igraph_matrix_t matrix; /* Create a small test graph. */ igraph_small(&graph, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); /* As usual with igraph functions, the data structure in which the result will be returned must be initialized in advance. */ igraph_matrix_init(&matrix, 0, 0); igraph_bibcoupling(&graph, &matrix, igraph_vss_all()); printf("Bibliographic coupling matrix:\n"); igraph_matrix_print(&matrix); igraph_cocitation(&graph, &matrix, igraph_vss_all()); printf("\nCocitation matrix:\n"); igraph_matrix_print(&matrix); /* Destroy data structures when we are done with them. */ igraph_matrix_destroy(&matrix); igraph_destroy(&graph); return 0; }
int igraph_similarity_jaccard(const igraph_t *graph, igraph_matrix_t *res,
const igraph_vs_t vids, igraph_neimode_t mode, igraph_bool_t loops);
The Jaccard similarity coefficient of two vertices is the number of common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for some (or all) of the vertices.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows and columns is the same
as the number of vertex ids in |
||||||
|
The vertex ids of the vertices for which the calculation will be done. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves in the neighbor sets. |
Returns:
|
Error code:
|
Time complexity: O(|V|^2 d), |V| is the number of vertices in the vertex iterator given, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.19. File examples/simple/igraph_similarity.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* 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_matrix(igraph_matrix_t *m, FILE *f) { long int i, j; for (i = 0; i < igraph_matrix_nrow(m); i++) { for (j = 0; j < igraph_matrix_ncol(m); j++) { fprintf(f, " %.2f", MATRIX(*m, i, j)); } fprintf(f, "\n"); } fprintf(f, "==========\n"); } int check_jaccard_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_jaccard(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_jaccard_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_jaccard_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int check_dice_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_dice(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_dice_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_dice_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int main() { igraph_t g; igraph_matrix_t m; int ret; igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); igraph_matrix_init(&m, 0, 0); ret = check_jaccard_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 1; } igraph_similarity_jaccard(&g, &m, igraph_vss_seq(1, 2), IGRAPH_ALL, 0); print_matrix(&m, stdout); ret = check_jaccard_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 3; } ret = check_jaccard_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 4; } ret = check_dice_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 5; } ret = check_dice_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 6; } ret = check_dice_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 7; } igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_ALL); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_OUT); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_IN); print_matrix(&m, stdout); igraph_matrix_destroy(&m); igraph_destroy(&g); return 0; }
int igraph_similarity_jaccard_pairs(const igraph_t *graph, igraph_vector_t *res,
const igraph_vector_t *pairs, igraph_neimode_t mode, igraph_bool_t loops);
The Jaccard similarity coefficient of two vertices is the number of common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for a list of vertex pairs.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a vector, the result of the calculation will
be stored here. The number of elements is the same as the number
of pairs in |
||||||
|
A vector that contains the pairs for which the similarity will be calculated. Each pair is defined by two consecutive elements, i.e. the first and second element of the vector specifies the first pair, the third and fourth element specifies the second pair and so on. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves in the neighbor sets. |
Returns:
|
Error code:
|
Time complexity: O(nd), n is the number of pairs in the given vector, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.20. File examples/simple/igraph_similarity.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* 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_matrix(igraph_matrix_t *m, FILE *f) { long int i, j; for (i = 0; i < igraph_matrix_nrow(m); i++) { for (j = 0; j < igraph_matrix_ncol(m); j++) { fprintf(f, " %.2f", MATRIX(*m, i, j)); } fprintf(f, "\n"); } fprintf(f, "==========\n"); } int check_jaccard_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_jaccard(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_jaccard_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_jaccard_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int check_dice_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_dice(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_dice_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_dice_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int main() { igraph_t g; igraph_matrix_t m; int ret; igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); igraph_matrix_init(&m, 0, 0); ret = check_jaccard_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 1; } igraph_similarity_jaccard(&g, &m, igraph_vss_seq(1, 2), IGRAPH_ALL, 0); print_matrix(&m, stdout); ret = check_jaccard_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 3; } ret = check_jaccard_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 4; } ret = check_dice_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 5; } ret = check_dice_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 6; } ret = check_dice_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 7; } igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_ALL); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_OUT); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_IN); print_matrix(&m, stdout); igraph_matrix_destroy(&m); igraph_destroy(&g); return 0; }
int igraph_similarity_jaccard_es(const igraph_t *graph, igraph_vector_t *res,
const igraph_es_t es, igraph_neimode_t mode, igraph_bool_t loops);
The Jaccard similarity coefficient of two vertices is the number of common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for the endpoints of edges in a given edge selector.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a vector, the result of the calculation will
be stored here. The number of elements is the same as the number
of edges in |
||||||
|
An edge selector that specifies the edges to be included in the result. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves in the neighbor sets. |
Returns:
|
Error code:
|
Time complexity: O(nd), n is the number of edges in the edge selector, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.21. File examples/simple/igraph_similarity.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* 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_matrix(igraph_matrix_t *m, FILE *f) { long int i, j; for (i = 0; i < igraph_matrix_nrow(m); i++) { for (j = 0; j < igraph_matrix_ncol(m); j++) { fprintf(f, " %.2f", MATRIX(*m, i, j)); } fprintf(f, "\n"); } fprintf(f, "==========\n"); } int check_jaccard_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_jaccard(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_jaccard_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_jaccard_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int check_dice_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_dice(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_dice_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_dice_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int main() { igraph_t g; igraph_matrix_t m; int ret; igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); igraph_matrix_init(&m, 0, 0); ret = check_jaccard_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 1; } igraph_similarity_jaccard(&g, &m, igraph_vss_seq(1, 2), IGRAPH_ALL, 0); print_matrix(&m, stdout); ret = check_jaccard_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 3; } ret = check_jaccard_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 4; } ret = check_dice_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 5; } ret = check_dice_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 6; } ret = check_dice_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 7; } igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_ALL); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_OUT); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_IN); print_matrix(&m, stdout); igraph_matrix_destroy(&m); igraph_destroy(&g); return 0; }
int igraph_similarity_dice(const igraph_t *graph, igraph_matrix_t *res,
const igraph_vs_t vids, igraph_neimode_t mode, igraph_bool_t loops);
The Dice similarity coefficient of two vertices is twice the number of common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for some (or all) of the vertices.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows and columns is the same
as the number of vertex ids in |
||||||
|
The vertex ids of the vertices for which the calculation will be done. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves as their own neighbors. |
Returns:
|
Error code:
|
Time complexity: O(|V|^2 d), |V| is the number of vertices in the vertex iterator given, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.22. File examples/simple/igraph_similarity.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* 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_matrix(igraph_matrix_t *m, FILE *f) { long int i, j; for (i = 0; i < igraph_matrix_nrow(m); i++) { for (j = 0; j < igraph_matrix_ncol(m); j++) { fprintf(f, " %.2f", MATRIX(*m, i, j)); } fprintf(f, "\n"); } fprintf(f, "==========\n"); } int check_jaccard_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_jaccard(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_jaccard_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_jaccard_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int check_dice_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_dice(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_dice_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_dice_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int main() { igraph_t g; igraph_matrix_t m; int ret; igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); igraph_matrix_init(&m, 0, 0); ret = check_jaccard_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 1; } igraph_similarity_jaccard(&g, &m, igraph_vss_seq(1, 2), IGRAPH_ALL, 0); print_matrix(&m, stdout); ret = check_jaccard_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 3; } ret = check_jaccard_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 4; } ret = check_dice_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 5; } ret = check_dice_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 6; } ret = check_dice_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 7; } igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_ALL); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_OUT); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_IN); print_matrix(&m, stdout); igraph_matrix_destroy(&m); igraph_destroy(&g); return 0; }
int igraph_similarity_dice_pairs(const igraph_t *graph, igraph_vector_t *res,
const igraph_vector_t *pairs, igraph_neimode_t mode, igraph_bool_t loops);
The Dice similarity coefficient of two vertices is twice the number of common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for a list of vertex pairs.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a vector, the result of the calculation will
be stored here. The number of elements is the same as the number
of pairs in |
||||||
|
A vector that contains the pairs for which the similarity will be calculated. Each pair is defined by two consecutive elements, i.e. the first and second element of the vector specifies the first pair, the third and fourth element specifies the second pair and so on. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves as their own neighbors. |
Returns:
|
Error code:
|
Time complexity: O(nd), n is the number of pairs in the given vector, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.23. File examples/simple/igraph_similarity.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* 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_matrix(igraph_matrix_t *m, FILE *f) { long int i, j; for (i = 0; i < igraph_matrix_nrow(m); i++) { for (j = 0; j < igraph_matrix_ncol(m); j++) { fprintf(f, " %.2f", MATRIX(*m, i, j)); } fprintf(f, "\n"); } fprintf(f, "==========\n"); } int check_jaccard_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_jaccard(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_jaccard_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_jaccard_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int check_dice_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_dice(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_dice_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_dice_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int main() { igraph_t g; igraph_matrix_t m; int ret; igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); igraph_matrix_init(&m, 0, 0); ret = check_jaccard_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 1; } igraph_similarity_jaccard(&g, &m, igraph_vss_seq(1, 2), IGRAPH_ALL, 0); print_matrix(&m, stdout); ret = check_jaccard_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 3; } ret = check_jaccard_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 4; } ret = check_dice_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 5; } ret = check_dice_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 6; } ret = check_dice_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 7; } igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_ALL); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_OUT); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_IN); print_matrix(&m, stdout); igraph_matrix_destroy(&m); igraph_destroy(&g); return 0; }
int igraph_similarity_dice_es(const igraph_t *graph, igraph_vector_t *res,
const igraph_es_t es, igraph_neimode_t mode, igraph_bool_t loops);
The Dice similarity coefficient of two vertices is twice the number of common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for the endpoints of edges in a given edge selector.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a vector, the result of the calculation will
be stored here. The number of elements is the same as the number
of edges in |
||||||
|
An edge selector that specifies the edges to be included in the result. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves as their own neighbors. |
Returns:
|
Error code:
|
Time complexity: O(nd), n is the number of pairs in the given vector, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.24. File examples/simple/igraph_similarity.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* 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_matrix(igraph_matrix_t *m, FILE *f) { long int i, j; for (i = 0; i < igraph_matrix_nrow(m); i++) { for (j = 0; j < igraph_matrix_ncol(m); j++) { fprintf(f, " %.2f", MATRIX(*m, i, j)); } fprintf(f, "\n"); } fprintf(f, "==========\n"); } int check_jaccard_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_jaccard(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_jaccard_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_jaccard_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int check_dice_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_dice(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_dice_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_dice_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int main() { igraph_t g; igraph_matrix_t m; int ret; igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); igraph_matrix_init(&m, 0, 0); ret = check_jaccard_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 1; } igraph_similarity_jaccard(&g, &m, igraph_vss_seq(1, 2), IGRAPH_ALL, 0); print_matrix(&m, stdout); ret = check_jaccard_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 3; } ret = check_jaccard_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 4; } ret = check_dice_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 5; } ret = check_dice_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 6; } ret = check_dice_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 7; } igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_ALL); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_OUT); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_IN); print_matrix(&m, stdout); igraph_matrix_destroy(&m); igraph_destroy(&g); return 0; }
int igraph_similarity_inverse_log_weighted(const igraph_t *graph,
igraph_matrix_t *res, const igraph_vs_t vids, igraph_neimode_t mode);
The inverse log-weighted similarity of two vertices is the number of their common neighbors, weighted by the inverse logarithm of their degrees. It is based on the assumption that two vertices should be considered more similar if they share a low-degree common neighbor, since high-degree common neighbors are more likely to appear even by pure chance.
Isolated vertices will have zero similarity to any other vertex. Self-similarities are not calculated.
See the following paper for more details: Lada A. Adamic and Eytan Adar: Friends and neighbors on the Web. Social Networks, 25(3):211-230, 2003.
Arguments:
|
The graph object to analyze. |
||||||
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows is the same as the
number of vertex ids in |
||||||
|
The vertex ids of the vertices for which the calculation will be done. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
Returns:
Error code:
|
Time complexity: O(|V|d^2), |V| is the number of vertices in the graph, d is the (maximum) degree of the vertices in the graph.
Example 13.25. File examples/simple/igraph_similarity.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* 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_matrix(igraph_matrix_t *m, FILE *f) { long int i, j; for (i = 0; i < igraph_matrix_nrow(m); i++) { for (j = 0; j < igraph_matrix_ncol(m); j++) { fprintf(f, " %.2f", MATRIX(*m, i, j)); } fprintf(f, "\n"); } fprintf(f, "==========\n"); } int check_jaccard_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_jaccard(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_jaccard_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_jaccard_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Jaccard similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int check_dice_all(const igraph_t* g, igraph_matrix_t* m, igraph_neimode_t mode, igraph_bool_t loops) { igraph_vector_t pairs, res; long int i, j, k, n; igraph_eit_t eit; igraph_vector_init(&res, 0); /* First, query the similarities for all the vertices to a matrix */ igraph_similarity_dice(g, m, igraph_vss_all(), mode, loops); /* Second, query the similarities for all pairs using a pair vector */ n = igraph_vcount(g); igraph_vector_init(&pairs, 0); for (i = 0; i < n; i++) { for (j = n - 1; j >= 0; j--) { igraph_vector_push_back(&pairs, i); igraph_vector_push_back(&pairs, j); } } igraph_similarity_dice_pairs(g, &res, &pairs, mode, loops); for (i = 0, k = 0; i < n; i++) { for (j = n - 1; j >= 0; j--, k++) { if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for vertex pair %ld-%ld " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } } } igraph_vector_destroy(&pairs); /* Third, query the similarities for all edges */ igraph_similarity_dice_es(g, &res, igraph_ess_all(IGRAPH_EDGEORDER_FROM), mode, loops); igraph_eit_create(g, igraph_ess_all(IGRAPH_EDGEORDER_FROM), &eit); k = 0; while (!IGRAPH_EIT_END(eit)) { long int eid = IGRAPH_EIT_GET(eit); i = IGRAPH_FROM(g, eid); j = IGRAPH_TO(g, eid); if (fabs(VECTOR(res)[k] - MATRIX(*m, i, j)) > 1e-6) { fprintf(stderr, "Dice similarity calculation for edge %ld-%ld (ID=%ld) " "does not match the value in the full matrix (%.6f vs %.6f)\n", i, j, eid, VECTOR(res)[k], MATRIX(*m, i, j)); return 1; } IGRAPH_EIT_NEXT(eit); k++; } igraph_eit_destroy(&eit); igraph_vector_destroy(&res); return 0; } int main() { igraph_t g; igraph_matrix_t m; int ret; igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1); igraph_matrix_init(&m, 0, 0); ret = check_jaccard_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 1; } igraph_similarity_jaccard(&g, &m, igraph_vss_seq(1, 2), IGRAPH_ALL, 0); print_matrix(&m, stdout); ret = check_jaccard_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 3; } ret = check_jaccard_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 4; } ret = check_dice_all(&g, &m, IGRAPH_ALL, 1); print_matrix(&m, stdout); if (ret) { return 5; } ret = check_dice_all(&g, &m, IGRAPH_OUT, 1); print_matrix(&m, stdout); if (ret) { return 6; } ret = check_dice_all(&g, &m, IGRAPH_IN, 0); print_matrix(&m, stdout); if (ret) { return 7; } igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_ALL); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_OUT); print_matrix(&m, stdout); igraph_similarity_inverse_log_weighted(&g, &m, igraph_vss_all(), IGRAPH_IN); print_matrix(&m, stdout); igraph_matrix_destroy(&m); igraph_destroy(&g); return 0; }
igraph_minimum_spanning_tree — Calculates one minimum spanning tree of a graph.igraph_minimum_spanning_tree_unweighted — Calculates one minimum spanning tree of an unweighted graph.igraph_minimum_spanning_tree_prim — Calculates one minimum spanning tree of a weighted graph.igraph_random_spanning_tree — Uniformly sample the spanning trees of a graphigraph_is_tree — Decides whether the graph is a tree.igraph_to_prufer — Converts a tree to its Prüfer sequence
int igraph_minimum_spanning_tree(const igraph_t* graph,
igraph_vector_t* res, const igraph_vector_t* weights);
If the graph has more minimum spanning trees (this is always the case, except if it is a forest) this implementation returns only the same one.
Directed graphs are considered as undirected for this computation.
If the graph is not connected then its minimum spanning forest is returned. This is the set of the minimum spanning trees of each component.
Arguments:
|
The graph object. |
|
An initialized vector, the IDs of the edges that constitute
a spanning tree will be returned here. Use
|
|
A vector containing the weights of the edges in the same order as the simple edge iterator visits them (i.e. in increasing order of edge IDs). |
Returns:
Error code:
|
Time complexity: O(|V|+|E|) for the unweighted case, O(|E| log |V|) for the weighted case. |V| is the number of vertices, |E| the number of edges in the graph.
See also:
|
Example 13.26. File examples/simple/igraph_minimum_spanning_tree.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> int main() { igraph_t g, tree; igraph_vector_t eb, edges; long int i; igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 10, 0, 11, 0, 12, 0, 13, 0, 17, 0, 19, 0, 21, 0, 31, 1, 2, 1, 3, 1, 7, 1, 13, 1, 17, 1, 19, 1, 21, 1, 30, 2, 3, 2, 7, 2, 8, 2, 9, 2, 13, 2, 27, 2, 28, 2, 32, 3, 7, 3, 12, 3, 13, 4, 6, 4, 10, 5, 6, 5, 10, 5, 16, 6, 16, 8, 30, 8, 32, 8, 33, 9, 33, 13, 33, 14, 32, 14, 33, 15, 32, 15, 33, 18, 32, 18, 33, 19, 33, 20, 32, 20, 33, 22, 32, 22, 33, 23, 25, 23, 27, 23, 29, 23, 32, 23, 33, 24, 25, 24, 27, 24, 31, 25, 31, 26, 29, 26, 33, 27, 33, 28, 31, 28, 33, 29, 32, 29, 33, 30, 32, 30, 33, 31, 32, 31, 33, 32, 33, -1); igraph_vector_init(&eb, igraph_ecount(&g)); igraph_edge_betweenness(&g, &eb, IGRAPH_UNDIRECTED, /*weights=*/ 0); for (i = 0; i < igraph_vector_size(&eb); i++) { VECTOR(eb)[i] = -VECTOR(eb)[i]; } igraph_minimum_spanning_tree_prim(&g, &tree, &eb); igraph_write_graph_edgelist(&tree, stdout); igraph_vector_init(&edges, 0); igraph_minimum_spanning_tree(&g, &edges, &eb); igraph_vector_print(&edges); igraph_vector_destroy(&edges); igraph_destroy(&tree); igraph_destroy(&g); igraph_vector_destroy(&eb); return 0; }
int igraph_minimum_spanning_tree_unweighted(const igraph_t *graph,
igraph_t *mst);
If the graph has more minimum spanning trees (this is always the case, except if it is a forest) this implementation returns only the same one.
Directed graphs are considered as undirected for this computation.
If the graph is not connected then its minimum spanning forest is returned. This is the set of the minimum spanning trees of each component.
Arguments:
|
The graph object. |
|
The minimum spanning tree, another graph object. Do
not initialize this object before passing it to
this function, but be sure to call |
Returns:
Error code:
|
Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| the number of edges in the graph.
See also:
|
int igraph_minimum_spanning_tree_prim(const igraph_t *graph, igraph_t *mst,
const igraph_vector_t *weights);
This function uses Prim's method for carrying out the computation, see Prim, R.C.: Shortest connection networks and some generalizations, Bell System Technical Journal, Vol. 36, 1957, 1389--1401.
If the graph has more than one minimum spanning tree, the current implementation returns always the same one.
Directed graphs are considered as undirected for this computation.
If the graph is not connected then its minimum spanning forest is returned. This is the set of the minimum spanning trees of each component.
Arguments:
|
The graph object. |
|
The result of the computation, a graph object containing
the minimum spanning tree of the graph.
Do not initialize this object before passing it to
this function, but be sure to call |
|
A vector containing the weights of the edges in the same order as the simple edge iterator visits them (i.e. in increasing order of edge IDs). |
Returns:
Error code:
|
Time complexity: O(|E| log |V|), |V| is the number of vertices, |E| the number of edges in the graph.
See also:
|
Example 13.27. File examples/simple/igraph_minimum_spanning_tree.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> int main() { igraph_t g, tree; igraph_vector_t eb, edges; long int i; igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 10, 0, 11, 0, 12, 0, 13, 0, 17, 0, 19, 0, 21, 0, 31, 1, 2, 1, 3, 1, 7, 1, 13, 1, 17, 1, 19, 1, 21, 1, 30, 2, 3, 2, 7, 2, 8, 2, 9, 2, 13, 2, 27, 2, 28, 2, 32, 3, 7, 3, 12, 3, 13, 4, 6, 4, 10, 5, 6, 5, 10, 5, 16, 6, 16, 8, 30, 8, 32, 8, 33, 9, 33, 13, 33, 14, 32, 14, 33, 15, 32, 15, 33, 18, 32, 18, 33, 19, 33, 20, 32, 20, 33, 22, 32, 22, 33, 23, 25, 23, 27, 23, 29, 23, 32, 23, 33, 24, 25, 24, 27, 24, 31, 25, 31, 26, 29, 26, 33, 27, 33, 28, 31, 28, 33, 29, 32, 29, 33, 30, 32, 30, 33, 31, 32, 31, 33, 32, 33, -1); igraph_vector_init(&eb, igraph_ecount(&g)); igraph_edge_betweenness(&g, &eb, IGRAPH_UNDIRECTED, /*weights=*/ 0); for (i = 0; i < igraph_vector_size(&eb); i++) { VECTOR(eb)[i] = -VECTOR(eb)[i]; } igraph_minimum_spanning_tree_prim(&g, &tree, &eb); igraph_write_graph_edgelist(&tree, stdout); igraph_vector_init(&edges, 0); igraph_minimum_spanning_tree(&g, &edges, &eb); igraph_vector_print(&edges); igraph_vector_destroy(&edges); igraph_destroy(&tree); igraph_destroy(&g); igraph_vector_destroy(&eb); return 0; }
int igraph_random_spanning_tree(const igraph_t *graph, igraph_vector_t *res, igraph_integer_t vid);
Performs a loop-erased random walk on the graph to uniformly sample its spanning trees. Edge directions are ignored.
Multi-graphs are supported, and edge multiplicities will affect the sampling
frequency. For example, consider the 3-cycle graph 1=2-3-1, with two edges
between vertices 1 and 2. Due to these parallel edges, the trees 1-2-3
and 3-1-2 will be sampled with multiplicity 2, while the tree
2-3-1 will be sampled with multiplicity 1.
Arguments:
|
The input graph. Edge directions are ignored. |
|
An initialized vector, the IDs of the edges that constitute
a spanning tree will be returned here. Use
|
|
This parameter is relevant if the graph is not connected. If negative, a random spanning forest of all components will be generated. Otherwise, it should be the ID of a vertex. A random spanning tree of the component containing the vertex will be generated. |
Returns:
Error code. |
See also:
int igraph_is_tree(const igraph_t *graph, igraph_bool_t *res, igraph_integer_t *root, igraph_neimode_t mode);
An undirected graph is a tree if it is connected and has no cycles.
In the directed case, a possible additional requirement is that all
edges are oriented away from a root (out-tree or arborescence) or all edges
are oriented towards a root (in-tree or anti-arborescence).
This test can be controlled using the mode parameter.
By convention, the null graph (i.e. the graph with no vertices) is considered not to be a tree.
Arguments:
|
The graph object to analyze. |
|
Pointer to a logical variable, the result will be stored here. |
|
If not |
|
For a directed graph this specifies whether to test for an
out-tree, an in-tree or ignore edge directions. The respective
possible values are:
|
Returns:
Error code:
|
Time complexity: At most O(|V|+|E|), the number of vertices plus the number of edges in the graph.
See also:
igraph_is_weakly_connected() |
Example 13.28. File examples/simple/igraph_tree.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> int main() { igraph_t graph; igraph_bool_t res; /* Create a directed binary tree on 15 nodes, with edges pointing towards the root. */ igraph_tree(&graph, 15, 2, IGRAPH_TREE_IN); igraph_is_tree(&graph, &res, NULL, IGRAPH_IN); printf("Is it an in-tree? %s\n", res ? "Yes" : "No"); igraph_is_tree(&graph, &res, NULL, IGRAPH_OUT); printf("Is it an out-tree? %s\n", res ? "Yes" : "No"); igraph_destroy(&graph); return 0; }
int igraph_to_prufer(const igraph_t *graph, igraph_vector_int_t* prufer);
A Prüfer sequence is a unique sequence of integers associated with a labelled tree. A tree on n >= 2 vertices can be represented by a sequence of n-2 integers, each between 0 and n-1 (inclusive).
Arguments:
|
Pointer to an initialized graph object which must be a tree on n >= 2 vertices. |
|
A pointer to the integer vector that should hold the Prüfer sequence; the vector must be initialized and will be resized to n - 2. |
Returns:
|
Error code:
|
See also:
igraph_transitivity_undirected — Calculates the transitivity (clustering coefficient) of a graph.igraph_transitivity_local_undirected — Calculates the local transitivity (clustering coefficient) of a graph.igraph_transitivity_avglocal_undirected — Average local transitivity (clustering coefficient).igraph_transitivity_barrat — Weighted transitivity, as defined by A. Barrat.
int igraph_transitivity_undirected(const igraph_t *graph,
igraph_real_t *res,
igraph_transitivity_mode_t mode);
The transitivity measures the probability that two neighbors of a vertex are connected. More precisely, this is the ratio of the triangles and connected triples in the graph, the result is a single real number. Directed graphs are considered as undirected ones and multi-edges are ignored.
Note that this measure is different from the local transitivity measure
(see igraph_transitivity_local_undirected() ) as it calculates a single
value for the whole graph.
Clustering coefficient is an alternative name for transitivity.
References:
S. Wasserman and K. Faust: Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
Arguments:
|
The graph object. Edge directions and multiplicites are ignored. |
|
Pointer to a real variable, the result will be stored here. |
|
Defines how to treat graphs with no connected triples.
|
Returns:
Error code:
|
See also:
Time complexity: O(|V|*d^2), |V| is the number of vertices in the graph, d is the average node degree.
Example 13.29. File examples/simple/igraph_transitivity.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> int main() { igraph_t g; igraph_real_t res; /* Trivial cases */ igraph_ring(&g, 100, IGRAPH_UNDIRECTED, 0, 0); igraph_transitivity_undirected(&g, &res, IGRAPH_TRANSITIVITY_NAN); igraph_destroy(&g); if (res != 0) { return 1; } igraph_full(&g, 20, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS); igraph_transitivity_undirected(&g, &res, IGRAPH_TRANSITIVITY_NAN); igraph_destroy(&g); if (res != 1) { return 2; } /* Degenerate cases */ igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 1, 2, 3, 4, 5, -1); igraph_transitivity_undirected(&g, &res, IGRAPH_TRANSITIVITY_NAN); /* res should be NaN here, any comparison must return false */ if (res == 0 || res > 0 || res < 0) { return 4; } igraph_transitivity_undirected(&g, &res, IGRAPH_TRANSITIVITY_ZERO); /* res should be zero here */ if (res) { return 5; } igraph_destroy(&g); /* Zachary Karate club */ igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 10, 0, 11, 0, 12, 0, 13, 0, 17, 0, 19, 0, 21, 0, 31, 1, 2, 1, 3, 1, 7, 1, 13, 1, 17, 1, 19, 1, 21, 1, 30, 2, 3, 2, 7, 2, 8, 2, 9, 2, 13, 2, 27, 2, 28, 2, 32, 3, 7, 3, 12, 3, 13, 4, 6, 4, 10, 5, 6, 5, 10, 5, 16, 6, 16, 8, 30, 8, 32, 8, 33, 9, 33, 13, 33, 14, 32, 14, 33, 15, 32, 15, 33, 18, 32, 18, 33, 19, 33, 20, 32, 20, 33, 22, 32, 22, 33, 23, 25, 23, 27, 23, 29, 23, 32, 23, 33, 24, 25, 24, 27, 24, 31, 25, 31, 26, 29, 26, 33, 27, 33, 28, 31, 28, 33, 29, 32, 29, 33, 30, 32, 30, 33, 31, 32, 31, 33, 32, 33, -1); igraph_transitivity_undirected(&g, &res, IGRAPH_TRANSITIVITY_NAN); igraph_destroy(&g); if (res != 0.2556818181818181767717) { fprintf(stderr, "%f != %f\n", res, 0.2556818181818181767717); return 3; } return 0; }
int igraph_transitivity_local_undirected(const igraph_t *graph,
igraph_vector_t *res,
const igraph_vs_t vids,
igraph_transitivity_mode_t mode);
The transitivity measures the probability that two neighbors of a vertex are connected. In case of the local transitivity, this probability is calculated separately for each vertex.
Note that this measure is different from the global transitivity measure
(see igraph_transitivity_undirected() ) as it calculates a transitivity
value for each vertex individually.
Clustering coefficient is an alternative name for transitivity.
References:
D. J. Watts and S. Strogatz: Collective dynamics of small-world networks. Nature 393(6684):440-442 (1998).
Arguments:
|
The input graph. Edge directions and multiplicities are ignored. |
|
Pointer to an initialized vector, the result will be stored here. It will be resized as needed. |
|
Vertex set, the vertices for which the local transitivity will be calculated. |
|
Defines how to treat vertices with degree less than two.
|
Returns:
Error code. |
See also:
Time complexity: O(n*d^2), n is the number of vertices for which the transitivity is calculated, d is the average vertex degree.
int igraph_transitivity_avglocal_undirected(const igraph_t *graph,
igraph_real_t *res,
igraph_transitivity_mode_t mode);
The transitivity measures the probability that two neighbors of a
vertex are connected. In case of the average local transitivity,
this probability is calculated for each vertex and then the average
is taken. Vertices with less than two neighbors require special treatment,
they will either be left out from the calculation or they will be considered
as having zero transitivity, depending on the mode argument.
Edge directions and edge multiplicities are ignored.
Note that this measure is different from the global transitivity measure
(see igraph_transitivity_undirected() ) as it simply takes the
average local transitivity across the whole network.
Clustering coefficient is an alternative name for transitivity.
References:
D. J. Watts and S. Strogatz: Collective dynamics of small-world networks. Nature 393(6684):440-442 (1998).
Arguments:
|
The input graph. Edge directions and multiplicites are ignored. |
|
Pointer to a real variable, the result will be stored here. |
|
Defines how to treat vertices with degree less than two.
|
Returns:
Error code. |
See also:
Time complexity: O(|V|*d^2), |V| is the number of vertices in the graph and d is the average degree.
int igraph_transitivity_barrat(const igraph_t *graph,
igraph_vector_t *res,
const igraph_vs_t vids,
const igraph_vector_t *weights,
igraph_transitivity_mode_t mode);
This is a local transitivity, i.e. a vertex-level index. For a
given vertex i, from all triangles in which it participates we
consider the weight of the edges incident on i. The transitivity
is the sum of these weights divided by twice the strength of the
vertex (see igraph_strength()) and the degree of the vertex
minus one. See Alain Barrat, Marc Barthelemy, Romualdo
Pastor-Satorras, Alessandro Vespignani: The architecture of complex
weighted networks, Proc. Natl. Acad. Sci. USA 101, 3747 (2004) at
http://arxiv.org/abs/cond-mat/0311416 for the exact formula.
Arguments:
|
The input graph. Edge directions are ignored for directed graphs. Note that the function does not work for non-simple graphs. |
|
Pointer to an initialized vector, the result will be stored here. It will be resized as needed. |
|
The vertices for which the calculation is performed. |
|
Edge weights. If this is a null pointer, then a
warning is given and |
|
Defines how to treat vertices with zero strength.
|
Returns:
Error code. |
Time complexity: O(|V|*d^2), |V| is the number of vertices in the graph, d is the average node degree.
See also:
|
int igraph_to_directed(igraph_t *graph,
igraph_to_directed_t mode);
If the supplied graph is directed, this function does nothing.
Arguments:
|
The graph object to convert. |
||||||||
|
Constant, specifies the details of how exactly the conversion is done. Possible values:
|
Returns:
Error code. |
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.
int igraph_to_undirected(igraph_t *graph,
igraph_to_undirected_t mode,
const igraph_attribute_combination_t *edge_comb);
If the supplied graph is undirected, this function does nothing.
Arguments:
|
The graph object to convert. |
|
Constant, specifies the details of how exactly the
conversion is done. Possible values: |
|
What to do with the edge attributes. See the igraph manual section about attributes for details. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.
Example 13.30. File examples/simple/igraph_to_undirected.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> int main() { igraph_vector_t v; igraph_t g; igraph_vector_init_int(&v, 2, 5, 5); igraph_lattice(&g, &v, 1, IGRAPH_DIRECTED, 1 /*mutual*/, 0 /*circular*/); igraph_to_undirected(&g, IGRAPH_TO_UNDIRECTED_COLLAPSE, /*edge_comb=*/ 0); igraph_write_graph_edgelist(&g, stdout); igraph_destroy(&g); igraph_vector_destroy(&v); printf("---\n"); igraph_small(&g, 10, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 3, 5, 6, 6, 5, 6, 7, 6, 7, 7, 6, 7, 8, 7, 8, 8, 7, 8, 7, 8, 8, 9, 9, 9, 9, -1); igraph_to_undirected(&g, IGRAPH_TO_UNDIRECTED_MUTUAL, /*edge_comb=*/ 0); igraph_write_graph_edgelist(&g, stdout); igraph_destroy(&g); return 0; }
int igraph_laplacian(const igraph_t *graph, igraph_matrix_t *res,
igraph_sparsemat_t *sparseres,
igraph_bool_t normalized,
const igraph_vector_t *weights);
The graph Laplacian matrix is similar to an adjacency matrix but contains -1's instead of 1's and the vertex degrees are included in the diagonal. So the result for edge i--j is -1 if i!=j and is equal to the degree of vertex i if i==j. igraph_laplacian will work on a directed graph; in this case, the diagonal will contain the out-degrees. Loop edges will be ignored.
The normalized version of the Laplacian matrix has 1 in the diagonal and -1/sqrt(d[i]d[j]) if there is an edge from i to j.
The first version of this function was written by Vincent Matossian.
Arguments:
|
Pointer to the graph to convert. |
|
Pointer to an initialized matrix object, the result is
stored here. It will be resized if needed.
If it is a null pointer, then it is ignored.
At least one of |
|
Pointer to an initialized sparse matrix object, the
result is stored here, if it is not a null pointer.
At least one of |
|
Whether to create a normalized Laplacian matrix. |
|
An optional vector containing edge weights, to calculate the weighted Laplacian matrix. Set it to a null pointer to calculate the unweighted Laplacian. |
Returns:
Error code. |
Time complexity: O(|V||V|), |V| is the number of vertices in the graph.
Example 13.31. File examples/simple/igraph_laplacian.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> igraph_bool_t check_laplacian(igraph_t* graph, const igraph_matrix_t* matrix, const igraph_vector_t* w) { igraph_vector_t vec, res; long int i, j; igraph_vector_init(&vec, 0); igraph_vector_init(&res, igraph_vcount(graph)); if (w) { igraph_strength(graph, &vec, igraph_vss_all(), IGRAPH_OUT, IGRAPH_NO_LOOPS, w); } else { igraph_degree(graph, &vec, igraph_vss_all(), IGRAPH_OUT, IGRAPH_NO_LOOPS); } for (i = 0; i < igraph_vcount(graph); i++) { VECTOR(vec)[i] = sqrt(VECTOR(vec)[i]); } for (i = 0; i < igraph_vcount(graph); i++) { for (j = 0; j < igraph_vcount(graph); j++) { VECTOR(res)[i] += MATRIX(*matrix, i, j) * VECTOR(vec)[j]; } } if (igraph_vector_min(&res) > 1e-7) { printf("Invalid Laplacian matrix:\n"); igraph_matrix_print(matrix); return 0; } igraph_vector_destroy(&vec); igraph_vector_destroy(&res); return 1; } int test_unnormalized_laplacian(const igraph_vector_t* w, igraph_bool_t dir) { igraph_t g; igraph_matrix_t m, m2; igraph_sparsemat_t sm; igraph_vector_t vec, *weights = NULL; igraph_matrix_init(&m, 1, 1); igraph_sparsemat_init(&sm, 0, 0, 0); if (w) { weights = (igraph_vector_t*)calloc(1, sizeof(igraph_vector_t)); igraph_vector_copy(weights, w); } /* No loop or multiple edges */ igraph_ring(&g, 5, dir, 0, 1); igraph_laplacian(&g, &m, &sm, 0, weights); igraph_matrix_init(&m2, 0, 0); igraph_sparsemat_as_matrix(&m2, &sm); if (!igraph_matrix_all_e_tol(&m, &m2, 0)) { return 41; } igraph_matrix_destroy(&m2); igraph_matrix_print(&m); printf("===\n"); /* Add some loop edges */ igraph_vector_init_real(&vec, 4, 1.0, 1.0, 2.0, 2.0); igraph_add_edges(&g, &vec, 0); igraph_vector_destroy(&vec); if (weights) { igraph_vector_push_back(weights, 2); igraph_vector_push_back(weights, 2); } igraph_laplacian(&g, &m, &sm, 0, weights); igraph_matrix_init(&m2, 0, 0); igraph_sparsemat_as_matrix(&m2, &sm); if (!igraph_matrix_all_e_tol(&m, &m2, 0)) { return 42; } igraph_matrix_destroy(&m2); igraph_matrix_print(&m); printf("===\n"); /* Duplicate some edges */ igraph_vector_init_real(&vec, 4, 1.0, 2.0, 3.0, 4.0); igraph_add_edges(&g, &vec, 0); igraph_vector_destroy(&vec); if (weights) { igraph_vector_push_back(weights, 3); igraph_vector_push_back(weights, 3); } igraph_laplacian(&g, &m, &sm, 0, weights); igraph_matrix_init(&m2, 0, 0); igraph_sparsemat_as_matrix(&m2, &sm); if (!igraph_matrix_all_e_tol(&m, &m2, 0)) { return 43; } igraph_matrix_destroy(&m2); igraph_matrix_print(&m); igraph_destroy(&g); igraph_matrix_destroy(&m); if (weights) { igraph_vector_destroy(weights); free(weights); } igraph_sparsemat_destroy(&sm); return 0; } int test_normalized_laplacian(const igraph_vector_t *w, igraph_bool_t dir) { igraph_t g; igraph_matrix_t m, m2; igraph_sparsemat_t sm; igraph_vector_t vec, *weights = 0; igraph_bool_t ok = 1; igraph_matrix_init(&m, 1, 1); igraph_sparsemat_init(&sm, 0, 0, 0); if (w) { weights = (igraph_vector_t*) calloc(1, sizeof(igraph_vector_t)); igraph_vector_copy(weights, w); } /* Undirected graph, no loop or multiple edges */ igraph_ring(&g, 5, dir, 0, 1); igraph_laplacian(&g, &m, &sm, 1, weights); igraph_matrix_init(&m2, 0, 0); igraph_sparsemat_as_matrix(&m2, &sm); if (!igraph_matrix_all_e_tol(&m, &m2, 0)) { return 44; } igraph_matrix_destroy(&m2); ok = ok && check_laplacian(&g, &m, weights); /* Add some loop edges */ igraph_vector_init_real(&vec, 4, 1.0, 1.0, 2.0, 2.0); igraph_add_edges(&g, &vec, 0); igraph_vector_destroy(&vec); if (weights) { igraph_vector_push_back(weights, 2); igraph_vector_push_back(weights, 2); } igraph_laplacian(&g, &m, &sm, 1, weights); igraph_matrix_init(&m2, 0, 0); igraph_sparsemat_as_matrix(&m2, &sm); if (!igraph_matrix_all_e_tol(&m, &m2, 0)) { return 45; } igraph_matrix_destroy(&m2); ok = ok && check_laplacian(&g, &m, weights); /* Duplicate some edges */ igraph_vector_init_real(&vec, 4, 1.0, 2.0, 3.0, 4.0); igraph_add_edges(&g, &vec, 0); igraph_vector_destroy(&vec); if (weights) { igraph_vector_push_back(weights, 3); igraph_vector_push_back(weights, 3); } igraph_laplacian(&g, &m, &sm, 1, weights); igraph_matrix_init(&m2, 0, 0); igraph_sparsemat_as_matrix(&m2, &sm); if (!igraph_matrix_all_e_tol(&m, &m2, 0)) { return 46; } igraph_matrix_destroy(&m2); ok = ok && check_laplacian(&g, &m, weights); igraph_destroy(&g); igraph_matrix_destroy(&m); if (weights) { igraph_vector_destroy(weights); free(weights); } if (ok) { printf("OK\n"); } igraph_sparsemat_destroy(&sm); return !ok; } int main() { int res; int i; igraph_vector_t weights; igraph_vector_init_real(&weights, 5, 1.0, 2.0, 3.0, 4.0, 5.0); for (i = 0; i < 8; i++) { igraph_bool_t is_normalized = i / 4; igraph_vector_t* v = ((i & 2) / 2 ? &weights : 0); igraph_bool_t dir = (i % 2 ? IGRAPH_DIRECTED : IGRAPH_UNDIRECTED); printf("=== %sormalized, %sweighted, %sdirected\n", (is_normalized ? "N" : "Unn"), (v != 0 ? "" : "un"), (dir == IGRAPH_DIRECTED ? "" : "un") ); if (is_normalized) { res = test_normalized_laplacian(v, dir); } else { res = test_unnormalized_laplacian(v, dir); } if (res) { return i + 1; } } igraph_vector_destroy(&weights); return 0; }
igraph_is_simple — Decides whether the input graph is a simple graph.igraph_is_loop — Find the loop edges in a graph.igraph_is_multiple — Find the multiple edges in a graph.igraph_has_multiple — Check whether the graph has at least one multiple edge.igraph_count_multiple — Count the number of appearances of the edges in a graph.
int igraph_is_simple(const igraph_t *graph, igraph_bool_t *res);
A graph is a simple graph if it does not contain loop edges and multiple edges.
Arguments:
|
The input graph. |
|
Pointer to a boolean constant, the result is stored here. |
Returns:
Error code. |
See also:
|
Time complexity: O(|V|+|E|).
int igraph_is_loop(const igraph_t *graph, igraph_vector_bool_t *res,
igraph_es_t es);
A loop edge is an edge from a vertex to itself.
Arguments:
|
The input graph. |
|
Pointer to an initialized boolean vector for storing the result, it will be resized as needed. |
|
The edges to check, for all edges supply |
Returns:
Error code. |
See also:
|
Time complexity: O(e), the number of edges to check.
Example 13.32. File examples/simple/igraph_is_loop.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2007-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_bool_t *v, FILE *f) { long int i; for (i = 0; i < igraph_vector_bool_size(v); i++) { fprintf(f, " %i", (int) VECTOR(*v)[i]); } fprintf(f, "\n"); } int main() { igraph_t graph; igraph_vector_bool_t v; igraph_vector_bool_init(&v, 0); igraph_small(&graph, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 1, 0, 1, 1, 0, 3, 4, 11, 10, -1); igraph_is_loop(&graph, &v, igraph_ess_all(IGRAPH_EDGEORDER_ID)); print_vector(&v, stdout); igraph_destroy(&graph); igraph_small(&graph, 0, IGRAPH_UNDIRECTED, 0, 0, 1, 1, 2, 2, 2, 3, 2, 4, 2, 5, 2, 6, 2, 2, 0, 0, -1); igraph_is_loop(&graph, &v, igraph_ess_all(IGRAPH_EDGEORDER_ID)); print_vector(&v, stdout); igraph_destroy(&graph); igraph_vector_bool_destroy(&v); return 0; }
int igraph_is_multiple(const igraph_t *graph, igraph_vector_bool_t *res,
igraph_es_t es);
An edge is a multiple edge if there is another edge with the same head and tail vertices in the graph.
Note that this function returns true only for the second or more appearances of the multiple edges.
Arguments:
|
The input graph. |
|
Pointer to a boolean vector, the result will be stored here. It will be resized as needed. |
|
The edges to check. Supply |
Returns:
Error code. |
See also:
Time complexity: O(e*d), e is the number of edges to check and d is the average degree (out-degree in directed graphs) of the vertices at the tail of the edges.
Example 13.33. File examples/simple/igraph_is_multiple.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2007-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_bool_t *v, FILE *f) { long int i; for (i = 0; i < igraph_vector_bool_size(v); i++) { fprintf(f, " %i", (int) VECTOR(*v)[i]); } fprintf(f, "\n"); } int main() { igraph_t graph; igraph_vector_bool_t v; igraph_vector_bool_init(&v, 0); igraph_small(&graph, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 1, 0, 1, 1, 0, 3, 4, 11, 10, -1); igraph_is_multiple(&graph, &v, igraph_ess_all(IGRAPH_EDGEORDER_ID)); print_vector(&v, stdout); igraph_destroy(&graph); igraph_small(&graph, 0, IGRAPH_UNDIRECTED, 0, 0, 1, 2, 1, 1, 2, 2, 2, 1, 2, 3, 2, 4, 2, 5, 2, 6, 2, 2, 3, 2, 0, 0, 6, 2, 2, 2, 0, 0, -1); igraph_is_multiple(&graph, &v, igraph_ess_all(IGRAPH_EDGEORDER_ID)); print_vector(&v, stdout); igraph_destroy(&graph); igraph_vector_bool_destroy(&v); return 0; }
int igraph_has_multiple(const igraph_t *graph, igraph_bool_t *res);
An edge is a multiple edge if there is another edge with the same head and tail vertices in the graph.
Arguments:
|
The input graph. |
|
Pointer to a boolean variable, the result will be stored here. |
Returns:
Error code. |
See also:
Time complexity: O(e*d), e is the number of edges to check and d is the average degree (out-degree in directed graphs) of the vertices at the tail of the edges.
Example 13.34. File examples/simple/igraph_has_multiple.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2007-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_bool_t *v, FILE *f) { long int i; for (i = 0; i < igraph_vector_bool_size(v); i++) { fprintf(f, " %i", (int) VECTOR(*v)[i]); } fprintf(f, "\n"); } int main() { igraph_t graph; igraph_bool_t res; igraph_small(&graph, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 1, 0, 1, 1, 0, 3, 4, 11, 10, -1); igraph_has_multiple(&graph, &res); if (!res) { return 1; } igraph_destroy(&graph); igraph_small(&graph, 0, IGRAPH_UNDIRECTED, 0, 0, 1, 2, 1, 1, 2, 2, 2, 1, 2, 3, 2, 4, 2, 5, 2, 6, 2, 2, 3, 2, 0, 0, 6, 2, 2, 2, 0, 0, -1); igraph_has_multiple(&graph, &res); if (!res) { return 2; } igraph_destroy(&graph); igraph_small(&graph, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 1, 1, 0, 3, 4, 11, 10, -1); igraph_has_multiple(&graph, &res); if (res) { return 3; } igraph_destroy(&graph); igraph_small(&graph, 0, IGRAPH_UNDIRECTED, 0, 0, 1, 2, 1, 1, 2, 2, 2, 3, 2, 4, 2, 5, 2, 6, 2, 2, -1); igraph_has_multiple(&graph, &res); if (!res) { return 4; } igraph_destroy(&graph); igraph_small(&graph, 0, IGRAPH_UNDIRECTED, 0, 0, 1, 2, 1, 1, 2, 2, 2, 3, 2, 4, 2, 5, 2, 6, -1); igraph_has_multiple(&graph, &res); if (res) { return 5; } igraph_destroy(&graph); igraph_small(&graph, 0, IGRAPH_UNDIRECTED, 0, 1, 0, 1, 1, 2, -1); igraph_has_multiple(&graph, &res); if (!res) { return 6; } igraph_destroy(&graph); igraph_small(&graph, 0, IGRAPH_UNDIRECTED, 0, 0, 0, 0, -1); igraph_has_multiple(&graph, &res); if (!res) { return 7; } igraph_destroy(&graph); return 0; }
int igraph_count_multiple(const igraph_t *graph, igraph_vector_t *res, igraph_es_t es);
If the graph has no multiple edges then the result vector will be filled with ones. (An edge is a multiple edge if there is another edge with the same head and tail vertices in the graph.)
Arguments:
|
The input graph. |
|
Pointer to a vector, the result will be stored here. It will be resized as needed. |
|
The edges to check. Supply |
Returns:
Error code. |
See also:
Time complexity: O(E d), E is the number of edges to check and d is the average degree (out-degree in directed graphs) of the vertices at the tail of the edges.
int igraph_assortativity_nominal(const igraph_t *graph,
const igraph_vector_t *types,
igraph_real_t *res,
igraph_bool_t directed);
Assuming the vertices of the input graph belong to different categories, this function calculates the assortativity coefficient of the graph. The assortativity coefficient is between minus one and one and it is one if all connections stay within categories, it is minus one, if the network is perfectly disassortative. For a randomly connected network it is (asymptotically) zero.
See equation (2) in M. E. J. Newman: Mixing patterns in networks, Phys. Rev. E 67, 026126 (2003) (http://arxiv.org/abs/cond-mat/0209450) for the proper definition.
Arguments:
|
The input graph, it can be directed or undirected. |
|
Vector giving the vertex types. They are assumed to be integer numbers, starting with zero. |
|
Pointer to a real variable, the result is stored here. |
|
Boolean, it gives whether to consider edge directions in a directed graph. It is ignored for undirected graphs. |
Returns:
Error code. |
Time complexity: O(|E|+t), |E| is the number of edges, t is the number of vertex types.
See also:
|
Example 13.35. File examples/simple/assortativity.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2009-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 <stdio.h> int main() { igraph_t g; FILE *karate, *neural; igraph_real_t res; igraph_vector_t types; igraph_vector_t degree, outdegree, indegree; igraph_real_t football_types[] = { 7, 0, 2, 3, 7, 3, 2, 8, 8, 7, 3, 10, 6, 2, 6, 2, 7, 9, 6, 1, 9, 8, 8, 7, 10, 0, 6, 9, 11, 1, 1, 6, 2, 0, 6, 1, 5, 0, 6, 2, 3, 7, 5, 6, 4, 0, 11, 2, 4, 11, 10, 8, 3, 11, 6, 1, 9, 4, 11, 10, 2, 6, 9, 10, 2, 9, 4, 11, 8, 10, 9, 6, 3, 11, 3, 4, 9, 8, 8, 1, 5, 3, 5, 11, 3, 6, 4, 9, 11, 0, 5, 4, 4, 7, 1, 9, 9, 10, 3, 6, 2, 1, 3, 0, 7, 0, 2, 3, 8, 0, 4, 8, 4, 9, 11 }; karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_vector_init(&types, 0); igraph_degree(&g, &types, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ neural = fopen("celegansneural.gml", "r"); igraph_read_graph_gml(&g, neural); fclose(neural); igraph_degree(&g, &types, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); igraph_vector_destroy(&types); /*---------------------*/ karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_vector_init(°ree, 0); igraph_degree(&g, °ree, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_vector_add_constant(°ree, -1); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ neural = fopen("celegansneural.gml", "r"); igraph_read_graph_gml(&g, neural); fclose(neural); igraph_degree(&g, °ree, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_vector_add_constant(°ree, -1); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_vector_destroy(°ree); /*---------------------*/ igraph_vector_init(&indegree, 0); igraph_vector_init(&outdegree, 0); igraph_degree(&g, &indegree, igraph_vss_all(), IGRAPH_IN, /*loops=*/ 1); igraph_degree(&g, &outdegree, igraph_vss_all(), IGRAPH_OUT, /*loops=*/ 1); igraph_vector_add_constant(&indegree, -1); igraph_vector_add_constant(&outdegree, -1); igraph_assortativity(&g, &outdegree, &indegree, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_vector_destroy(&indegree); igraph_vector_destroy(&outdegree); /*---------------------*/ igraph_assortativity_degree(&g, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_assortativity_degree(&g, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ igraph_small(&g, sizeof(football_types) / sizeof(igraph_real_t), IGRAPH_UNDIRECTED, 0, 1, 2, 3, 0, 4, 4, 5, 3, 5, 2, 6, 6, 7, 7, 8, 8, 9, 0, 9, 4, 9, 5, 10, 10, 11, 5, 11, 3, 11, 12, 13, 2, 13, 2, 14, 12, 14, 14, 15, 13, 15, 2, 15, 4, 16, 9, 16, 0, 16, 16, 17, 12, 17, 12, 18, 18, 19, 17, 20, 20, 21, 8, 21, 7, 21, 9, 22, 7, 22, 21, 22, 8, 22, 22, 23, 9, 23, 4, 23, 16, 23, 0, 23, 11, 24, 24, 25, 1, 25, 3, 26, 12, 26, 14, 26, 26, 27, 17, 27, 1, 27, 17, 27, 4, 28, 11, 28, 24, 28, 19, 29, 29, 30, 19, 30, 18, 31, 31, 32, 21, 32, 15, 32, 13, 32, 6, 32, 0, 33, 1, 33, 25, 33, 19, 33, 31, 34, 26, 34, 12, 34, 18, 34, 34, 35, 0, 35, 29, 35, 19, 35, 30, 35, 18, 36, 12, 36, 20, 36, 19, 36, 36, 37, 1, 37, 25, 37, 33, 37, 18, 38, 16, 38, 28, 38, 26, 38, 14, 38, 12, 38, 38, 39, 6, 39, 32, 39, 13, 39, 15, 39, 7, 40, 3, 40, 40, 41, 8, 41, 4, 41, 23, 41, 9, 41, 0, 41, 16, 41, 34, 42, 29, 42, 18, 42, 26, 42, 42, 43, 36, 43, 26, 43, 31, 43, 38, 43, 12, 43, 14, 43, 19, 44, 35, 44, 30, 44, 44, 45, 13, 45, 33, 45, 1, 45, 37, 45, 25, 45, 21, 46, 46, 47, 22, 47, 6, 47, 15, 47, 2, 47, 39, 47, 32, 47, 44, 48, 48, 49, 32, 49, 46, 49, 30, 50, 24, 50, 11, 50, 28, 50, 50, 51, 40, 51, 8, 51, 22, 51, 21, 51, 3, 52, 40, 52, 5, 52, 52, 53, 25, 53, 48, 53, 49, 53, 46, 53, 39, 54, 31, 54, 38, 54, 14, 54, 34, 54, 18, 54, 54, 55, 31, 55, 6, 55, 35, 55, 29, 55, 19, 55, 30, 55, 27, 56, 56, 57, 1, 57, 42, 57, 44, 57, 48, 57, 3, 58, 6, 58, 17, 58, 36, 58, 36, 59, 58, 59, 59, 60, 10, 60, 39, 60, 6, 60, 47, 60, 13, 60, 15, 60, 2, 60, 43, 61, 47, 61, 54, 61, 18, 61, 26, 61, 31, 61, 34, 61, 61, 62, 20, 62, 45, 62, 17, 62, 27, 62, 56, 62, 27, 63, 58, 63, 59, 63, 42, 63, 63, 64, 9, 64, 32, 64, 60, 64, 2, 64, 6, 64, 47, 64, 13, 64, 0, 65, 27, 65, 17, 65, 63, 65, 56, 65, 20, 65, 65, 66, 59, 66, 24, 66, 44, 66, 48, 66, 16, 67, 41, 67, 46, 67, 53, 67, 49, 67, 67, 68, 15, 68, 50, 68, 21, 68, 51, 68, 7, 68, 22, 68, 8, 68, 4, 69, 24, 69, 28, 69, 50, 69, 11, 69, 69, 70, 43, 70, 65, 70, 20, 70, 56, 70, 62, 70, 27, 70, 60, 71, 18, 71, 14, 71, 34, 71, 54, 71, 38, 71, 61, 71, 31, 71, 71, 72, 2, 72, 10, 72, 3, 72, 40, 72, 52, 72, 7, 73, 49, 73, 53, 73, 67, 73, 46, 73, 73, 74, 2, 74, 72, 74, 5, 74, 10, 74, 52, 74, 3, 74, 40, 74, 20, 75, 66, 75, 48, 75, 57, 75, 44, 75, 75, 76, 27, 76, 59, 76, 20, 76, 70, 76, 66, 76, 56, 76, 62, 76, 73, 77, 22, 77, 7, 77, 51, 77, 21, 77, 8, 77, 77, 78, 23, 78, 50, 78, 28, 78, 22, 78, 8, 78, 68, 78, 7, 78, 51, 78, 31, 79, 43, 79, 30, 79, 19, 79, 29, 79, 35, 79, 55, 79, 79, 80, 37, 80, 29, 80, 16, 81, 5, 81, 40, 81, 10, 81, 72, 81, 3, 81, 81, 82, 74, 82, 39, 82, 77, 82, 80, 82, 30, 82, 29, 82, 7, 82, 53, 83, 81, 83, 69, 83, 73, 83, 46, 83, 67, 83, 49, 83, 83, 84, 24, 84, 49, 84, 52, 84, 3, 84, 74, 84, 10, 84, 81, 84, 5, 84, 3, 84, 6, 85, 14, 85, 38, 85, 43, 85, 80, 85, 12, 85, 26, 85, 31, 85, 44, 86, 53, 86, 75, 86, 57, 86, 48, 86, 80, 86, 66, 86, 86, 87, 17, 87, 62, 87, 56, 87, 24, 87, 20, 87, 65, 87, 49, 88, 58, 88, 83, 88, 69, 88, 46, 88, 53, 88, 73, 88, 67, 88, 88, 89, 1, 89, 37, 89, 25, 89, 33, 89, 55, 89, 45, 89, 5, 90, 8, 90, 23, 90, 0, 90, 11, 90, 50, 90, 24, 90, 69, 90, 28, 90, 29, 91, 48, 91, 66, 91, 69, 91, 44, 91, 86, 91, 57, 91, 80, 91, 91, 92, 35, 92, 15, 92, 86, 92, 48, 92, 57, 92, 61, 92, 66, 92, 75, 92, 0, 93, 23, 93, 80, 93, 16, 93, 4, 93, 82, 93, 91, 93, 41, 93, 9, 93, 34, 94, 19, 94, 55, 94, 79, 94, 80, 94, 29, 94, 30, 94, 82, 94, 35, 94, 70, 95, 69, 95, 76, 95, 62, 95, 56, 95, 27, 95, 17, 95, 87, 95, 37, 95, 48, 96, 17, 96, 76, 96, 27, 96, 56, 96, 65, 96, 20, 96, 87, 96, 5, 97, 86, 97, 58, 97, 11, 97, 59, 97, 63, 97, 97, 98, 77, 98, 48, 98, 84, 98, 40, 98, 10, 98, 5, 98, 52, 98, 81, 98, 89, 99, 34, 99, 14, 99, 85, 99, 54, 99, 18, 99, 31, 99, 61, 99, 71, 99, 14, 99, 99, 100, 82, 100, 13, 100, 2, 100, 15, 100, 32, 100, 64, 100, 47, 100, 39, 100, 6, 100, 51, 101, 30, 101, 94, 101, 1, 101, 79, 101, 58, 101, 19, 101, 55, 101, 35, 101, 29, 101, 100, 102, 74, 102, 52, 102, 98, 102, 72, 102, 40, 102, 10, 102, 3, 102, 102, 103, 33, 103, 45, 103, 25, 103, 89, 103, 37, 103, 1, 103, 70, 103, 72, 104, 11, 104, 0, 104, 93, 104, 67, 104, 41, 104, 16, 104, 87, 104, 23, 104, 4, 104, 9, 104, 89, 105, 103, 105, 33, 105, 62, 105, 37, 105, 45, 105, 1, 105, 80, 105, 25, 105, 25, 106, 56, 106, 92, 106, 2, 106, 13, 106, 32, 106, 60, 106, 6, 106, 64, 106, 15, 106, 39, 106, 88, 107, 75, 107, 98, 107, 102, 107, 72, 107, 40, 107, 81, 107, 5, 107, 10, 107, 84, 107, 4, 108, 9, 108, 7, 108, 51, 108, 77, 108, 21, 108, 78, 108, 22, 108, 68, 108, 79, 109, 30, 109, 63, 109, 1, 109, 33, 109, 103, 109, 105, 109, 45, 109, 25, 109, 89, 109, 37, 109, 67, 110, 13, 110, 24, 110, 80, 110, 88, 110, 49, 110, 73, 110, 46, 110, 83, 110, 53, 110, 23, 111, 64, 111, 46, 111, 78, 111, 8, 111, 21, 111, 51, 111, 7, 111, 108, 111, 68, 111, 77, 111, 52, 112, 96, 112, 97, 112, 57, 112, 66, 112, 63, 112, 44, 112, 92, 112, 75, 112, 91, 112, 28, 113, 20, 113, 95, 113, 59, 113, 70, 113, 17, 113, 87, 113, 76, 113, 65, 113, 96, 113, 83, 114, 88, 114, 110, 114, 53, 114, 49, 114, 73, 114, 46, 114, 67, 114, 58, 114, 15, 114, 104, 114, -1); igraph_simplify(&g, /*multiple=*/ 1, /*loops=*/ 1, /*edge_comb=*/ 0); igraph_vector_view(&types, football_types, sizeof(football_types) / sizeof(igraph_real_t)); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); return 0; }
int igraph_assortativity(const igraph_t *graph,
const igraph_vector_t *types1,
const igraph_vector_t *types2,
igraph_real_t *res,
igraph_bool_t directed);
This function calculates the assortativity coefficient of the input graph. This coefficient is basically the correlation between the actual connectivity patterns of the vertices and the pattern expected from the distribution of the vertex types.
See equation (21) in M. E. J. Newman: Mixing patterns in networks, Phys. Rev. E 67, 026126 (2003) (http://arxiv.org/abs/cond-mat/0209450) for the proper definition. The actual calculation is performed using equation (26) in the same paper for directed graphs, and equation (4) in M. E. J. Newman: Assortative mixing in networks, Phys. Rev. Lett. 89, 208701 (2002) (http://arxiv.org/abs/cond-mat/0205405/) for undirected graphs.
Arguments:
|
The input graph, it can be directed or undirected. |
|
The vertex values, these can be arbitrary numeric values. |
|
A second value vector to be using for the incoming edges when calculating assortativity for a directed graph. Supply a null pointer here if you want to use the same values for outgoing and incoming edges. This argument is ignored (with a warning) if it is not a null pointer and undirected assortativity coefficient is being calculated. |
|
Pointer to a real variable, the result is stored here. |
|
Boolean, whether to consider edge directions for directed graphs. It is ignored for undirected graphs. |
Returns:
Error code. |
Time complexity: O(|E|), linear in the number of edges of the graph.
See also:
|
Example 13.36. File examples/simple/assortativity.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2009-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 <stdio.h> int main() { igraph_t g; FILE *karate, *neural; igraph_real_t res; igraph_vector_t types; igraph_vector_t degree, outdegree, indegree; igraph_real_t football_types[] = { 7, 0, 2, 3, 7, 3, 2, 8, 8, 7, 3, 10, 6, 2, 6, 2, 7, 9, 6, 1, 9, 8, 8, 7, 10, 0, 6, 9, 11, 1, 1, 6, 2, 0, 6, 1, 5, 0, 6, 2, 3, 7, 5, 6, 4, 0, 11, 2, 4, 11, 10, 8, 3, 11, 6, 1, 9, 4, 11, 10, 2, 6, 9, 10, 2, 9, 4, 11, 8, 10, 9, 6, 3, 11, 3, 4, 9, 8, 8, 1, 5, 3, 5, 11, 3, 6, 4, 9, 11, 0, 5, 4, 4, 7, 1, 9, 9, 10, 3, 6, 2, 1, 3, 0, 7, 0, 2, 3, 8, 0, 4, 8, 4, 9, 11 }; karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_vector_init(&types, 0); igraph_degree(&g, &types, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ neural = fopen("celegansneural.gml", "r"); igraph_read_graph_gml(&g, neural); fclose(neural); igraph_degree(&g, &types, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); igraph_vector_destroy(&types); /*---------------------*/ karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_vector_init(°ree, 0); igraph_degree(&g, °ree, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_vector_add_constant(°ree, -1); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ neural = fopen("celegansneural.gml", "r"); igraph_read_graph_gml(&g, neural); fclose(neural); igraph_degree(&g, °ree, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_vector_add_constant(°ree, -1); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_vector_destroy(°ree); /*---------------------*/ igraph_vector_init(&indegree, 0); igraph_vector_init(&outdegree, 0); igraph_degree(&g, &indegree, igraph_vss_all(), IGRAPH_IN, /*loops=*/ 1); igraph_degree(&g, &outdegree, igraph_vss_all(), IGRAPH_OUT, /*loops=*/ 1); igraph_vector_add_constant(&indegree, -1); igraph_vector_add_constant(&outdegree, -1); igraph_assortativity(&g, &outdegree, &indegree, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_vector_destroy(&indegree); igraph_vector_destroy(&outdegree); /*---------------------*/ igraph_assortativity_degree(&g, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_assortativity_degree(&g, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ igraph_small(&g, sizeof(football_types) / sizeof(igraph_real_t), IGRAPH_UNDIRECTED, 0, 1, 2, 3, 0, 4, 4, 5, 3, 5, 2, 6, 6, 7, 7, 8, 8, 9, 0, 9, 4, 9, 5, 10, 10, 11, 5, 11, 3, 11, 12, 13, 2, 13, 2, 14, 12, 14, 14, 15, 13, 15, 2, 15, 4, 16, 9, 16, 0, 16, 16, 17, 12, 17, 12, 18, 18, 19, 17, 20, 20, 21, 8, 21, 7, 21, 9, 22, 7, 22, 21, 22, 8, 22, 22, 23, 9, 23, 4, 23, 16, 23, 0, 23, 11, 24, 24, 25, 1, 25, 3, 26, 12, 26, 14, 26, 26, 27, 17, 27, 1, 27, 17, 27, 4, 28, 11, 28, 24, 28, 19, 29, 29, 30, 19, 30, 18, 31, 31, 32, 21, 32, 15, 32, 13, 32, 6, 32, 0, 33, 1, 33, 25, 33, 19, 33, 31, 34, 26, 34, 12, 34, 18, 34, 34, 35, 0, 35, 29, 35, 19, 35, 30, 35, 18, 36, 12, 36, 20, 36, 19, 36, 36, 37, 1, 37, 25, 37, 33, 37, 18, 38, 16, 38, 28, 38, 26, 38, 14, 38, 12, 38, 38, 39, 6, 39, 32, 39, 13, 39, 15, 39, 7, 40, 3, 40, 40, 41, 8, 41, 4, 41, 23, 41, 9, 41, 0, 41, 16, 41, 34, 42, 29, 42, 18, 42, 26, 42, 42, 43, 36, 43, 26, 43, 31, 43, 38, 43, 12, 43, 14, 43, 19, 44, 35, 44, 30, 44, 44, 45, 13, 45, 33, 45, 1, 45, 37, 45, 25, 45, 21, 46, 46, 47, 22, 47, 6, 47, 15, 47, 2, 47, 39, 47, 32, 47, 44, 48, 48, 49, 32, 49, 46, 49, 30, 50, 24, 50, 11, 50, 28, 50, 50, 51, 40, 51, 8, 51, 22, 51, 21, 51, 3, 52, 40, 52, 5, 52, 52, 53, 25, 53, 48, 53, 49, 53, 46, 53, 39, 54, 31, 54, 38, 54, 14, 54, 34, 54, 18, 54, 54, 55, 31, 55, 6, 55, 35, 55, 29, 55, 19, 55, 30, 55, 27, 56, 56, 57, 1, 57, 42, 57, 44, 57, 48, 57, 3, 58, 6, 58, 17, 58, 36, 58, 36, 59, 58, 59, 59, 60, 10, 60, 39, 60, 6, 60, 47, 60, 13, 60, 15, 60, 2, 60, 43, 61, 47, 61, 54, 61, 18, 61, 26, 61, 31, 61, 34, 61, 61, 62, 20, 62, 45, 62, 17, 62, 27, 62, 56, 62, 27, 63, 58, 63, 59, 63, 42, 63, 63, 64, 9, 64, 32, 64, 60, 64, 2, 64, 6, 64, 47, 64, 13, 64, 0, 65, 27, 65, 17, 65, 63, 65, 56, 65, 20, 65, 65, 66, 59, 66, 24, 66, 44, 66, 48, 66, 16, 67, 41, 67, 46, 67, 53, 67, 49, 67, 67, 68, 15, 68, 50, 68, 21, 68, 51, 68, 7, 68, 22, 68, 8, 68, 4, 69, 24, 69, 28, 69, 50, 69, 11, 69, 69, 70, 43, 70, 65, 70, 20, 70, 56, 70, 62, 70, 27, 70, 60, 71, 18, 71, 14, 71, 34, 71, 54, 71, 38, 71, 61, 71, 31, 71, 71, 72, 2, 72, 10, 72, 3, 72, 40, 72, 52, 72, 7, 73, 49, 73, 53, 73, 67, 73, 46, 73, 73, 74, 2, 74, 72, 74, 5, 74, 10, 74, 52, 74, 3, 74, 40, 74, 20, 75, 66, 75, 48, 75, 57, 75, 44, 75, 75, 76, 27, 76, 59, 76, 20, 76, 70, 76, 66, 76, 56, 76, 62, 76, 73, 77, 22, 77, 7, 77, 51, 77, 21, 77, 8, 77, 77, 78, 23, 78, 50, 78, 28, 78, 22, 78, 8, 78, 68, 78, 7, 78, 51, 78, 31, 79, 43, 79, 30, 79, 19, 79, 29, 79, 35, 79, 55, 79, 79, 80, 37, 80, 29, 80, 16, 81, 5, 81, 40, 81, 10, 81, 72, 81, 3, 81, 81, 82, 74, 82, 39, 82, 77, 82, 80, 82, 30, 82, 29, 82, 7, 82, 53, 83, 81, 83, 69, 83, 73, 83, 46, 83, 67, 83, 49, 83, 83, 84, 24, 84, 49, 84, 52, 84, 3, 84, 74, 84, 10, 84, 81, 84, 5, 84, 3, 84, 6, 85, 14, 85, 38, 85, 43, 85, 80, 85, 12, 85, 26, 85, 31, 85, 44, 86, 53, 86, 75, 86, 57, 86, 48, 86, 80, 86, 66, 86, 86, 87, 17, 87, 62, 87, 56, 87, 24, 87, 20, 87, 65, 87, 49, 88, 58, 88, 83, 88, 69, 88, 46, 88, 53, 88, 73, 88, 67, 88, 88, 89, 1, 89, 37, 89, 25, 89, 33, 89, 55, 89, 45, 89, 5, 90, 8, 90, 23, 90, 0, 90, 11, 90, 50, 90, 24, 90, 69, 90, 28, 90, 29, 91, 48, 91, 66, 91, 69, 91, 44, 91, 86, 91, 57, 91, 80, 91, 91, 92, 35, 92, 15, 92, 86, 92, 48, 92, 57, 92, 61, 92, 66, 92, 75, 92, 0, 93, 23, 93, 80, 93, 16, 93, 4, 93, 82, 93, 91, 93, 41, 93, 9, 93, 34, 94, 19, 94, 55, 94, 79, 94, 80, 94, 29, 94, 30, 94, 82, 94, 35, 94, 70, 95, 69, 95, 76, 95, 62, 95, 56, 95, 27, 95, 17, 95, 87, 95, 37, 95, 48, 96, 17, 96, 76, 96, 27, 96, 56, 96, 65, 96, 20, 96, 87, 96, 5, 97, 86, 97, 58, 97, 11, 97, 59, 97, 63, 97, 97, 98, 77, 98, 48, 98, 84, 98, 40, 98, 10, 98, 5, 98, 52, 98, 81, 98, 89, 99, 34, 99, 14, 99, 85, 99, 54, 99, 18, 99, 31, 99, 61, 99, 71, 99, 14, 99, 99, 100, 82, 100, 13, 100, 2, 100, 15, 100, 32, 100, 64, 100, 47, 100, 39, 100, 6, 100, 51, 101, 30, 101, 94, 101, 1, 101, 79, 101, 58, 101, 19, 101, 55, 101, 35, 101, 29, 101, 100, 102, 74, 102, 52, 102, 98, 102, 72, 102, 40, 102, 10, 102, 3, 102, 102, 103, 33, 103, 45, 103, 25, 103, 89, 103, 37, 103, 1, 103, 70, 103, 72, 104, 11, 104, 0, 104, 93, 104, 67, 104, 41, 104, 16, 104, 87, 104, 23, 104, 4, 104, 9, 104, 89, 105, 103, 105, 33, 105, 62, 105, 37, 105, 45, 105, 1, 105, 80, 105, 25, 105, 25, 106, 56, 106, 92, 106, 2, 106, 13, 106, 32, 106, 60, 106, 6, 106, 64, 106, 15, 106, 39, 106, 88, 107, 75, 107, 98, 107, 102, 107, 72, 107, 40, 107, 81, 107, 5, 107, 10, 107, 84, 107, 4, 108, 9, 108, 7, 108, 51, 108, 77, 108, 21, 108, 78, 108, 22, 108, 68, 108, 79, 109, 30, 109, 63, 109, 1, 109, 33, 109, 103, 109, 105, 109, 45, 109, 25, 109, 89, 109, 37, 109, 67, 110, 13, 110, 24, 110, 80, 110, 88, 110, 49, 110, 73, 110, 46, 110, 83, 110, 53, 110, 23, 111, 64, 111, 46, 111, 78, 111, 8, 111, 21, 111, 51, 111, 7, 111, 108, 111, 68, 111, 77, 111, 52, 112, 96, 112, 97, 112, 57, 112, 66, 112, 63, 112, 44, 112, 92, 112, 75, 112, 91, 112, 28, 113, 20, 113, 95, 113, 59, 113, 70, 113, 17, 113, 87, 113, 76, 113, 65, 113, 96, 113, 83, 114, 88, 114, 110, 114, 53, 114, 49, 114, 73, 114, 46, 114, 67, 114, 58, 114, 15, 114, 104, 114, -1); igraph_simplify(&g, /*multiple=*/ 1, /*loops=*/ 1, /*edge_comb=*/ 0); igraph_vector_view(&types, football_types, sizeof(football_types) / sizeof(igraph_real_t)); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); return 0; }
int igraph_assortativity_degree(const igraph_t *graph,
igraph_real_t *res,
igraph_bool_t directed);
Assortativity based on vertex degree, please see the discussion at
the documentation of igraph_assortativity() for details.
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to a real variable, the result is stored here. |
|
Boolean, whether to consider edge directions for directed graphs. This argument is ignored for undirected graphs. Supply 1 (=TRUE) here to do the natural thing, i.e. use directed version of the measure for directed graphs and the undirected version for undirected graphs. |
Returns:
Error code. |
Time complexity: O(|E|+|V|), |E| is the number of edges, |V| is the number of vertices.
See also:
|
Example 13.37. File examples/simple/assortativity.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2009-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 <stdio.h> int main() { igraph_t g; FILE *karate, *neural; igraph_real_t res; igraph_vector_t types; igraph_vector_t degree, outdegree, indegree; igraph_real_t football_types[] = { 7, 0, 2, 3, 7, 3, 2, 8, 8, 7, 3, 10, 6, 2, 6, 2, 7, 9, 6, 1, 9, 8, 8, 7, 10, 0, 6, 9, 11, 1, 1, 6, 2, 0, 6, 1, 5, 0, 6, 2, 3, 7, 5, 6, 4, 0, 11, 2, 4, 11, 10, 8, 3, 11, 6, 1, 9, 4, 11, 10, 2, 6, 9, 10, 2, 9, 4, 11, 8, 10, 9, 6, 3, 11, 3, 4, 9, 8, 8, 1, 5, 3, 5, 11, 3, 6, 4, 9, 11, 0, 5, 4, 4, 7, 1, 9, 9, 10, 3, 6, 2, 1, 3, 0, 7, 0, 2, 3, 8, 0, 4, 8, 4, 9, 11 }; karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_vector_init(&types, 0); igraph_degree(&g, &types, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ neural = fopen("celegansneural.gml", "r"); igraph_read_graph_gml(&g, neural); fclose(neural); igraph_degree(&g, &types, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); igraph_vector_destroy(&types); /*---------------------*/ karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_vector_init(°ree, 0); igraph_degree(&g, °ree, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_vector_add_constant(°ree, -1); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ neural = fopen("celegansneural.gml", "r"); igraph_read_graph_gml(&g, neural); fclose(neural); igraph_degree(&g, °ree, igraph_vss_all(), IGRAPH_ALL, /*loops=*/ 1); igraph_vector_add_constant(°ree, -1); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_assortativity(&g, °ree, 0, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_vector_destroy(°ree); /*---------------------*/ igraph_vector_init(&indegree, 0); igraph_vector_init(&outdegree, 0); igraph_degree(&g, &indegree, igraph_vss_all(), IGRAPH_IN, /*loops=*/ 1); igraph_degree(&g, &outdegree, igraph_vss_all(), IGRAPH_OUT, /*loops=*/ 1); igraph_vector_add_constant(&indegree, -1); igraph_vector_add_constant(&outdegree, -1); igraph_assortativity(&g, &outdegree, &indegree, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_vector_destroy(&indegree); igraph_vector_destroy(&outdegree); /*---------------------*/ igraph_assortativity_degree(&g, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ karate = fopen("karate.gml", "r"); igraph_read_graph_gml(&g, karate); fclose(karate); igraph_assortativity_degree(&g, &res, /*directed=*/ 1); printf("%.5f\n", res); igraph_destroy(&g); /*---------------------*/ igraph_small(&g, sizeof(football_types) / sizeof(igraph_real_t), IGRAPH_UNDIRECTED, 0, 1, 2, 3, 0, 4, 4, 5, 3, 5, 2, 6, 6, 7, 7, 8, 8, 9, 0, 9, 4, 9, 5, 10, 10, 11, 5, 11, 3, 11, 12, 13, 2, 13, 2, 14, 12, 14, 14, 15, 13, 15, 2, 15, 4, 16, 9, 16, 0, 16, 16, 17, 12, 17, 12, 18, 18, 19, 17, 20, 20, 21, 8, 21, 7, 21, 9, 22, 7, 22, 21, 22, 8, 22, 22, 23, 9, 23, 4, 23, 16, 23, 0, 23, 11, 24, 24, 25, 1, 25, 3, 26, 12, 26, 14, 26, 26, 27, 17, 27, 1, 27, 17, 27, 4, 28, 11, 28, 24, 28, 19, 29, 29, 30, 19, 30, 18, 31, 31, 32, 21, 32, 15, 32, 13, 32, 6, 32, 0, 33, 1, 33, 25, 33, 19, 33, 31, 34, 26, 34, 12, 34, 18, 34, 34, 35, 0, 35, 29, 35, 19, 35, 30, 35, 18, 36, 12, 36, 20, 36, 19, 36, 36, 37, 1, 37, 25, 37, 33, 37, 18, 38, 16, 38, 28, 38, 26, 38, 14, 38, 12, 38, 38, 39, 6, 39, 32, 39, 13, 39, 15, 39, 7, 40, 3, 40, 40, 41, 8, 41, 4, 41, 23, 41, 9, 41, 0, 41, 16, 41, 34, 42, 29, 42, 18, 42, 26, 42, 42, 43, 36, 43, 26, 43, 31, 43, 38, 43, 12, 43, 14, 43, 19, 44, 35, 44, 30, 44, 44, 45, 13, 45, 33, 45, 1, 45, 37, 45, 25, 45, 21, 46, 46, 47, 22, 47, 6, 47, 15, 47, 2, 47, 39, 47, 32, 47, 44, 48, 48, 49, 32, 49, 46, 49, 30, 50, 24, 50, 11, 50, 28, 50, 50, 51, 40, 51, 8, 51, 22, 51, 21, 51, 3, 52, 40, 52, 5, 52, 52, 53, 25, 53, 48, 53, 49, 53, 46, 53, 39, 54, 31, 54, 38, 54, 14, 54, 34, 54, 18, 54, 54, 55, 31, 55, 6, 55, 35, 55, 29, 55, 19, 55, 30, 55, 27, 56, 56, 57, 1, 57, 42, 57, 44, 57, 48, 57, 3, 58, 6, 58, 17, 58, 36, 58, 36, 59, 58, 59, 59, 60, 10, 60, 39, 60, 6, 60, 47, 60, 13, 60, 15, 60, 2, 60, 43, 61, 47, 61, 54, 61, 18, 61, 26, 61, 31, 61, 34, 61, 61, 62, 20, 62, 45, 62, 17, 62, 27, 62, 56, 62, 27, 63, 58, 63, 59, 63, 42, 63, 63, 64, 9, 64, 32, 64, 60, 64, 2, 64, 6, 64, 47, 64, 13, 64, 0, 65, 27, 65, 17, 65, 63, 65, 56, 65, 20, 65, 65, 66, 59, 66, 24, 66, 44, 66, 48, 66, 16, 67, 41, 67, 46, 67, 53, 67, 49, 67, 67, 68, 15, 68, 50, 68, 21, 68, 51, 68, 7, 68, 22, 68, 8, 68, 4, 69, 24, 69, 28, 69, 50, 69, 11, 69, 69, 70, 43, 70, 65, 70, 20, 70, 56, 70, 62, 70, 27, 70, 60, 71, 18, 71, 14, 71, 34, 71, 54, 71, 38, 71, 61, 71, 31, 71, 71, 72, 2, 72, 10, 72, 3, 72, 40, 72, 52, 72, 7, 73, 49, 73, 53, 73, 67, 73, 46, 73, 73, 74, 2, 74, 72, 74, 5, 74, 10, 74, 52, 74, 3, 74, 40, 74, 20, 75, 66, 75, 48, 75, 57, 75, 44, 75, 75, 76, 27, 76, 59, 76, 20, 76, 70, 76, 66, 76, 56, 76, 62, 76, 73, 77, 22, 77, 7, 77, 51, 77, 21, 77, 8, 77, 77, 78, 23, 78, 50, 78, 28, 78, 22, 78, 8, 78, 68, 78, 7, 78, 51, 78, 31, 79, 43, 79, 30, 79, 19, 79, 29, 79, 35, 79, 55, 79, 79, 80, 37, 80, 29, 80, 16, 81, 5, 81, 40, 81, 10, 81, 72, 81, 3, 81, 81, 82, 74, 82, 39, 82, 77, 82, 80, 82, 30, 82, 29, 82, 7, 82, 53, 83, 81, 83, 69, 83, 73, 83, 46, 83, 67, 83, 49, 83, 83, 84, 24, 84, 49, 84, 52, 84, 3, 84, 74, 84, 10, 84, 81, 84, 5, 84, 3, 84, 6, 85, 14, 85, 38, 85, 43, 85, 80, 85, 12, 85, 26, 85, 31, 85, 44, 86, 53, 86, 75, 86, 57, 86, 48, 86, 80, 86, 66, 86, 86, 87, 17, 87, 62, 87, 56, 87, 24, 87, 20, 87, 65, 87, 49, 88, 58, 88, 83, 88, 69, 88, 46, 88, 53, 88, 73, 88, 67, 88, 88, 89, 1, 89, 37, 89, 25, 89, 33, 89, 55, 89, 45, 89, 5, 90, 8, 90, 23, 90, 0, 90, 11, 90, 50, 90, 24, 90, 69, 90, 28, 90, 29, 91, 48, 91, 66, 91, 69, 91, 44, 91, 86, 91, 57, 91, 80, 91, 91, 92, 35, 92, 15, 92, 86, 92, 48, 92, 57, 92, 61, 92, 66, 92, 75, 92, 0, 93, 23, 93, 80, 93, 16, 93, 4, 93, 82, 93, 91, 93, 41, 93, 9, 93, 34, 94, 19, 94, 55, 94, 79, 94, 80, 94, 29, 94, 30, 94, 82, 94, 35, 94, 70, 95, 69, 95, 76, 95, 62, 95, 56, 95, 27, 95, 17, 95, 87, 95, 37, 95, 48, 96, 17, 96, 76, 96, 27, 96, 56, 96, 65, 96, 20, 96, 87, 96, 5, 97, 86, 97, 58, 97, 11, 97, 59, 97, 63, 97, 97, 98, 77, 98, 48, 98, 84, 98, 40, 98, 10, 98, 5, 98, 52, 98, 81, 98, 89, 99, 34, 99, 14, 99, 85, 99, 54, 99, 18, 99, 31, 99, 61, 99, 71, 99, 14, 99, 99, 100, 82, 100, 13, 100, 2, 100, 15, 100, 32, 100, 64, 100, 47, 100, 39, 100, 6, 100, 51, 101, 30, 101, 94, 101, 1, 101, 79, 101, 58, 101, 19, 101, 55, 101, 35, 101, 29, 101, 100, 102, 74, 102, 52, 102, 98, 102, 72, 102, 40, 102, 10, 102, 3, 102, 102, 103, 33, 103, 45, 103, 25, 103, 89, 103, 37, 103, 1, 103, 70, 103, 72, 104, 11, 104, 0, 104, 93, 104, 67, 104, 41, 104, 16, 104, 87, 104, 23, 104, 4, 104, 9, 104, 89, 105, 103, 105, 33, 105, 62, 105, 37, 105, 45, 105, 1, 105, 80, 105, 25, 105, 25, 106, 56, 106, 92, 106, 2, 106, 13, 106, 32, 106, 60, 106, 6, 106, 64, 106, 15, 106, 39, 106, 88, 107, 75, 107, 98, 107, 102, 107, 72, 107, 40, 107, 81, 107, 5, 107, 10, 107, 84, 107, 4, 108, 9, 108, 7, 108, 51, 108, 77, 108, 21, 108, 78, 108, 22, 108, 68, 108, 79, 109, 30, 109, 63, 109, 1, 109, 33, 109, 103, 109, 105, 109, 45, 109, 25, 109, 89, 109, 37, 109, 67, 110, 13, 110, 24, 110, 80, 110, 88, 110, 49, 110, 73, 110, 46, 110, 83, 110, 53, 110, 23, 111, 64, 111, 46, 111, 78, 111, 8, 111, 21, 111, 51, 111, 7, 111, 108, 111, 68, 111, 77, 111, 52, 112, 96, 112, 97, 112, 57, 112, 66, 112, 63, 112, 44, 112, 92, 112, 75, 112, 91, 112, 28, 113, 20, 113, 95, 113, 59, 113, 70, 113, 17, 113, 87, 113, 76, 113, 65, 113, 96, 113, 83, 114, 88, 114, 110, 114, 53, 114, 49, 114, 73, 114, 46, 114, 67, 114, 58, 114, 15, 114, 104, 114, -1); igraph_simplify(&g, /*multiple=*/ 1, /*loops=*/ 1, /*edge_comb=*/ 0); igraph_vector_view(&types, football_types, sizeof(football_types) / sizeof(igraph_real_t)); igraph_assortativity_nominal(&g, &types, &res, /*directed=*/ 0); printf("%.5f\n", res); igraph_destroy(&g); return 0; }
int igraph_coreness(const igraph_t *graph, igraph_vector_t *cores,
igraph_neimode_t mode);
The k-core of a graph is a maximal subgraph in which each vertex has at least degree k. (Degree here means the degree in the subgraph of course.). The coreness of a vertex is the highest order of a k-core containing the vertex.
This function implements the algorithm presented in Vladimir Batagelj, Matjaz Zaversnik: An O(m) Algorithm for Cores Decomposition of Networks.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the result of the computation will be stored here. It will be resized as needed. For each vertex it contains the highest order of a core containing the vertex. |
|
For directed graph it specifies whether to calculate
in-cores, out-cores or the undirected version. It is ignored
for undirected graphs. Possible values: |
Returns:
Error code. |
Time complexity: O(|E|), the number of edges.
int igraph_is_dag(const igraph_t* graph, igraph_bool_t *res);
A directed acyclic graph (DAG) is a directed graph with no cycles.
Arguments:
|
The input graph. |
|
Pointer to a boolean constant, the result is stored here. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), where |V| and |E| are the number of vertices and edges in the original input graph.
See also:
|
int igraph_topological_sorting(const igraph_t* graph, igraph_vector_t *res,
igraph_neimode_t mode);
A topological sorting of a directed acyclic graph (DAG) is a linear ordering of its vertices where each vertex comes before all nodes to which it has edges. Every DAG has at least one topological sort, and may have many. This function returns one possible topological sort among them. If the graph is not acyclic (it has at least one cycle), an error is raised.
Arguments:
|
The input graph. |
|
Pointer to a vector, the result will be stored here. It will be resized if needed. |
|
Specifies how to use the direction of the edges.
For |
Returns:
Error code. |
Time complexity: O(|V|+|E|), where |V| and |E| are the number of vertices and edges in the original input graph.
See also:
|
Example 13.38. File examples/simple/igraph_topological_sorting.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-2020 The igraph development team <igraph@igraph.org> 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, see <https://www.gnu.org/licenses/>. */ #include <igraph.h> #include <stdio.h> int main() { igraph_t graph; igraph_vector_t res; /* Test graph taken from http://en.wikipedia.org/wiki/Topological_sorting * @ 05.03.2006 */ igraph_small(&graph, 8, IGRAPH_DIRECTED, 0, 3, 0, 4, 1, 3, 2, 4, 2, 7, 3, 5, 3, 6, 3, 7, 4, 6, -1); igraph_vector_init(&res, 0); /* Sort the vertices in "increasing" order. */ igraph_topological_sorting(&graph, &res, IGRAPH_OUT); igraph_vector_print(&res); printf("\n"); /* Sort the vertices in "decreasing" order. */ igraph_topological_sorting(&graph, &res, IGRAPH_IN); igraph_vector_print(&res); /* Destroy data structures when done using them. */ igraph_destroy(&graph); igraph_vector_destroy(&res); return 0; }
int igraph_feedback_arc_set(const igraph_t *graph, igraph_vector_t *result,
const igraph_vector_t *weights, igraph_fas_algorithm_t algo);
algorithms.
A feedback arc set is a set of edges whose removal makes the graph acyclic. We are usually interested in minimum feedback arc sets, i.e. sets of edges whose total weight is minimal among all the feedback arc sets.
For undirected graphs, the problem is simple: one has to find a maximum weight spanning tree and then remove all the edges not in the spanning tree. For directed graphs, this is an NP-hard problem, and various heuristics are usually used to find an approximate solution to the problem. This function implements a few of these heuristics.
Arguments:
|
The graph object. |
||||
|
An initialized vector, the result will be returned here. |
||||
|
Weight vector or NULL if no weights are specified. |
||||
|
The algorithm to use to solve the problem if the graph is directed. Possible values:
|
Returns:
Error code:
|
Example 13.39. File examples/simple/igraph_feedback_arc_set.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* IGraph library. Copyright (C) 2011-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 <string.h> int main() { igraph_t g; igraph_vector_t weights, result; igraph_bool_t dag; igraph_vector_init(&result, 0); /***********************************************************************/ /* Approximation with Eades' method */ /***********************************************************************/ /* Simple unweighted graph */ igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, -1); igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_APPROX_EADES); igraph_vector_print(&result); igraph_delete_edges(&g, igraph_ess_vector(&result)); igraph_is_dag(&g, &dag); if (!dag) { return 1; } igraph_destroy(&g); /* Simple weighted graph */ igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, -1); igraph_vector_init_int_end(&weights, -1, 1, 1, 3, 1, 1, 1, 1, 1, 1, -1); igraph_feedback_arc_set(&g, &result, &weights, IGRAPH_FAS_APPROX_EADES); igraph_vector_print(&result); igraph_delete_edges(&g, igraph_ess_vector(&result)); igraph_is_dag(&g, &dag); if (!dag) { return 2; } igraph_vector_destroy(&weights); igraph_destroy(&g); /* Simple unweighted graph with loops */ igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, 1, 1, 4, 4, -1); igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_APPROX_EADES); igraph_vector_print(&result); igraph_delete_edges(&g, igraph_ess_vector(&result)); igraph_is_dag(&g, &dag); if (!dag) { return 3; } igraph_destroy(&g); igraph_vector_destroy(&result); return 0; }
Example 13.40. File examples/simple/igraph_feedback_arc_set_ip.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* IGraph library. Copyright (C) 2011-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 <string.h> int main() { igraph_t g; igraph_vector_t weights, result; igraph_bool_t dag; int retval; igraph_vector_init(&result, 0); igraph_set_error_handler(&igraph_error_handler_printignore); /***********************************************************************/ /* Exact solution with integer programming */ /***********************************************************************/ /* Simple unweighted graph */ igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, -1); retval = igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_EXACT_IP); if (retval == IGRAPH_UNIMPLEMENTED) { return 77; } igraph_vector_print(&result); igraph_delete_edges(&g, igraph_ess_vector(&result)); igraph_is_dag(&g, &dag); if (!dag) { return 1; } igraph_destroy(&g); /* Simple weighted graph */ igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, -1); igraph_vector_init_int_end(&weights, -1, 1, 1, 3, 1, 1, 1, 1, 1, 1, -1); igraph_feedback_arc_set(&g, &result, &weights, IGRAPH_FAS_EXACT_IP); igraph_vector_print(&result); igraph_delete_edges(&g, igraph_ess_vector(&result)); igraph_is_dag(&g, &dag); if (!dag) { return 2; } igraph_vector_destroy(&weights); igraph_destroy(&g); /* Simple unweighted graph with loops */ igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, 1, 1, 4, 4, -1); igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_EXACT_IP); igraph_vector_print(&result); igraph_delete_edges(&g, igraph_ess_vector(&result)); igraph_is_dag(&g, &dag); if (!dag) { return 3; } igraph_destroy(&g); /* Disjoint union of two almost identical graphs */ igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, 1, 1, 4, 4, 7, 8, 8, 9, 9, 7, 9, 10, 9, 11, 7, 11, 11, 10, 12, 7, 13, 12, -1); igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_EXACT_IP); igraph_vector_print(&result); igraph_delete_edges(&g, igraph_ess_vector(&result)); igraph_is_dag(&g, &dag); if (!dag) { return 4; } igraph_destroy(&g); /* Graph with lots of isolated vertices */ igraph_small(&g, 10000, IGRAPH_DIRECTED, 0, 1, -1); igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_EXACT_IP); igraph_vector_print(&result); igraph_delete_edges(&g, igraph_ess_vector(&result)); igraph_is_dag(&g, &dag); if (!dag) { return 5; } igraph_destroy(&g); igraph_vector_destroy(&result); return 0; }
Time complexity: depends on algo, see the time complexities there.
int igraph_maximum_cardinality_search(const igraph_t *graph,
igraph_vector_t *alpha,
igraph_vector_t *alpham1);
This function implements the maximum cardinality search algorithm.
It computes a rank alpha for each vertex, such that visiting
vertices in decreasing rank order corresponds to always choosing
the vertex with the most already visited neighbors as the next one
to visit.
Maximum cardinality search is useful in deciding the chordality of a graph. A graph is chordal if and only if any two neighbors of a vertex which are higher in rank than it are connected to each other.
References:
Robert E Tarjan and Mihalis Yannakakis: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal of Computation 13, 566--579, 1984. https://doi.org/10.1137/0213035
Arguments:
|
The input graph. Edge directions will be ignored. |
|
Pointer to an initialized vector, the result is stored here.
It will be resized, as needed. Upon return it contains
the rank of the each vertex in the range 0 to |
|
Pointer to an initialized vector or a |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in terms of the number of vertices and edges.
See also:
int igraph_is_chordal(const igraph_t *graph,
const igraph_vector_t *alpha,
const igraph_vector_t *alpham1,
igraph_bool_t *chordal,
igraph_vector_t *fill_in,
igraph_t *newgraph);
A graph is chordal if each of its cycles of four or more nodes
has a chord, i.e. an edge joining two nodes that are not
adjacent in the cycle. An equivalent definition is that any
chordless cycles have at most three nodes.
If either alpha or alpha1 is given, then the other is
calculated by taking simply the inverse. If neither are given,
then igraph_maximum_cardinality_search() is called to calculate
them.
Arguments:
|
The input graph. Edge directions will be ignored. |
|
Either an alpha vector coming from
|
|
Either an inverse alpha vector coming from |
|
Pointer to a boolean. If not NULL the result is stored here. |
|
Pointer to an initialized vector, or a |
|
Pointer to an uninitialized graph, or a |
Returns:
Error code. |
Time complexity: O(n).
See also:
int igraph_is_matching(const igraph_t* graph,
const igraph_vector_bool_t* types, const igraph_vector_long_t* matching,
igraph_bool_t* result);
This function checks a matching vector and verifies whether its length matches the number of vertices in the given graph, its values are between -1 (inclusive) and the number of vertices (exclusive), and whether there exists a corresponding edge in the graph for every matched vertex pair. For bipartite graphs, it also verifies whether the matched vertices are in different parts of the graph.
Arguments:
|
The input graph. It can be directed but the edge directions will be ignored. |
|
If the graph is bipartite and you are interested in bipartite
matchings only, pass the vertex types here. If the graph is
non-bipartite, simply pass |
|
The matching itself. It must be a vector where element i contains the ID of the vertex that vertex i is matched to, or -1 if vertex i is unmatched. |
|
Pointer to a boolean variable, the result will be returned here. |
See also:
|
Time complexity: O(|V|+|E|) where |V| is the number of vertices and |E| is the number of edges.
Example 13.41. File examples/simple/igraph_maximum_bipartite_matching.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* IGraph library. Copyright (C) 2012 Tamas Nepusz <ntamas@gmail.com> 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 test_graph_from_leda_tutorial() { /* Test graph from the LEDA tutorial: * http://www.leda-tutorial.org/en/unofficial/ch05s03s05.html */ igraph_t graph; igraph_vector_bool_t types; igraph_vector_long_t matching; igraph_integer_t matching_size; igraph_real_t matching_weight; igraph_bool_t is_matching; int i; igraph_small(&graph, 0, 0, 0, 8, 0, 12, 0, 14, 1, 9, 1, 10, 1, 13, 2, 8, 2, 9, 3, 10, 3, 11, 3, 13, 4, 9, 4, 14, 5, 14, 6, 9, 6, 14, 7, 8, 7, 12, 7, 14 , -1); igraph_vector_bool_init(&types, 15); for (i = 0; i < 15; i++) { VECTOR(types)[i] = (i >= 8); } igraph_vector_long_init(&matching, 0); igraph_maximum_bipartite_matching(&graph, &types, &matching_size, &matching_weight, &matching, 0, 0); if (matching_size != 6) { printf("matching_size is %ld, expected: 6\n", (long)matching_size); return 1; } if (matching_weight != 6) { printf("matching_weight is %ld, expected: 6\n", (long)matching_weight); return 2; } igraph_is_maximal_matching(&graph, &types, &matching, &is_matching); if (!is_matching) { printf("not a matching: "); igraph_vector_long_print(&matching); return 3; } igraph_vector_long_destroy(&matching); igraph_vector_bool_destroy(&types); igraph_destroy(&graph); return 0; } int test_weighted_graph_from_mit_notes() { /* Test graph from the following lecture notes: * http://math.mit.edu/~goemans/18433S07/matching-notes.pdf */ igraph_t graph; igraph_vector_bool_t types; igraph_vector_long_t matching; igraph_vector_t weights; igraph_integer_t matching_size; igraph_real_t matching_weight; igraph_bool_t is_matching; igraph_real_t weight_array[] = { 2, 7, 2, 3, 1, 3, 9, 3, 3, 1, 3, 3, 1, 2, 4, 1, 2, 3 }; int i; igraph_small(&graph, 0, 0, 0, 6, 0, 7, 0, 8, 0, 9, 1, 5, 1, 6, 1, 7, 1, 8, 1, 9, 2, 5, 2, 6, 2, 7, 2, 8, 2, 9, 3, 5, 3, 7, 3, 9, 4, 7, -1); igraph_vector_bool_init(&types, 10); for (i = 0; i < 10; i++) { VECTOR(types)[i] = (i >= 5); } igraph_vector_long_init(&matching, 0); igraph_vector_init_copy(&weights, weight_array, sizeof(weight_array) / sizeof(weight_array[0])); igraph_maximum_bipartite_matching(&graph, &types, &matching_size, &matching_weight, &matching, &weights, 0); if (matching_size != 4) { printf("matching_size is %ld, expected: 4\n", (long)matching_size); return 1; } if (matching_weight != 19) { printf("matching_weight is %ld, expected: 19\n", (long)matching_weight); return 2; } igraph_is_maximal_matching(&graph, &types, &matching, &is_matching); if (!is_matching) { printf("not a matching: "); igraph_vector_long_print(&matching); return 3; } igraph_vector_destroy(&weights); igraph_vector_long_destroy(&matching); igraph_vector_bool_destroy(&types); igraph_destroy(&graph); return 0; } int test_weighted_graph_generated() { /* Several randomly generated small test graphs */ igraph_t graph; igraph_vector_bool_t types; igraph_vector_long_t matching; igraph_vector_t weights; igraph_integer_t matching_size; igraph_real_t matching_weight; igraph_real_t weight_array_1[] = { 8, 5, 9, 18, 20, 13 }; igraph_real_t weight_array_2[] = { 20, 4, 20, 3, 13, 1 }; int i; igraph_vector_bool_init(&types, 10); for (i = 0; i < 10; i++) { VECTOR(types)[i] = (i >= 5); } igraph_vector_long_init(&matching, 0); /* Case 1 */ igraph_small(&graph, 0, 0, 0, 8, 2, 7, 3, 7, 3, 8, 4, 5, 4, 9, -1); igraph_vector_init_copy(&weights, weight_array_1, sizeof(weight_array_1) / sizeof(weight_array_1[0])); igraph_maximum_bipartite_matching(&graph, &types, &matching_size, &matching_weight, &matching, &weights, 0); if (matching_weight != 43) { printf("matching_weight is %ld, expected: 43\n", (long)matching_weight); return 2; } igraph_vector_destroy(&weights); igraph_destroy(&graph); /* Case 2 */ igraph_small(&graph, 0, 0, 0, 5, 0, 6, 1, 7, 2, 5, 3, 5, 3, 9, -1); igraph_vector_init_copy(&weights, weight_array_2, sizeof(weight_array_2) / sizeof(weight_array_2[0])); igraph_maximum_bipartite_matching(&graph, &types, &matching_size, &matching_weight, &matching, &weights, 0); if (matching_weight != 41) { printf("matching_weight is %ld, expected: 41\n", (long)matching_weight); return 2; } igraph_vector_destroy(&weights); igraph_destroy(&graph); igraph_vector_long_destroy(&matching); igraph_vector_bool_destroy(&types); return 0; } int test_weighted_graph_from_file(const char* fname, int type1_count, long exp_weight) { igraph_t graph; igraph_vector_bool_t types; igraph_vector_long_t matching; igraph_vector_t weights; igraph_real_t matching_weight; FILE* f; int i, n; f = fopen(fname, "r"); if (!f) { fprintf(stderr, "No such file: %s\n", fname); return 1; } igraph_read_graph_ncol(&graph, f, 0, 1, IGRAPH_ADD_WEIGHTS_YES, 0); fclose(f); n = igraph_vcount(&graph); igraph_vector_bool_init(&types, n); for (i = 0; i < n; i++) { VECTOR(types)[i] = (i >= type1_count); } igraph_vector_long_init(&matching, 0); igraph_vector_init(&weights, 0); EANV(&graph, "weight", &weights); igraph_maximum_bipartite_matching(&graph, &types, 0, &matching_weight, &matching, &weights, 0); igraph_vector_destroy(&weights); igraph_vector_long_print(&matching); if (matching_weight != exp_weight) { printf("matching_weight is %ld, expected: %ld\n", (long)matching_weight, (long)exp_weight); return 2; } igraph_vector_destroy(&weights); igraph_vector_long_destroy(&matching); igraph_vector_bool_destroy(&types); igraph_destroy(&graph); return 0; } // This test addresses issue #1110, where an incorrect // types vector (i.e. that doesn't correspond to a bipartite // labelling of the graph) would cause a possible infinite loop. int test_incorrect_types() { igraph_t g; igraph_vector_bool_t types; igraph_vector_t weights; igraph_integer_t matching_size; igraph_real_t weighted_size; igraph_vector_long_t matching; igraph_error_type_t err; igraph_small(&g, 4, IGRAPH_UNDIRECTED, 0, 1, 0, 2, 0, 3, -1); igraph_vector_bool_init(&types, 4); VECTOR(types)[0] = 0; VECTOR(types)[1] = 1; VECTOR(types)[2] = 0; VECTOR(types)[3] = 1; igraph_vector_long_init(&matching, 0); igraph_vector_init(&weights, igraph_vcount(&g)); igraph_vector_fill(&weights, 1.0); igraph_set_error_handler(&igraph_error_handler_ignore); // Test incorrect types err = igraph_maximum_bipartite_matching(&g, &types, &matching_size, NULL, &matching, NULL, 0); if (err != IGRAPH_EINVAL) { return 3; } // Test correct types VECTOR(types)[2] = 1; err = igraph_maximum_bipartite_matching(&g, &types, &matching_size, NULL, &matching, NULL, 0); if (err == IGRAPH_EINVAL) { return 4; } // Test incorrect types for weighted graph VECTOR(types)[2] = 0; err = igraph_maximum_bipartite_matching(&g, &types, &matching_size, &weighted_size, &matching, &weights, 0); if (err != IGRAPH_EINVAL) { return 5; } // Test correct types for weighted graph VECTOR(types)[2] = 1; err = igraph_maximum_bipartite_matching(&g, &types, &matching_size, &weighted_size, &matching, &weights, 0); if (err == IGRAPH_EINVAL) { return 6; } igraph_vector_destroy(&weights); igraph_vector_long_destroy(&matching); igraph_vector_bool_destroy(&types); igraph_destroy(&g); return 0; } int main() { igraph_set_attribute_table(&igraph_cattribute_table); if (test_graph_from_leda_tutorial()) { return 1; } if (test_weighted_graph_from_mit_notes()) { return 2; } if (test_weighted_graph_generated()) { return 3; } if (test_incorrect_types()) { return 4; } if (!IGRAPH_FINALLY_STACK_EMPTY) { printf("Finally stack still has %d elements.\n", IGRAPH_FINALLY_STACK_SIZE()); return 5; } return 0; }
int igraph_is_maximal_matching(const igraph_t* graph,
const igraph_vector_bool_t* types, const igraph_vector_long_t* matching,
igraph_bool_t* result);
A matching is maximal if and only if there exists no unmatched vertex in a graph such that one of its neighbors is also unmatched.
Arguments:
|
The input graph. It can be directed but the edge directions will be ignored. |
|
If the graph is bipartite and you are interested in bipartite
matchings only, pass the vertex types here. If the graph is
non-bipartite, simply pass |
|
The matching itself. It must be a vector where element i contains the ID of the vertex that vertex i is matched to, or -1 if vertex i is unmatched. |
|
Pointer to a boolean variable, the result will be returned here. |
See also:
|
Time complexity: O(|V|+|E|) where |V| is the number of vertices and |E| is the number of edges.
Example 13.42. File examples/simple/igraph_maximum_bipartite_matching.c
/* -*- mode: C -*- */ /* vim:set ts=4 sw=4 sts=4 et: */ /* IGraph library. Copyright (C) 2012 Tamas Nepusz <ntamas@gmail.com> 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 test_graph_from_leda_tutorial() { /* Test graph from the LEDA tutorial: * http://www.leda-tutorial.org/en/unofficial/ch05s03s05.html */ igraph_t graph; igraph_vector_bool_t types; igraph_vector_long_t matching; igraph_integer_t matching_size; igraph_real_t matching_weight; igraph_bool_t is_matching; int i; igraph_small(&graph, 0, 0, 0, 8, 0, 12, 0, 14, 1, 9, 1, 10, 1, 13, 2, 8, 2, 9, 3, 10, 3, 11, 3, 13, 4, 9, 4, 14, 5, 14, 6, 9, 6, 14, 7, 8, 7, 12, 7, 14 , -1);