For using the igraph C library
These functions usually calculate some structural propertyof a graph, like its diameter, the degree of the nodes, etc.
igraph_error_t igraph_are_adjacent(const igraph_t *graph, igraph_integer_t v1, igraph_integer_t v2, igraph_bool_t *res);
Decides whether there are any edges that havev1 andv2as endpoints. This function is of course symmetric for undirectedgraphs.
Arguments:
| The graph object. |
| The first vertex. |
| The second vertex. |
| Boolean, |
Returns:
The error code |
Time complexity: O( min(log(d1), log(d2)) ),d1 is the (out-)degree ofv1 and d2 is the (in-)degree ofv2.
igraph_error_t igraph_spanner(const igraph_t *graph, igraph_vector_int_t *spanner, igraph_real_t stretch, const igraph_vector_t *weights);
A spanner of a graphG = (V,E) with a stretcht is asubgraphH = (V,Es) such thatEs is a subset ofEand the distance between any pair of nodes inH is at mostttimes the distance inG. The returned graph is always a spanner ofthe given graph with the specified stretch. For weighted graphs thenumber of edges in the spanner isO(k n^(1 + 1 / k)), wherek isk = (t + 1) / 2,m is the number of edgesandn is the number of nodes inG. For unweighted graphs the numberof edges isO(n^(1 + 1 / k) + kn).
This function is based on the algorithm of Baswana and Sen: "A Simple andLinear Time Randomized Algorithm for Computing Sparse Spanners inWeighted Graphs".https://doi.org/10.1002/rsa.20130
Arguments:
| An undirected connected graph object. If the graph is directed, the directions of the edges will be ignored. |
| An initialized vector, the IDs of the edges that constitute the calculated spanner will be returned here. Use |
| The stretch factor |
| The edge weights or |
Returns:
Error code:
|
Time complexity: The algorithm is a randomized Las Vegas algorithm. The expectedrunning time is O(km) where k is the value mentioned above and m is the numberof edges.
igraph_distances — Length of the shortest paths between vertices.igraph_distances_cutoff — Length of the shortest paths between vertices, with cutoff.igraph_distances_dijkstra — Weighted shortest path lengths between vertices.igraph_distances_dijkstra_cutoff — Weighted shortest path lengths between vertices, with cutoff.igraph_distances_bellman_ford — Weighted shortest path lengths between vertices, allowing negative weights.igraph_distances_johnson — Weighted shortest path lengths between vertices, using Johnson's algorithm.igraph_distances_floyd_warshall — Weighted all-pairs shortest path lengths with the Floyd-Warshall 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 (Dijkstra).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 (Bellman-Ford).igraph_get_shortest_path_astar — A* gives the shortest path from one vertex to another, with heuristic.igraph_astar_heuristic_func_t — Distance estimator for A* algorithm.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_k_shortest_paths — k shortest paths between two vertices.igraph_get_all_simple_paths — List all simple paths from one source.igraph_average_path_length — The average unweighted shortest path length between all vertex pairs.igraph_average_path_length_dijkstra — 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_eccentricity_dijkstra — Eccentricity of some vertices, using weighted edges.igraph_radius — Radius of a graph.igraph_radius_dijkstra — Radius of a graph, using weighted edges.igraph_graph_center — Central vertices of a graph.igraph_graph_center_dijkstra — Central vertices of a graph, using weighted edges.igraph_pseudo_diameter — Approximation and lower bound of diameter.igraph_pseudo_diameter_dijkstra — Approximation and lower bound of the diameter of a weighted graph.igraph_voronoi — Voronoi partitioning of a graph.igraph_vertex_path_from_edge_path — Converts a walk of edge IDs to the traversed vertex IDs.igraph_error_t igraph_distances(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:
|
Example 13.1. Fileexamples/simple/distances.c
#include <igraph.h>intmain(void) { igraph_t graph;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_real_t cutoff;igraph_small(&graph, 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_matrix_init(&res, 0, 0);printf("Unweighted distances:\n\n");igraph_distances(&graph, &res,igraph_vss_all(),igraph_vss_all(), IGRAPH_OUT);igraph_matrix_print(&res); cutoff = 3;/* distances longer than this will be returned as infinity */printf("\nUnweighted distances with a cutoff of %g:\n\n", cutoff);igraph_distances_cutoff(&graph, &res,igraph_vss_all(),igraph_vss_all(), IGRAPH_OUT, cutoff);igraph_matrix_print(&res);printf("\nWeighted distances:\n\n");igraph_vector_view(&weights, weights_data,sizeof(weights_data) /sizeof(weights_data[0]));igraph_distances_dijkstra(&graph, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT);igraph_matrix_print(&res); cutoff = 8;/* distances longer than this will be returned as infinity */printf("\nWeighted distances with a cutoff of %g:\n\n", cutoff);igraph_distances_dijkstra_cutoff(&graph, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT, cutoff);igraph_matrix_print(&res);igraph_matrix_destroy(&res);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_distances_cutoff(const igraph_t *graph, igraph_matrix_t *res, const igraph_vs_t from, const igraph_vs_t to, igraph_neimode_t mode, igraph_real_t cutoff);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
This function is similar toigraph_distances(), butpaths longer thancutoff will not be considered.
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._d | ||||||
| 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:
| ||||||
| The maximal length of paths that will be considered. When the distance of two vertices is greater than this value, it will be returned as |
Returns:
Error code:
|
Time complexity: O(s |E| + |V|), where s is the number of source vertices to use,and |V| and |E| are the number of vertices and edges in the graph.
See also:
|
Example 13.2. Fileexamples/simple/distances.c
#include <igraph.h>intmain(void) { igraph_t graph;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_real_t cutoff;igraph_small(&graph, 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_matrix_init(&res, 0, 0);printf("Unweighted distances:\n\n");igraph_distances(&graph, &res,igraph_vss_all(),igraph_vss_all(), IGRAPH_OUT);igraph_matrix_print(&res); cutoff = 3;/* distances longer than this will be returned as infinity */printf("\nUnweighted distances with a cutoff of %g:\n\n", cutoff);igraph_distances_cutoff(&graph, &res,igraph_vss_all(),igraph_vss_all(), IGRAPH_OUT, cutoff);igraph_matrix_print(&res);printf("\nWeighted distances:\n\n");igraph_vector_view(&weights, weights_data,sizeof(weights_data) /sizeof(weights_data[0]));igraph_distances_dijkstra(&graph, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT);igraph_matrix_print(&res); cutoff = 8;/* distances longer than this will be returned as infinity */printf("\nWeighted distances with a cutoff of %g:\n\n", cutoff);igraph_distances_dijkstra_cutoff(&graph, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT, cutoff);igraph_matrix_print(&res);igraph_matrix_destroy(&res);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_distances_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, which can findthe weighted shortest path lengths from a source vertex to allother vertices. This function allows specifying a set of sourceand target vertices. The algorithm is run independently for eachsource and the results are retained only for the specified targets.This implementation uses a binary heap for efficiency.
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|V|+|V|), where |V| is the number ofvertices, |E| the number of edges and s the number of sources.
See also:
|
Example 13.3. Fileexamples/simple/distances.c
#include <igraph.h>intmain(void) { igraph_t graph;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_real_t cutoff;igraph_small(&graph, 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_matrix_init(&res, 0, 0);printf("Unweighted distances:\n\n");igraph_distances(&graph, &res,igraph_vss_all(),igraph_vss_all(), IGRAPH_OUT);igraph_matrix_print(&res); cutoff = 3;/* distances longer than this will be returned as infinity */printf("\nUnweighted distances with a cutoff of %g:\n\n", cutoff);igraph_distances_cutoff(&graph, &res,igraph_vss_all(),igraph_vss_all(), IGRAPH_OUT, cutoff);igraph_matrix_print(&res);printf("\nWeighted distances:\n\n");igraph_vector_view(&weights, weights_data,sizeof(weights_data) /sizeof(weights_data[0]));igraph_distances_dijkstra(&graph, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT);igraph_matrix_print(&res); cutoff = 8;/* distances longer than this will be returned as infinity */printf("\nWeighted distances with a cutoff of %g:\n\n", cutoff);igraph_distances_dijkstra_cutoff(&graph, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT, cutoff);igraph_matrix_print(&res);igraph_matrix_destroy(&res);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_distances_dijkstra_cutoff(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, igraph_real_t cutoff);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
This function is similar toigraph_distances_dijkstra(), butpaths longer thancutoff will not be considered.
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 ( |
| The maximal length of paths that will be considered. When the distance of two vertices is greater than this value, it will be returned as |
Returns:
Error code. |
Time complexity: at most O(s |E| log|V| + |V|), where |V| is the number ofvertices, |E| the number of edges and s the number of sources. Thecutoff parameter will limit the number of edges traversed from eachsource vertex, which reduces the computation time.
See also:
|
Example 13.4. Fileexamples/simple/distances.c
#include <igraph.h>intmain(void) { igraph_t graph;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_real_t cutoff;igraph_small(&graph, 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_matrix_init(&res, 0, 0);printf("Unweighted distances:\n\n");igraph_distances(&graph, &res,igraph_vss_all(),igraph_vss_all(), IGRAPH_OUT);igraph_matrix_print(&res); cutoff = 3;/* distances longer than this will be returned as infinity */printf("\nUnweighted distances with a cutoff of %g:\n\n", cutoff);igraph_distances_cutoff(&graph, &res,igraph_vss_all(),igraph_vss_all(), IGRAPH_OUT, cutoff);igraph_matrix_print(&res);printf("\nWeighted distances:\n\n");igraph_vector_view(&weights, weights_data,sizeof(weights_data) /sizeof(weights_data[0]));igraph_distances_dijkstra(&graph, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT);igraph_matrix_print(&res); cutoff = 8;/* distances longer than this will be returned as infinity */printf("\nWeighted distances with a cutoff of %g:\n\n", cutoff);igraph_distances_dijkstra_cutoff(&graph, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT, cutoff);igraph_matrix_print(&res);igraph_matrix_destroy(&res);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_distances_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 weightedshortest paths to all vertices from a single source, allowing negative weights.It is run independently for the given sources. If there are no negativeweights, you are better off withigraph_distances_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. |
| The edge weights. There must not be any cycle 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 cycle 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 ofvertices, |E| the number of edges and s the number of sources.
See also:
|
Example 13.5. Fileexamples/simple/bellman_ford.c
#include <igraph.h>intmain(void) { 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(weights_data_0[0]));igraph_matrix_init(&res, 0, 0);igraph_distances_bellman_ford(&g, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT);igraph_matrix_print(&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(weights_data_1[0]));igraph_matrix_init(&res, 0, 0);igraph_distances_bellman_ford(&g, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT);igraph_matrix_print(&res);/***************************************//* Same graph with negative cycle */igraph_set_error_handler(igraph_error_handler_ignore);igraph_vector_view(&weights, weights_data_2,sizeof(weights_data_2) /sizeof(weights_data_2[0]));if (igraph_distances_bellman_ford(&g, &res,igraph_vss_all(),igraph_vss_all(), &weights, IGRAPH_OUT) != IGRAPH_ENEGCYCLE) {return 1; }igraph_matrix_destroy(&res);igraph_destroy(&g);if (!IGRAPH_FINALLY_STACK_EMPTY) {return 1; }return 0;}
igraph_error_t igraph_distances_johnson(const igraph_t *graph, igraph_matrix_t *res, const igraph_vs_t from, const igraph_vs_t to, const igraph_vector_t *weights);
This algorithm supports directed graphs with negative edge weights, and performsbetter than the Bellman-Ford method when distances are calculated from many differentsources, the typical use case being all-pairs distance calculations. It works by usinga single-source Bellman-Ford run to transform all edge weights to non-negative ones,then invoking Dijkstra's algorithm with the new weights. See the Wikipedia pagefor more details:http://en.wikipedia.org/wiki/Johnson's_algorithm.
If no edge weights are supplied, then the unweighted version,igraph_distances()is called. If none of the supplied edge weights are negative, then Dijkstra's algorithmis used by callingigraph_distances_dijkstra().
Note that Johnson's algorithm applies only to directed graphs. This function rejectsundirected graphs withany negative edge weights, even when thefrom andtovertices are all in connected components that are free of negative weights.
References:
Donald B. Johnson: Efficient Algorithms for Shortest Paths in Sparse Networks.J. ACM 24, 1 (1977), 1–13.https://doi.org/10.1145/321992.321993
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 numberof vertices and edges, s is the number of source vertices.
See also:
|
igraph_error_t igraph_distances_floyd_warshall( const igraph_t *graph, igraph_matrix_t *res, igraph_vs_t from, igraph_vs_t to, const igraph_vector_t *weights, igraph_neimode_t mode, const igraph_floyd_warshall_algorithm_t method);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
The Floyd-Warshall algorithm computes weighted shortest path lengths betweenall pairs of vertices at the same time. It is useful with very dense weighted graphs,as its running time is primarily determined by the vertex count, and is not sensitiveto the graph density. In sparse graphs, other methods such as the Dijkstra orBellman-Ford algorithms will perform significantly better.
In addition to the original Floyd-Warshall algorithm, igraph contains implementationsof variants that offer better asymptotic complexity as well as better practicalrunning times for most instances. See the reference below for more information.
Note that internally this function always computes the distance matrixfor all pairs of vertices. Thefrom andto parameters only serveto subset this matrix, but do not affect the time or memory taken by thecalculation.
Reference:
Brodnik, A., Grgurovič, M., Požar, R.:Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time,Ars Mathematica Contemporanea, vol. 22, issue 1, p. #P1.01 (2021).https://doi.org/10.26493/1855-3974.2467.497
Arguments:
| The graph object. | ||||||
| An intialized matrix, the distances will be stored here. | ||||||
| The source vertices. | ||||||
| The target vertices. | ||||||
| The edge weights. If | ||||||
| The type of shortest paths to be use for the calculation in directed graphs. Possible values:
| ||||||
| The type of the algorithm used.
|
Returns:
Error code. |
See also:
|
Time complexity:The original variant has complexity O(|V|^3 + |E|).The "Tree" variant has expected-case complexity of O(|V|^2 log^2 |V|)according to Brodnik et al., while its worst-time complexity remains O(|V|^3).Here |V| denotes the number of vertices and |E| is the number of edges.
igraph_error_t igraph_get_shortest_paths(const igraph_t *graph, igraph_vector_int_list_t *vertices, igraph_vector_int_list_t *edges, igraph_integer_t from, const igraph_vs_t to, igraph_neimode_t mode, igraph_vector_int_t *parents, igraph_vector_int_t *inbound_edges);
Finds unweighted shortest paths from a single source vertex to the specifiedsets of target vertices. If there is more than one geodesic between two vertices,this function gives only one of them. Useigraph_get_all_shortest_paths()to findall shortest paths.
Arguments:
| The graph object. | ||||||
| The result, the IDs of the vertices along the paths. This is a list of integer vectors where each element is an | ||||||
| The result, the IDs of the edges along the paths. This is a list of integer vectors where each element is an | ||||||
| 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 | ||||||
| A pointer to an initialized igraph vector or |
Returns:
Error code:
|
Time complexity: O(|V|+|E|),|V| is the number of vertices,|E| the number of edges in thegraph.
See also:
|
Example 13.6. Fileexamples/simple/igraph_get_shortest_paths.c
#include <igraph.h>#include <stdlib.h>intcheck_evecs(const igraph_t *graph,const igraph_vector_int_list_t *vecs,const igraph_vector_int_list_t *evecs, int error_code) { igraph_bool_t directed =igraph_is_directed(graph); igraph_integer_t i, n =igraph_vector_int_list_size(vecs);if (igraph_vector_int_list_size(evecs) != n) {exit(error_code + 1); }for (i = 0; i < n; i++) { igraph_vector_int_t *vvec =igraph_vector_int_list_get_ptr(vecs, i); igraph_vector_int_t *evec =igraph_vector_int_list_get_ptr(evecs, i); igraph_integer_t j, n2 =igraph_vector_int_size(evec);if (igraph_vector_int_size(vvec) == 0 && n2 == 0) {continue; }if (igraph_vector_int_size(vvec) != n2 + 1) {exit(error_code + 2); }for (j = 0; j < n2; j++) { igraph_integer_t edge =VECTOR(*evec)[j]; igraph_integer_t from =VECTOR(*vvec)[j]; igraph_integer_t to =VECTOR(*vvec)[j + 1];if (directed) {if (from !=IGRAPH_FROM(graph, edge) || to !=IGRAPH_TO (graph, edge)) {exit(error_code); } }else { igraph_integer_t from2 =IGRAPH_FROM(graph, edge); igraph_integer_t to2 =IGRAPH_TO(graph, edge); igraph_integer_t min1 = from < to ? from : to; igraph_integer_t max1 = from < to ? to : from; igraph_integer_t min2 = from2 < to2 ? from2 : to2; igraph_integer_t max2 = from2 < to2 ? to2 : from2;if (min1 != min2 || max1 != max2) {exit(error_code + 3); } } } }return 0;}intmain(void) { igraph_t g; igraph_vector_int_list_t vecs, evecs; igraph_vector_int_t parents, inbound; igraph_integer_t i; igraph_vs_t vs;igraph_ring(&g, 10, IGRAPH_DIRECTED, 0, 1);igraph_vector_int_list_init(&vecs, 0);igraph_vector_int_list_init(&evecs, 0);igraph_vector_int_init(&parents, 0);igraph_vector_int_init(&inbound, 0);igraph_vs_vector_small(&vs, 1, 3, 5, 2, 1, -1);igraph_get_shortest_paths(&g, &vecs, &evecs, 0, vs, IGRAPH_OUT, &parents, &inbound);check_evecs(&g, &vecs, &evecs, 10);for (i = 0; i <igraph_vector_int_list_size(&vecs); i++) {igraph_vector_int_print(igraph_vector_int_list_get_ptr(&vecs, i)); }igraph_vector_int_print(&parents);igraph_vector_int_print(&inbound);igraph_vector_int_list_destroy(&vecs);igraph_vector_int_list_destroy(&evecs);igraph_vector_int_destroy(&parents);igraph_vector_int_destroy(&inbound);igraph_vs_destroy(&vs);igraph_destroy(&g);if (!IGRAPH_FINALLY_STACK_EMPTY) {return 1; }return 0;}
igraph_error_t igraph_get_shortest_path(const igraph_t *graph, igraph_vector_int_t *vertices, igraph_vector_int_t *edges, igraph_integer_t from, igraph_integer_t to, igraph_neimode_t mode);
Calculates and returns a single unweighted shortest path from agiven vertex to another one. If there is more than one shortestpath between the two vertices, then an arbitrary one is returned.
This function is a wrapper toigraph_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 initialized 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 andedges in the graph.
See also:
|
igraph_error_t igraph_get_shortest_paths_dijkstra(const igraph_t *graph, igraph_vector_int_list_t *vertices, igraph_vector_int_list_t *edges, igraph_integer_t from, igraph_vs_t to, const igraph_vector_t *weights, igraph_neimode_t mode, igraph_vector_int_t *parents, igraph_vector_int_t *inbound_edges);
Finds weighted shortest paths from a single source vertex to the specifiedsets of target vertices using Dijkstra's algorithm. If there is more thanone path with the smallest weight between two vertices, this function givesonly one of them. To find all such paths, useigraph_get_all_shortest_paths_dijkstra().
Arguments:
| The graph object. | ||||||
| The result, the IDs of the vertices along the paths. This is a list of integer vectors where each element is an | ||||||
| The result, the IDs of the edges along the paths. This is a list of integer vectors where each element is an | ||||||
| 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 parent of each vertex in the single source shortest path tree is returned here. The parent of vertex i in the tree is the vertex from which vertex i was reached. The parent 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|V|+|V|), where |V| is the number ofvertices and |E| is the number of edges
See also:
|
Example 13.7. Fileexamples/simple/igraph_get_shortest_paths_dijkstra.c
#include <igraph.h>#include <stdlib.h>intmain(void) { igraph_t g; igraph_vector_int_list_t vecs, evecs; igraph_vector_int_t parents, inbound; igraph_integer_t i; igraph_real_t weights[] = { 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;igraph_vector_int_list_init(&vecs, 0);igraph_vector_int_list_init(&evecs, 0);igraph_vector_int_init(&parents, 0);igraph_vector_int_init(&inbound, 0);igraph_vs_vector_small(&vs, 0, 1, 3, 5, 2, 1, -1);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, weights,sizeof(weights) /sizeof(weights[0]));igraph_get_shortest_paths_dijkstra(&g,/*vertices=*/ &vecs,/*edges=*/ &evecs,/*from=*/ 0,/*to=*/ vs, &weights_vec, IGRAPH_OUT, &parents,/*inbound_edges=*/ &inbound);printf("Vertices:\n");for (i = 0; i <igraph_vector_int_list_size(&vecs); i++) {igraph_vector_int_print(igraph_vector_int_list_get_ptr(&vecs, i)); }printf("\nEdges:\n");for (i = 0; i <igraph_vector_int_list_size(&evecs); i++) {igraph_vector_int_print(igraph_vector_int_list_get_ptr(&evecs, i)); }printf("\nParents:\n");igraph_vector_int_print(&parents);printf("\nInbound:\n");igraph_vector_int_print(&inbound);igraph_vector_int_list_destroy(&vecs);igraph_vector_int_list_destroy(&evecs);igraph_vector_int_destroy(&parents);igraph_vector_int_destroy(&inbound);igraph_vs_destroy(&vs);igraph_destroy(&g);return 0;}
igraph_error_t igraph_get_shortest_path_dijkstra(const igraph_t *graph, igraph_vector_int_t *vertices, igraph_vector_int_t *edges, igraph_integer_t from, igraph_integer_t to, const igraph_vector_t *weights, igraph_neimode_t mode);
Finds a weighted shortest path from a single source vertex toa single target, using Dijkstra's algorithm. If more than oneshortest path exists, an arbitrary one is returned.
This function is a special case (and a wrapper) toigraph_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 initialized 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|V|+|V|), |V| is the number of vertices,|E| is the number of edges in the graph.
See also:
|
igraph_error_t igraph_get_shortest_paths_bellman_ford(const igraph_t *graph, igraph_vector_int_list_t *vertices, igraph_vector_int_list_t *edges, igraph_integer_t from, igraph_vs_t to, const igraph_vector_t *weights, igraph_neimode_t mode, igraph_vector_int_t *parents, igraph_vector_int_t *inbound_edges);
This function calculates weighted shortest paths from or to a single vertexusing the Bellman-Ford algorithm, whihc can handle negative weights. Whenthere is more than one shortest path between two vertices, only one of themis returned. When there are no negative weights,igraph_get_shortest_paths_dijkstra() is likely to be faster.
Arguments:
| The input graph, can be directed. |
| The result, the IDs of the vertices along the paths. This is a list of integer vectors where each element is an |
| The result, the IDs of the edges along the paths. This is a list of integer vectors where each element is an |
| 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 must not be any cycle 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 cycle 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 parent of each vertex in the single source shortest path tree is returned here. The parent of vertex i in the tree is the vertex from which vertex i was reached. The parent 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 ofvertices, |E| the number of edges.
See also:
|
igraph_error_t igraph_get_shortest_path_bellman_ford(const igraph_t *graph, igraph_vector_int_t *vertices, igraph_vector_int_t *edges, igraph_integer_t from, igraph_integer_t to, const igraph_vector_t *weights, igraph_neimode_t mode);
Finds a weighted shortest path from a single source vertex toa single target using the Bellman-Ford algorithm.
This function is a special case (and a wrapper) toigraph_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 initialized 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 must not be any cycle 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 cycle 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:
|
igraph_error_t igraph_get_shortest_path_astar(const igraph_t *graph, igraph_vector_int_t *vertices, igraph_vector_int_t *edges, igraph_integer_t from, igraph_integer_t to, const igraph_vector_t *weights, igraph_neimode_t mode, igraph_astar_heuristic_func_t *heuristic, void *extra);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Calculates a shortest path from a single source vertex to a singletarget, using the A* algorithm. A* tries to find a shortest path bystarting atfrom and moving to vertices that lie on a path withthe lowest estimated length. This length estimate is the sum of twonumbers: the distance from the source (from) to the intermediate vertex,and the value returned by the heuristic function. The heuristic functionprovides an estimate the distance between intermediate candidatevertices and the target vertexto. The A* algorithm is guaranteedto give the correct shortest path (if one exists) only if the heuristicdoes not overestimate distances, i.e. if the heuristic function isadmissible.
Arguments:
| The input graph, it can be directed or undirected. |
| Pointer to an initialized vector or the |
| Pointer to an initialized vector or the |
| The ID of the source vertex. |
| The ID of the target vertex. |
| Optional edge weights. Supply |
| A constant specifying how edge directions are considered in directed graphs. |
| A function that provides distance estimates to the target vertex. See |
| This is passed on to the heuristic function. |
Returns:
Error code. |
Time complexity: In the worst case, O(|E|log|V|+|V|), where|V| is the number of vertices and|E| is the number of edges in the graph.The running time depends on the accuracy of the distance estimatesreturned by the heuristic function. Assuming that the heuristicis admissible, the better the estimates, the shortert the runningtime.
typedef igraph_error_t igraph_astar_heuristic_func_t( igraph_real_t *result, igraph_integer_t from, igraph_integer_t to, void *extra);
igraph_get_shortest_path_astar() uses a heuristic based on a distanceestimate to the target vertex to guide its search, and determinewhich vertex to try next. The heuristic function is expected to computean estimate of the distance betweenfrom andto. In order forigraph_get_shortest_path_astar() to find an exact shortest path,the distance must not be overestimated, i.e. the heuristic functionmust beadmissible.
Arguments:
| The result of the heuristic, i.e. the estimated distance. A lower value will mean this vertex will be a better candidate for exploration. |
| The vertex ID of the candidate vertex will be passed here. |
| The vertex ID of the endpoint of the path, i.e. the |
| The |
Returns:
Error code. Must return |
See also:
igraph_error_t igraph_get_all_shortest_paths(const igraph_t *graph, igraph_vector_int_list_t *vertices, igraph_vector_int_list_t *edges, igraph_vector_int_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. Every edge is considered separately,therefore in graphs with multi-edges, this function may producea very large number of results.
Arguments:
| The graph object. | ||||||
| The result, the IDs of the vertices along the paths. This is a list of integer vectors where each element is an | ||||||
| The result, the IDs of the edges along the paths. This is a list of integer vectors where each element is an | ||||||
| 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 worstcase.
igraph_error_t igraph_get_all_shortest_paths_dijkstra(const igraph_t *graph, igraph_vector_int_list_t *vertices, igraph_vector_int_list_t *edges, igraph_vector_int_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 integer vector list or NULL. If not NULL, then each vector object contains the vertices along a shortest path from | ||||||
| Pointer to an initialized integer vector list or NULL. If not NULL, then each vector object contains the edges along a shortest path from | ||||||
| Pointer to an initialized igraph_vector_int_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|V|+|V|), where |V| is the number ofvertices and |E| is the number of edges
See also:
|
Example 13.8. Fileexamples/simple/igraph_get_all_shortest_paths_dijkstra.c
#include <igraph.h>#include <stdlib.h>voidprint_and_destroy_items(igraph_vector_int_list_t* vec) { igraph_integer_t i;/* Sort the paths in a deterministic manner to avoid problems with * different qsort() implementations on different platforms */igraph_vector_int_list_sort(vec, igraph_vector_int_colex_cmp);for (i = 0; i <igraph_vector_int_list_size(vec); i++) {igraph_vector_int_print(igraph_vector_int_list_get_ptr(vec, i)); }igraph_vector_int_list_destroy(vec);}intmain(void) { igraph_t g; igraph_vector_int_list_t vertices, edges; igraph_real_t weights[] = { 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_vector_int_t nrgeo; igraph_vs_t vs;igraph_vector_int_list_init(&vertices, 0);igraph_vector_int_list_init(&edges, 0);igraph_vs_vector_small(&vs, 1, 3, 4, 5, 2, 1, -1);igraph_vector_int_init(&nrgeo, 0);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, weights,sizeof(weights) /sizeof(weights[0]));igraph_get_all_shortest_paths_dijkstra( &g,/*vertices=*/ &vertices,/*edges=*/ &edges,/*nrgeo=*/ &nrgeo,/*from=*/ 0,/*to=*/ vs,/*weights=*/ &weights_vec,/*mode=*/ IGRAPH_OUT);printf("Vertices:\n");print_and_destroy_items(&vertices);printf("\nEdges:\n");print_and_destroy_items(&edges);printf("\nNumber of geodesics:\n");igraph_vector_int_print(&nrgeo);igraph_vector_int_destroy(&nrgeo);igraph_vs_destroy(&vs);igraph_destroy(&g);return 0;}
igraph_error_t igraph_get_k_shortest_paths( const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_int_list_t *vertex_paths, igraph_vector_int_list_t *edge_paths, igraph_integer_t k, igraph_integer_t from, igraph_integer_t to, igraph_neimode_t mode);
This function returns thek shortest paths between two vertices, in order ofincreasing lengths.
Reference:
Yen, Jin Y.:An algorithm for finding shortest routes from all source nodes to a givendestination in general networks.Quarterly of Applied Mathematics. 27 (4): 526–530. (1970)https://doi.org/10.1090/qam/253822
Arguments:
| The graph object. | ||||||
| The edge weights of the graph. Can be | ||||||
| Pointer to an initialized list of integer vectors, the result will be stored here in | ||||||
| Pointer to an initialized list of integer vectors, the result will be stored here in | ||||||
| The number of paths. | ||||||
| The ID of the vertex from which the paths are calculated. | ||||||
| The ID of the vertex to which the paths are calculated. | ||||||
| The type of paths to be used for the calculation in directed graphs. Possible values:
|
Returns:
Error code:
|
Time complexity: k |V| (|V| log|V| + |E|), where |V| is the number of vertices,and |E| is the number of edges.
See also:
igraph_error_t 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 vertexis visited more than once.
Note that potentially there are exponentially manypaths between two vertices of a graph, and you mayrun out of memory when using this function when thegraph has many cycles. Consider using thecutoffparameter when you do not need long paths.
Arguments:
| The input graph. |
| Initialized integer vector. The paths are returned here in terms of their vertices, separated by |
| 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. |
See also:
Time complexity: O(n!) in the worst case, n is the number ofvertices.
igraph_error_t 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 becausethe graph has fewer than two vertices, or if the graph has no edges andunconn is set totrue, 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.9. Fileexamples/simple/igraph_average_path_length.c
#include <igraph.h>intmain(void) { 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;}
igraph_error_t 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 graphhas fewer than two vertices, or if the graph has no edges andunconn is set totrue,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 ofvertices and |E| is the number of edges.
See also:
|
Example 13.10. Fileexamples/simple/igraph_grg_game.c
#include <igraph.h>#include <math.h>intmain(void) { 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)) { igraph_integer_t e =IGRAPH_EIT_GET(eit); igraph_integer_t u =IGRAPH_FROM(&graph, e); igraph_integer_t 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;}
igraph_error_t 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 pathlength between all pairs of vertices. In directed graphs, both directionsare considered, meaning that each vertex pair appears twice in the histogram.
Arguments:
| The input graph. |
| Pointer to an initialized vector, the result is stored here. The first (i.e. index 0) element contains the number of shortest paths of length 1, the second of length 2, etc. The supplied vector is resized as needed. |
| Pointer to a real number, the number of vertex pairs for which the second vertex is not reachable from the first is stored here. |
| Whether to consider directed paths in a directed graph. This argument is ignored for undirected graphs. |
Returns:
Error code. |
Time complexity: O(|V||E|), the number of vertices times the numberof edges.
See also:
igraph_error_t igraph_diameter(const igraph_t *graph, igraph_real_t *res, igraph_integer_t *from, igraph_integer_t *to, igraph_vector_int_t *vertex_path, igraph_vector_int_t *edge_path, igraph_bool_t directed, igraph_bool_t unconn);
The diameter of a graph is the length of the longest shortest path it has,i.e. the maximum eccentricity of the graph's vertices.This function computes both the diameter, as well as a 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 |
| 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|), thenumber of vertices times the number of edges.
See also:
|
Example 13.11. Fileexamples/simple/igraph_diameter.c
#include <igraph.h>voidprint_vector_int(igraph_vector_int_t *v) { igraph_integer_t i, n =igraph_vector_int_size(v);for (i = 0; i < n; i++) {printf(" %" IGRAPH_PRId,VECTOR(*v)[i]); }printf("\n");}intmain(void) { igraph_t g; igraph_real_t result; igraph_integer_t from, to; igraph_vector_int_t path, path_edge;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, 0, IGRAPH_UNDIRECTED, 1);/* printf("Diameter: %" IGRAPH_PRId "\n", (igraph_integer_t) result); */igraph_destroy(&g);igraph_ring(&g, 10, IGRAPH_DIRECTED, 0, 0);igraph_vector_int_init(&path, 0);igraph_vector_int_init(&path_edge, 0);igraph_diameter(&g, &result, &from, &to, &path, &path_edge, IGRAPH_DIRECTED, 1);printf( "diameter: %" IGRAPH_PRId ", from %" IGRAPH_PRId " to %" IGRAPH_PRId "\n", (igraph_integer_t) result, from, to );print_vector_int(&path);print_vector_int(&path_edge);igraph_vector_int_destroy(&path);igraph_vector_int_destroy(&path_edge);igraph_destroy(&g);return 0;}
igraph_error_t igraph_diameter_dijkstra(const igraph_t *graph, const igraph_vector_t *weights, igraph_real_t *res, igraph_integer_t *from, igraph_integer_t *to, igraph_vector_int_t *vertex_path, igraph_vector_int_t *edge_path, igraph_bool_t directed, igraph_bool_t unconn);
This function computes the weighted diameter of a graph, defined as the longestweighted shortest path, or the maximum weighted eccentricity of the graph'svertices. A corresponding shortest path, as well as its endpoints,can also be optionally computed.
If the graph has no vertices,IGRAPH_NAN is returned.
Arguments:
| The input graph, can be directed or undirected. |
| The edge weights of the graph. Can be |
| 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 |
| 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:
|
igraph_error_t igraph_girth(const igraph_t *graph, igraph_real_t *girth, igraph_vector_int_t *circle);
The current implementation works for undirected graphs only,directed graphs are treated as undirected graphs. Self-loops andmultiple edges are ignored, i.e. cycles of length 1 or 2 arenot considered.
For graphs that contain no cycles, and only for such graphs,infinity is returned.
The first implementation of this function was done by Keith Briggs,thanks Keith.
Reference:
Alon Itai and Michael Rodeh:Finding a minimum circuit in a graph Proceedings of the ninth annual ACM symposium on Theory ofcomputing, 1-10, 1977.https://doi.org/10.1145/800105.803390
Arguments:
| The input graph. Edge directions will be ignored. |
| Pointer to an |
| 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 nocycles at all then the function needs O(|V|+|E|) time to realizethis and then it stops.
Example 13.12. Fileexamples/simple/igraph_girth.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_real_t girth; igraph_vector_int_t v; igraph_vector_int_t circle; igraph_integer_t chord[] = { 0, 50 };igraph_ring(&g, 100, IGRAPH_UNDIRECTED, 0, 1);igraph_vector_int_view(&v, chord,sizeof(chord) /sizeof(chord[0]));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_int_init(&circle, 1);VECTOR(circle)[0] = 2;igraph_girth(&g, &girth, &circle);if (girth != IGRAPH_INFINITY) {return 2; }if (igraph_vector_int_size(&circle) != 0) {return 3; }igraph_vector_int_destroy(&circle);igraph_destroy(&g);return 0;}
igraph_error_t 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 shortestdistance from (or to) the vertex, to (or from) all vertices in thegraph, and taking the maximum.
This implementation ignores vertex pairs that are in differentcomponents. 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(|S| (|V|+|E|)), where |V| is the number ofvertices, |E| is the number of edges and |S| is the number ofvertices for which eccentricity is calculated.
See also:
Example 13.13. Fileexamples/simple/igraph_eccentricity.c
#include <igraph.h>intmain(void) { 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;}
igraph_error_t igraph_eccentricity_dijkstra(const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_t *res, igraph_vs_t vids, igraph_neimode_t mode);
The eccentricity of a vertex is calculated by measuring the shortestdistance from (or to) the vertex, to (or from) all vertices in thegraph, and taking the maximum.
This implementation ignores vertex pairs that are in differentcomponents. Isolated vertices have eccentricity zero.
Arguments:
| The input graph, it can be directed or undirected. |
| 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, |
| 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| |E| log|V| + |V|), where |V| is the number ofvertices, |E| the number of edges.
igraph_error_t 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 ofits vertices, seeigraph_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 ofvertices and |E| is the number of edges.
See also:
|
Example 13.14. Fileexamples/simple/igraph_radius.c
#include <igraph.h>intmain(void) { 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;}
igraph_error_t igraph_radius_dijkstra(const igraph_t *graph, const igraph_vector_t *weights, igraph_real_t *radius, igraph_neimode_t mode);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
The radius of a graph is the defined as the minimum eccentricity ofits vertices, seeigraph_eccentricity().
Arguments:
| The input graph, it can be directed or undirected. |
| 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, |
| 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| |E| log|V| + |V|), where |V| is the number ofvertices, |E| the number of edges.
See also:
|
igraph_error_t igraph_graph_center( const igraph_t *graph, igraph_vector_int_t *res, igraph_neimode_t mode);
The central vertices of a graph are calculated by finding the verticeswith the minimum eccentricity. This concept is typically applied to(strongly) connected graphs. In disconnected graphs, the smallesteccentricity is taken across all components.
Arguments:
| The input graph, it can be directed or undirected. |
| Pointer to an initialized vector, 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 ofvertices and |E| is the number of edges.
See also:
igraph_error_t igraph_graph_center_dijkstra( const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_int_t *res, igraph_neimode_t mode);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
The central vertices of a graph are calculated by finding the verticeswith the minimum eccentricity. This function takes edge weights intoaccount and uses Dijkstra's algorithm for the shortest path calculation.The concept of the graph center is typically applied to(strongly) connected graphs. In disconnected graphs, the smallesteccentricity is taken across all components.
Arguments:
| The input graph, it can be directed or undirected. |
| 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, |
| Pointer to an initialized vector, the result is stored here. |
| What kind of paths to consider for the calculation: |
Returns:
Error code. |
Time complexity: O(|V| |E| log|V| + |V|), where |V| is the number ofvertices, |E| the number of edges.
See also:
igraph_error_t igraph_pseudo_diameter(const igraph_t *graph, igraph_real_t *diameter, igraph_integer_t vid_start, igraph_integer_t *from, igraph_integer_t *to, igraph_bool_t directed, igraph_bool_t unconn);
This algorithm finds a pseudo-peripheral vertex and returns itseccentricity. This value can be used as an approximationand lower bound of the diameter of a graph.
A pseudo-peripheral vertex is a vertex v, such that for everyvertex u which is as far away from v as possible, v is also asfar away from u as possible. The process of finding one dependson where the search starts, and for a disconnected graph themaximum diameter found will be that of the componentvid_startis in.
Arguments:
| The input graph, if it is directed, its edge directions are ignored. |
| Pointer to a real variable, the result is stored here. |
| Id of the starting vertex. If this is negative, a random starting vertex is chosen. |
| Pointer to an integer, if not |
| Pointer to an integer, 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|)), where |V| is the number ofvertices and |E| is the number of edges.
See also:
igraph_error_t igraph_pseudo_diameter_dijkstra(const igraph_t *graph, const igraph_vector_t *weights, igraph_real_t *diameter, igraph_integer_t vid_start, igraph_integer_t *from, igraph_integer_t *to, igraph_bool_t directed, igraph_bool_t unconn);
This algorithm finds a pseudo-peripheral vertex and returns itsweighted eccentricity. This value can be used as an approximationand lower bound of the diameter of a graph.
A pseudo-peripheral vertex is a vertex v, such that for everyvertex u which is as far away from v as possible, v is also asfar away from u as possible. The process of finding one dependson where the search starts, and for a disconnected graph themaximum diameter found will be that of the componentvid_startis in.
If the graph has no vertices,IGRAPH_NAN is returned.
Arguments:
| The input graph, can be directed or undirected. |
| The edge weights of the graph. Can be |
| This will contain the weighted pseudo-diameter. |
| Id of the starting vertex. If this is negative, a random starting vertex is chosen. |
| If not |
| 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:
igraph_error_t igraph_voronoi( const igraph_t *graph, igraph_vector_int_t *membership, igraph_vector_t *distances, const igraph_vector_int_t *generators, const igraph_vector_t *weights, igraph_neimode_t mode, igraph_voronoi_tiebreaker_t tiebreaker);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
To obtain a Voronoi partitioning of a graph, we start with a set of generatorvertices, which will define the partitions. Each vertex is assigned to the generatorvertex from (or to) which it is closest.
This function uses a BFS search for unweighted graphs and Dijkstra's algorithmfor weights ones.
Arguments:
| The graph to partition. | ||||||
| If not | ||||||
| If not | ||||||
| Vertex IDs of the generator vertices. | ||||||
| The edge weights, interpreted as lengths in the shortest path calculation. All weights must be non-negative. | ||||||
| In directed graphs, whether to compute distancesfrom generator vertices to other vertices ( | ||||||
| Controls which generator vertex to assign a vertex to when it is at equal distance from/to multiple generator vertices.
Note that |
Returns:
Error code. |
Time complexity: In weighted graphs, O((log |S|) |E| (log |V|) + |V|), and inunweighted graphs O((log |S|) |E| + |V|), where |S| is the number of generatorvertices, and |V| and |E| are the number of vertices and edges in the graph.
See also:
igraph_error_t igraph_vertex_path_from_edge_path( const igraph_t *graph, igraph_integer_t start, const igraph_vector_int_t *edge_path, igraph_vector_int_t *vertex_path, igraph_neimode_t mode);
This function is useful when you have a sequence of edge IDs representing acontinuous walk in a graph and you would like to obtain the vertex IDs thatthe walk traverses. The function is used implicitly by several shortest pathrelated functions to convert a path of edge IDs to the correspondingrepresentation that describes the path in terms of vertex IDs instead.
The result will always contain one more vertex than the number of providededges. If no edges are given, the output will contain only the start vertex.
The walk is allowed to traverse the same vertex more than once. It issuitable for use on paths, cycles, or arbitrary walks.
Arguments:
| The graph that the edge IDs refer to. |
| The start vertex of the path. If negative, it is determined automatically. This is only possible if the walk contains at least one edge. If only one edge is present in an undirected walk, one of its endpoints will be selected arbitrarily. |
| The sequence of edge IDs that describe the path. |
| The sequence of vertex IDs traversed will be returned here. |
| A constant specifying how edge directions are considered in directed graphs. |
Returns:
Error code: |
Time complexity: O(n) where n is the length of the walk.
igraph_get_widest_path — Widest path from one vertex to another one.igraph_get_widest_paths — Widest paths from a single vertex.igraph_widest_path_widths_dijkstra — Widths of widest paths between vertices.igraph_widest_path_widths_floyd_warshall — Widths of widest paths between vertices.igraph_error_t igraph_get_widest_path(const igraph_t *graph, igraph_vector_int_t *vertices, igraph_vector_int_t *edges, igraph_integer_t from, igraph_integer_t to, const igraph_vector_t *weights, igraph_neimode_t mode);
Calculates a single widest path from a single vertex to anotherone, using Dijkstra's algorithm.
This function is a special case (and a wrapper) toigraph_get_widest_paths().
Arguments:
| The input graph, it can be directed or undirected. | ||||||
| Pointer to an initialized vector or | ||||||
| Pointer to an initialized vector or | ||||||
| The ID of the source vertex. | ||||||
| The ID of the target vertex. | ||||||
| The edge weights, interpreted as widths. Edge weights can be negative, but must not be NaN. Edges with negative infinite weight are ignored. The weight vector is required: if | ||||||
| The type of widest paths to be used for the calculation in directed graphs. Possible values:
|
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:
|
igraph_error_t igraph_get_widest_paths(const igraph_t *graph, igraph_vector_int_list_t *vertices, igraph_vector_int_list_t *edges, igraph_integer_t from, igraph_vs_t to, const igraph_vector_t *weights, igraph_neimode_t mode, igraph_vector_int_t *parents, igraph_vector_int_t *inbound_edges);
Calculates the widest paths from a single vertex to all other specifiedvertices, using a modified Dijkstra's algorithm. The width of a path isdefined as the width of the narrowest edge in the path.If there is more thanone path with the largest width between two vertices, this function givesonly one of them.
Arguments:
| The graph object. | ||||||
| The result, the IDs of the vertices along the paths. This is a list of integer vectors where each element is an | ||||||
| The result, the IDs of the edges along the paths. This is a list of integer vectors where each element is an | ||||||
| The ID of the vertex from/to which the widest paths are calculated. | ||||||
| Vertex sequence with the IDs of the vertices to/from which the widest paths will be calculated. A vertex may be given multiple times. | ||||||
| The edge weights, interpreted as widths. Edge weights can be negative, but must not be NaN. Edges with negative infinite weight are ignored. The weight vector is required: if | ||||||
| The type of widest 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 parent of each vertex in the single source widest path tree is returned here. The parent of vertex | ||||||
| A pointer to an initialized igraph vector or |
Returns:
Error code:
|
Time complexity: O(|E|log|E|+|V|), where |V| is the number ofvertices in the graph and |E| is the number of edges
See also:
|
igraph_error_t igraph_widest_path_widths_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 a modified Dijkstra's algorithm, which can findthe widest path widths from a source vertex to all other vertices. The widthof a path is defined as the width of the narrowest edge in the path.
This function allows specifying a set of source and target vertices. Thealgorithm is run independently for each source and the results are retainedonly for the specified targets. This implementation uses a binary heap forefficiency.
Arguments:
| The input graph, can be directed. |
| An initialized matrix, the result will be written here. The matrix will be resized as needed. Each row will contain the widths 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, interpreted as widths. Edge weights can be negative, but must not be NaN. Edges with negative infinite weight are ignored. The weight vector is required: if |
| 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 ofvertices in the graph, |E| the number of edges and s the number of sources.
See also:
|
igraph_error_t igraph_widest_path_widths_floyd_warshall(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 a modified Floyd-Warshall algorithm, to find thewidest path widths between a set of source and target vertices. The widthof a path is defined as the width of the narrowest edge in the path.
This algorithm is primarily useful for all-pairs path widths in very densegraphs, as its running time is manily determined by the vertex count, andis not sensitive to the graph density. In sparse graphs, other methods suchas Dijkstra's algorithm, implemented inigraph_widest_path_widths_dijkstra() will perform better.
Note that internally this function always computes the path width matrixfor all pairs of vertices. Thefrom andto parameters only serveto subset this matrix, but do not affect the time taken by thecalculation.
Arguments:
| The input graph, can be directed. |
| An initialized matrix, the result will be written here. The matrix will be resized as needed. Each row will contain the widths from a single source to the vertices given in the |
| The source vertices. |
| The target vertices. |
| The edge weights, interpreted as widths. Edge weights can be negative, but must not be NaN. Edges with negative infinite weight are ignored. The weight vector is required: if |
| For directed graphs; whether to follow paths along edge directions ( |
Returns:
Error code. |
Time complexity: O(|V|^3), where |V| is the number of vertices in the graph.
See also:
|
igraph_error_t 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 inversedistances between all pairs of vertices:E_g = 1/(N*(N-1)) sum_{i!=j} 1/d_ij,whereN is the number of vertices. The inverse distance between pairsthat are not reachable from each other is considered to be zero. For graphswith 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 andO(|V| |E|) for unweighted ones. |V| denotes the number ofvertices and |E| denotes the number of edges.
See also:
igraph_error_t 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) betweenits neighbours through the rest of the network. The local efficiency around theremoved vertex is the average of the inverse of these distances.
The inverse distance between two vertices which are not reachable from each otheris considered to be zero. The local efficiency around a vertex with fewer than twoneighbours 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 andO(|E|^2) for unweighted ones. |E| denotes the number of edges.
See also:
igraph_error_t 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. Edges with positive infinite weight are ignored. | ||||||
| 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 andO(|E|^2) for unweighted ones. |E| denotes the number of edges.
See also:
igraph_error_t igraph_neighborhood_size(const igraph_t *graph, igraph_vector_int_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 verticeswhich are closer to the vertex than the order. I.e., order 0 isalways the vertex itself, order 1 is the vertex plus its immediateneighbors, order 2 is order 1 plus the immediate neighbors of thevertices in order 1, etc.
This function calculates the size of the neighborhoodof 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. Negative values are treated as infinity. |
| 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 whichthe calculation is performed, d is the average degree, o is the order.
igraph_error_t igraph_neighborhood(const igraph_t *graph, igraph_vector_int_list_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 verticeswhich are closer to the vertex than the order. I.e., order 0 isalways the vertex itself, order 1 is the vertex plus its immediateneighbors, order 2 is order 1 plus the immediate neighbors of thevertices in order 1, etc.
This function calculates the vertices within theneighborhood of the specified vertices.
Arguments:
| The input graph. |
| An initialized list of integer vectors. The result of the calculation will be stored here. The list will be resized as needed. |
| The vertices for which the calculation is performed. |
| Integer giving the order of the neighborhood. Negative values are treated as infinity. |
| 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 whichthe calculation is performed, d is the average degree, o is theorder.
igraph_error_t igraph_neighborhood_graphs(const igraph_t *graph, igraph_graph_list_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 verticeswhich are closer to the vertex than the order. Ie. order 0 isalways the vertex itself, order 1 is the vertex plus its immediateneighbors, order 2 is order 1 plus the immediate neighbors of thevertices in order 1, etc.
This function finds every vertex in the neighborhoodof a given parameter vertex and creates the induced subgraph from thesevertices.
The first version of this function was written byVincent Matossian, thanks Vincent.
Arguments:
| The input graph. |
| Pointer to a list of graphs, the result will be stored here. Each item in the list is anigraph_t object. The list will be resized as needed. |
| The vertices for which the calculation is performed. |
| Integer giving the order of the neighborhood. Negative values are treated as infinity. |
| 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 forwhich the calculation is performed, |V| and |E| are the number ofvertices and edges in the original input graph.
The scan statistic is a summary of the locality statistics that is computedfrom the local neighborhood of each vertex. For details, seePriebe, C. E., Conroy, J. M., Marchette, D. J., Park, Y. (2005).Scan Statistics on Enron Graphs. Computational and Mathematical Organization Theory.
igraph_error_t 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 forunweighted, and the vertex strength for weighted graphs. Seeigraph_degree() andigraph_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. |
igraph_error_t 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 the1-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. |
igraph_error_t igraph_local_scan_k_ecount(const igraph_t *graph, igraph_integer_t 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. |
igraph_error_t 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 forunweighted, and the vertex strength for weighted graphs. Seeigraph_degree() andigraph_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. |
igraph_error_t 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 the1-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:
|
igraph_error_t igraph_local_scan_k_ecount_them(const igraph_t *us, const igraph_t *them, igraph_integer_t 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 thek-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 |
| 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. |
See also:
|
igraph_error_t igraph_local_scan_neighborhood_ecount(const igraph_t *graph, igraph_vector_t *res, const igraph_vector_t *weights, const igraph_vector_int_list_t *neighborhoods);
Count the number of edges, or sum the edge weights inneighborhoods given as a parameter.
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_local_scan_subset_ecount()instead.
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 ofigraph_vector_int_t objects, the neighborhoods, one for each vertex in the graph. |
Returns:
Error code. |
igraph_error_t igraph_local_scan_subset_ecount(const igraph_t *graph, igraph_vector_t *res, const igraph_vector_t *weights, const igraph_vector_int_list_t *subsets);
Count the number of edges, or sum the edge weights ininduced subgraphs from vertices 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 ofigraph_vector_int_t objects, the vertex subsets. |
Returns:
Error code. |
igraph_subcomponent — The vertices reachable from a given vertex.igraph_connected_components — Calculates the (weakly or strongly) connected components in a graph.igraph_clusters — Calculates the (weakly or strongly) connected components in a graph (deprecated alias).igraph_is_connected — Decides whether the graph is (weakly or strongly) connected.igraph_decompose — Decomposes a graph into connected components.igraph_decompose_destroy — Frees the contents of a pointer vector holding graphs.igraph_reachability — Calculates which vertices are reachable from each vertex in the graph.igraph_count_reachable — The number of vertices reachable from each vertex in the graph.igraph_transitive_closure — Computes the transitive closure of a graph.igraph_biconnected_components — Calculates biconnected components.igraph_articulation_points — Finds the articulation points in a graph.igraph_bridges — Finds all bridges in a graph.igraph_is_biconnected — Checks whether a graph is biconnected.igraph_error_t igraph_subcomponent( const igraph_t *graph, igraph_vector_int_t *res, igraph_integer_t vertex, igraph_neimode_t mode);
This function returns the set of vertices reachable from a specifiedvertex. In undirected graphs, this is simple the set of vertices withinthe same component.
Arguments:
| The graph object. | ||||||
| The result, vector with the IDs of the vertices reachable from | ||||||
| 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 andedges in the graph.
See also:
|
igraph_error_t igraph_connected_components( const igraph_t *graph, igraph_vector_int_t *membership, igraph_vector_int_t *csize, igraph_integer_t *no, igraph_connectedness_t mode);
When computing strongly connected components, the components will beindexed in topological order. In other words, vertexv is reachablefrom vertexu precisely whenmembership[u] <= membership[v].
Arguments:
| The graph object to analyze. | ||||
| For every vertex the ID of its component is given. The vector has to be preinitialized and will be resized as needed. Alternatively this argument can be | ||||
| For every component it gives its size, the order being defined by the component IDs. The vector must be preinitialized and will be resized as needed. 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:
This parameter is ignored for undirected graphs. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), where |V| and |E| are the number of verticesand edges in the graph.
Example 13.15. Fileexamples/simple/igraph_contract_vertices.c
#include <igraph.h>/* Create the condensation of a directed graph. * Seehttps://en.wikipedia.org/wiki/Strongly_connected_component#Definitions * This example demonstrates how to write a basic igraph function, complete * with error handling. */igraph_error_tcondensation(const igraph_t *graph, igraph_t *cond) { igraph_vector_int_t membership;/* Data structures such as vector must be initialized in igraph before use. */IGRAPH_CHECK(igraph_vector_int_init(&membership, 0));/* Adding the initialized vector to the "finally" stack ensures that it will * be automatically destroyed if an error occurs. */IGRAPH_FINALLY(igraph_vector_int_destroy, &membership);/* Functions that return an error code can be wrapped in IGRAPH_CHECK to pass that error * up to the caller. */IGRAPH_CHECK(igraph_connected_components(graph, &membership,/* csize */ NULL,/* no */ NULL, IGRAPH_STRONG));/* To compute the condensation, we simply contract strongly connected components. * Since igraph_contract_vertices() modifies graphs in-place, we make a copy first. */IGRAPH_CHECK(igraph_copy(cond, graph));/* Since we are not done creating the condensation yet, we add 'cond' to the * "finally" stack, so that it will be destroyed if an error occurs. */IGRAPH_FINALLY(igraph_destroy, cond);/* Contract strongly connected components. */IGRAPH_CHECK(igraph_contract_vertices(cond, &membership, NULL));/* igraph_contract_vertices() preserves all edges, some of which become * parallel edges or self-loops after the contraction. We simplify these. */IGRAPH_CHECK(igraph_simplify(cond,/* remove_multiple */ true,/* remove_loops */ true, NULL));/* Data structures that are no longer needed must be explicitly destroyed. * If they were added to the "finally" stack, they must be removed explicitly, * in the opposite order to how they were added. IGRAPH_FINALLY_CLEAN removes * the indicated number of entries from the "finally" stack. We remove * 'membership' because it was destroyed, and 'cond' because the responsibility * to destroy it is now with the caller. */igraph_vector_int_destroy(&membership);IGRAPH_FINALLY_CLEAN(2);return IGRAPH_SUCCESS;/* return with no error */}intmain(void) { igraph_t graph, cond;/* Create a random directed graph with mean degree 2 and compute its condensation. */igraph_erdos_renyi_game_gnm(&graph, 100, 200, IGRAPH_DIRECTED, IGRAPH_NO_LOOPS);condensation(&graph, &cond);printf("Number of vertices in the condensation: %" IGRAPH_PRId "\n",igraph_vcount(&cond));igraph_write_graph_edgelist(&cond, stdout);/* Destroy data structures that are no longer needed. */igraph_destroy(&graph);igraph_destroy(&cond);return 0;}
igraph_error_t igraph_clusters(const igraph_t *graph, igraph_vector_int_t *membership, igraph_vector_int_t *csize, igraph_integer_t *no, igraph_connectedness_t mode);
Deprecated since version 0.10. Please do not use this function in newcode; useigraph_connected_components()instead.
igraph_error_t igraph_is_connected(const igraph_t *graph, igraph_bool_t *res, igraph_connectedness_t mode);
A graph is considered connected when any of its vertices is reachablefrom any other. A directed graph with this property is calledstrongly connected. A directed graph that would be connected whenignoring the directions of its edges is calledweakly connected.
A graph with zero vertices (i.e. the null graph) isnot connected bydefinition. This behaviour changed in igraph 0.9; earlier versions assumedthat the null graph is connected. See the following issue on Github for theargument that led us to change the definition:https://github.com/igraph/igraph/issues/1539
The return value of this function is cached in the graph itself, separatelyfor weak and strong connectivity. Calling the function multiple times withno modifications to the graph in between will return a cached value in O(1)time.
Arguments:
| The graph object to analyze. |
| Pointer to a Boolean 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: |
See also:
|
Time complexity: O(|V|+|E|), thenumber of verticesplus the number of edges in the graph.
igraph_error_t igraph_decompose(const igraph_t *graph, igraph_graph_list_t *components, igraph_connectedness_t mode, igraph_integer_t maxcompno, igraph_integer_t minelements);
Creates a separate graph for each component of a graph. Note that thevertex IDs in the new graphs will be different than in the originalgraph, except when there is only a single component in the original graph.
Arguments:
| The original graph. |
| This list of graphs will contain the individual components. It should be initialized before calling this function and will be resized to hold the graphs. |
| 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 numberof edges.
Example 13.16. Fileexamples/simple/igraph_decompose.c
#include <igraph.h>#include <stdlib.h>intmain(void) { igraph_t ring, g, *component; igraph_graph_list_t complist; igraph_integer_t i; igraph_integer_t edges[] = { 0, 1, 1, 2, 2, 0, 3, 4, 4, 5, 5, 6, 8, 9, 9, 10 }; igraph_vector_int_t v;igraph_graph_list_init(&complist, 0);/* A ring, a single component */igraph_ring(&ring, 10, IGRAPH_UNDIRECTED, 0, 1);igraph_decompose(&ring, &complist, IGRAPH_WEAK, -1, 0); component =igraph_graph_list_get_ptr(&complist, 0);igraph_write_graph_edgelist(component, stdout);igraph_destroy(&ring);igraph_graph_list_clear(&complist);/* Random graph with a giant component */igraph_erdos_renyi_game_gnp(&g, 100, 4.0 / 100, IGRAPH_UNDIRECTED, 0);igraph_decompose(&g, &complist, IGRAPH_WEAK, -1, 20);if (igraph_graph_list_size(&complist) != 1) {return 1; }igraph_destroy(&g);igraph_graph_list_clear(&complist);/* A toy graph, three components maximum, with at least 2 vertices each */igraph_create(&g,igraph_vector_int_view(&v, edges,sizeof(edges) /sizeof(edges[0])), 0, IGRAPH_DIRECTED);igraph_decompose(&g, &complist, IGRAPH_WEAK, 3, 2);for (i = 0; i <igraph_graph_list_size(&complist); i++) { component =igraph_graph_list_get_ptr(&complist, i);igraph_write_graph_edgelist(component, stdout); }igraph_destroy(&g);igraph_graph_list_destroy(&complist);return 0;}
void igraph_decompose_destroy(igraph_vector_ptr_t *complist);
This function destroys and frees alligraph_tobjects held incomplist. However, it does not destroycomplist itself. Useigraph_vector_ptr_destroy() to destroycomplist.
Arguments:
| The list of graphs to destroy. |
Time complexity: O(n), n is the number of items.
Deprecated since version 0.10.0. Please do not use this function in newcode.
igraph_error_t igraph_reachability( const igraph_t *graph, igraph_vector_int_t *membership, igraph_vector_int_t *csize, igraph_integer_t *no_of_components, igraph_bitset_list_t *reach, igraph_neimode_t mode);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
The resulting list will contain one bitset for each strongly connected component.The bitset for component i will have its j-th bit set, if vertex j is reachablefrom some vertex in component i in 0 or more steps.In particular, a vertex is always reachable from itself.
Arguments:
| The graph object to analyze. |
| Pointer to an integer vector. For every vertex, the ID of its component is given. The vector will be resized as needed. This parameter must not be |
| Pointer to an integer vector or |
| Pointer to an integer or |
| A list of bitsets representing the result. It will be resized as needed. |
| In directed graphs, controls the treatment of edge directions. Ignored in undirected graphs. With |
Returns:
Error code: |
See also:
|
Time complexity: O(|C||V|/w + |V| + |E|), where|C| is the number of strongly connected components (at most |V|),|V| is the number of vertices, and|E| is the number of edges respectively,and w is the bit width ofigraph_integer_t, typically theword size of the machine (32 or 64).
igraph_error_t igraph_count_reachable(const igraph_t *graph, igraph_vector_int_t *counts, igraph_neimode_t mode);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Arguments:
| The graph object to analyze. |
| Integer vector. |
| In directed graphs, controls the treatment of edge directions. Ignored in undirected graphs. With |
Returns:
Error code: |
See also:
Time complexity: O(|C||V|/w + |V| + |E|), where|C| is the number of strongly connected components (at most |V|),|V| is the number of vertices, and|E| is the number of edges respectively,and w is the bit width ofigraph_integer_t, typically theword size of the machine (32 or 64).
igraph_error_t igraph_transitive_closure(const igraph_t *graph, igraph_t *closure);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
The resulting graph will have an edge from vertexi to vertexjifj is reachable fromi.
Arguments:
| The graph object to analyze. |
| The resulting graph representing the transitive closure. |
Returns:
Error code: |
See also:
Time complexity: O(|V|^2 + |E|), where|V| is the number of vertices, and|E| is the number of edges, respectively.
igraph_error_t igraph_biconnected_components(const igraph_t *graph, igraph_integer_t *no, igraph_vector_int_list_t *tree_edges, igraph_vector_int_list_t *component_edges, igraph_vector_int_list_t *components, igraph_vector_int_t *articulation_points);
A graph is biconnected if the removal of any single vertex (andits incident edges) does not disconnect it.
A biconnected component of a graph is a maximal biconnectedsubgraph of it. The biconnected components of a graph can be givenby a partition of its edges: every edge is a member of exactlyone biconnected component. Note that this is not true forvertices: the same vertex can be part of many biconnectedcomponents, while isolated vertices are part of none at all.
Note that some authors do not consider the graph consisting oftwo connected vertices as biconnected, however, igraph does.
igraph does not consider components containing a single vertex only asbeing biconnected. Isolated vertices will not be part of any of thebiconnected components. This means that checking whether there is a singlebiconnected component is not sufficient for determining if a graph isbiconnected. Useigraph_is_biconnected() for this purpose.
Arguments:
| The input graph. It will be treated as undirected. |
| If not a |
| If not a |
| If not a |
| If not a |
| 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 andedges, but only if you do not calculatecomponents andcomponent_edges. If you calculatecomponents, then it isquadratic in the number of vertices. If you calculatecomponent_edges as well, then it is cubic in the number ofvertices.
See also:
Example 13.17. Fileexamples/simple/igraph_biconnected_components.c
#include <igraph.h>/* Prints a vector of edge IDs as u--v vertex pairs. */voidprint_edge_vector(const igraph_t *graph,const igraph_vector_int_t *edges) {const igraph_integer_t n =igraph_vector_int_size(edges);for (igraph_integer_t i=0; i < n; i++) { igraph_integer_t edge =VECTOR(*edges)[i];printf("%" IGRAPH_PRId "--%" IGRAPH_PRId " ",IGRAPH_FROM(graph, edge),IGRAPH_TO(graph, edge)); }printf("\n");}intmain(void) { igraph_t graph; igraph_vector_int_list_t component_vertices, component_edges; igraph_integer_t no;/* Create an example graph. */igraph_small(&graph, 7, IGRAPH_UNDIRECTED, 0,1, 1,2, 2,3, 3,0, 2,4, 4,5, 5,2, 0,6, 0,7, -1);/* The data structures that the result will be written to must be initialized first. */igraph_vector_int_list_init(&component_vertices, 0);igraph_vector_int_list_init(&component_edges, 0);igraph_biconnected_components(&graph, &no, NULL, &component_edges, &component_vertices, NULL);printf("Number of components: %" IGRAPH_PRId "\n", no);for (igraph_integer_t i=0; i < no; i++) {printf("\n");printf("Component %" IGRAPH_PRId ":\n", i);printf("Vertices: ");igraph_vector_int_print(igraph_vector_int_list_get_ptr(&component_vertices, i));printf("Edges: ");print_edge_vector(&graph,igraph_vector_int_list_get_ptr(&component_edges, i)); }/* Destroy data structures after we no longer need them. */igraph_vector_int_list_destroy(&component_edges);igraph_vector_int_list_destroy(&component_vertices);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_articulation_points(const igraph_t *graph, igraph_vector_int_t *res);
A vertex is an articulation point if its removal increasesthe number of (weakly) connected components in the graph.
Note that a graph without any articulation points is not necessarilybiconnected. Counterexamples are the two-vertex complete graph as wellas empty graphs. Useigraph_is_biconnected() to check whethera graph is biconnected.
Arguments:
| The input graph. It will be treated as undirected. |
| 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:
igraph_error_t igraph_bridges(const igraph_t *graph, igraph_vector_int_t *bridges);
An edge is a bridge if its removal increases the number of (weakly)connected components in the graph.
Arguments:
| The input graph. It will be treated as undirected. |
| 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_error_t igraph_is_biconnected(const igraph_t *graph, igraph_bool_t *res);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
A graph is biconnected if the removal of any single vertex (andits incident edges) does not disconnect it.
igraph does not consider single-vertex graphs biconnected.
Note that some authors do not consider the graph consisting oftwo connected vertices as biconnected, however, igraph does.
Arguments:
| The input graph. It will be treated as undirected. |
| If not a |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices and edges.
See also:
Example 13.18. Fileexamples/simple/igraph_is_biconnected.c
#include <igraph.h>#include <stdio.h>intmain(void) { igraph_t g; igraph_bool_t result;igraph_small(&g, 7, 0, 0, 1, 1, 2, 2, 3, 3, 0, 2, 4, 4, 5, 2, 5, -1);igraph_is_biconnected(&g, &result);printf("Graph is%sbiconnected.\n", result ? " " : " not ");igraph_destroy(&g);return 0;}
igraph_error_t igraph_site_percolation( const igraph_t *graph, igraph_vector_int_t *giant_size, igraph_vector_int_t *edge_count, const igraph_vector_int_t *vertex_order);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Calculates the site percolation curve, i.e. the size of the largest connectedcomponent as vertices are added in the given order. If bothgiant_sizeandvertex_order are reversed, it is the size of the largest componentas vertices are removed from the graph. If no vertex order is given, a randomone will be used.
Arguments:
| The graph that vertices are assumed to be in. Edge directions are ignored. |
|
|
|
|
| The order the vertices are added in. Must not contain duplicates. If |
Returns:
Error code. |
See also:
|
Time complexity: O(|V| + |E| a(|E|)) where a is the inverse Ackermann function,for all practical purposes it is not above 5.
igraph_error_t igraph_bond_percolation( const igraph_t *graph, igraph_vector_int_t *giant_size, igraph_vector_int_t *vertex_count, const igraph_vector_int_t *edge_order);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Calculates the bond percolation curve, i.e. the size of the largest connectedcomponent as edges are added to the graph in the order given. If bothgiant_size andedge_order are reversed, it is the size of the largestcomponent as edges are removed from the graph. If no edge order is given,a random one will be used.
Arguments:
| The graph that edges are assumed to be in. Edge directions are ignored. |
|
|
|
|
| The order the edges are added in. Must not contain duplicates. If |
Returns:
Error code. |
See also:
|
Time complexity: O(|V| + |E| a(|E|)) where a is the inverse Ackermann function,for all practical purposes it is not above 5.
igraph_error_t igraph_edgelist_percolation( const igraph_vector_int_t *edges, igraph_vector_int_t *giant_size, igraph_vector_int_t *vertex_count);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Calculates the size of the largest connected component as edges are addedto a graph in the given order. This function differs fromigraph_bond_percolation() in that it take a list of vertex pairs as input.
Arguments:
| Vector of edges, where the i-th edge has endpoints |
|
|
|
|
Returns:
Error code. |
See also:
|
Time complexity: O(|E| a(|E|)) where a is the inverse Ackermann function,for all practical purposes it is not above 5.
igraph_error_t igraph_is_graphical(const igraph_vector_int_t *out_degrees, const igraph_vector_int_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 performthe 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-timealgorithm 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, butnot self-loops, there is an additional condition that the sum of degrees be no smaller than twicethe maximum degree. If at most one self-loop is allowed per vertex, but no multi-edges, a modifiedversion 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 ofin- and out-degrees is the same. If only multi-edges are allowed, but not self loops, there is anadditional condition that the sum of out-degrees (or equivalently, in-degrees) is no smaller thanthe maximum total degree. If single self-loops are allowed, but not multi-edges, the problem is equivalentto realizability as a simple bipartite graph, thus the Gale-Ryser theorem can be used; seeigraph_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).https://egres.elte.hu/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), where n is the length of the degree sequence(s).
igraph_error_t igraph_is_bigraphical(const igraph_vector_int_t *degrees1, const igraph_vector_int_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 ofa bipartite graph. Such a pair of degree sequence is calledbigraphical.
When multi-edges are allowed, it is sufficient to check that the sum of degrees is thesame in the two partitions. For simple graphs, the Gale-Ryser theorem is usedwith 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), where n is the length of the larger 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 implementation.igraph_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, also called weighted vertex degree.igraph_eigenvector_centrality — Eigenvector centrality of the vertices.igraph_hub_and_authority_scores — Kleinberg's hub and authority scores (HITS).igraph_convergence_degree — Calculates the convergence degree of each edge in a graph.igraph_error_t igraph_closeness(const igraph_t *graph, igraph_vector_t *res, igraph_vector_int_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 othervertices can be reached from it (or the other way: how easily itcan be reached from the other vertices). It is defined asthe 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 themean distance to (or from) allreachable vertices. In undirectedgraphs, this is equivalent to computing the closeness separately ineach connected component. The optionalall_reachable outputparameter is provided to help detect when the graph is disconnected.
While there is no universally adopted definition of closeness centralityfor disconnected graphs, there have been some attempts for generalizingthe concept to the disconnected case. One type of approach considers the mean distanceonly to reachable vertices, then re-scales the obtained certrality scoreby 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 inreachable_count.
In disconnected graphs, consider using the harmonic centrality,computable usingigraph_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. NaN values re not allowed as weights. Supply a null pointer here for traditional, unweighted closeness. | ||||||
| If true, the inverse of the mean distance to reachable vertices is returned. If false, the inverse of the sum of distances is returned. |
Returns:
Error code:
|
Time complexity: O(n|E|) for the unweighted case and O(n|E|log|V|+|V|)for the weighted case, where n is the numberof vertices for which the calculation is done, |V| is the number of verticesand |E| is the number of edges in the graph.
See also:
Other centrality types: |
igraph_error_t 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 toall other vertices. The inverse distance to an unreachable vertexis 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|) for the unweighted case and O(n*|E|log|V|+|V|)for the weighted case, where n is the numberof vertices for which the calculation is done, |V| is the number of verticesand |E| is the number of edges in the graph.
See also:
Other centrality types: |
igraph_error_t 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 geodesicsgoing through it. If there are more than one geodesic between twovertices, the value of these geodesics are weighted by one over thenumber of geodesics.
Reference:
Ulrik Brandes: A faster algorithm for betweenness centrality.The Journal of Mathematical Sociology, 25(2), 163–177 (2001).https://doi.org/10.1080/0022250X.2001.9990249
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. |
| 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 andedges in the graph.Note that the time complexity is independent of the number ofvertices for which the score is calculated.
See also:
Other centrality types: |
igraph_error_t 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 geodesicsgoing through it. If there are more than one geodesics between twovertices, the value of these geodesics are weighted by one over thenumber of geodesics.
Reference:
Ulrik Brandes: A faster algorithm for betweenness centrality.The Journal of Mathematical Sociology, 25(2), 163–177 (2001).https://doi.org/10.1080/0022250X.2001.9990249
Arguments:
| The graph object. |
| The result of the computation, vector containing the betweenness scores for the edges. |
| 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 andedges 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. |
igraph_error_t 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 arandom walker traversing the graph would spend on that vertex.The walker follows the out-edges with probabilities proportionalto their weights. Additionally, in each step, it restarts the walkfrom a random vertex with probability1 - damping.If the random walker gets stuck in a sink vertex, it will also restartfrom a random vertex.
The PageRank centrality is mainly useful for directed graphs. In undirectedgraphs it converges to trivial values proportional to degrees as the dampingfactor approaches 1.
Starting from version 0.9, igraph has two PageRank implementations,and the user can choose between them. The first implementation isIGRAPH_PAGERANK_ALGO_ARPACK, which phrases the PageRank calculationas an eigenvalue problem, which is then solved using the ARPACK library.This was the default before igraph version 0.7. The second and recommendedimplementation isIGRAPH_PAGERANK_ALGO_PRPACK. This is using thePRPACK package, seehttps://github.com/dgleich/prpack. PRPACK uses analgebraic method, i.e. solves a linear system to obtain the PageRankscores.
Note that the PageRank of a given vertex depends on the PageRankof all other vertices, so even if you want to calculate the PageRank foronly some of the vertices, all of them must be calculated. Requestingthe PageRank for only some of the vertices does not result in anyperformance increase at all.
References:
Sergey Brin and Larry Page: The Anatomy of a Large-Scale HypertextualWeb Search Engine. Proceedings of the 7th World-Wide Web Conference,Brisbane, Australia, April 1998.https://doi.org/10.1016/S0169-7552(98)00110-X
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. When using |
| The vertex IDs for which the PageRank is returned. This parameter is only for convenience. Computing PageRank for fewer than all vertices will not speed up the calculation. |
| 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.19. Fileexamples/simple/igraph_pagerank.c
#include <igraph.h>#include <float.h>intmain(void) { 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;}
igraph_error_t 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, butwhen the random walk is restarted, a new starting vertex is chosen non-uniformly,according to the distribution specified inreset(instead of the uniform distribution in the original PageRank measure).Thereset distribution is used both when restarting randomly with probability1 - damping, and when the walker is forced to restart due to beingstuck in a sink vertex (a vertex with no outgoing edges).
Note that the personalized PageRank of a given vertex depends on thepersonalized PageRank of all other vertices, so even if you want to calculatethe personalized PageRank for only some of the vertices, all of them must becalculated. Requesting the personalized PageRank for only some of the verticesdoes 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. When using |
| The vertex IDs for which the PageRank is returned. This parameter is only for convenience. Computing PageRank for fewer than all vertices will not speed up the calculation. |
| 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:
|
igraph_error_t 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, butwhen the random walk is restarted, a new starting vertex is chosen according toa specified distribution.This distribution is used both when restarting randomly with probability1 - damping, and when the walker is forced to restart due to beingstuck in a sink vertex (a vertex with no outgoing edges).
This simplified interface takes a vertex sequence and resets the random walk toone of the vertices in the specified vertex sequence, chosen uniformly. A typicalapplication of personalized PageRank is when the random walk is reset to the samevertex every time: this can easily be achieved usingigraph_vss_1() whichgenerates a vertex sequence containing only a single vertex.
Note that the personalized PageRank of a given vertex depends on thepersonalized PageRank of all other vertices, so even if you want to calculatethe personalized PageRank for only some of the vertices, all of them must becalculated. Requesting the personalized PageRank for only some of the verticesdoes 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. When using |
| The vertex IDs for which the PageRank is returned. This parameter is only for convenience. Computing PageRank for fewer than all vertices will not speed up the calculation. |
| 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. The walk will be restarted from a vertex in this set, chosen uniformly at random. Duplicate vertices are allowed. |
| 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:
|
igraph_error_t 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 givenvertices, also known as structural holes.
Burt's constraint is higher if ego has less, or mutually strongerrelated (i.e. more redundant) contacts. Burt's measure ofconstraint, C[i], of vertex i's ego network V[i], is defined fordirected and valued graphs,
C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j inV[], j != i)
for a graph of order (i.e. number of vertices) N, where proportionaltie 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 andthe latter being the graph adjacency matrix. For isolated vertices,constraint is undefined.
Burt, R.S. (2004). Structural holes and good ideas. AmericanJournal of Sociology 110, 349-399.
The first R version of this function was contributed by JeroenBruggeman.
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 forwhich the constraint is calculated and d is the average degree, |V|is the number of vertices, |E| the number of edges in thegraph. If the weights argument isNULL then the time complexityis O(|V|+n*d^2).
igraph_error_t 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 iscalculated. If the graph has no vertices, orvids 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) ifloops istrue, and O(v*d) otherwise. v is the numberof vertices for which the degree will be calculated, and d is their(average) degree.
See also:
|
igraph_error_t 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 theweights of all incident edges. In a non-weighted network this isexactly 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 ( |
| Boolean, whether to count loop edges as well. |
| A vector giving the edge weights. If this is a |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number vertices andedges.
See also:
|
igraph_error_t 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 anetwork. It assigns relative scores to all nodes in the network basedon the principle that connections from high-scoring nodes contributemore to the score of the node in question than equal connections fromlow-scoring nodes. Specifically, the eigenvector centrality of eachvertex is proportional to the sum of eigenvector centralities of itsneighbors. In practice, the centralities are determined by calculating theeigenvector corresponding to the largest positive eigenvalue of theadjacency matrix. In the undirected case, this function considersthe diagonal entries of the adjacency matrix to betwice the number ofself-loops on the corresponding vertex.
In the weighted case, the eigenvector centrality of a vertex is proportionalto the weighted sum of centralities of its neighbours, i.e.c_j = sum_i w_ij c_i, wherew_ij is the weightof the edge connecting vertexi toj. The weights of parallel edgesare added up.
The centrality scores returned by igraph can be normalized(using thescale parameter) such that the largest eigenvector centralityscore is 1 (with one exception, see below).
In the directed case, the left eigenvector of the adjacency matrix iscalculated. In other words, the centrality of a vertex is proportionalto the sum of centralities of vertices pointing to it.
Eigenvector centrality is meaningful only for (strongly) connected graphs.Undirected graphs that are not connected should be decomposed into connectedcomponents, and the eigenvector centrality calculated for each separately.The scores between components will not be comparable.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 theadjacency matrix of an empty graph does not possess positive eigenvalues,therefore the eigenvector centrality is not meaningful for these graphs.igraph will return an eigenvalue of zero in such cases. The returnedeigenvector centralities will all be equal for vertices with zero out-degree,and zeros for other vertices. Such pathological cases can be detectedby asking igraph to calculate the eigenvalue as well (using thevalueparameter, see below) and checking whether the eigenvalue is very closeto zero.
When working with directed graphs, consider using hub and authorityscores instead, seeigraph_hub_and_authority_scores().
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 (indicating no edge weights), or a vector giving the weights of the edges. Weights should be positive to guarantee a meaningful result. The algorithm might produce complex numbers when some weights are negative and the graph is directed. 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.20. Fileexamples/simple/eigenvector_centrality.c
#include <igraph.h>intmain(void) { igraph_t graph;igraph_vector_t vector, weights; igraph_real_t value;/* Create a star graph, with vertex 0 at the center, and associated edge weights. */igraph_star(&graph, 10, IGRAPH_STAR_UNDIRECTED, 0);igraph_vector_init_range(&weights, 1,igraph_ecount(&graph)+1);/* Initialize the vector where the result will be stored. */igraph_vector_init(&vector, 0);/* Compute eigenvector centrality. */igraph_eigenvector_centrality(&graph, &vector, &value, IGRAPH_UNDIRECTED,/*scale=*/ true, &weights,/*options=*/ NULL);/* Print results. */printf("eigenvalue: %g\n", value);printf("eigenvector:\n");igraph_vector_print(&vector);/* Free allocated data structures. */igraph_vector_destroy(&vector);igraph_vector_destroy(&weights);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_hub_and_authority_scores(const igraph_t *graph, igraph_vector_t *hub_vector, igraph_vector_t *authority_vector, igraph_real_t *value, igraph_bool_t scale, const igraph_vector_t *weights, igraph_arpack_options_t *options);
Hub and authority scores are a generalization of the ideas behindeigenvector centrality to directed graphs. The authority score ofa vertex is proportional to the sum of the hub scores of verticesthat point to it. Conversely, the hub score of a vertex is proportionalto the sum of authority scores of vertices that it points to. Theseconcepts are also known under the name Hyperlink-Induced Topic Search (HITS).
The hub and authority scores of the vertices are defined as the principaleigenvectors ofA A^T andA^T A, respectively,whereA is the adjacency matrix of the graph andA^Tis its transposed.
If vectorh anda contain hub and authority scores, then the twoscores are related byh = Aa anda = A^T h.When the principal eigenvalue ofA A^T is degenerate, thereis no unique solution to the hub- and authority-score problem.igraph guarantees that the scores that are returned are matching, i.e. arerelated by these formulas, even in this situation.
The concept of hub and authority scores were developed fordirected graphs.In undirected graphs, both the hub and authority scores are equal to theeigenvector centrality, which can be computed usingigraph_eigenvector_centrality().
See the following reference on the meaning of this score:J. Kleinberg. Authoritative sources in a hyperlinkedenvironment. Proc. 9th ACM-SIAM Symposium on DiscreteAlgorithms, 1998. Extended version in Journal of theACM 46(1999).https://doi.org/10.1145/324133.324140Also appears as IBM Research Report RJ 10076, May1997.
Arguments:
| The input graph. Can be directed and undirected. |
| Pointer to an initialized vector, the hub scores are stored here. If a null pointer then it is ignored. |
| Pointer to an initialized vector, the authority scores are stored here. If a null pointer then it is ignored. |
| If not a null pointer then the eigenvalue corresponding to the calculated eigenvectors 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 (meaning 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:
|
igraph_error_t 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 wherethe shortest paths passing through (i, j) originate, and similarly, let usdefined the output set of an edge (i, j) as the set of vertices where theshortest paths passing through (i, j) terminate. The convergence degree ofan edge is defined as the normalized value of the difference between thesize of the input set and the output set, i.e. the difference of themdivided by the sum of them. Convergence degrees are in the range (-1, 1); apositive value indicates that the edge isconvergent since the shortestpaths passing through it originate from a larger set and terminate in asmaller set, while a negative value indicates that the edge isdivergentsince 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 inundirected graphs as there is no distinction between the input and outputset. Therefore, for undirected graphs, the input and output sets of an edgeare determined by orienting the edge arbitrarily while keeping the remainingedges undirected, and then taking the absolute value of the convergencedegree.
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_error_t igraph_closeness_cutoff(const igraph_t *graph, igraph_vector_t *res, igraph_vector_int_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 centralityby considering only those shortest paths whose length is no greaterthen 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: At most O(n|E|) for the unweighted case and O(n|E|log|V|+|V|)for the weighted case, where n is the numberof vertices for which the calculation is done, |V| is the number of verticesand |E| is the number of edges in the graph. The timing decreases with smallercutoffs in a way that depends on the graph structure.
See also:
|
igraph_error_t 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 consideredto 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: At most O(n|E|) for the unweighted case and O(n|E|log|V|+|V|)for the weighted case, where n is the numberof vertices for which the calculation is done, |V| is the number of verticesand |E| is the number of edges in the graph. The timing decreases with smallercutoffs in a way that depends on the graph structure.
See also:
|
igraph_error_t 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 centralityby considering only those shortest paths whose length is no greaterthen 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. |
| 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 andedges in the graph.Note that the time complexity is independent of the number ofvertices for which the score is calculated.
See also:
|
igraph_error_t 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 centralityby considering only those shortest paths whose length is no greaterthen the given cutoff value.
Arguments:
| The graph object. |
| The result of the computation, vector containing the betweenness scores for the edges. |
| 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 andedges in the graph.
See also:
|
igraph_error_t igraph_betweenness_subset(const igraph_t *graph, igraph_vector_t *res, const igraph_vs_t vids, igraph_bool_t directed, const igraph_vs_t sources, const igraph_vs_t targets, const igraph_vector_t *weights);
This function computes the subset-limited version of betweenness centralityby considering only those shortest paths that lie between vertices in a givensource and target subset.
Arguments:
| The graph object. |
| The result of the computation, a vector containing the betweenness score for the subset of vertices. |
| The vertices for which the subset-limited betweenness centrality scores will be computed. |
| If true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
| A vertex selector for the sources of the shortest paths taken into considuration in the betweenness calculation. |
| A vertex selector for the targets of the shortest paths taken into considuration in the betweenness calculation. |
| 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(|S||E|), where|S| is the number of vertices in the subset and|E| is the number of edges in the graph.
See also:
|
igraph_error_t igraph_edge_betweenness_subset(const igraph_t *graph, igraph_vector_t *res, const igraph_es_t eids, igraph_bool_t directed, const igraph_vs_t sources, const igraph_vs_t targets, const igraph_vector_t *weights);
This function computes the subset-limited version of edge betweenness centralityby considering only those shortest paths that lie between vertices in a givensource and target subset.
Arguments:
| The graph object. |
| The result of the computation, vector containing the betweenness scores for the edges. |
| The edges for which the subset-limited betweenness centrality scores will be computed. |
| If true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
| A vertex selector for the sources of the shortest paths taken into considuration in the betweenness calculation. |
| A vertex selector for the targets of the shortest paths taken into considuration in the betweenness calculation. |
| An optional weight vector for weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
Returns:
Error code: |
Time complexity: O(|S||E|), where|S| is the number of vertices in the subset and|E| is the number of edges in the graph.
See also:
|
igraph_centralization — Calculate the centralization score from the node level scores.igraph_centralization_degree — Calculate vertex degree and graph centralization.igraph_centralization_betweenness — Calculate vertex betweenness and graph centralization.igraph_centralization_closeness — Calculate vertex closeness and graph centralization.igraph_centralization_eigenvector_centrality — Calculate eigenvector centrality scores and graph centralization.igraph_centralization_degree_tmax — Theoretical maximum for graph centralization based on degree.igraph_centralization_betweenness_tmax — Theoretical maximum for graph centralization based on betweenness.igraph_centralization_closeness_tmax — Theoretical maximum for graph centralization based on closeness.igraph_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 ispossible to define a graph level centralization index, bycalculating the sum of the deviations from the maximum centralityscore. Consequently, the higher the centralization index of thegraph, the more centralized the structure is.
In order to make graphs of different sizes comparable,the centralization index is usually normalized to a number betweenzero and one, by dividing the (unnormalized) centralization scoreof the most centralized structure with the same number of vertices.
For most centrality indices, the most centralized structure is thestar graph, a single center connected to all other nodes in the network.There is 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 nodelevel scores and the theoretical maximum are given. It is called byall the measure-specific centralization functions. It uses the calculation
C = sum_v ((max_u c_u) - c_v)
wherec are the centrality scores passed inscores. Ifnormalizedistrue, thenC/theoretical_max is returned.
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.21. Fileexamples/simple/centralization.c
#include <igraph.h>intmain(void) { igraph_t graph; igraph_real_t cent;/* Create an undirected star graph, which is the most centralized graph * with several common centrality scores. */printf("undirected star graph:\n");igraph_star(&graph, 10, IGRAPH_STAR_UNDIRECTED,/*center=*/ 0);igraph_centralization_degree(&graph,/*res=*/ NULL,/*mode=*/ IGRAPH_ALL, IGRAPH_NO_LOOPS, ¢,/*theoretical_max=*/ NULL,/*normalized=*/ true);printf("degree centralization: %g\n", cent);igraph_centralization_betweenness(&graph,/*res=*/ NULL, IGRAPH_UNDIRECTED, ¢,/*theoretical_max=*/ NULL,/*normalized=*/ true);printf("betweenness centralization: %g\n", cent);igraph_centralization_closeness(&graph,/*res=*/ NULL, IGRAPH_ALL, ¢,/*theoretical_max=*/ NULL,/*normalized=*/ true);printf("closeness centralization: %g\n", cent);igraph_destroy(&graph);/* With eigenvector centrality, the most centralized structure is * a graph containing a single edge. */printf("\ngraph with single edge:\n");igraph_small(&graph,/*n=*/ 10,/*directed=*/ 0, 0,1, -1);igraph_centralization_eigenvector_centrality( &graph,/*vector=*/ NULL,/*value=*/ NULL, IGRAPH_DIRECTED,/*scale=*/ true,/*options=*/ NULL, ¢,/*theoretical_max=*/ NULL,/*normalized=*/ true);printf("eigenvector centralization: %g\n", cent);igraph_destroy(&graph);return 0;}
igraph_error_t 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 itsarguments toigraph_degree(); and it calculates the graphlevel centralization index based on the results by callingigraph_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 ofigraph_degree() plus O(n),the number of vertices queried, for calculating the centralizationscore.
igraph_error_t 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 verticesby passing its arguments toigraph_betweenness(); and itcalculates the graph level centralization index based on theresults by callingigraph_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 ofigraph_betweenness() plusO(n), the number of vertices queried, for calculating thecentralization score.
igraph_error_t 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 verticesby passing its arguments toigraph_closeness(); and itcalculates the graph level centralization index based on theresults by callingigraph_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 ofigraph_closeness() plusO(n), the number of vertices queried, for calculating thecentralization score.
igraph_error_t 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 verticesby passing its arguments toigraph_eigenvector_centrality);and it calculates the graph level centralization index based on theresults by callingigraph_centralization().
Note that vertex-level eigenvector centrality scores do not havea natural scale. As with any eigenvector, their interpretation isinvariant to scaling by a constant factor. However, due to howgraph-levelcentralization is defined, its value depends on thespecific scale/normalization used for vertex-level scores. Which oftwo graphs will have a higher eigenvectorcentralization dependson the choice of normalization for centralities. This function makesthe specific choice of scaling vertex-level centrality scores by theirmaximum (i.e. it uses the ∞-norm). Other normalization choices, suchas the 1-norm or 2-norm are not currently implemented.
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. |
| Boolean scalar, whether to consider edge directions in a directed graph. It is ignored for undirected graphs. |
| This parameter is deprecated and ignored since igraph 0.10.14. Vertex-level centrality scores are always scaled to have a maximum of 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 ofigraph_eigenvector_centrality() plus O(|V|), the number of verticesfor the calculating the centralization.
igraph_error_t 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 centralitybased on vertex degree.
There are two ways to call this function, the first is to supply agraph as thegraph argument, and then the number ofvertices is taken from this object, and its directedness isconsidered as well. Thenodes argument is ignored inthis case. Themode argument is also ignored if thesupplied graph is undirected.
The other way is to supply a null pointer as thegraphargument. In this case thenodes andmodearguments are considered.
The most centralized structure is the star. More specifically, forundirected graphs it is the star, for directed graphs it is thein-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, 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:
igraph_error_t 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 centralitybased on vertex betweenness.
There are two ways to call this function, the first is to supply agraph as thegraph argument, and then the number ofvertices is taken from this object, and its directedness isconsidered as well. Thenodes argument is ignored inthis case. Thedirected argument is also ignored if thesupplied graph is undirected.
The other way is to supply a null pointer as thegraphargument. In this case thenodes anddirectedarguments 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, 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:
igraph_error_t 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 centralitybased on vertex closeness.
There are two ways to call this function, the first is to supply agraph as thegraph argument, and then the number ofvertices is taken from this object, and its directedness isconsidered as well. Thenodes argument is ignored inthis case. Themode argument is also ignored if thesupplied graph is undirected.
The other way is to supply a null pointer as thegraphargument. In this case thenodes andmodearguments 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 kind 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:
igraph_error_t 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 centralitybased on vertex eigenvector centrality.
There are two ways to call this function, the first is to supply agraph as thegraph argument, and then the number ofvertices is taken from this object, and its directedness isconsidered as well. Thenodes argument is ignored inthis case. Thedirected argument is also ignored if thesupplied graph is undirected.
The other way is to supply a null pointer as thegraphargument. In this case thenodes anddirectedarguments are considered.
The most centralized directed structure is assumed to bethe in-star.The most centralized undirected structure is assumed to be the graphwith a single edge. igraph continues to implement these choices forhistorical reason. Keep in mind that neither of these two structuresis connected, which makes their use debatable in the context ofeigenvector centrality calculations. Eigenvector centrality is notuniquely defined for disconnected structures.
Note that vertex-level eigenvector centrality scores do not havea natural scale. As with any eigenvector, their interpretation isinvariant to scaling by a constant factor. However, due to howgraph-levelcentralization is defined, its value depends on thespecific scale/normalization used for vertex-level scores. Moreover,which of two graphs will have a higher eigenvectorcentralizationalso depends on the choice of normalization for centralities. Thisfunction makes the specific choice of scaling vertex-level centralityscores by their maximum (i.e. it uses the ∞-norm). Other normalizationchoices, such as the 1-norm or 2-norm are not currently implemented.
Arguments:
| A graph object or a null pointer, see the description above. |
| The number of nodes. This is ignored if the |
| Boolean, whether to consider edge directions. This argument is ignored if |
| This parameter is deprecated and ignored since igraph 0.10.14. Vertex-level centrality scores are always assumed to be scaled 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.igraph_error_t igraph_bibcoupling(const igraph_t *graph, igraph_matrix_t *res, const igraph_vs_t vids);
The bibliographic coupling of two vertices is the numberof other vertices they both cite,igraph_bibcoupling() calculatesthis.The bibliographic coupling score for each given vertex and allother 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 inthe graph, d is the (maximum)degree of the vertices in the graph.
See also:
Example 13.22. Fileexamples/simple/igraph_cocitation.c
#include <igraph.h>#include <stdio.h>intmain(void) { 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;}
igraph_error_t 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 ofthem.igraph_cocitation() simply counts how many times two vertices arecocited.The cocitation score for each given vertex and all other verticesin 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| isthe number of vertices in the graph,d is the (maximum) degree ofthe vertices in the graph.
See also:
Example 13.23. Fileexamples/simple/igraph_cocitation.c
#include <igraph.h>#include <stdio.h>intmain(void) { 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;}
igraph_error_t 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 commonneighbors divided by the number of vertices that are neighbors of atleast one of the two vertices being considered. This function calculatesthe 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.24. Fileexamples/simple/igraph_similarity.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_matrix_t m; igraph_vector_int_t pairs;igraph_vector_t res; igraph_integer_t i, j, n;igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1);igraph_matrix_init(&m, 0, 0);igraph_vector_init(&res, 0);igraph_vector_int_init(&pairs, 0); n =igraph_vcount(&g);for (i = 0; i < n; i++) {for (j = n - 1; j >= 0; j--) {igraph_vector_int_push_back(&pairs, i);igraph_vector_int_push_back(&pairs, j); } }printf("Jaccard similarity:\n");igraph_similarity_jaccard(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nJaccard similarity, pairs:\n");igraph_similarity_jaccard_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nJaccard similarity with edge selector:\n");igraph_similarity_jaccard_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nDice similarity:\n");igraph_similarity_dice(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nDice similarity, pairs:\n");igraph_similarity_dice_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nDice similarity with edge selector:\n");igraph_similarity_dice_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nWeighted inverse log similarity:\n");igraph_similarity_inverse_log_weighted(&g, &m,igraph_vss_all(), IGRAPH_ALL);igraph_matrix_printf(&m, "%.2f");igraph_matrix_destroy(&m);igraph_destroy(&g);igraph_vector_destroy(&res);igraph_vector_int_destroy(&pairs);return 0;}
igraph_error_t igraph_similarity_jaccard_pairs(const igraph_t *graph, igraph_vector_t *res, const igraph_vector_int_t *pairs, igraph_neimode_t mode, igraph_bool_t loops);
The Jaccard similarity coefficient of two vertices is the number of commonneighbors divided by the number of vertices that are neighbors of atleast one of the two vertices being considered. This function calculatesthe 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 isthe (maximum) degree of the vertices in the graph.
See also:
|
Example 13.25. Fileexamples/simple/igraph_similarity.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_matrix_t m; igraph_vector_int_t pairs;igraph_vector_t res; igraph_integer_t i, j, n;igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1);igraph_matrix_init(&m, 0, 0);igraph_vector_init(&res, 0);igraph_vector_int_init(&pairs, 0); n =igraph_vcount(&g);for (i = 0; i < n; i++) {for (j = n - 1; j >= 0; j--) {igraph_vector_int_push_back(&pairs, i);igraph_vector_int_push_back(&pairs, j); } }printf("Jaccard similarity:\n");igraph_similarity_jaccard(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nJaccard similarity, pairs:\n");igraph_similarity_jaccard_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nJaccard similarity with edge selector:\n");igraph_similarity_jaccard_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nDice similarity:\n");igraph_similarity_dice(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nDice similarity, pairs:\n");igraph_similarity_dice_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nDice similarity with edge selector:\n");igraph_similarity_dice_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nWeighted inverse log similarity:\n");igraph_similarity_inverse_log_weighted(&g, &m,igraph_vss_all(), IGRAPH_ALL);igraph_matrix_printf(&m, "%.2f");igraph_matrix_destroy(&m);igraph_destroy(&g);igraph_vector_destroy(&res);igraph_vector_int_destroy(&pairs);return 0;}
igraph_error_t 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 commonneighbors divided by the number of vertices that are neighbors of atleast one of the two vertices being considered. This function calculatesthe pairwise Jaccard similarities for the endpoints of edges in a given edgeselector.
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 isthe (maximum) degree of the vertices in the graph.
See also:
|
Example 13.26. Fileexamples/simple/igraph_similarity.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_matrix_t m; igraph_vector_int_t pairs;igraph_vector_t res; igraph_integer_t i, j, n;igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1);igraph_matrix_init(&m, 0, 0);igraph_vector_init(&res, 0);igraph_vector_int_init(&pairs, 0); n =igraph_vcount(&g);for (i = 0; i < n; i++) {for (j = n - 1; j >= 0; j--) {igraph_vector_int_push_back(&pairs, i);igraph_vector_int_push_back(&pairs, j); } }printf("Jaccard similarity:\n");igraph_similarity_jaccard(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nJaccard similarity, pairs:\n");igraph_similarity_jaccard_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nJaccard similarity with edge selector:\n");igraph_similarity_jaccard_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nDice similarity:\n");igraph_similarity_dice(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nDice similarity, pairs:\n");igraph_similarity_dice_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nDice similarity with edge selector:\n");igraph_similarity_dice_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nWeighted inverse log similarity:\n");igraph_similarity_inverse_log_weighted(&g, &m,igraph_vss_all(), IGRAPH_ALL);igraph_matrix_printf(&m, "%.2f");igraph_matrix_destroy(&m);igraph_destroy(&g);igraph_vector_destroy(&res);igraph_vector_int_destroy(&pairs);return 0;}
igraph_error_t 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 commonneighbors divided by the sum of the degrees of the vertices. This functioncalculates 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),where |V| is the number of vertices in the vertex iterator given, andd is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.27. Fileexamples/simple/igraph_similarity.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_matrix_t m; igraph_vector_int_t pairs;igraph_vector_t res; igraph_integer_t i, j, n;igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1);igraph_matrix_init(&m, 0, 0);igraph_vector_init(&res, 0);igraph_vector_int_init(&pairs, 0); n =igraph_vcount(&g);for (i = 0; i < n; i++) {for (j = n - 1; j >= 0; j--) {igraph_vector_int_push_back(&pairs, i);igraph_vector_int_push_back(&pairs, j); } }printf("Jaccard similarity:\n");igraph_similarity_jaccard(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nJaccard similarity, pairs:\n");igraph_similarity_jaccard_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nJaccard similarity with edge selector:\n");igraph_similarity_jaccard_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nDice similarity:\n");igraph_similarity_dice(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nDice similarity, pairs:\n");igraph_similarity_dice_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nDice similarity with edge selector:\n");igraph_similarity_dice_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nWeighted inverse log similarity:\n");igraph_similarity_inverse_log_weighted(&g, &m,igraph_vss_all(), IGRAPH_ALL);igraph_matrix_printf(&m, "%.2f");igraph_matrix_destroy(&m);igraph_destroy(&g);igraph_vector_destroy(&res);igraph_vector_int_destroy(&pairs);return 0;}
igraph_error_t igraph_similarity_dice_pairs(const igraph_t *graph, igraph_vector_t *res, const igraph_vector_int_t *pairs, igraph_neimode_t mode, igraph_bool_t loops);
The Dice similarity coefficient of two vertices is twice the number of commonneighbors divided by the sum of the degrees of the vertices. This functioncalculates 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 isthe (maximum) degree of the vertices in the graph.
See also:
|
Example 13.28. Fileexamples/simple/igraph_similarity.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_matrix_t m; igraph_vector_int_t pairs;igraph_vector_t res; igraph_integer_t i, j, n;igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1);igraph_matrix_init(&m, 0, 0);igraph_vector_init(&res, 0);igraph_vector_int_init(&pairs, 0); n =igraph_vcount(&g);for (i = 0; i < n; i++) {for (j = n - 1; j >= 0; j--) {igraph_vector_int_push_back(&pairs, i);igraph_vector_int_push_back(&pairs, j); } }printf("Jaccard similarity:\n");igraph_similarity_jaccard(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nJaccard similarity, pairs:\n");igraph_similarity_jaccard_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nJaccard similarity with edge selector:\n");igraph_similarity_jaccard_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nDice similarity:\n");igraph_similarity_dice(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nDice similarity, pairs:\n");igraph_similarity_dice_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nDice similarity with edge selector:\n");igraph_similarity_dice_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nWeighted inverse log similarity:\n");igraph_similarity_inverse_log_weighted(&g, &m,igraph_vss_all(), IGRAPH_ALL);igraph_matrix_printf(&m, "%.2f");igraph_matrix_destroy(&m);igraph_destroy(&g);igraph_vector_destroy(&res);igraph_vector_int_destroy(&pairs);return 0;}
igraph_error_t 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 commonneighbors divided by the sum of the degrees of the vertices. This functioncalculates the pairwise Dice similarities for the endpoints of edges in a givenedge 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 isthe (maximum) degree of the vertices in the graph.
See also:
|
Example 13.29. Fileexamples/simple/igraph_similarity.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_matrix_t m; igraph_vector_int_t pairs;igraph_vector_t res; igraph_integer_t i, j, n;igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1);igraph_matrix_init(&m, 0, 0);igraph_vector_init(&res, 0);igraph_vector_int_init(&pairs, 0); n =igraph_vcount(&g);for (i = 0; i < n; i++) {for (j = n - 1; j >= 0; j--) {igraph_vector_int_push_back(&pairs, i);igraph_vector_int_push_back(&pairs, j); } }printf("Jaccard similarity:\n");igraph_similarity_jaccard(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nJaccard similarity, pairs:\n");igraph_similarity_jaccard_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nJaccard similarity with edge selector:\n");igraph_similarity_jaccard_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nDice similarity:\n");igraph_similarity_dice(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nDice similarity, pairs:\n");igraph_similarity_dice_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nDice similarity with edge selector:\n");igraph_similarity_dice_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nWeighted inverse log similarity:\n");igraph_similarity_inverse_log_weighted(&g, &m,igraph_vss_all(), IGRAPH_ALL);igraph_matrix_printf(&m, "%.2f");igraph_matrix_destroy(&m);igraph_destroy(&g);igraph_vector_destroy(&res);igraph_vector_int_destroy(&pairs);return 0;}
igraph_error_t 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 oftheir common neighbors, weighted by the inverse logarithm of their degrees.It is based on the assumption that two vertices should be consideredmore similar if they share a low-degree common neighbor, since high-degreecommon 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.
Note that the presence of loop edges may yield counter-intuitiveresults. A node with a loop edge is considered to be a neighbor of itselftwice (because there are two edge stems incident on the node). Adding aloop edge to a node may decrease its similarity to other nodes, but it mayalsoincrease it. For instance, if nodes A and B are connected but shareno common neighbors, their similarity is zero. However, if a loop edge isadded to B, then B itself becomes a common neighbor of A and B and thus thesimilarity of A and B will be increased. Consider removing loop edgesexplicitly before invoking this function usingigraph_simplify().
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.https://doi.org/10.1016/S0378-8733(03)00009-1
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 inthe graph, d is the (maximum)degree of the vertices in the graph.
Example 13.30. Fileexamples/simple/igraph_similarity.c
#include <igraph.h>intmain(void) { igraph_t g; igraph_matrix_t m; igraph_vector_int_t pairs;igraph_vector_t res; igraph_integer_t i, j, n;igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 2, 1, 2, 0, 3, 0, -1);igraph_matrix_init(&m, 0, 0);igraph_vector_init(&res, 0);igraph_vector_int_init(&pairs, 0); n =igraph_vcount(&g);for (i = 0; i < n; i++) {for (j = n - 1; j >= 0; j--) {igraph_vector_int_push_back(&pairs, i);igraph_vector_int_push_back(&pairs, j); } }printf("Jaccard similarity:\n");igraph_similarity_jaccard(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nJaccard similarity, pairs:\n");igraph_similarity_jaccard_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nJaccard similarity with edge selector:\n");igraph_similarity_jaccard_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nDice similarity:\n");igraph_similarity_dice(&g, &m,igraph_vss_range(1, 3), IGRAPH_ALL, 0);igraph_matrix_printf(&m, "%.2f");printf("\nDice similarity, pairs:\n");igraph_similarity_dice_pairs(&g, &res, &pairs, IGRAPH_ALL, 0);igraph_vector_print(&res);printf("\nDice similarity with edge selector:\n");igraph_similarity_dice_es(&g, &res,igraph_ess_all(IGRAPH_EDGEORDER_FROM), IGRAPH_IN, 0);igraph_vector_print(&res);printf("\nWeighted inverse log similarity:\n");igraph_similarity_inverse_log_weighted(&g, &m,igraph_vss_all(), IGRAPH_ALL);igraph_matrix_printf(&m, "%.2f");igraph_matrix_destroy(&m);igraph_destroy(&g);igraph_vector_destroy(&res);igraph_vector_int_destroy(&pairs);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 samples the spanning trees of a graph.igraph_is_tree — Decides whether the graph is a tree.igraph_is_forest — Decides whether the graph is a forest.igraph_to_prufer — Converts a tree to its Prüfer sequence.igraph_error_t igraph_minimum_spanning_tree( const igraph_t *graph, igraph_vector_int_t *res, const igraph_vector_t *weights);
Finds a spanning tree of the graph. If the graph is not connectedthen its minimum spanning forest is returned. This is the set of theminimum spanning trees of each component.
Directed graphs are considered as undirected for this computation.
This function is deterministic, i.e. it always returns the samespanning tree. Seeigraph_random_spanning_tree() for the uniformrandom sampling of spanning trees of a graph.
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| thenumber of edges in the graph.
See also:
|
Example 13.31. Fileexamples/simple/igraph_minimum_spanning_tree.c
#include <igraph.h>intmain(void) { igraph_t graph;igraph_vector_t eb; igraph_vector_int_t edges;/* Create the vector where the tree edges will be stored. */igraph_vector_int_init(&edges, 0);/* Create the Frucht graph */igraph_famous(&graph, "Frucht");/* Compute the edge betweenness. */igraph_vector_init(&eb,igraph_ecount(&graph));igraph_edge_betweenness(&graph, &eb, IGRAPH_UNDIRECTED,/*weights=*/ NULL);/* Use Prim's algorithm to compute the edges that belong to the minimum weight * spanning tree, using edge betweenness values as edge weights. */igraph_minimum_spanning_tree(&graph, &edges, &eb);printf("Minimum spanning tree edges:\n");igraph_vector_int_print(&edges);/* A maximum spanning tree can be computed by first negating the weights. */igraph_vector_scale(&eb, -1);/* Compute and output the edges that belong to the maximum weight spanning tree, * letting igraph automatically select the most suitable algorithm. */igraph_minimum_spanning_tree(&graph, &edges, &eb);printf("\nMaximum spanning tree edges:\n");igraph_vector_int_print(&edges); igraph_real_t total_tree_weight = 0; igraph_integer_t n =igraph_vector_int_size(&edges);for (igraph_integer_t i=0; i < n; i++) { total_tree_weight += -VECTOR(eb)[VECTOR(edges)[i] ]; }printf("\nTotal maximum spanning tree weight: %g\n", total_tree_weight);/* Clean up */igraph_destroy(&graph);igraph_vector_destroy(&eb);igraph_vector_int_destroy(&edges);return 0;}
igraph_error_t igraph_minimum_spanning_tree_unweighted(const igraph_t *graph, igraph_t *mst);
Deprecated since version 0.10.14. Please do not use this function in newcode; useigraph_minimum_spanning_tree()instead.
If the graph has more minimum spanning trees (this is always thecase, except if it is a forest) this implementation returns onlythe same one.
Directed graphs are considered as undirected for this computation.
If the graph is not connected then its minimum spanning forest isreturned. This is the set of the minimum spanning trees of eachcomponent.
Arguments:
| The graph object. Edge directions will be ignored. |
| The minimum spanning tree, another graph object. Donot initialize this object before passing it to this function, but be sure to call |
Returns:
Error code: |
Time complexity: O(|V|+|E|),|V| is thenumber of vertices, |E| the numberof edges in the graph.
See also:
|
igraph_error_t igraph_minimum_spanning_tree_prim(const igraph_t *graph, igraph_t *mst, const igraph_vector_t *weights);
Deprecated since version 0.10.14. Please do not use this function in newcode; useigraph_minimum_spanning_tree()instead.
Finds a spanning tree or spanning forest for which the sum of edgeweights is the smallest. This function uses Prim's method for carryingout the computation.
Directed graphs are considered as undirected for this computation.
Reference:
Prim, R.C.: Shortest connection networks and somegeneralizations, Bell System TechnicalJournal, Vol. 36,1957, 1389--1401.https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
Arguments:
| The graph object. Edge directions will be ignored. |
| The result of the computation, a graph object containing the minimum spanning tree of the graph. Donot 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 thegraph.
See also:
|
Example 13.32. Fileexamples/simple/igraph_minimum_spanning_tree.c
#include <igraph.h>intmain(void) { igraph_t graph;igraph_vector_t eb; igraph_vector_int_t edges;/* Create the vector where the tree edges will be stored. */igraph_vector_int_init(&edges, 0);/* Create the Frucht graph */igraph_famous(&graph, "Frucht");/* Compute the edge betweenness. */igraph_vector_init(&eb,igraph_ecount(&graph));igraph_edge_betweenness(&graph, &eb, IGRAPH_UNDIRECTED,/*weights=*/ NULL);/* Use Prim's algorithm to compute the edges that belong to the minimum weight * spanning tree, using edge betweenness values as edge weights. */igraph_minimum_spanning_tree(&graph, &edges, &eb);printf("Minimum spanning tree edges:\n");igraph_vector_int_print(&edges);/* A maximum spanning tree can be computed by first negating the weights. */igraph_vector_scale(&eb, -1);/* Compute and output the edges that belong to the maximum weight spanning tree, * letting igraph automatically select the most suitable algorithm. */igraph_minimum_spanning_tree(&graph, &edges, &eb);printf("\nMaximum spanning tree edges:\n");igraph_vector_int_print(&edges); igraph_real_t total_tree_weight = 0; igraph_integer_t n =igraph_vector_int_size(&edges);for (igraph_integer_t i=0; i < n; i++) { total_tree_weight += -VECTOR(eb)[VECTOR(edges)[i] ]; }printf("\nTotal maximum spanning tree weight: %g\n", total_tree_weight);/* Clean up */igraph_destroy(&graph);igraph_vector_destroy(&eb);igraph_vector_int_destroy(&edges);return 0;}
igraph_error_t igraph_random_spanning_tree(const igraph_t *graph, igraph_vector_int_t *res, igraph_integer_t vid);
Performs a loop-erased random walk on the graph to uniformly sampleits spanning trees. Edge directions are ignored.
Multi-graphs are supported, and edge multiplicities will affect the samplingfrequency. For example, consider the 3-cycle graph1=2-3-1, with two edgesbetween vertices 1 and 2. Due to these parallel edges, the trees1-2-3and3-1-2 will be sampled with multiplicity 2, while the tree2-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:
igraph_error_t 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, an additional requirement is that all edgesare oriented away from a root (out-tree or arborescence) or all edgesare oriented towards a root (in-tree or anti-arborescence).This test can be controlled using themode parameter.
By convention, the null graph (i.e. the graph with no vertices) is considerednot to be connected, and therefore not a tree.
Arguments:
| The graph object to analyze. |
| Pointer to a Boolean 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|), thenumber of vertices plus the number of edges in the graph.
See also:
|
Example 13.33. Fileexamples/simple/igraph_kary_tree.c
#include <igraph.h>intmain(void) { igraph_t graph; igraph_bool_t res;/* Create a directed binary tree on 15 nodes, with edges pointing towards the root. */igraph_kary_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;}
igraph_error_t igraph_is_forest(const igraph_t *graph, igraph_bool_t *res, igraph_vector_int_t *roots, igraph_neimode_t mode);
An undirected graph is a forest if it has no cycles. Equivalently,a graph is a forest if all connected components are trees.
In the directed case, an additional requirement is that edges in eachtree are oriented away from the root (out-trees or arborescences) or all edgesare oriented towards the root (in-trees or anti-arborescences).This test can be controlled using themode parameter.
By convention, the null graph (i.e. the graph with no vertices) is consideredto be a forest.
Theres return value of this function is cached in the graph itself ifmode is set toIGRAPH_ALL or if the graph is undirected. Calling thefunction multiple times with no modifications to the graph in betweenwill return a cached value in O(1) time if the roots are not requested.
Arguments:
| The graph object to analyze. |
| Pointer to a Boolean variable. If not |
| If not |
| For a directed graph this specifies whether to test for an out-forest, an in-forest or ignore edge directions. The respective possible values are: |
Returns:
Error code: |
Time complexity: At most O(|V|+|E|), thenumber of vertices plus the number of edges in the graph.
See also:
|
igraph_error_t igraph_to_prufer(const igraph_t *graph, igraph_vector_int_t* prufer);
A Prüfer sequence is a unique sequence of integers associatedwith a labelled tree. A tree on n >= 2 vertices can be represented by asequence 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 — The local transitivity (clustering coefficient) of some vertices.igraph_transitivity_avglocal_undirected — Average local transitivity (clustering coefficient).igraph_transitivity_barrat — Weighted local transitivity of some vertices, as defined by A. Barrat.igraph_ecc — Edge clustering coefficient of some edges.igraph_error_t 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 avertex are connected. More precisely, this is the ratio of thetriangles and connected triples in the graph, the result is asingle real number. Directed graphs are considered as undirected onesand multi-edges are ignored.
Note that this measure is different from the local transitivity measure(seeigraph_transitivity_local_undirected() ) as it calculates a singlevalue for the whole graph.
Clustering coefficient is an alternative name for transitivity.
References:
S. Wasserman and K. Faust: Social Network Analysis: Methods andApplications. 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 inthe graph, d is the average node degree.
Example 13.34. Fileexamples/simple/igraph_transitivity.c
#include <igraph.h>intmain(void) { 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;}
igraph_error_t 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 avertex are connected. In case of the local transitivity, thisprobability is calculated separately for each vertex.
Note that this measure is different from the global transitivity measure(seeigraph_transitivity_undirected() ) as it calculates a transitivityvalue 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 whichthe transitivity is calculated, d is the average vertex degree.
igraph_error_t 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 avertex are connected. In case of the average local transitivity,this probability is calculated for each vertex and then the averageis taken. Vertices with less than two neighbors require special treatment,they will either be left out from the calculation or they will be consideredas having zero transitivity, depending on themode argument.Edge directions and edge multiplicities are ignored.
Note that this measure is different from the global transitivity measure(seeigraph_transitivity_undirected() ) as it simply takes theaverage 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 thegraph and d is the average degree.
igraph_error_t 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 agiven vertexi, from all triangles in which it participates weconsider the weight of the edges incident oni. The transitivityis the sum of these weights divided by twice the strength of thevertex (seeigraph_strength()) and the degree of the vertexminus one. See equation (5) in Alain Barrat, Marc Barthelemy, RomualdoPastor-Satorras, Alessandro Vespignani: The architecture of complexweighted networks, Proc. Natl. Acad. Sci. USA 101, 3747 (2004) athttps://doi.org/10.1073/pnas.0400087101 for the exact formula.
Arguments:
| The input graph. Edge directions are ignored for directed graphs. Note that the function doesnot 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 inthe graph, d is the average node degree.
See also:
|
igraph_error_t igraph_ecc(const igraph_t *graph, igraph_vector_t *res, const igraph_es_t eids, igraph_integer_t k, igraph_bool_t offset, igraph_bool_t normalize);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
The edge clustering coefficientC^(k)_ij of an edge (i, j)is defined based on the number of k-cycles the edge participates in,z^(k)_ij, and the largest number of such cycles it couldparticipate in given the degrees of its endpoints,s^(k)_ij.The original definition given in the reference below is:
C^(k)_ij = (z^(k)_ij + 1) / s^(k)_ij
Fork=3,s^(k)_ij = min(d_i - 1, d_j - 1),whered_i andd_j are the edge endpoint degrees.Fork=4,s^(k)_ij = (d_i - 1) (d_j - 1).
Thenormalize andoffset parameters allow for skipping normalizationbys^(k) and offsetting the cycle countz^(k)by one in the numerator ofC^(k). Set both totrue tocompute the original definition of this metric.
This function ignores edge multiplicities when listing k-cycles(i.e.z^(k)), but not when computing the maximum number ofcycles an edge can participate in (s^(k)).
Reference:
F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi,PNAS 101, 2658 (2004).https://doi.org/10.1073/pnas.0400054101
Arguments:
| The input graph. |
| Initialized vector, the result will be stored here. |
| The edges for which the edge clustering coefficient will be computed. |
| Size of cycles to use in calculation. Must be at least 3. Currently only values of 3 and 4 are supported. |
| Boolean, whether to add one to cycle counts. When |
| Boolean, whether to normalize cycle counts by the maximum possible count |
Returns:
Error code. |
Time complexity: Whenk is 3, O(|V| d log d + |E| d).Whenk is 4, O(|V| d log d + |E| d^2). d denotes the degree of vertices.
igraph_error_t 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 numberof edges.
igraph_error_t 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 numberof edges.
Example 13.35. Fileexamples/simple/igraph_to_undirected.c
#include <igraph.h>intmain(void) { igraph_vector_int_t v; igraph_t g;igraph_vector_int_init_int(&v, 2, 5, 5);igraph_square_lattice(&g, &v, 1, IGRAPH_DIRECTED, 1/*mutual*/, 0/*periodic*/);igraph_to_undirected(&g, IGRAPH_TO_UNDIRECTED_COLLAPSE,/*edge_comb=*/ 0);igraph_write_graph_edgelist(&g, stdout);igraph_destroy(&g);igraph_vector_int_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;}
igraph_error_t igraph_get_laplacian( const igraph_t *graph, igraph_matrix_t *res, igraph_neimode_t mode, igraph_laplacian_normalization_t normalization, const igraph_vector_t *weights);
The Laplacian matrixL of a graph is defined asL_ij = - A_ij wheni != j andL_ii = d_i - A_ii. HereA denotes the (possibly weighted)adjacency matrix andd_i is the degree (or strength, if weighted)of vertexi. In directed graphs, themode parameter controls whether to useout- or in-degrees. Correspondingly, the rows or columns will sum to zero.In undirected graphs,A_ii is taken to betwice the number(or total weight) of self-loops, ensuring thatd_i = \sum_j A_ij.Thus, the Laplacian of an undirected graph is the same as the Laplacianof a directed one obtained by replacing each undirected edge with two reciprocaldirected ones.
More compactly,L = D - A where theD is a diagonal matrixcontaining the degrees. The Laplacian matrix can also be normalized, with severalconventional normalization methods. Seeigraph_laplacian_normalization_t forthe methods available in igraph.
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. |
| Controls whether to use out- or in-degrees in directed graphs. If set to |
| The normalization method to use when calculating the Laplacian matrix. See |
| An optional vector containing non-negative 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|^2), |V| is the number of vertices in the graph.
Example 13.36. Fileexamples/simple/igraph_get_laplacian.c
#include <igraph.h>intmain(void) { igraph_t g;igraph_vector_t weights; igraph_matrix_t m;igraph_matrix_init(&m, 1, 1);igraph_vector_init_int(&weights, 5, 1, 2, 3, 4, 5);igraph_ring(&g, 5, IGRAPH_DIRECTED, 0, 1);igraph_get_laplacian(&g, &m, IGRAPH_OUT, IGRAPH_LAPLACIAN_SYMMETRIC, &weights);igraph_matrix_print(&m);igraph_vector_destroy(&weights);igraph_matrix_destroy(&m);igraph_destroy(&g);}
igraph_error_t igraph_get_laplacian_sparse( const igraph_t *graph, igraph_sparsemat_t *sparseres, igraph_neimode_t mode, igraph_laplacian_normalization_t normalization, const igraph_vector_t *weights);
Seeigraph_get_laplacian() for the definition of the Laplacian matrix.
The first version of this function was written by Vincent Matossian.
Arguments:
| Pointer to the graph to convert. |
| Pointer to an initialized sparse matrix object, the result is stored here. |
| Controls whether to use out- or in-degrees in directed graphs. If set to |
| The normalization method to use when calculating the Laplacian matrix. See |
| An optional vector containing non-negative 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(|E|), |E| is the number of edges in the graph.
Example 13.37. Fileexamples/simple/igraph_get_laplacian_sparse.c
#include <igraph.h>inttest_laplacian(constigraph_vector_t *w, igraph_bool_t dir,igraph_laplacian_normalization_t normalization) { igraph_t g; igraph_matrix_t m; igraph_sparsemat_t sm; igraph_vector_int_t vec;igraph_vector_t *weights = 0; igraph_neimode_t mode = IGRAPH_OUT;igraph_sparsemat_init(&sm, 0, 0, 0);if (w) { weights = (igraph_vector_t*)calloc(1,sizeof(igraph_vector_t));igraph_vector_init_copy(weights, w); }/* Base graph, no loop or multiple edges */igraph_ring(&g, 5, dir, 0, 1);igraph_get_laplacian_sparse(&g, &sm, mode, normalization, weights);igraph_matrix_init(&m, 0, 0);igraph_sparsemat_as_matrix(&m, &sm);igraph_matrix_print(&m);igraph_matrix_destroy(&m);printf("===\n");/* Add some loop edges */igraph_vector_int_init_int(&vec, 4, 1, 1, 2, 2);igraph_add_edges(&g, &vec, 0);igraph_vector_int_destroy(&vec);if (weights) {igraph_vector_push_back(weights, 2);igraph_vector_push_back(weights, 2); }igraph_get_laplacian_sparse(&g, &sm, mode, normalization, weights);igraph_matrix_init(&m, 0, 0);igraph_sparsemat_as_matrix(&m, &sm);igraph_matrix_print(&m);igraph_matrix_destroy(&m);printf("===\n");/* Duplicate some edges */igraph_vector_int_init_int(&vec, 4, 1, 2, 3, 4);igraph_add_edges(&g, &vec, 0);igraph_vector_int_destroy(&vec);if (weights) {igraph_vector_push_back(weights, 3);igraph_vector_push_back(weights, 3); }igraph_get_laplacian_sparse(&g, &sm, mode, normalization, weights);igraph_matrix_init(&m, 0, 0);igraph_sparsemat_as_matrix(&m, &sm);igraph_matrix_print(&m);igraph_matrix_destroy(&m);printf("===\n");/* Add an isolated vertex */igraph_add_vertices(&g, 1, NULL);igraph_get_laplacian_sparse(&g, &sm, mode, normalization, weights);igraph_matrix_init(&m, 0, 0);igraph_sparsemat_as_matrix(&m, &sm);igraph_matrix_print(&m);igraph_matrix_destroy(&m);igraph_destroy(&g);if (weights) {igraph_vector_destroy(weights);free(weights); }igraph_sparsemat_destroy(&sm);return 0;}intmain(void) { int res; int i;igraph_vector_t weights;igraph_vector_init_int(&weights, 5, 1, 2, 3, 4, 5);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") ); res =test_laplacian(v, dir, is_normalized ? IGRAPH_LAPLACIAN_SYMMETRIC : IGRAPH_LAPLACIAN_UNNORMALIZED);if (res) {return i + 1; } }igraph_vector_destroy(&weights);return 0;}
typedef enum { IGRAPH_LAPLACIAN_UNNORMALIZED = 0, IGRAPH_LAPLACIAN_SYMMETRIC = 1, IGRAPH_LAPLACIAN_LEFT = 2, IGRAPH_LAPLACIAN_RIGHT = 3} igraph_laplacian_normalization_t;Normalization methods forigraph_get_laplacian() andigraph_get_laplacian_sparse(). In the following,A refers to the(possibly weighted) adjacency matrix andD is a diagonal matrix containingdegrees (unweighted case) or strengths (weighted case). Out-, in- or total degreesare used according to themode parameter.
Values:
| Unnormalized Laplacian, |
| Symmetrically normalized Laplacian, |
| Left-stochastic normalized Laplacian, |
| Right-stochastic normalized Laplacian, |
igraph_is_simple — Decides whether the input graph is a simple graph.igraph_is_loop — Find the loop edges in a graph.igraph_has_loop — Returns whether the graph has at least one loop edge.igraph_count_loops — Counts the self-loops in the 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 — The multiplicity of some edges in a graph.igraph_count_multiple_1 — The multiplicity of a single edge in a graph.igraph_error_t igraph_is_simple(const igraph_t *graph, igraph_bool_t *res);
A graph is a simple graph if it does not contain loop edges andmultiple 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|).
igraph_error_t igraph_is_loop(const igraph_t *graph, igraph_vector_bool_t *res, igraph_es_t es);
A loop edge, also called a self-loop, 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.38. Fileexamples/simple/igraph_is_loop.c
#include <igraph.h>voidanalyze_loops(const igraph_t *graph) { igraph_vector_bool_t is_loop; igraph_bool_t has_loop; igraph_integer_t loop_count;igraph_has_loop(graph, &has_loop);printf("Has loops? %s\n", has_loop ? "Yes" : "No");igraph_count_loops(graph, &loop_count);printf("How many? %" IGRAPH_PRId "\n", loop_count);igraph_vector_bool_init(&is_loop, 0);igraph_is_loop(graph, &is_loop,igraph_ess_all(IGRAPH_EDGEORDER_ID));printf("Loop positions: ");igraph_vector_bool_print(&is_loop);igraph_vector_bool_destroy(&is_loop);printf("\n");}intmain(void) { igraph_t graph;igraph_small(&graph, 0, IGRAPH_DIRECTED, 0,1, 1,2, 2,1, 0,1, 1,0, 3,4, 11,10, -1);analyze_loops(&graph);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);analyze_loops(&graph);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_has_loop(const igraph_t *graph, igraph_bool_t *res);
A loop edge is an edge from a vertex to itself.
The return value of this function is cached in the graph itself; callingthe function multiple times with no modifications to the graph in betweenwill return a cached value in O(1) time.
Arguments:
| The input graph. |
| Pointer to an initialized boolean vector for storing the result. |
Returns:
Error code. |
See also:
|
Time complexity: O(e), the number of edges to check.
Example 13.39. Fileexamples/simple/igraph_is_loop.c
#include <igraph.h>voidanalyze_loops(const igraph_t *graph) { igraph_vector_bool_t is_loop; igraph_bool_t has_loop; igraph_integer_t loop_count;igraph_has_loop(graph, &has_loop);printf("Has loops? %s\n", has_loop ? "Yes" : "No");igraph_count_loops(graph, &loop_count);printf("How many? %" IGRAPH_PRId "\n", loop_count);igraph_vector_bool_init(&is_loop, 0);igraph_is_loop(graph, &is_loop,igraph_ess_all(IGRAPH_EDGEORDER_ID));printf("Loop positions: ");igraph_vector_bool_print(&is_loop);igraph_vector_bool_destroy(&is_loop);printf("\n");}intmain(void) { igraph_t graph;igraph_small(&graph, 0, IGRAPH_DIRECTED, 0,1, 1,2, 2,1, 0,1, 1,0, 3,4, 11,10, -1);analyze_loops(&graph);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);analyze_loops(&graph);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_count_loops(const igraph_t *graph, igraph_integer_t *loop_count);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Counts loop edges, i.e. edges whose two endpoints coincide.
Arguments:
| The input graph. |
| Pointer to an integer, the number of self-loops will be stored here. |
Returns:
Error code. |
Time complexity: O(|E|), linear in the number of edges.
Example 13.40. Fileexamples/simple/igraph_is_loop.c
#include <igraph.h>voidanalyze_loops(const igraph_t *graph) { igraph_vector_bool_t is_loop; igraph_bool_t has_loop; igraph_integer_t loop_count;igraph_has_loop(graph, &has_loop);printf("Has loops? %s\n", has_loop ? "Yes" : "No");igraph_count_loops(graph, &loop_count);printf("How many? %" IGRAPH_PRId "\n", loop_count);igraph_vector_bool_init(&is_loop, 0);igraph_is_loop(graph, &is_loop,igraph_ess_all(IGRAPH_EDGEORDER_ID));printf("Loop positions: ");igraph_vector_bool_print(&is_loop);igraph_vector_bool_destroy(&is_loop);printf("\n");}intmain(void) { igraph_t graph;igraph_small(&graph, 0, IGRAPH_DIRECTED, 0,1, 1,2, 2,1, 0,1, 1,0, 3,4, 11,10, -1);analyze_loops(&graph);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);analyze_loops(&graph);igraph_destroy(&graph);return 0;}
igraph_error_t 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 anotheredge with the same head and tail vertices in the graph.
Note that this function returns true only for the second or moreappearances 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 theaverage degree (out-degree in directed graphs) of the vertices at thetail of the edges.
Example 13.41. Fileexamples/simple/igraph_is_multiple.c
#include <igraph.h>voidprint_vector(igraph_vector_bool_t *v, FILE *f) { igraph_integer_t i;for (i = 0; i <igraph_vector_bool_size(v); i++) {fprintf(f, " %i",VECTOR(*v)[i] ? 1 : 0); }fprintf(f, "\n");}intmain(void) { 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;}
igraph_error_t igraph_has_multiple(const igraph_t *graph, igraph_bool_t *res);
An edge is a multiple edge if there is anotheredge with the same head and tail vertices in the graph.
The return value of this function is cached in the graph itself; callingthe function multiple times with no modifications to the graph in betweenwill return a cached value in O(1) time.
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 theaverage degree (out-degree in directed graphs) of the vertices at thetail of the edges.
Example 13.42. Fileexamples/simple/igraph_has_multiple.c
#include <igraph.h>intmain(void) { 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;}
igraph_error_t igraph_count_multiple(const igraph_t *graph, igraph_vector_int_t *res, igraph_es_t es);
An edge is called a multiple edge when there is one or more otheredge between the same two vertices. The multiplicity of an edgeis the number of edges between its endpoints.
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 theaverage degree (out-degree in directed graphs) of the vertices at thetail of the edges.
igraph_error_t igraph_count_multiple_1(const igraph_t *graph, igraph_integer_t *res, igraph_integer_t eid);
Arguments:
| The input graph. |
| Pointer to an iteger, the result will be stored here. |
| The ID of the edge to check. |
Returns:
Error code. |
See also:
|
Time complexity: O(d), where d is the out-degree of the tail of the edge.
igraph_assortativity_nominal — Assortativity of a graph based on vertex categories.igraph_assortativity — Assortativity based on numeric properties of vertices.igraph_assortativity_degree — Assortativity of a graph based on vertex degree.igraph_avg_nearest_neighbor_degree — Average neighbor degree.igraph_degree_correlation_vector — Degree correlation function.igraph_joint_type_distribution — Mixing matrix for vertex categories.igraph_joint_degree_distribution — The joint degree distribution of a graph.igraph_joint_degree_matrix — The joint degree matrix of a graph.igraph_rich_club_sequence — Density sequence of subgraphs formed by sequential vertex removal.igraph_error_t igraph_assortativity_nominal(const igraph_t *graph, const igraph_vector_int_t *types, igraph_real_t *res, igraph_bool_t directed, igraph_bool_t normalized);
Assuming the vertices of the input graph belong to differentcategories, this function calculates the assortativity coefficient ofthe graph. The assortativity coefficient is between minus one and oneand it is one if all connections stay within categories, it isminus one, if the network is perfectly disassortative. For arandomly connected network it is (asymptotically) zero.
The unnormalized version, computed whennormalized is set to false,is identical to the modularity, and is defined as follows fordirected networks:
1/m sum_ij (A_ij - k^out_i k^in_j / m) d(i,j),
wherem denotes the number of edges,A_ij is the adjacency matrix,k^out andk^in are the out- and in-degrees,andd(i,j) is one if verticesi andj are in the samecategory and zero otherwise.
The normalized assortativity coefficient is obtained by dividing theprevious expression by
1/m sum_ij (m - k^out_i k^in_j d(i,j) / m).
It can take any value within the interval [-1, 1].
Undirected graphs are effectively treated as directed ones with all-reciprocaledges. Thus, self-loops are taken into account twice in undirected graphs.
References:
M. E. J. Newman: Mixing patterns in networks,Phys. Rev. E 67, 026126 (2003)https://doi.org/10.1103/PhysRevE.67.026126.See section II and equation (2) for the definition of the concept.
For an educational overview of assortativity, seeM. E. J. Newman,Networks: An Introduction, Oxford University Press (2010).https://doi.org/10.1093/acprof%3Aoso/9780199206650.001.0001.
Arguments:
| The input graph, it can be directed or undirected. |
| Integer vector giving the vertex categories. The types are represented by integers starting at 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. |
| Boolean, whether to compute the usual normalized assortativity. The unnormalized version is identical to modularity. Supply true here to compute the standard assortativity. |
Returns:
Error code. |
Time complexity: O(|E|+t), |E| is the number of edges, t is thenumber of vertex types.
See also:
|
Example 13.43. Fileexamples/simple/igraph_assortativity_nominal.c
#include <igraph.h>#include <stdio.h>intmain(void) { igraph_integer_t nodes = 120, types = 4; igraph_matrix_t pref_matrix;igraph_matrix_init(&pref_matrix, types, types);igraph_rng_seed(igraph_rng_default(), 42);printf("Randomly generated graph with %" IGRAPH_PRId " nodes and %" IGRAPH_PRId " vertex types\n\n", nodes, types);/* Generate preference matrix giving connection probabilities for different vertex types */for (igraph_integer_t i = 0; i < types; i++) {for (igraph_integer_t j = 0; j < types; j++) {MATRIX(pref_matrix, i, j) = (i == j ? 0.1: 0.01); } } igraph_vector_int_t node_type_vec;igraph_vector_int_init(&node_type_vec, nodes);for (int i = 0; i < 5; i++) { igraph_real_t assortativity; igraph_t g;/* Generate undirected graph with 1000 nodes and 50 vertex types */igraph_preference_game(&g, nodes, types,/* type_dist= */ NULL,/* fixed_sizes= */ 1, &pref_matrix, &node_type_vec, IGRAPH_UNDIRECTED, IGRAPH_NO_LOOPS);igraph_assortativity_nominal(&g, &node_type_vec, &assortativity, IGRAPH_UNDIRECTED, 1);printf("Assortativity before rewiring = %g\n", assortativity);/* Rewire graph */igraph_rewire(&g, 10 *igraph_ecount(&g), IGRAPH_REWIRING_SIMPLE);igraph_assortativity_nominal(&g, &node_type_vec, &assortativity, IGRAPH_UNDIRECTED, 1);printf("Assortativity after rewiring = %g\n\n", assortativity);igraph_destroy(&g); }igraph_vector_int_destroy(&node_type_vec);igraph_matrix_destroy(&pref_matrix);}
igraph_error_t igraph_assortativity(const igraph_t *graph, const igraph_vector_t *values, const igraph_vector_t *values_in, igraph_real_t *res, igraph_bool_t directed, igraph_bool_t normalized);
This function calculates the assortativity coefficient of agraph based on given valuesx_i for each vertexi. This type ofassortativity coefficient equals the Pearson correlation of the valuesat the two ends of the edges.
The unnormalized covariance of values, computed whennormalized isset to false, is defined as follows in a directed graph:
cov(x_out, x_in) = 1/m sum_ij (A_ij - k^out_i k^in_j / m) x_i x_j,
wherem denotes the number of edges,A_ij is the adjacency matrix, andk^out andk^in are the out- and in-degrees.x_out andx_in refer to the sets of vertex values at the start and end ofthe directed edges.
The normalized covariance, i.e. Pearson correlation, is obtained by dividingthe previous expression bysqrt(var(x_out)) sqrt(var(x_in)), where
var(x_out) = 1/m sum_i k^out_i x_i^2 - (1/m sum_i k^out_i x_i^2)^2
var(x_in) = 1/m sum_j k^in_j x_j^2 - (1/m sum_j k^in_j x_j^2)^2
Undirected graphs are effectively treated as directed graphs where all edgesare reciprocal. Therefore, self-loops are effectively considered twice inundirected graphs.
References:
M. E. J. Newman: Mixing patternsin networks, Phys. Rev. E 67, 026126 (2003)https://doi.org/10.1103/PhysRevE.67.026126.See section III and equation (21) for the definition, and equation (26) forperforming the calculation in directed graphs with the degrees as values.
M. E. J. Newman: Assortative mixing in networks,Phys. Rev. Lett. 89, 208701 (2002)https://doi.org/10.1103/PhysRevLett.89.208701.See equation (4) for performing the calculation in undirectedgraphs with the degrees as values.
For an educational overview of the concept of assortativity, seeM. E. J. Newman,Networks: An Introduction, Oxford University Press (2010).https://doi.org/10.1093/acprof%3Aoso/9780199206650.001.0001.
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 used for the incoming edges when calculating assortativity for a directed graph. Supply |
| 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. |
| Boolean, whether to compute the normalized covariance, i.e. Pearson correlation. Supply true here to compute the standard assortativity. |
Returns:
Error code. |
Time complexity: O(|E|), linear in the number of edges of thegraph.
See also:
|
igraph_error_t igraph_assortativity_degree(const igraph_t *graph, igraph_real_t *res, igraph_bool_t directed);
Assortativity based on vertex degree, please see the discussion atthe documentation ofigraph_assortativity() for details.This function simply callsigraph_assortativity() withthe degrees as the vertex values and normalization enabled.In the directed case, it uses out-degrees as out-values andin-degrees as in-values.
For regular graphs, i.e. graphs in which all vertices have thesame degree, computing degree correlations is not meaningful,and this function returns NaN.
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 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| isthe number of vertices.
See also:
|
Example 13.44. Fileexamples/simple/igraph_assortativity_degree.c
#include <igraph.h>#include <stdio.h>intmain(void){ igraph_t g; igraph_integer_t vcount = 1000; igraph_real_t pf = 0.2;/* Seed random number generator to ensure reproducibility. */igraph_rng_seed(igraph_rng_default(), 42);printf("Forest fire model network with %" IGRAPH_PRId " vertices and %g forward burning probability.\n\n", vcount, pf);for (int i = 0; i < 5; i++) { igraph_real_t assortativity;/* Generate graph from the forest fire model. */igraph_forest_fire_game(&g, vcount, pf, 1.0, 1, IGRAPH_UNDIRECTED);/* Compute assortativity. */igraph_assortativity_degree(&g, &assortativity,/* ignore edge directions */ IGRAPH_UNDIRECTED);printf("Assortativity before rewiring = %g\n", assortativity);/* Randomize the graph while preserving the degrees. */igraph_rewire(&g, 20 *igraph_ecount(&g), IGRAPH_REWIRING_SIMPLE);/* Re-compute assortativity. Did it change? */igraph_assortativity_degree(&g, &assortativity,/* ignore edge directions */ IGRAPH_UNDIRECTED);printf("Assortativity after rewiring = %g\n\n", assortativity);igraph_destroy(&g); }}
igraph_error_t igraph_avg_nearest_neighbor_degree(const igraph_t *graph, igraph_vs_t vids, igraph_neimode_t mode, igraph_neimode_t neighbor_degree_mode, igraph_vector_t *knn, igraph_vector_t *knnk, const igraph_vector_t *weights);
Calculates the average degree of the neighbors for each vertex (knn), andoptionally, the same quantity as a function of the vertex degree (knnk).
For isolated verticesknn is set to NaN. The same is done inknnk forvertex degrees that don't appear in the graph.
The weighted version computes a weighted average of the neighbor degrees as
k_nn_u = 1/s_u sum_v w_uv k_v,
wheres_u = sum_v w_uv is the sum of the incident edge weightsof vertexu, i.e. its strength.The sum runs over the neighborsv of vertexuas indicated bymode.w_uv denotes the weighted adjacency matrixandk_v is the neighbors' degree, specified byneighbor_degree_mode.This is equation (6) in the reference below.
When only thek_nn(k) degree correlation function is needed,igraph_degree_correlation_vector() can be used as well. This function providesmore flexible control over how degree at each end of directed edges are computed.
Reference:
A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani,The architecture of complex weighted networks,Proc. Natl. Acad. Sci. USA 101, 3747 (2004).https://dx.doi.org/10.1073/pnas.0400087101
Arguments:
| The input graph. It may be directed. |
| The vertices for which the calculation is performed. |
| The type of neighbors to consider in directed graphs. |
| The type of degree to average in directed graphs. |
| Pointer to an initialized vector, the result will be stored here. It will be resized as needed. Supply a |
| Pointer to an initialized vector, the average neighbor degree as a function of the vertex degree is stored here. This is sometimes referred to as the |
| Optional edge weights. Supply a null pointer here for the non-weighted version. |
Returns:
Error code. |
See also:
|
Time complexity: O(|V|+|E|), linear in the number of vertices andedges.
Example 13.45. Fileexamples/simple/igraph_avg_nearest_neighbor_degree.c
#include <igraph.h>intmain(void) { igraph_t graph;igraph_vector_t knn, knnk;igraph_vector_t weights;igraph_famous(&graph, "Zachary");igraph_vector_init(&knn, 0);igraph_vector_init(&knnk, 0);igraph_avg_nearest_neighbor_degree(&graph,igraph_vss_all(), IGRAPH_ALL, IGRAPH_ALL, &knn, &knnk,/*weights=*/ NULL);printf("knn: ");igraph_vector_print(&knn);printf("knn(k): ");igraph_vector_print(&knnk);igraph_vector_init_range(&weights, 0,igraph_ecount(&graph));igraph_avg_nearest_neighbor_degree(&graph,igraph_vss_all(), IGRAPH_ALL, IGRAPH_ALL, &knn, &knnk, &weights);igraph_vector_destroy(&weights);printf("knn: ");igraph_vector_print(&knn);printf("knn(k): ");igraph_vector_print(&knnk);igraph_vector_destroy(&knn);igraph_vector_destroy(&knnk);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_degree_correlation_vector( const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_t *knnk, igraph_neimode_t from_mode, igraph_neimode_t to_mode, igraph_bool_t directed_neighbors);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Computes the degree correlation functionk_nn(k), defined as themean degree of the targets of directed edges whose source has degreek.The averaging is done over all directed edges. Thefrom_mode andto_modeparameters control how the source and target vertex degrees are computed.This way the out-in, out-out, in-in and in-out degree correlation functionscan all be computed.
In undirected graphs, edges are treated as if they were a pair of reciprocal directedones.
If P_ij is the joint degree distribution of the graph, computable withigraph_joint_degree_distribution(), thenk_nn(k) = (sum_j j P_kj) / (sum_j P_kj).
The functionigraph_avg_nearest_neighbor_degree(), whose main purpose is tocalculate the average neighbor degree for each vertex separately, can also computek_nn(k). It differs from this function in that it can take a subsetof vertices to base the calculation on, but it does not allow the same fine-grainedcontrol over how degrees are computed.
References:
R. Pastor-Satorras, A. Vazquez, A. Vespignani:Dynamical and Correlation Properties of the Internet,Phys. Rev. Lett., vol. 87, pp. 258701 (2001).https://doi.org/10.1103/PhysRevLett.87.258701
A. Vazquez, R. Pastor-Satorras, A. Vespignani:Large-scale topological and dynamical properties of the Internet,Phys. Rev. E, vol. 65, pp. 066130 (2002).https://doi.org/10.1103/PhysRevE.65.066130
A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani,The architecture of complex weighted networks,Proc. Natl. Acad. Sci. USA 101, 3747 (2004).https://dx.doi.org/10.1073/pnas.0400087101
Arguments:
| The input graph. |
| An optional weight vector. If not |
| An initialized vector, the result will be written here. |
| How to compute the degree of sources? Can be |
| How to compute the degree of sources? Can be |
| Whether to consider |
Returns:
Error code. |
See also:
|
Time complexity: O(|E| + |V|)
igraph_error_t igraph_joint_type_distribution( const igraph_t *graph, const igraph_vector_t *weights, igraph_matrix_t *p, const igraph_vector_int_t *from_types, const igraph_vector_int_t *to_types, igraph_bool_t directed, igraph_bool_t normalized);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Computes the mixing matrix M_ij, i.e. the joint distribution of vertex typesat the endpoints directed of edges. Categories are represented by non-negative integerindices, passed infrom_types andto_types. The row and column counts ofmwill be one larger than the largest source and target type, respectively. Re-index typevectors usingigraph_reindex_membership() if they are not contiguous integers,to avoid producing a very large matrix.
M_ij is proportional to the probability that a randomly chosen ordered pair of verticeshave typesi andj.
When there is a single categorization of vertices, i.e.from_types andto_typesare the same, M_ij is related to the modularity (igraph_modularity()) and nominalassortativity (igraph_assortativity_nominal()). Leta_i = sum_j M_ij andb_j = sum_i M_ij. If M_ij is normalized, i.e.sum_ij M_ij = 1,and the types represent membership in vertex partitions, then the modularity of thepartitioning can be computed as
Q = sum_ii M_ii - sum_i a_i b_i
The normalized nominal assortativity is
Q / (1 - sum_i a_i b_i)
igraph_joint_degree_distribution() is a special case of this function, withcategories consisting vertices of the same degree.
References:
M. E. J. Newman: Mixing patterns in networks,Phys. Rev. E 67, 026126 (2003)https://doi.org/10.1103/PhysRevE.67.026126.
Arguments:
| The input graph. |
| A vector containing the weights of the edges. If passing a |
| The mixing matrix |
| Vertex types for source vertices. These must be non-negative integers. |
| Vertex types for target vertices. These must be non-negative integers. If |
| Whether to treat edges are directed. Ignored for undirected graphs. |
| Whether to normalize the matrix so that entries sum to 1.0. If false, matrix entries will be connection counts. Normalization is not meaningful if some edge weights are negative. |
Returns:
Error code. |
See also:
|
Time complexity: O(E), where E is the number of edges in the input graph.
igraph_error_t igraph_joint_degree_distribution( const igraph_t *graph, const igraph_vector_t *weights, igraph_matrix_t *p, igraph_neimode_t from_mode, igraph_neimode_t to_mode, igraph_bool_t directed_neighbors, igraph_bool_t normalized, igraph_integer_t max_from_degree, igraph_integer_t max_to_degree);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
Computes the joint degree distributionP_ij of a graph, used in thestudy of degree correlations.P_ij is the probability that a randomlychosen ordered pair ofconnected vertices have degreesi andj.
In directed graphs, directionally connectedu -> v pairsare considered. The joint degree distribution of an undirected graph is thesame as that of the corresponding directed graph in which all connection arebidirectional, assuming thatfrom_mode isIGRAPH_OUT,to_mode isIGRAPH_IN anddirected_neighbors is true.
Whennormalized is false,sum_ij P_ij gives the totalnumber of connections in a directed graph, or twice that value in anundirected graph. The sum is taken over ordered(i,j) degreepairs.
The joint degree distribution relates to other concepts used in the study ofdegree correlations. IfP_ij is normalized then the degree correlationfunctionk_nn(k) is obtained as
k_nn(k) = (sum_j j P_kj) / (sum_j P_kj).
The non-normalized degree assortativity is obtained as
a = sum_ij i j (P_ij - q_i r_j),
whereq_i = sum_k P_ik andr_j = sum_k P_kj.
Note that the joint degree distributionP_ij is similar, but not identicalto the joint degree matrixJ_ij computed byigraph_joint_degree_matrix().If the graph is undirected, then the diagonal entries of an unnormalizedP_ijare double that ofJ_ij, as any undirected connection between same-degree verticesis counted in both directions. In contrast toigraph_joint_degree_matrix(),this function returns matrices which include the row and column correspondingto zero degrees. In directed graphs, this row and column is not necessarilyzero whenfrom_mode is different fromIGRAPH_OUT orto_mode is differentfromIGRAPH_IN.
References:
M. E. J. Newman: Mixing patterns in networks,Phys. Rev. E 67, 026126 (2003)https://doi.org/10.1103/PhysRevE.67.026126.
Arguments:
| A pointer to an initialized graph object. |
| A vector containing the weights of the edges. If passing a |
| A pointer to an initialized matrix that will be resized. The |
| How to compute the degree of sources? Can be |
| How to compute the degree of targets? Can be |
| Whether to consider |
| Whether to normalize the matrix so that entries sum to 1.0. If false, matrix entries will be connection counts. Normalization is not meaningful if some edge weights are negative. |
| The largest source vertex degree to consider. If negative, the largest source degree will be used. The row count of the result matrix is one larger than this value. |
| The largest target vertex degree to consider. If negative, the largest target degree will be used. The column count of the result matrix is one larger than this value. |
Returns:
Error code. |
See also:
|
Time complexity: O(E), where E is the number of edges in the input graph.
igraph_error_t igraph_joint_degree_matrix( const igraph_t *graph, const igraph_vector_t *weights, igraph_matrix_t *jdm, igraph_integer_t max_out_degree, igraph_integer_t max_in_degree);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
In graph theory, the joint degree matrixJ_ij of a graph gives the numberof edges, or sum of edge weights, between vertices of degreei and degreej. This function storesJ_ij intojdm[i-1, j-1].Each edge, including self-loops, is counted precisely once, both in undirectedand directed graphs.
sum_(i,j) J_ij is the total number of edges (or total edge weight)m in the graph, where(i,j) refers to ordered or unorderedpairs in directed and undirected graphs, respectively. ThusJ_ij / mis the probability that an edge chosen at random (with probability proportionalto its weight) connects vertices with degreesi andj.
Note thatJ_ij is similar, but not identical to the joint degreedistribution, computed byigraph_joint_degree_distribution(),which is defined forordered(i, j) degreepairs even in the undirected case. When considering undirected graphs, thediagonal of the joint degree distribution is twice that of the jointdegree matrix.
References:
Isabelle Stanton and Ali Pinar:Constructing and sampling graphs with a prescribed joint degree distribution.ACM J. Exp. Algorithmics 17, Article 3.5 (2012).https://doi.org/10.1145/2133803.2330086
Arguments:
| A pointer to an initialized graph object. |
| A vector containing the weights of the edges. If passing a |
| A pointer to an initialized matrix that will be resized. The values will be written here. |
| Number of rows in the result, i.e. the largest (out-)degree to consider. If negative, the largest (out-)degree of the graph will be used. |
| Number of columns in the result, i.e. the largest (in-)degree to consider. If negative, the largest (in-)degree of the graph will be used. |
Returns:
Error code. |
See also:
|
Time complexity: O(E), where E is the number of edges in input graph.
igraph_error_t igraph_rich_club_sequence( const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_t *res, const igraph_vector_int_t *vertex_order, igraph_bool_t normalized, igraph_bool_t loops, igraph_bool_t directed);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
This function takes a graph and a vertex ordering as input, sequentiallyremoves the vertices in the given order, and calculates the density of theremaining subgraph after each removal.
Density is calculated as the ratio of the number of edges (or total edgeweight, if weighted) to the number of total possible edges in the graph.The latter is dependent on whether the graph is directed and whetherself-loops are assumed to be possible: for undirected graphs withoutself-loops, this total is given byn(n-1)/2,and for directed graphs byn(n-1).When self-loops are allowed, these are adjusted ton(n+1)/2for undirected andn^2 for directed graphs.
Vertex order can be sorted by degree so that the resulting density sequencehelps reveal how interconnected a graph is across different degree levels,or the presence of a "rich-club" effect.
Arguments:
| The graph object to analyze. |
| Vector of edge weights. If |
| Initialized vector, the result will be written here. |
| Vector giving the order in which vertices are removed. |
| If |
| Whether self-loops are assumed to be possible. Ignored when normalized is not requested. |
| If false, directed graphs will be treated as undirected. Ignored with undirected graphs. |
Returns:
Error code: |
Time complexity: O(|V| + |E|)where |V| is the number of vertices and |E| the number of edges in the graph given.
See also:
|
igraph_error_t igraph_coreness(const igraph_t *graph, igraph_vector_int_t *cores, igraph_neimode_t mode);
The k-core of a graph is a maximal subgraph in which each vertexhas at least degree k. (Degree here means the degree in thesubgraph of course.). The coreness of a vertex is the highest orderof a k-core containing the vertex.
This function implements the algorithm presented in VladimirBatagelj, Matjaz Zaversnik: An O(m) Algorithm for CoresDecomposition of Networks.https://arxiv.org/abs/cs/0310049
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.
igraph_error_t igraph_trussness(const igraph_t* graph, igraph_vector_int_t* trussness);
A k-truss is a subgraph in which every edge occurs in at leastk-2 trianglesin the subgraph. The trussness of an edge indicates the highest k-truss thatthe edge occurs in.
This function returns the highestk for each edge. If you are interested ina particular k-truss subgraph, you can subset the graph to those edgeswhich are>= k because each k-truss is a subgraph of a(k–1)-trussThus, to get all 4-trusses, takek >= 4 because the 5-trusses, 6-trusses,etc. need to be included.
The current implementation of this function iteratively decrements supportof each edge using O(|E|) space and O(|E|^1.5) time. The implementation doesnot support multigraphs; useigraph_simplify() to collapse edges beforecalling this function.
Reference:
See Algorithm 2 in:Wang, Jia, and James Cheng. "Truss decomposition in massive networks."Proceedings of the VLDB Endowment 5.9 (2012): 812-823.https://doi.org/10.14778/2311906.2311909
Arguments:
| The input graph. Loop edges are allowed; multigraphs are not. |
| Pointer to initialized vector of truss values that willindicate the highest k-truss each edge occurs in. It will be resized asneeded. |
Returns:
Error code. |
Time complexity: It should be O(|E|^1.5) according to the reference.
igraph_is_dag — Checks whether a graph is a directed acyclic graph (DAG).igraph_topological_sorting — Calculate a possible topological sorting of the graph.igraph_feedback_arc_set — Feedback arc set of a graph using exact or heuristic methods.igraph_feedback_vertex_set — Feedback vertex set of a graph.igraph_error_t igraph_is_dag(const igraph_t* graph, igraph_bool_t *res);
A directed acyclic graph (DAG) is a directed graph with no cycles.
This function returns false for undirected graphs.
The return value of this function is cached in the graph itself; callingthe function multiple times with no modifications to the graph in betweenwill return a cached value in O(1) time.
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 ofvertices and edges in the original input graph.
See also:
|
igraph_error_t igraph_topological_sorting( const igraph_t* graph, igraph_vector_int_t *res, igraph_neimode_t mode);
A topological sorting of a directed acyclic graph (DAG) is a linear orderingof its vertices where each vertex comes before all nodes to which it hasedges. Every DAG has at least one topological sort, and may have many.This function returns one possible topological sort among them. If thegraph contains any cycles that are not self-loops, 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 ofvertices and edges in the original input graph.
See also:
|
Example 13.46. Fileexamples/simple/igraph_topological_sorting.c
#include <igraph.h>#include <stdio.h>intmain(void) { igraph_t graph; igraph_vector_int_t res;/* Test graph taken fromhttp://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_int_init(&res, 0);/* Sort the vertices in "increasing" order. */igraph_topological_sorting(&graph, &res, IGRAPH_OUT);igraph_vector_int_print(&res);printf("\n");/* Sort the vertices in "decreasing" order. */igraph_topological_sorting(&graph, &res, IGRAPH_IN);igraph_vector_int_print(&res);/* Destroy data structures when done using them. */igraph_destroy(&graph);igraph_vector_int_destroy(&res);return 0;}
igraph_error_t igraph_feedback_arc_set( const igraph_t *graph, igraph_vector_int_t *result, const igraph_vector_t *weights, igraph_fas_algorithm_t algo);
A feedback arc set is a set of edges whose removal makes the graph acyclic.We are usually interested inminimum feedback arc sets, i.e. sets of edgeswhose total weight is the smallest among all the feedback arc sets.
For undirected graphs, the solution is simple: one has to find a maximum weightspanning tree and then remove all the edges not in the spanning tree. For directedgraphs, this is an NP-complete problem, and various heuristics are usually used tofind an approximate solution to the problem. This function implements both exactmethods and heuristics, selectable with thealgo parameter.
References:
Eades P, Lin X and Smyth WF:A fast and effective heuristic for the feedback arc set problem.Information Processing Letters 47(6), pp 319-323 (1993).https://doi.org/10.1016/0020-0190(93)90079-O
Baharev A, Hermann S, Arnold N and Tobias A:An Exact Method for the Minimum Feedback Arc Set Problem.ACM Journal of Experimental Algorithmics 26, 1–28 (2021).https://doi.org/10.1145/3446429.
Arguments:
| The graph object. | ||||||||
| An initialized vector, the result will be written here. | ||||||||
| Weight vector or | ||||||||
| The algorithm to use to solve the problem if the graph is directed. Possible values:
|
Returns:
Error code: |
Example 13.47. Fileexamples/simple/igraph_feedback_arc_set.c
#include <igraph.h>#include <string.h>intmain(void) { igraph_t g;igraph_vector_t weights; igraph_vector_int_t result; igraph_bool_t dag;igraph_vector_int_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_int_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_int_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_int_print(&result);igraph_delete_edges(&g,igraph_ess_vector(&result));igraph_is_dag(&g, &dag);if (!dag) {return 3; }igraph_destroy(&g);/* Null graph */igraph_empty(&g, 0, IGRAPH_DIRECTED);igraph_feedback_arc_set(&g, &result, NULL, IGRAPH_FAS_APPROX_EADES);if (igraph_vector_int_size(&result) != 0) {return 4; }igraph_destroy(&g);/* Singleton graph */igraph_empty(&g, 1, IGRAPH_DIRECTED);igraph_feedback_arc_set(&g, &result, NULL, IGRAPH_FAS_APPROX_EADES);if (igraph_vector_int_size(&result) != 0) {return 5; }igraph_destroy(&g);igraph_vector_int_destroy(&result);return 0;}
Example 13.48. Fileexamples/simple/igraph_feedback_arc_set_ip.c
#include <igraph.h>#include <string.h>intmain(void) { igraph_t g;igraph_vector_t weights; igraph_vector_int_t result; igraph_bool_t dag;igraph_error_t retval;igraph_vector_int_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_int_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_int_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_int_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_int_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_int_print(&result);igraph_delete_edges(&g,igraph_ess_vector(&result));igraph_is_dag(&g, &dag);if (!dag) {return 5; }igraph_destroy(&g);/* Null graph */igraph_empty(&g, 0, IGRAPH_DIRECTED);igraph_feedback_arc_set(&g, &result, NULL, IGRAPH_FAS_EXACT_IP);if (igraph_vector_int_size(&result) != 0) {return 6; }igraph_destroy(&g);/* Singleton graph */igraph_empty(&g, 1, IGRAPH_DIRECTED);igraph_feedback_arc_set(&g, &result, NULL, IGRAPH_FAS_EXACT_IP);if (igraph_vector_int_size(&result) != 0) {return 7; }igraph_destroy(&g);igraph_vector_int_destroy(&result);return 0;}
Time complexity: depends onalgo, see the time complexities there.
igraph_error_t igraph_feedback_vertex_set( const igraph_t *graph, igraph_vector_int_t *result, const igraph_vector_t *vertex_weights, igraph_fvs_algorithm_t algo);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
A feedback vertex set is a set of vertices whose removal makes the graphacyclic. Finding aminimum feedback vertex set is an NP-completeproblem, both on directed and undirected graphs.
Arguments:
| The graph. | ||
| An initialized vector, the result will be written here. | ||
| Vertex weight vector or | ||
| Algorithm to use. Possible values:
|
Returns:
Error code. |
Time complexity: depends onalgo, see the time complexities there.
igraph_error_t igraph_maximum_cardinality_search(const igraph_t *graph, igraph_vector_int_t *alpha, igraph_vector_int_t *alpham1);
This function implements the maximum cardinality search algorithm.It computes a rankalpha for each vertex, such that visitingvertices in decreasing rank order corresponds to always choosingthe vertex with the most already visited neighbors as the next oneto visit.
Maximum cardinality search is useful in deciding the chordalityof a graph. A graph is chordal if and only if any two neighborsof a vertex which are higher in rank than it are connected toeach other.
References:
Robert E Tarjan and Mihalis Yannakakis: Simple linear-timealgorithms to test chordality of graphs, test acyclicity ofhypergraphs, 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 ofvertices and edges.
See also:
igraph_error_t igraph_is_chordal(const igraph_t *graph, const igraph_vector_int_t *alpha, const igraph_vector_int_t *alpham1, igraph_bool_t *chordal, igraph_vector_int_t *fill_in, igraph_t *newgraph);
A graph is chordal if each of its cycles of four or more nodeshas a chord, i.e. an edge joining two nodes that are notadjacent in the cycle. An equivalent definition is that anychordless cycles have at most three nodes.If eitheralpha oralpham1 is given, then the other iscalculated by taking simply the inverse. If neither are given,thenigraph_maximum_cardinality_search() is called to calculatethem.
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:
igraph_error_t igraph_is_matching(const igraph_t *graph, const igraph_vector_bool_t *types, const igraph_vector_int_t *matching, igraph_bool_t *result);
This function checks a matching vector and verifies whether its lengthmatches the number of vertices in the given graph, its values are between-1 (inclusive) and the number of vertices (exclusive), and whether thereexists a corresponding edge in the graph for every matched vertex pair.For bipartite graphs, it also verifies whether the matched vertices arein 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.49. Fileexamples/simple/igraph_maximum_bipartite_matching.c
#include <igraph.h>#include <stdio.h>intmain(void) {/* 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_int_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_int_init(&matching, 0);igraph_maximum_bipartite_matching(&graph, &types, &matching_size, &matching_weight, &matching, 0, 0);if (matching_size != 6) {printf("matching_size is %" IGRAPH_PRId ", expected: 6\n", matching_size);return 1; }if (matching_weight != 6) {printf("matching_weight is %" IGRAPH_PRId ", expected: 6\n", (igraph_integer_t) matching_weight);return 2; }igraph_is_maximal_matching(&graph, &types, &matching, &is_matching);if (!is_matching) {printf("not a matching: ");igraph_vector_int_print(&matching);return 3; }igraph_vector_int_destroy(&matching);igraph_vector_bool_destroy(&types);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_is_maximal_matching(const igraph_t *graph, const igraph_vector_bool_t *types, const igraph_vector_int_t *matching, igraph_bool_t *result);
A matching is maximal if and only if there exists no unmatched vertex in agraph 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. |
Returns:
Error code. |
See also:
|
Time complexity: O(|V|+|E|) where |V| is the number of vertices and|E| is the number of edges.
Example 13.50. Fileexamples/simple/igraph_maximum_bipartite_matching.c
#include <igraph.h>#include <stdio.h>intmain(void) {/* 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_int_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_int_init(&matching, 0);igraph_maximum_bipartite_matching(&graph, &types, &matching_size, &matching_weight, &matching, 0, 0);if (matching_size != 6) {printf("matching_size is %" IGRAPH_PRId ", expected: 6\n", matching_size);return 1; }if (matching_weight != 6) {printf("matching_weight is %" IGRAPH_PRId ", expected: 6\n", (igraph_integer_t) matching_weight);return 2; }igraph_is_maximal_matching(&graph, &types, &matching, &is_matching);if (!is_matching) {printf("not a matching: ");igraph_vector_int_print(&matching);return 3; }igraph_vector_int_destroy(&matching);igraph_vector_bool_destroy(&types);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_maximum_bipartite_matching(const igraph_t *graph, const igraph_vector_bool_t *types, igraph_integer_t *matching_size, igraph_real_t *matching_weight, igraph_vector_int_t *matching, const igraph_vector_t *weights, igraph_real_t eps);
A matching in a bipartite graph is a partial assignment of verticesof the first kind to vertices of the second kind such that each vertex ofthe first kind is matched to at most one vertex of the second kind andvice versa, and matched vertices must be connected by an edge in the graph.The size (or cardinality) of a matching is the number of edges.A matching is a maximum matching if there exists no other matching withlarger cardinality. For weighted graphs, a maximum matching is a matchingwhose edges have the largest possible total weight among all possiblematchings.
Maximum matchings in bipartite graphs are found by the push-relabel algorithmwith greedy initialization and a global relabeling after every n/2 steps wheren is the number of vertices in the graph.
References: Cherkassky BV, Goldberg AV, Martin P, Setubal JC and Stolfi J:Augment or push: A computational study of bipartite matching andunit-capacity flow algorithms. ACM Journal of Experimental Algorithmics 3,1998.
Kaya K, Langguth J, Manne F and Ucar B: Experiments on push-relabel-basedmaximum cardinality matching algorithms for bipartite graphs. TechnicalReport TR/PA/11/33 of the Centre Europeen de Recherche et de FormationAvancee en Calcul Scientifique, 2011.
Arguments:
| The input graph. It can be directed but the edge directions will be ignored. |
| Boolean vector giving the vertex types of the graph. |
| The size of the matching (i.e. the number of matched vertex pairs will be returned here). It may be |
| The weight of the matching if the edges are weighted, or the size of the matching again if the edges are unweighted. It may be |
| 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. |
| A null pointer (=no edge weights), or a vector giving the weights of the edges. Note that the algorithm is stable only for integer weights. |
| A small real number used in equality tests in the weighted bipartite matching algorithm. Two real numbers are considered equal in the algorithm if their difference is smaller than |
Returns:
Error code. |
Time complexity: O(sqrt(|V|) |E|) for unweighted graphs (according to thetechnical report referenced above), O(|V||E|) for weighted graphs.
Example 13.51. Fileexamples/simple/igraph_maximum_bipartite_matching.c
#include <igraph.h>#include <stdio.h>intmain(void) {/* 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_int_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_int_init(&matching, 0);igraph_maximum_bipartite_matching(&graph, &types, &matching_size, &matching_weight, &matching, 0, 0);if (matching_size != 6) {printf("matching_size is %" IGRAPH_PRId ", expected: 6\n", matching_size);return 1; }if (matching_weight != 6) {printf("matching_weight is %" IGRAPH_PRId ", expected: 6\n", (igraph_integer_t) matching_weight);return 2; }igraph_is_maximal_matching(&graph, &types, &matching, &is_matching);if (!is_matching) {printf("not a matching: ");igraph_vector_int_print(&matching);return 3; }igraph_vector_int_destroy(&matching);igraph_vector_bool_destroy(&types);igraph_destroy(&graph);return 0;}
igraph_error_t igraph_unfold_tree(const igraph_t *graph, igraph_t *tree, igraph_neimode_t mode, const igraph_vector_int_t *roots, igraph_vector_int_t *vertex_index);
A graph is converted into a tree (or forest, if it is unconnected),by performing a breadth-first search on it, and replicatingvertices that were found a second, third, etc. time.
Arguments:
| The input graph, it can be either directed or undirected. |
| Pointer to an uninitialized graph object, the result is stored here. |
| For directed graphs; whether to follow paths along edge directions ( |
| A numeric vector giving the root vertex, or vertices (if the graph is not connected), to start from. |
| Pointer to an initialized vector, or a null pointer. If not a null pointer, then a mapping from the vertices in the new graph to the ones in the original is created here. |
Returns:
Error code. |
Time complexity: O(n+m), linear in the number vertices and edges.
igraph_density — Calculate the density of a graph.igraph_mean_degree — The mean degree of a graph.igraph_reciprocity — Calculates the reciprocity of a directed graph.igraph_diversity — Structural diversity index of the vertices.igraph_is_mutual — Check whether some edges of a directed graph are mutual.igraph_has_mutual — Check whether a directed graph has any mutual edges.igraph_get_adjacency — The adjacency matrix of a graph.igraph_get_adjacency_sparse — Returns the adjacency matrix of a graph in a sparse matrix format.igraph_get_stochastic — Stochastic adjacency matrix of a graph.igraph_get_stochastic_sparse — The stochastic adjacency matrix of a graph.igraph_get_edgelist — The list of edges in a graph.igraph_error_t igraph_density(const igraph_t *graph, igraph_real_t *res, igraph_bool_t loops);
The density of a graph is simply the ratio of the actual number of itsedges and the largest possible number of edges it could have.The maximum number of edges depends on interpretation: are verticesallowed to have a connection to themselves? This is controlled by theloops parameter.
Note that density is ill-defined for graphs which have multiple edgesbetween some pairs of vertices. Consider callingigraph_simplify()on such graphs. This function does not check whether the graph hasparallel edges. The result it returns for such graphs is not meaningful.
Arguments:
| The input graph object. It must not have parallel edges. |
| Pointer to a real number, the result will be stored here. |
| Boolean constant, whether to include self-loops in the calculation. If this constant is |
Returns:
Error code. |
Time complexity: O(1).
igraph_error_t igraph_mean_degree(const igraph_t *graph, igraph_real_t *res, igraph_bool_t loops);
This function is experimental and its signature is not considered final yet.We reserve the right to change the function signature without changing themajor version of igraph. Use it at your own risk.
This is a convenience function that computes the average of all vertexdegrees. In directed graphs, the average of out-degrees and in-degrees isthe same; this is the number that is returned. For the null graph, whichhas no vertices, NaN is returned.
Arguments:
| The input graph object. |
| Pointer to a real number, the result will be stored here. |
| Whether to consider self-loops during the calculation. |
Returns:
Error code. |
Time complexity: O(1) if self-loops are considered,O(|E|) where |E| is the number of edges if self-loops are ignored.
igraph_error_t igraph_reciprocity(const igraph_t *graph, igraph_real_t *res, igraph_bool_t ignore_loops, igraph_reciprocity_t mode);
In a directed graph, the measure of reciprocity defines the proportion ofmutual connections. It is most commonly defined as the probability that theopposite counterpart of a randomly chosen directed edge is also included inthe graph. In adjacency matrix notation:1 - (sum_ij |A_ij - A_ji|) / (2 sum_ij A_ij).In multigraphs, each parallel edge between two vertices must have its ownseparate reciprocal edge, in accordance with the above formula. This measureis calculated if themode argument isIGRAPH_RECIPROCITY_DEFAULT.
For directed graphs with no edges, NaN is returned.For undirected graphs, 1 is returned unconditionally.
Prior to igraph version 0.6, another measure was implemented, defined as theprobability of having mutual connections between a vertex pair if we knowthat there is a (possibly non-mutual) connection between them. In otherwords, (unordered) vertex pairs are classified into three groups:(1) disconnected, (2) non-reciprocally connected, (3) reciprocally connected.The result is the size of group (3), divided by the sum of groupsizes (2)+(3). This measure is calculated ifmode isIGRAPH_RECIPROCITY_RATIO.
Arguments:
| The graph object. |
| Pointer to an |
| Whether to ignore self-loops when counting edges. Self-loops are considered as a mutual connection. |
| Type of reciprocity to calculate, possible values are |
Returns:
Error code: |
Time complexity: O(|V|+|E|), |V| is the number of vertices,|E| is the number of edges.
Example 13.52. Fileexamples/simple/igraph_reciprocity.c
#include <igraph.h>#include <math.h>intmain(void) { igraph_t g; igraph_real_t res;/* Trivial cases */igraph_ring(&g, 100, IGRAPH_UNDIRECTED, 0, 0);igraph_reciprocity(&g, &res, 0, IGRAPH_RECIPROCITY_DEFAULT);igraph_destroy(&g);if (res != 1) {return 1; }/* Small test graph */igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 0, 2, 0, 3, 1, 0, 2, 3, 3, 2, -1);igraph_reciprocity(&g, &res, 0, IGRAPH_RECIPROCITY_RATIO);igraph_destroy(&g);if (res != 0.5) {fprintf(stderr, "%f != %f\n", res, 0.5);return 2; }igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 1, -1);igraph_reciprocity(&g, &res, 0, IGRAPH_RECIPROCITY_DEFAULT);igraph_destroy(&g);if (fabs(res - 2.0 / 3.0) > 1e-15) {fprintf(stderr, "%f != %f\n", res, 2.0 / 3.0);return 3; }return 0;}
igraph_error_t igraph_diversity(const igraph_t *graph, const igraph_vector_t *weights, igraph_vector_t *res, const igraph_vs_t vids);
This measure was defined in Nathan Eagle, Michael Macy and RobClaxton: Network Diversity and Economic Development, Science 328,1029--1031, 2010.
It is simply the (normalized) Shannon entropy of theincident edges' weights.D(i) = H(i) / log(k[i]),andH(i) = -sum(p[i,j] log(p[i,j]), j=1..k[i]),wherep[i,j] = w[i,j] / sum(w[i,l], l=1..k[i]),k[i] is the (total) degree of vertexi,andw[i,j] is the weight of the edge(s) betweenvertexi andj. The diversity of isolated vertices will be NaN(not-a-number), while that of vertices with a single connectionwill be zero.
The measure works only if the graph is undirected and has no multiple edges.If the graph has multiple edges, simplify it first usingigraph_simplify(). If the graph is directed, convert it into an undirectedgraph withigraph_to_undirected() .
Arguments:
| The undirected input graph. |
| The edge weights, in the order of the edge IDs, must have appropriate length. Weights must be non-negative. |
| An initialized vector, the results are stored here. |
| Vertex selector that specifies the vertices which to calculate the measure. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear.
igraph_error_t igraph_is_mutual(const igraph_t *graph, igraph_vector_bool_t *res, igraph_es_t es, igraph_bool_t loops);
An (A,B) non-loop directed edge is mutual if the graph containsthe (B,A) edge too. Whether directed self-loops are considered mutualis controlled by theloops parameter.
An undirected graph only has mutual edges, by definition.
Edge multiplicity is not considered here, e.g. if there are two(A,B) edges and one (B,A) edge, then all three are considered to bemutual.
Arguments:
| The input graph. |
| Pointer to an initialized vector, the result is stored here. |
| The sequence of edges to check. Supply |
| Boolean, whether to consider directed self-loops to be mutual. |
Returns:
Error code. |
Time complexity: O(n log(d)), n is the number of edges supplied, dis the maximum in-degree of the vertices that are targets of thesupplied edges. An upper limit of the time complexity is O(n log(|E|)),|E| is the number of edges in the graph.
igraph_error_t igraph_has_mutual(const igraph_t *graph, igraph_bool_t *res, igraph_bool_t loops);
An (A,B) non-loop directed edge is mutual if the graph containsthe (B,A) edge too. Whether directed self-loops are considered mutualis controlled by theloops parameter.
In undirected graphs, all edges are considered mutual by definition.Thus for undirected graph, this function returns false only when thereare no edges.
To check whether a graph is an oriented graph, use this function inconjunction withigraph_is_directed().
Arguments:
| The input graph. |
| Pointer to a boolean, the result will be stored here. |
| Boolean, whether to consider directed self-loops to be mutual. |
Returns:
Error code. |
Time complexity: O(|E| log(d)) where d is the maximum in-degree.
igraph_error_t igraph_get_adjacency( const igraph_t *graph, igraph_matrix_t *res, igraph_get_adjacency_t type, const igraph_vector_t *weights, igraph_loops_t loops);
The result is an adjacency matrix. Entry i, j of the matrixcontains the number of edges connecting vertex i to vertex j in the unweightedcase, or the total weight of edges connecting vertex i to vertex j in theweighted case.
Arguments:
| Pointer to the graph to convert | ||||||
| Pointer to an initialized matrix object, it will be resized if needed. | ||||||
| Constant specifying the type of the adjacency matrix to create for undirected graphs. It is ignored for directed graphs. Possible values:
| ||||||
| An optional vector containing the weight of each edge in the graph. Supply a null pointer here to make all edges have the same weight of 1. | ||||||
| Constant specifying how loop edges should be handled. Possible values:
|
Returns:
Error code: |
See also:
|
Time complexity: O(|V||V|), |V| is the number of vertices in the graph.
igraph_error_t igraph_get_adjacency_sparse( const igraph_t *graph, igraph_sparsemat_t *res, igraph_get_adjacency_t type, const igraph_vector_t *weights, igraph_loops_t loops);
Arguments:
| The input graph. | ||||||
| Pointer to aninitialized sparse matrix. The result will be stored here. The matrix will be resized as needed. | ||||||
| Constant specifying the type of the adjacency matrix to create for undirected graphs. It is ignored for directed graphs. Possible values:
| ||||||
| An optional vector containing the weight of each edge in the graph. Supply a null pointer here to make all edges have the same weight of 1. | ||||||
| Constant specifying how loop edges should be handled. Possible values:
|
Returns:
Error code: |
See also:
|
Time complexity: TODO.
igraph_error_t igraph_get_stochastic( const igraph_t *graph, igraph_matrix_t *res, igraph_bool_t column_wise, const igraph_vector_t *weights);
Stochastic matrix of a graph. The stochastic matrix of a graph isits adjacency matrix, normalized row-wise or column-wise, such thatthe sum of each row (or column) is one.
Arguments:
| The input graph. |
| Pointer to an initialized matrix, the result is stored here. It will be resized as needed. |
| Whether to normalize column-wise. |
| An optional vector containing the weight of each edge in the graph. Supply a null pointer here to make all edges have the same weight of 1. |
Returns:
Error code. |
Time complexity: O(|V||V|), |V| is the number of vertices in the graph.
See also:
|
igraph_error_t igraph_get_stochastic_sparse( const igraph_t *graph, igraph_sparsemat_t *res, igraph_bool_t column_wise, const igraph_vector_t *weights);
Stochastic matrix of a graph. The stochastic matrix of a graph isits adjacency matrix, normalized row-wise or column-wise, such thatthe sum of each row (or column) is one.
Arguments:
| The input graph. |
| Pointer to aninitialized sparse matrix, the result is stored here. The matrix will be resized as needed. |
| Whether to normalize column-wise. |
| An optional vector containing the weight of each edge in the graph. Supply a null pointer here to make all edges have the same weight of 1. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices andedges.
See also:
|
igraph_error_t igraph_get_edgelist(const igraph_t *graph, igraph_vector_int_t *res, igraph_bool_t bycol);
The order of the edges is given by the edge IDs.
Arguments:
| Pointer to the graph object |
| Pointer to an initialized vector object, it will be resized. |
| Boolean constant. If true, the edges will be returned columnwise, e.g. the first edge is |
Returns:
Error code. |
See also:
|
Time complexity: O(|E|), the number of edges in the graph.
igraph_are_connected — Decides whether two vertices are adjacent (deprecated alias).igraph_shortest_paths — Length of the shortest paths between vertices.igraph_shortest_paths_dijkstra — Weighted shortest path lengths between vertices (deprecated).igraph_shortest_paths_bellman_ford — Weighted shortest path lengths between vertices, allowing negative weights (deprecated).igraph_shortest_paths_johnson — Weighted shortest path lengths between vertices, using Johnson's algorithm (deprecated).igraph_get_stochastic_sparsemat — Stochastic adjacency matrix of a graph (deprecated).igraph_get_sparsemat — Converts an igraph graph to a sparse matrix (deprecated).igraph_laplacian — Returns the Laplacian matrix of a graph (deprecated).igraph_hub_score — Kleinberg's hub scores.igraph_authority_score — Kleinberg's authority scores.igraph_error_t igraph_are_connected(const igraph_t *graph, igraph_integer_t v1, igraph_integer_t v2, igraph_bool_t *res);
Deprecated since version 0.10.10. Please do not use this function in newcode; useigraph_are_adjacent()instead.
Decides whether there are any edges that havev1 andv2as endpoints. This function is of course symmetric for undirectedgraphs.
Arguments:
| The graph object. |
| The first vertex. |
| The second vertex. |
| Boolean, |
Returns:
The error code |
Time complexity: O( min(log(d1), log(d2)) ),d1 is the (out-)degree ofv1 and d2 is the (in-)degree ofv2.
igraph_error_t 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);
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_distances()instead.
igraph_error_t 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);
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_distances_dijkstra()instead.
igraph_error_t 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);
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_distances_bellman_ford()instead.
igraph_error_t 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);
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_distances_johnson()instead.
igraph_error_t igraph_get_stochastic_sparsemat(const igraph_t *graph, igraph_sparsemat_t *res, igraph_bool_t column_wise);
This function is deprecated in favour ofigraph_get_stochastic_sparse(),but does not work in an identical way. This function takes anuninitializedigraph_sparsemat_t whileigraph_get_stochastic_sparse() takesan already initialized one.
Arguments:
| The input graph. |
| Pointer to anuninitialized sparse matrix, the result is stored here. The matrix will be resized as needed. |
| Whether to normalize column-wise. For undirected graphs this argument does not have any effect. |
Returns:
Error code. |
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_get_stochastic_sparse()instead.
igraph_error_t igraph_get_sparsemat(const igraph_t *graph, igraph_sparsemat_t *res);
If the graph is undirected, then a symmetric matrix is created.
This function is deprecated in favour ofigraph_get_adjacency_sparse(),but does not work in an identical way. This function takes anuninitializedigraph_sparsemat_t whileigraph_get_adjacency_sparse() takesan already initialized one.
Arguments:
| The input graph. |
| Pointer to anuninitialized sparse matrix. The result will be stored here. |
Returns:
Error code. |
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_get_adjacency_sparse()instead.
igraph_error_t igraph_laplacian( const igraph_t *graph, igraph_matrix_t *res, igraph_sparsemat_t *sparseres, igraph_bool_t normalized, const igraph_vector_t *weights);
This function produces the Laplacian matrix of a graph in either dense orsparse format. Whennormalized is set to true, the type of normalizationused depends on the directnedness of the graph: symmetric normalizationis used for undirected graphs and left stochastic normalization fordirected graphs.
Arguments:
| Pointer to the graph to convert. |
| Pointer to an initialized matrix object or |
| Pointer to an initialized sparse matrix object or |
| Controls whether to use out- or in-degrees in directed graphs. If set to |
| Boolean, whether to normalize the result. |
| An optional vector containing non-negative edge weights, to calculate the weighted Laplacian matrix. Set it to a null pointer to calculate the unweighted Laplacian. |
Returns:
Error code. |
Deprecated since version 0.10.0. Please do not use this function in newcode; useigraph_get_laplacian()instead.
igraph_error_t 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);
Deprecated since version 0.10.5. Please do not use this function in newcode; useigraph_hub_and_authority_scores()instead.
The hub scores of the vertices are defined as the principaleigenvector ofA A^T, whereA is the adjacencymatrix of the graph,A^T is its transposed.
See the following reference on the meaning of this score:J. Kleinberg. Authoritative sources in a hyperlinkedenvironment. Proc. 9th ACM-SIAM Symposium on DiscreteAlgorithms, 1998. Extended version in Journal of theACM 46(1999). Also appears as IBM Research Report RJ 10076, May1997.
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:
|
igraph_error_t 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);
Deprecated since version 0.10.5. Please do not use this function in newcode; useigraph_hub_and_authority_scores()instead.
The authority scores of the vertices are defined as the principaleigenvector ofA^T A, whereA is the adjacencymatrix of the graph,A^T is its transposed.
See the following reference on the meaning of this score:J. Kleinberg. Authoritative sources in a hyperlinkedenvironment. Proc. 9th ACM-SIAM Symposium on DiscreteAlgorithms, 1998. Extended version in Journal of theACM 46(1999). Also appears as IBM Research Report RJ 10076, May1997.
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:
|
| ← Chapter 12. Graph, vertex and edge attributes | Chapter 14. Graph cycles → |