For using the igraph C library
These functions usually calculate some structural property of a graph, like its diameter, the degree of the nodes, etc.
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 have v1 and v2
as endpoints. This function is of course symmetric for undirected
graphs.
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 of v1 and d2 is the (in-)degree of v2.
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 graph G = (V,E) with a stretch t is a
subgraph H = (V,Es) such that Es is a subset of E
and the distance between any pair of nodes in H is at most t
times the distance in G. The returned graph is always a spanner of
the given graph with the specified stretch. For weighted graphs the
number of edges in the spanner is O(k n^(1 + 1 / k)), where
k is k = (t + 1) / 2, m is the number of edges
and n is the number of nodes in G. For unweighted graphs the number
of edges is O(n^(1 + 1 / k) + kn).
This function is based on the algorithm of Baswana and Sen: "A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted 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 expected running time is O(km) where k is the value mentioned above and m is the number of 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 — Calculates the average unweighted shortest path length between all vertex pairs.igraph_average_path_length_dijkstra — Calculates the average weighted shortest path length between all vertex pairs.igraph_path_length_hist — Create a histogram of all shortest path lengths.igraph_diameter — Calculates the diameter of a graph (longest geodesic).igraph_diameter_dijkstra — Calculates the weighted diameter of a graph using Dijkstra's algorithm.igraph_girth — The girth of a graph is the length of the shortest cycle in it.igraph_eccentricity — Eccentricity of some vertices.igraph_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 path 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. File examples/simple/distances.c
#include <igraph.h> int main(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 the major version of igraph. Use it at your own risk.
This function is similar to igraph_distances(), but
paths longer than cutoff 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. File examples/simple/distances.c
#include <igraph.h> int main(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 find the weighted shortest path lengths from a source vertex to all other vertices. This function allows specifying a set of source and target vertices. The algorithm is run independently for each source 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 of vertices, |E| the number of edges and s the number of sources.
See also:
|
Example 13.3. File examples/simple/distances.c
#include <igraph.h> int main(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 the major version of igraph. Use it at your own risk.
This function is similar to igraph_distances_dijkstra(), but
paths longer than cutoff 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 of
vertices, |E| the number of edges and s the number of sources. The
cutoff parameter will limit the number of edges traversed from each
source vertex, which reduces the computation time.
See also:
|
Example 13.4. File examples/simple/distances.c
#include <igraph.h> int main(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 weighted
shortest paths to all vertices from a single source, allowing negative weights.
It is run independently for the given sources. If there are no negative
weights, you are better off with igraph_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 closed loop in
the graph that has a negative total weight (since this would allow
us to decrease the weight of any path containing at least a single
vertex of this loop infinitely). Additionally, no edge weight may
be NaN. If either case does not hold, an error is returned. If this
is a null pointer, then the unweighted version,
|
|
For directed graphs; whether to follow paths along edge
directions ( |
Returns:
Error code. |
Time complexity: O(s*|E|*|V|), where |V| is the number of vertices, |E| the number of edges and s the number of sources.
See also:
|
Example 13.5. File examples/simple/bellman_ford.c
#include <igraph.h> int main(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 loop */ 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_ENEGLOOP) { 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 performs better than the Bellman-Ford method when distances are calculated from many different sources, the typical use case being all-pairs distance calculations. It works by using a 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 page for 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 algorithm
is used by calling igraph_distances_dijkstra().
Note that Johnson's algorithm applies only to directed graphs. This function rejects
undirected graphs with any negative edge weights, even when the from and to
vertices 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 number of 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 the major version of igraph. Use it at your own risk.
The Floyd-Warshall algorithm computes weighted shortest path lengths between all 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 sensitive to the graph density. In sparse graphs, other methods such as the Dijkstra or Bellman-Ford algorithms will perform significantly better.
In addition to the original Floyd-Warshall algorithm, igraph contains implementations of variants that offer better asymptotic complexity as well as better practical running times for most instances. See the reference below for more information.
Note that internally this function always computes the distance matrix
for all pairs of vertices. The from and to parameters only serve
to subset this matrix, but do not affect the time or memory taken by the
calculation.
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 specified
sets of target vertices. If there is more than one geodesic between two vertices,
this function gives only one of them. Use igraph_get_all_shortest_paths()
to find all 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 the graph.
See also:
|
Example 13.6. File examples/simple/igraph_get_shortest_paths.c
#include <igraph.h> #include <stdlib.h> int check_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; } int main(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 a given vertex to another one. If there is more than one shortest path between the two vertices, then an arbitrary one is returned.
This function is a wrapper to igraph_get_shortest_paths()
for the special case when only one target vertex is considered.
Arguments:
|
The input graph, it can be directed or undirected. Directed paths are considered in directed graphs. |
|
Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex IDs along the path are stored here, including the source and target vertices. |
|
Pointer to an 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 and edges 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 specified
sets of target vertices using Dijkstra's algorithm. If there is more than
one path with the smallest weight between two vertices, this function gives
only one of them. To find all such paths, use
igraph_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 of vertices and |E| is the number of edges
See also:
|
Example 13.7. File examples/simple/igraph_get_shortest_paths_dijkstra.c
#include <igraph.h> #include <stdlib.h> int main(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 to a single target, using Dijkstra's algorithm. If more than one shortest path exists, an arbitrary one is returned.
This function is a special case (and a wrapper) to
igraph_get_shortest_paths_dijkstra().
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex IDs along the path are stored here, including the source and target vertices. |
|
Pointer to an 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 vertex
using the Bellman-Ford algorithm, whihc can handle negative weights. When
there is more than one shortest path between two vertices, only one of them
is 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 closed loop in
the graph that has a negative total weight (since this would allow
us to decrease the weight of any path containing at least a single
vertex of this loop infinitely). If this is a null pointer, then the
unweighted version, |
|
For directed graphs; whether to follow paths along edge
directions ( |
|
A pointer to an initialized igraph vector or null.
If not null, a vector containing the 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 of vertices, |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 to a single target using the Bellman-Ford algorithm.
This function is a special case (and a wrapper) to
igraph_get_shortest_paths_bellman_ford().
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to an initialized vector or a null pointer. If not a null pointer, then the vertex IDs along the path are stored here, including the source and target vertices. |
|
Pointer to an 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 closed loop in the graph that has a negative total weight (since this would allow us to decrease the weight of any path containing at least a single vertex of this loop infinitely). If this is a null pointer, then the unweighted version is called. |
|
A constant specifying how edge directions are
considered in directed graphs. |
Returns:
Error code. |
Time complexity: O(|E|log|E|+|V|), |V| is the number of vertices, |E| is the number of edges in the graph.
See also:
|
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 the major version of igraph. Use it at your own risk.
Calculates a shortest path from a single source vertex to a single
target, using the A* algorithm. A* tries to find a shortest path by
starting at from and moving to vertices that lie on a path with
the lowest estimated length. This length estimate is the sum of two
numbers: the distance from the source (from) to the intermediate vertex,
and the value returned by the heuristic function. The heuristic function
provides an estimate the distance between intermediate candidate
vertices and the target vertex to. The A* algorithm is guaranteed
to give the correct shortest path (if one exists) only if the heuristic
does not overestimate distances, i.e. if the heuristic function is
admissible.
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 estimates returned by the heuristic function. Assuming that the heuristic is admissible, the better the estimates, the shortert the running time.
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 distance
estimate to the target vertex to guide its search, and determine
which vertex to try next. The heurstic function is expected to compute
an estimate of the distance between from and to. In order for
igraph_get_shortest_path_astar() to find an exact shortest path,
the distance must not be overestimated, i.e. the heuristic function
must be admissible.
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 produce a 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 worst case.
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 of vertices and |E| is the number of edges
See also:
|
Example 13.8. File examples/simple/igraph_get_all_shortest_paths_dijkstra.c
#include <igraph.h> #include <stdlib.h> void print_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); } int main(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 the k shortest paths between two vertices, in order of
increasing lengths.
Reference:
Yen, Jin Y.: An algorithm for finding shortest routes from all source nodes to a given destination 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:
|
See also:
Time complexity: k |V| (|V| log|V| + |E|), where |V| is the number of vertices, and |E| is the number of edges.
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 vertex is visited more than once.
Note that potentially there are exponentially many
paths between two vertices of a graph, and you may
run out of memory when using this function when the
graph has many cycles. Consider using the cutoff
parameter 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 of vertices.
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 because the graph
has fewer than two vertices, or if the graph has no edges and unconn is set to true,
NaN is returned.
Arguments:
|
The graph object. |
|
Pointer to a real number, this will contain the result. |
|
Pointer to a real number. If not a null pointer, the number of ordered vertex pairs where the second vertex is unreachable from the first one will be stored here. |
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
|
What to do if the graph is not connected. If
|
Returns:
Error code:
|
Time complexity: O(|V| |E|), the number of vertices times the number of edges.
See also:
|
Example 13.9. File examples/simple/igraph_average_path_length.c
#include <igraph.h> int main(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 graph
has fewer than two vertices, or if the graph has no edges and unconn is set to true,
NaN is returned.
All distinct ordered vertex pairs are taken into account.
Arguments:
|
The graph object. |
|
Pointer to a real number, this will contain the result. |
|
Pointer to a real number. If not a null pointer, the number of ordered vertex pairs where the second vertex is unreachable from the first one will be stored here. |
|
The edge weights. All edge weights must be
non-negative for Dijkstra's algorithm to work. Additionally, no
edge weight may be NaN. If either case does not hold, an error
is returned. If this is a null pointer, then the unweighted
version, |
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
|
If |
Returns:
|
Error code:
|
Time complexity: O(|V| |E| log|E| + |V|), where |V| is the number of vertices and |E| is the number of edges.
See also:
|
Example 13.10. File examples/simple/igraph_grg_game.c
#include <igraph.h> #include <math.h> int main(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 path length between each pair of vertices. For directed graphs both directions might be considered and then every pair of vertices appears twice in the histogram.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the result is stored here. The first (i.e. zeroth) element contains the number of shortest paths of length 1, etc. The supplied vector is resized as needed. |
|
Pointer to a real number, the number of pairs for which the second vertex is not reachable from the first is stored here. |
|
Whether to consider directed paths in a directed graph (if not zero). This argument is ignored for undirected graphs. |
Returns:
Error code. |
Time complexity: O(|V||E|), the number of vertices times the number of edges.
See also:
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|), the number of vertices times the number of edges.
See also:
|
Example 13.11. File examples/simple/igraph_diameter.c
#include <igraph.h> void print_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"); } int main(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 longest
weighted shortest path, or the maximum weighted eccentricity of the graph's
vertices. 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 and multiple edges are ignored, i.e. cycles of length 1 or 2 are not 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 of computing , 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 no cycles at all then the function needs O(|V|+|E|) time to realize this and then it stops.
Example 13.12. File examples/simple/igraph_girth.c
#include <igraph.h> int main(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 shortest distance from (or to) the vertex, to (or from) all vertices in the graph, and taking the maximum.
This implementation ignores vertex pairs that are in different components. Isolated vertices have eccentricity zero.
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to an initialized vector, the result is stored here. |
|
The vertices for which the eccentricity is calculated. |
|
What kind of paths to consider for the calculation:
|
Returns:
Error code. |
Time complexity: O(|S| (|V|+|E|)), where |V| is the number of vertices, |E| is the number of edges and |S| is the number of vertices for which eccentricity is calculated.
See also:
Example 13.13. File examples/simple/igraph_eccentricity.c
#include <igraph.h> int main(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 shortest distance from (or to) the vertex, to (or from) all vertices in the graph, and taking the maximum.
This implementation ignores vertex pairs that are in different components. Isolated vertices have eccentricity zero.
Arguments:
|
The input graph, it can be directed or undirected. |
|
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 of vertices, |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 of
its vertices, see igraph_eccentricity().
Arguments:
|
The input graph, it can be directed or undirected. |
|
Pointer to a real variable, the result is stored here. |
|
What kind of paths to consider for the calculation:
|
Returns:
Error code. |
Time complexity: O(|V|(|V|+|E|)), where |V| is the number of vertices and |E| is the number of edges.
See also:
|
Example 13.14. File examples/simple/igraph_radius.c
#include <igraph.h> int main(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 the major version of igraph. Use it at your own risk.
The radius of a graph is the defined as the minimum eccentricity of
its vertices, see igraph_eccentricity().
Arguments:
|
The input graph, it can be directed or undirected. |
|
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 of vertices, |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 vertices with the minimum eccentricity. This concept is typically applied to (strongly) connected graphs. In disconnected graphs, the smallest eccentricity 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 of vertices 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 the major version of igraph. Use it at your own risk.
The central vertices of a graph are calculated by finding the vertices with the minimum eccentricity. This function takes edge weights into account 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 smallest eccentricity 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 of vertices, |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 its eccentricity. This value can be used as an approximation and lower bound of the diameter of a graph.
A pseudo-peripheral vertex is a vertex v, such that for every
vertex u which is as far away from v as possible, v is also as
far away from u as possible. The process of finding one depends
on where the search starts, and for a disconnected graph the
maximum diameter found will be that of the component vid_start
is 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 of vertices 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 its weighted eccentricity. This value can be used as an approximation and lower bound of the diameter of a graph.
A pseudo-peripheral vertex is a vertex v, such that for every
vertex u which is as far away from v as possible, v is also as
far away from u as possible. The process of finding one depends
on where the search starts, and for a disconnected graph the
maximum diameter found will be that of the component vid_start
is 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 the major version of igraph. Use it at your own risk.
To obtain a Voronoi partitioning of a graph, we start with a set of generator vertices, which will define the partitions. Each vertex is assigned to the generator vertex from (or to) which it is closest.
This function uses a BFS search for unweighted graphs and Dijkstra's algorithm for 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 distances from
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 in unweighted graphs O((log |S|) |E| + |V|), where |S| is the number of generator vertices, 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 a continuous path in a graph and you would like to obtain the vertex IDs that the path traverses. The function is used implicitly by several shortest path related functions to convert a path of edge IDs to the corresponding representation that describes the path in terms of vertex IDs instead.
Arguments:
|
the graph that the edge IDs refer to |
|
the start vertex of the path |
|
the sequence of edge IDs that describe the path |
|
the sequence of vertex IDs traversed will be returned here |
Returns:
Error code: |
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 another one, using Dijkstra's algorithm.
This function is a special case (and a wrapper) to
igraph_get_widest_paths().
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. Edge weights can be negative. If this is a null pointer or if any edge weight is NaN, then an error is returned. Edges with positive infinite weight are ignored. |
|
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_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 node to all other specified nodes, using a modified Dijkstra's algorithm. If there is more than one path with the largest width between two vertices, this function gives only one of them.
Arguments:
|
The graph object. |
||||||
|
The result, the IDs of the vertices along the paths.
This is a 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 might be given multiple times. |
||||||
|
The edge weights. Edge weights can be negative. If this is a null pointer or if any edge weight is NaN, then an error is returned. Edges with positive infinite weight are ignored. |
||||||
|
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 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 widest path tree is returned here. The
inbound edge of vertex i in the tree is the edge via which vertex i
was reached. The start vertex and vertices that were not reached
during the search will have -1 in the corresponding entry of the
vector. Note that the search terminates if all the vertices in
|
Returns:
|
Error code:
|
Time complexity: O(|E|log|E|+|V|), where |V| is the number of vertices 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 find the widest path widths from a source vertex to all other vertices. This function allows specifying a set of source and target vertices. The algorithm is run independently for each source 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 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. Edge weights can be negative. If this is a null pointer or if any edge weight is NaN, then an error is returned. Edges with positive infinite weight are ignored. |
|
For directed graphs; whether to follow paths along edge
directions ( |
Returns:
Error code. |
Time complexity: O(s*(|E|log|E|+|V|)), where |V| is the number of vertices 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 the widest path widths between a set of source and target vertices. It is primarily useful for all-pairs path widths in very dense graphs, as its running time is manily determined by the vertex count, and is not sensitive to the graph density. In sparse graphs, other methods such as the Dijkstra algorithm, will perform better.
Note that internally this function always computes the path width matrix
for all pairs of vertices. The from and to parameters only serve
to subset this matrix, but do not affect the time taken by the
calculation.
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 widths from a single source, to the
vertices given in the |
|
The source vertices. |
|
The target vertices. |
|
The edge weights. Edge weights can be negative. If this is a null pointer or if any edge weight is NaN, then an error is returned. Edges with positive infinite weight are ignored. |
|
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 inverse distances
between all pairs of vertices: E_g = 1/(N*(N-1)) sum_{i!=j} 1/d_ij,
where N is the number of vertices.
The inverse distance between pairs that are not reachable from each other is considered
to be zero. For graphs with fewer than 2 vertices, NaN is returned.
Reference: V. Latora and M. Marchiori, Efficient Behavior of Small-World Networks, Phys. Rev. Lett. 87, 198701 (2001). https://dx.doi.org/10.1103/PhysRevLett.87.198701
Arguments:
|
The graph object. |
|
Pointer to a real number, this will contain the result. |
|
The edge weights. All edge weights must be
non-negative for Dijkstra's algorithm to work. Additionally, no
edge weight may be NaN. If either case does not hold, an error
is returned. If this is a null pointer, then the unweighted
version, |
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
Returns:
|
Error code:
|
Time complexity: O(|V| |E| log|E| + |V|) for weighted graphs and O(|V| |E|) for unweighted ones. |V| denotes the number of vertices and |E| denotes the number of edges.
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) between its neighbours through the rest of the network. The local efficiency around the removed vertex is the average of the inverse of these distances.
The inverse distance between two vertices which are not reachable from each other is considered to be zero. The local efficiency around a vertex with fewer than two neighbours is taken to be zero by convention.
Reference: I. Vragović, E. Louis, and A. Díaz-Guilera, Efficiency of informational transfer in regular and complex networks, Phys. Rev. E 71, 1 (2005). http://dx.doi.org/10.1103/PhysRevE.71.036122
Arguments:
|
The graph object. |
||||||
|
Pointer to an initialized vector, this will contain the result. |
||||||
|
The vertices around which the local efficiency will be calculated. |
||||||
|
The edge weights. All edge weights must be
non-negative. Additionally, no edge weight may be NaN. If either
case does not hold, an error is returned. If this is a null
pointer, then the unweighted version,
|
||||||
|
Boolean, whether to consider directed paths. Ignored for undirected graphs. |
||||||
|
How to determine the local neighborhood of each vertex in directed graphs. Ignored in undirected graphs.
|
Returns:
|
Error code:
|
Time complexity: O(|E|^2 log|E|) for weighted graphs and O(|E|^2) for unweighted ones. |E| denotes the number of edges.
See also:
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 and O(|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 vertices which are closer to the vertex than the order. I.e., order 0 is always the vertex itself, order 1 is the vertex plus its immediate neighbors, order 2 is order 1 plus the immediate neighbors of the vertices in order 1, etc.
This function calculates the size of the neighborhood of the given order for the given vertices.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the result will be stored here. It will be resized as needed. |
|
The vertices for which the calculation is performed. |
|
Integer giving the order of the neighborhood. |
|
Specifies how to use the direction of the edges if a
directed graph is analyzed. For |
|
The minimum distance to include a vertex in the counting. Vertices reachable with a path shorter than this value are excluded. If this is one, then the starting vertex is not counted. If this is two, then its neighbors are not counted either, etc. |
Returns:
Error code. |
See also:
|
Time complexity: O(n*d*o), where n is the number vertices for which the calculation is performed, d is the average degree, o is the order.
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 vertices which are closer to the vertex than the order. I.e., order 0 is always the vertex itself, order 1 is the vertex plus its immediate neighbors, order 2 is order 1 plus the immediate neighbors of the vertices in order 1, etc.
This function calculates the vertices within the neighborhood of the specified vertices.
Arguments:
|
The input graph. |
|
An initialized 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. |
|
Specifies how to use the direction of the edges if a
directed graph is analyzed. For |
|
The minimum distance to include a vertex in the counting. Vertices reachable with a path shorter than this value are excluded. If this is one, then the starting vertex is not counted. If this is two, then its neighbors are not counted either, etc. |
Returns:
Error code. |
See also:
|
Time complexity: O(n*d*o), n is the number of vertices for which the calculation is performed, d is the average degree, o is the order.
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 vertices which are closer to the vertex than the order. Ie. order 0 is always the vertex itself, order 1 is the vertex plus its immediate neighbors, order 2 is order 1 plus the immediate neighbors of the vertices in order 1, etc.
This function finds every vertex in the neighborhood of a given parameter vertex and creates the induced subgraph from these vertices.
The first version of this function was written by Vincent Matossian, thanks Vincent.
Arguments:
|
The input graph. |
|
Pointer to a list of graphs, the result will be stored
here. Each item in the list is an |
|
The vertices for which the calculation is performed. |
|
Integer giving the order of the neighborhood. |
|
Specifies how to use the direction of the edges if a
directed graph is analyzed. For |
|
The minimum distance to include a vertex in the counting. Vertices reachable with a path shorter than this value are excluded. If this is one, then the starting vertex is not counted. If this is two, then its neighbors are not counted either, etc. |
Returns:
Error code. |
See also:
|
Time complexity: O(n*(|V|+|E|)), where n is the number vertices for which the calculation is performed, |V| and |E| are the number of vertices and edges in the original input graph.
The scan statistic is a summary of the locality statistics that is computed from the local neighborhood of each vertex. For details, see Priebe, C. E., Conroy, J. M., Marchette, D. J., Park, Y. (2005). Scan Statistics on Enron Graphs. Computational and Mathematical Organization Theory.
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 for
unweighted, and the vertex strength for weighted graphs. See igraph_degree() and igraph_strength().
Arguments:
|
The input graph |
|
An initialized vector, the results are stored here. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
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 the 1-neighborhood of vertices.
Arguments:
|
The input graph |
|
An initialized vector, the results are stored here. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
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 for
unweighted, and the vertex strength for weighted graphs. See igraph_degree() and igraph_strength().
Arguments:
|
The input graph, to use to extract the neighborhoods. |
|
The input graph to use for the actually counting. |
|
An initialized vector, the results are stored here. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
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 the 1-neighborhood of vertices.
Arguments:
|
The input graph to extract the neighborhoods. |
|
The input graph to perform the counting. |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
See also:
|
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 the k-neighborhood of vertices.
Arguments:
|
The input graph to extract the neighborhoods. |
|
The input graph to perform the counting. |
|
The size of the neighborhood, non-negative integer.
The k=0 case is special, see |
|
Weight vector for weighted graphs, null pointer for unweighted graphs. |
|
Type of the neighborhood, |
Returns:
Error code. |
See also:
|
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 in neighborhoods given as a parameter.
Deprecated since version 0.10.0. Please do not use this function in new
code; use igraph_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 of igraph_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 in induced 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 of igraph_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 specified vertex. In undirected graphs, this is simple the set of vertices within the 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 and edges 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 be
indexed in topological order. In other words, vertex v is reachable
from vertex u precisely when membership[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 vertices and edges in the graph.
Example 13.15. File examples/simple/igraph_contract_vertices.c
#include <igraph.h> /* Create the condensation of a directed graph. * See https://en.wikipedia.org/wiki/Strongly_connected_component#Definitions * This example demonstrates how to write a basic igraph function, complete * with error handling. */ igraph_error_t condensation(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 */ } int main(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 new
code; use igraph_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 reachable from any other. A directed graph with this property is called strongly connected. A directed graph that would be connected when ignoring the directions of its edges is called weakly connected.
A graph with zero vertices (i.e. the null graph) is not connected by definition. This behaviour changed in igraph 0.9; earlier versions assumed that the null graph is connected. See the following issue on Github for the argument that led us to change the definition: https://github.com/igraph/igraph/issues/1539
The return value of this function is cached in the graph itself, separately for weak and strong connectivity. Calling the function multiple times with no modifications to the graph in between will return a cached value in O(1) time.
Arguments:
|
The graph object to analyze. |
|
Pointer to a logical variable, the result will be stored here. |
|
For a directed graph this specifies whether to calculate
weak or strong connectedness. Possible values:
|
Returns:
Error code:
|
Time complexity: O(|V|+|E|), the number of vertices plus the number of edges in the graph.
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 the vertex IDs in the new graphs will be different than in the original graph, 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 number of edges.
Example 13.16. File examples/simple/igraph_decompose.c
#include <igraph.h> #include <stdlib.h> int main(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 all igraph_t
objects held in complist. However, it does not destroy
complist itself. Use igraph_vector_ptr_destroy() to destroy
complist.
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 new code.
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 the major 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 reachable from 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 of igraph_integer_t, typically the word 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 the major 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 of igraph_integer_t, typically the word 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 the major version of igraph. Use it at your own risk.
The resulting graph will have an edge from vertex i to vertex j
if j is reachable from i.
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 (and its incident edges) does not disconnect it.
A biconnected component of a graph is a maximal biconnected subgraph of it. The biconnected components of a graph can be given by a partition of its edges: every edge is a member of exactly one biconnected component. Note that this is not true for vertices: the same vertex can be part of many biconnected components, while isolated vertices are part of none at all.
Note that some authors do not consider the graph consisting of two connected vertices as biconnected, however, igraph does.
igraph does not consider components containing a single vertex only as
being biconnected. Isolated vertices will not be part of any of the
biconnected components. This means that checking whether there is a single
biconnected component is not sufficient for determining if a graph is
biconnected. Use igraph_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 and
edges, but only if you do not calculate components and
component_edges. If you calculate components, then it is
quadratic in the number of vertices. If you calculate
component_edges as well, then it is cubic in the number of
vertices.
See also:
Example 13.17. File examples/simple/igraph_biconnected_components.c
#include <igraph.h> /* Prints a vector of edge IDs as u--v vertex pairs. */ void print_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"); } int main(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 increases the number of (weakly) connected components in the graph.
Note that a graph without any articulation points is not necessarily
biconnected. Counterexamples are the two-vertex complete graph as well
as empty graphs. Use igraph_is_biconnected() to check whether
a 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 the major version of igraph. Use it at your own risk.
A graph is biconnected if the removal of any single vertex (and its incident edges) does not disconnect it.
igraph does not consider single-vertex graphs biconnected.
Note that some authors do not consider the graph consisting of two 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. File examples/simple/igraph_is_biconnected.c
#include <igraph.h> #include <stdio.h> int main(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_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 perform the check also when either self-loops, multi-edge, or both are allowed in the graph.
For simple undirected graphs, the Erdős-Gallai conditions are checked using the linear-time algorithm of Cloteaux. If both self-loops and multi-edges are allowed, it is sufficient to chek that that sum of degrees is even. If only multi-edges are allowed, but not self-loops, there is an additional condition that the sum of degrees be no smaller than twice the maximum degree. If at most one self-loop is allowed per vertex, but no multi-edges, a modified version of the Erdős-Gallai conditions are used (see Cairns & Mendan).
For simple directed graphs, the Fulkerson-Chen-Anstee theorem is used with the relaxation by Berger.
If both self-loops and multi-edges are allowed, then it is sufficient to check that the sum of
in- and out-degrees is the same. If only multi-edges are allowed, but not self loops, there is an
additional condition that the sum of out-degrees (or equivalently, in-degrees) is no smaller than
the maximum total degree. If single self-loops are allowed, but not multi-edges, the problem is equivalent
to realizability as a simple bipartite graph, thus the Gale-Ryser theorem can be used; see
igraph_is_bigraphical() for more information.
References:
P. Erdős and T. Gallai, Gráfok előírt fokú pontokkal, Matematikai Lapok 11, pp. 264–274 (1960). https://users.renyi.hu/~p_erdos/1961-05.pdf
Z Király, Recognizing graphic degree sequences and generating all realizations. TR-2011-11, Egerváry Research Group, H-1117, Budapest, Hungary. ISSN 1587-4451 (2012). http://bolyai.cs.elte.hu/egres/tr/egres-11-11.pdf
B. Cloteaux, Is This for Real? Fast Graphicality Testing, Comput. Sci. Eng. 17, 91 (2015). https://dx.doi.org/10.1109/MCSE.2015.125
A. Berger, A note on the characterization of digraphic sequences, Discrete Math. 314, 38 (2014). https://dx.doi.org/10.1016/j.disc.2013.09.010
G. Cairns and S. Mendan, Degree Sequence for Graphs with Loops (2013). https://arxiv.org/abs/1303.2145v1
Arguments:
|
A vector of integers specifying the degree sequence for undirected graphs or the out-degree sequence for directed graphs. |
||||||||
|
A vector of integers specifying the in-degree sequence for
directed graphs. For undirected graphs, it must be |
||||||||
|
The types of edges to allow in the graph:
|
||||||||
|
Pointer to a Boolean. The result will be stored here. |
Returns:
Error code. |
See also:
|
Time complexity: O(n), 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 of a bipartite graph. Such a pair of degree sequence is called bigraphical.
When multi-edges are allowed, it is sufficient to check that the sum of degrees is the same in the two partitions. For simple graphs, the Gale-Ryser theorem is used with Berger's relaxation.
References:
H. J. Ryser, Combinatorial Properties of Matrices of Zeros and Ones, Can. J. Math. 9, 371 (1957). https://dx.doi.org/10.4153/cjm-1957-044-3
D. Gale, A theorem on flows in networks, Pacific J. Math. 7, 1073 (1957). https://dx.doi.org/10.2140/pjm.1957.7.1073
A. Berger, A note on the characterization of digraphic sequences, Discrete Math. 314, 38 (2014). https://dx.doi.org/10.1016/j.disc.2013.09.010
Arguments:
|
A vector of integers specifying the degrees in the first partition |
||||
|
A vector of integers specifying the degrees in the second partition |
||||
|
The types of edges to allow in the graph:
|
||||
|
Pointer to a Boolean. The result will be stored here. |
Returns:
Error code. |
See also:
Time complexity: O(n), 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 other vertices can be reached from it (or the other way: how easily it can be reached from the other vertices). It is defined as the inverse of the mean distance to (or from) all other vertices.
Closeness centrality is meaningful only for connected graphs.
If the graph is not connected, igraph computes the inverse of the
mean distance to (or from) all reachable vertices. In undirected
graphs, this is equivalent to computing the closeness separately in
each connected component. The optional all_reachable output
parameter is provided to help detect when the graph is disconnected.
While there is no universally adopted definition of closeness centrality
for disconnected graphs, there have been some attempts for generalizing
the concept to the disconnected case. One type of approach considers the mean distance
only to reachable vertices, then re-scales the obtained certrality score
by a factor that depends on the number of reachable vertices
(i.e. the size of the component in the undirected case).
To facilitate computing these generalizations of closeness centrality,
the number of reachable vertices (not including the starting vertex)
is returned in reachable_count.
In disconnected graphs, consider using the harmonic centrality,
computable using igraph_harmonic_centrality().
For isolated vertices, i.e. those having no associated paths, NaN is returned.
Arguments:
|
The graph object. |
||||||
|
The result of the computation, a vector containing the closeness centrality scores for the given vertices. |
||||||
|
If not |
||||||
|
Pointer to a Boolean. If not |
||||||
|
The vertices for which the closeness centrality will be computed. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
An optional vector containing edge weights for weighted closeness. No edge weight may be NaN. Supply a null pointer here for traditional, unweighted closeness. |
||||||
|
If true, the inverse of the mean distance to reachable vetices is returned. If false, the inverse of the sum of distances is returned. |
Returns:
|
Error code:
|
Time complexity: O(n|E|) for the unweighted case and O(n|E|log|V|+|V|) for the weighted case, where n is the number of vertices for which the calculation is done, |V| is the number of vertices and |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 to all other vertices. The inverse distance to an unreachable vertex is considered to be zero.
References:
M. Marchiori and V. Latora, Harmony in the small-world, Physica A 285, pp. 539-546 (2000). https://doi.org/10.1016/S0378-4371%2800%2900311-3
Y. Rochat, Closeness Centrality Extended to Unconnected Graphs: the Harmonic Centrality Index, ASNA 2009. https://infoscience.epfl.ch/record/200525
S. Vigna and P. Boldi, Axioms for Centrality, Internet Mathematics 10, (2014). https://doi.org/10.1080/15427951.2013.865686
Arguments:
|
The graph object. |
||||||
|
The result of the computation, a vector containing the harmonic centrality scores for the given vertices. |
||||||
|
The vertices for which the harmonic centrality will be computed. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
An optional vector containing edge weights for
weighted harmonic centrality. No edge weight may be NaN.
If |
||||||
|
Boolean, whether to normalize the result. If true, the result is the mean inverse path length to other vertices, i.e. it is normalized by the number of vertices minus one. If false, the result is the sum of inverse path lengths to other vertices. |
Returns:
|
Error code:
|
Time complexity: O(n|E|) for the unweighted case and O(n*|E|log|V|+|V|) for the weighted case, where n is the number of vertices for which the calculation is done, |V| is the number of vertices and |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 geodesics going through it. If there are more than one geodesic between two vertices, the value of these geodesics are weighted by one over the number of geodesics.
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. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional vector containing edge weights for calculating weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
Returns:
Error code:
|
Time complexity: O(|V||E|), |V| and |E| are the number of vertices and edges in the graph. Note that the time complexity is independent of the number of vertices for which the score is calculated.
See also:
Other centrality types: |
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 geodesics going through it. If there are more than one geodesics between two vertices, the value of these geodesics are weighted by one over the number of geodesics.
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. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional weight vector for weighted edge betweenness. No edge weight may be NaN. Supply a null pointer here for the unweighted version. |
Returns:
Error code:
|
Time complexity: O(|V||E|), |V| and |E| are the number of vertices and edges in the graph.
See also:
Other centrality types: |
typedef enum {
IGRAPH_PAGERANK_ALGO_ARPACK = 1,
IGRAPH_PAGERANK_ALGO_PRPACK = 2
} igraph_pagerank_algo_t;
Algorithms to calculate PageRank.
Values:
|
Use the ARPACK library, this was the PageRank implementation in igraph from version 0.5, until version 0.7. |
|
Use the PRPACK library. Currently this implementation is recommended. |
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 a
random walker traversing the graph would spend on that vertex.
The walker follows the out-edges with probabilities proportional
to their weights. Additionally, in each step, it restarts the walk
from a random vertex with probability 1 - damping.
If the random walker gets stuck in a sink vertex, it will also restart
from a random vertex.
The PageRank centrality is mainly useful for directed graphs. In undirected graphs it converges to trivial values proportional to degrees as the damping factor approaches 1.
Starting from version 0.9, igraph has two PageRank implementations,
and the user can choose between them. The first implementation is
IGRAPH_PAGERANK_ALGO_ARPACK, which phrases the PageRank calculation
as an eigenvalue problem, which is then solved using the ARPACK library.
This was the default before igraph version 0.7. The second and recommended
implementation is IGRAPH_PAGERANK_ALGO_PRPACK. This is using the
PRPACK package, see https://github.com/dgleich/prpack. PRPACK uses an
algebraic method, i.e. solves a linear system to obtain the PageRank
scores.
Note that the PageRank of a given vertex depends on the PageRank of all other vertices, so even if you want to calculate the PageRank for only some of the vertices, all of them must be calculated. Requesting the PageRank for only some of the vertices does not result in any performance increase at all.
References:
Sergey Brin and Larry Page: The Anatomy of a Large-Scale Hypertextual Web Search Engine. Proceedings of the 7th World-Wide Web Conference, Brisbane, Australia, April 1998. 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. File examples/simple/igraph_pagerank.c
#include <igraph.h> #include <float.h> int main(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, but
when the random walk is restarted, a new starting vertex is chosen non-uniformly,
according to the distribution specified in reset
(instead of the uniform distribution in the original PageRank measure).
The reset distribution is used both when restarting randomly with probability
1 - damping, and when the walker is forced to restart due to being
stuck in a sink vertex (a vertex with no outgoing edges).
Note that the personalized PageRank of a given vertex depends on the personalized PageRank of all other vertices, so even if you want to calculate the personalized PageRank for only some of the vertices, all of them must be calculated. Requesting the personalized PageRank for only some of the vertices does not result in any performance increase at all.
Arguments:
|
The graph object. |
|
The PageRank implementation to use. Possible values:
|
|
Pointer to an initialized vector, the result is stored here. It is resized as needed. |
|
Pointer to a real variable. 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, but
when the random walk is restarted, a new starting vertex is chosen according to
a specified distribution.
This distribution is used both when restarting randomly with probability
1 - damping, and when the walker is forced to restart due to being
stuck in a sink vertex (a vertex with no outgoing edges).
This simplified interface takes a vertex sequence and resets the random walk to
one of the vertices in the specified vertex sequence, chosen uniformly. A typical
application of personalized PageRank is when the random walk is reset to the same
vertex every time - this can easily be achieved using igraph_vss_1() which
generates a vertex sequence containing only a single vertex.
Note that the personalized PageRank of a given vertex depends on the personalized PageRank of all other vertices, so even if you want to calculate the personalized PageRank for only some of the vertices, all of them must be calculated. Requesting the personalized PageRank for only some of the vertices does not result in any performance increase at all.
Arguments:
|
The graph object. |
|
The PageRank implementation to use. Possible values:
|
|
Pointer to an initialized vector, the result is stored here. It is resized as needed. |
|
Pointer to a real variable. 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. |
|
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 given vertices, also known as structural holes.
Burt's constraint is higher if ego has less, or mutually stronger related (i.e. more redundant) contacts. Burt's measure of constraint, C[i], of vertex i's ego network V[i], is defined for directed and valued graphs,
C[i] = sum( sum( (p[i,q] p[q,j])^2, q in V[i], q != i,j ), j in V[], j != i)
for a graph of order (i.e. number of vertices) N, where proportional tie strengths are defined as
p[i,j]=(a[i,j]+a[j,i]) / sum(a[i,k]+a[k,i], k in V[i], k != i),
a[i,j] are elements of A and the latter being the graph adjacency matrix. For isolated vertices, constraint is undefined.
Burt, R.S. (2004). Structural holes and good ideas. American Journal of Sociology 110, 349-399.
The first R version of this function was contributed by Jeroen Bruggeman.
Arguments:
|
A graph object. |
|
Pointer to an initialized vector, the result will be stored here. The vector will be resized to have the appropriate size for holding the result. |
|
Vertex selector containing the vertices for which the constraint should be calculated. |
|
Vector giving the weights of the edges. If it is
|
Returns:
Error code. |
Time complexity: O(|V|+E|+n*d^2), n is the number of vertices for
which the constraint is calculated and d is the average degree, |V|
is the number of vertices, |E| the number of edges in the
graph. If the weights argument is NULL then the time complexity
is O(|V|+n*d^2).
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 is
calculated. If the graph has no vertices, or vids is empty,
0 is returned, as this is the smallest possible value for degrees.
Arguments:
|
The input graph. |
|
Pointer to an integer ( |
|
Vector giving the vertex IDs for which the maximum degree will be calculated. |
|
Defines the type of the degree.
|
|
Boolean, gives whether the self-loops should be counted. |
Returns:
Error code:
|
Time complexity: O(v) if loops is true, and O(v*d) otherwise. v is the number
of vertices for which the degree will be calculated, and d is their
(average) degree.
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 the weights of all incident edges. In a non-weighted network this is exactly the vertex degree.
Arguments:
|
The input graph. |
|
Pointer to an initialized vector, the result is stored here. It will be resized as needed. |
|
The vertices for which the calculation is performed. |
|
Gives whether to count only outgoing ( |
|
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 and edges.
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 a network. It assigns relative scores to all nodes in the network based on the principle that connections from high-scoring nodes contribute more to the score of the node in question than equal connections from low-scoring nodes. Specifically, the eigenvector centrality of each vertex is proportional to the sum of eigenvector centralities of its neighbors. In practice, the centralities are determined by calculating the eigenvector corresponding to the largest positive eigenvalue of the adjacency matrix. In the undirected case, this function considers the diagonal entries of the adjacency matrix to be twice the number of self-loops on the corresponding vertex.
In the weighted case, the eigenvector centrality of a vertex is proportional
to the weighted sum of centralities of its neighbours, i.e.
c_j = sum_i w_ij c_i, where w_ij is the weight
of the edge connecting vertex i to j. The weights of parallel edges
are added up.
The centrality scores returned by igraph can be normalized
(using the scale parameter) such that the largest eigenvector centrality
score is 1 (with one exception, see below).
In the directed case, the left eigenvector of the adjacency matrix is calculated. In other words, the centrality of a vertex is proportional to the sum of centralities of vertices pointing to it.
Eigenvector centrality is meaningful only for (strongly) connected graphs. Undirected graphs that are not connected should be decomposed into connected components, 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 the
adjacency 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 returned
eigenvector centralities will all be equal for vertices with zero out-degree,
and zeros for other vertices. Such pathological cases can be detected
by asking igraph to calculate the eigenvalue as well (using the value
parameter, see below) and checking whether the eigenvalue is very close
to zero.
When working with directed graphs, consider using hub and authority
scores instead, see igraph_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. File examples/simple/eigenvector_centrality.c
#include "igraph.h" #include <math.h> int main(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 behind eigenvector centrality to directed graphs. The authority score of a vertex is proportional to the sum of the hub scores of vertices that point to it. Conversely, the hub score of a vertex is proportional to the sum of authority scores of vertices that it points to. These concepts are also known under the name Hyperlink-Induced Topic Search (HITS).
The hub and authority scores of the vertices are defined as the principal
eigenvectors of A A^T and A^T A, respectively,
where A is the adjacency matrix of the graph and A^T
is its transposed.
If vector h and a contain hub and authority scores, then the two
scores are related by h = Aa and a = A^T h.
When the principal eigenvalue of A A^T is degenerate, there
is no unique solution to the hub- and authority-score problem.
igraph guarantees that the scores that are returned are matching, i.e. are
related by these formulas, even in this situation.
The concept of hub and authority scores were developed for directed graphs.
In undirected graphs, both the hub and authority scores are equal to the
eigenvector centrality, which can be computed using
igraph_eigenvector_centrality().
See the following reference on the meaning of this score: J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). https://doi.org/10.1145/324133.324140 Also appears as IBM Research Report RJ 10076, May 1997.
Arguments:
|
The input graph. Can be directed and undirected. |
|
Pointer to an initialized vector, the 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 where the shortest paths passing through (i, j) originate, and similarly, let us defined the output set of an edge (i, j) as the set of vertices where the shortest paths passing through (i, j) terminate. The convergence degree of an edge is defined as the normalized value of the difference between the size of the input set and the output set, i.e. the difference of them divided by the sum of them. Convergence degrees are in the range (-1, 1); a positive value indicates that the edge is convergent since the shortest paths passing through it originate from a larger set and terminate in a smaller set, while a negative value indicates that the edge is divergent since the paths originate from a small set and terminate in a larger set.
Note that the convergence degree as defined above does not make sense in undirected graphs as there is no distinction between the input and output set. Therefore, for undirected graphs, the input and output sets of an edge are determined by orienting the edge arbitrarily while keeping the remaining edges undirected, and then taking the absolute value of the convergence degree.
Arguments:
|
The input graph, it can be either directed or undirected. |
|
Pointer to an initialized vector; the convergence degrees of
each edge will be stored here. May be |
|
Pointer to an initialized vector; the size of the input set of
each edge will be stored here. May be |
|
Pointer to an initialized vector; the size of the output set of
each edge will be stored here. May be |
Returns:
Error code. |
Time complexity: O(|V||E|), the number of vertices times the number of edges.
igraph_closeness_cutoff — Range limited closeness centrality.igraph_harmonic_centrality_cutoff — Range limited harmonic centrality.igraph_betweenness_cutoff — Range-limited betweenness centrality.igraph_edge_betweenness_cutoff — Range-limited betweenness centrality of the edges.
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 centrality by considering only those shortest paths whose length is no greater then the given cutoff value.
Arguments:
|
The graph object. |
||||||
|
The result of the computation, a vector containing the range-limited closeness centrality scores for the given vertices. |
||||||
|
If not |
||||||
|
Pointer to a Boolean. If not |
||||||
|
The vertices for which the range limited closeness centrality will be computed. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
An optional vector containing edge weights for weighted closeness. No edge weight may be NaN. Supply a null pointer here for traditional, unweighted closeness. |
||||||
|
If true, the inverse of the mean distance to vertices reachable within the cutoff is returned. If false, the inverse of the sum of distances is returned. |
||||||
|
The maximal length of paths that will be considered. If negative, the exact closeness will be calculated (no upper limit on path lengths). |
Returns:
|
Error code:
|
Time complexity: At most O(n|E|) for the unweighted case and O(n|E|log|V|+|V|) for the weighted case, where n is the number of vertices for which the calculation is done, |V| is the number of vertices and |E| is the number of edges in the graph. The timing decreases with smaller cutoffs 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 considered to be zero.
Arguments:
|
The graph object. |
||||||
|
The result of the computation, a vector containing the range limited harmonic centrality scores for the given vertices. |
||||||
|
The vertices for which the harmonic centrality will be computed. |
||||||
|
The type of shortest paths to be used for the calculation in directed graphs. Possible values:
|
||||||
|
An optional vector containing edge weights for
weighted harmonic centrality. No edge weight may be NaN.
If |
||||||
|
Boolean, whether to normalize the result. If true, the result is the mean inverse path length to other vertices. i.e. it is normalized by the number of vertices minus one. If false, the result is the sum of inverse path lengths to other vertices. |
||||||
|
The maximal length of paths that will be considered. The inverse distance to vertices that are not reachable within the cutoff path length is considered to be zero. Supply a negative value to compute the exact harmonic centrality, without any upper limit on the length of paths. |
Returns:
|
Error code:
|
Time complexity: At most O(n|E|) for the unweighted case and O(n|E|log|V|+|V|) for the weighted case, where n is the number of vertices for which the calculation is done, |V| is the number of vertices and |E| is the number of edges in the graph. The timing decreases with smaller cutoffs 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 centrality by considering only those shortest paths whose length is no greater then the given cutoff value.
Arguments:
|
The graph object. |
|
The result of the computation, a vector containing the range-limited betweenness scores for the specified vertices. |
|
The vertices for which the range-limited betweenness centrality scores will be computed. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional vector containing edge weights for calculating weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
|
The maximal length of paths that will be considered. If negative, the exact betweenness will be calculated, and there will be no upper limit on path lengths. |
Returns:
Error code:
|
Time complexity: O(|V||E|), |V| and |E| are the number of vertices and edges in the graph. Note that the time complexity is independent of the number of vertices for which the score is calculated.
See also:
|
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 centrality by considering only those shortest paths whose length is no greater then the given cutoff value.
Arguments:
|
The graph object. |
|
The result of the computation, vector containing the betweenness scores for the edges. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional weight vector for weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
|
The maximal length of paths that will be considered. If negative, the exact betweenness will be calculated (no upper limit on path lengths). |
Returns:
Error code:
|
Time complexity: O(|V||E|), |V| and |E| are the number of vertices and edges in the graph.
See also:
|
igraph_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 centrality by considering only those shortest paths that lie between vertices in a given source 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. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional vector containing edge weights for calculating weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
|
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. |
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 centrality by considering only those shortest paths that lie between vertices in a given source 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. |
|
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs. |
|
An optional weight vector for weighted betweenness. No edge weight may be NaN. Supply a null pointer here for unweighted betweenness. |
|
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. |
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 is possible to define a graph level centralization index, by calculating the sum of the deviations from the maximum centrality score. Consequently, the higher the centralization index of the graph, the more centralized the structure is.
In order to make graphs of different sizes comparable, the centralization index is usually normalized to a number between zero and one, by dividing the (unnormalized) centralization score of the most centralized structure with the same number of vertices.
For most centrality indices, the most centralized structure is the star graph, a single center connected to all other nodes in the network. There 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 node level scores and the theoretical maximum are given. It is called by all the measure-specific centralization functions. It uses the calculation
C = sum_v ((max_u c_u) - c_v)
where c are the centrality scores passed in scores. If normalized
is true, then C/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. File examples/simple/centralization.c
#include <igraph.h> int main(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 its
arguments to igraph_degree(); and it calculates the graph
level centralization index based on the results by calling igraph_centralization().
Arguments:
|
The input graph. |
|
A vector if you need the node-level degree scores, or a null pointer otherwise. |
|
Constant the specifies the type of degree for directed
graphs. Possible values: |
|
Boolean, whether to consider loop edges when calculating the degree (and the centralization). |
|
Pointer to a real number, the centralization score is placed here. |
|
Pointer to real number or a null pointer. If not a null pointer, then the theoretical maximum graph centrality score for a graph with the same number vertices is stored here. |
|
Boolean, whether to calculate a normalized
centralization score. See |
Returns:
Error code. |
See also:
Time complexity: the complexity of igraph_degree() plus O(n),
the number of vertices queried, for calculating the centralization
score.
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 vertices
by passing its arguments to igraph_betweenness(); and it
calculates the graph level centralization index based on the
results by calling igraph_centralization().
Arguments:
|
The input graph. |
|
A vector if you need the node-level betweenness scores, or a null pointer otherwise. |
|
Boolean, whether to consider directed paths when calculating betweenness. |
|
Pointer to a real number, the centralization score is placed here. |
|
Pointer to real number or a null pointer. If not a null pointer, then the theoretical maximum graph centrality score for a graph with the same number vertices is stored here. |
|
Boolean, whether to calculate a normalized
centralization score. See |
Returns:
Error code. |
See also:
Time complexity: the complexity of igraph_betweenness() plus
O(n), the number of vertices queried, for calculating the
centralization score.
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 vertices
by passing its arguments to igraph_closeness(); and it
calculates the graph level centralization index based on the
results by calling igraph_centralization().
Arguments:
|
The input graph. |
|
A vector if you need the node-level closeness scores, or a null pointer otherwise. |
|
Constant the specifies the type of closeness for directed
graphs. Possible values: |
|
Pointer to a real number, the centralization score is placed here. |
|
Pointer to real number or a null pointer. If not a null pointer, then the theoretical maximum graph centrality score for a graph with the same number vertices is stored here. |
|
Boolean, whether to calculate a normalized
centralization score. See |
Returns:
Error code. |
See also:
Time complexity: the complexity of igraph_closeness() plus
O(n), the number of vertices queried, for calculating the
centralization score.
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 vertices
by passing its arguments to igraph_eigenvector_centrality);
and it calculates the graph level centralization index based on the
results by calling igraph_centralization().
Note that vertex-level eigenvector centrality scores do not have a natural scale. As with any eigenvector, their interpretation is invariant to scaling by a constant factor. However, due to how graph-level centralization is defined, its value depends on the specific scale/normalization used for vertex-level scores. Which of two graphs will have a higher eigenvector centralization depends on the choice of normalization for centralities. This function makes the specific choice of scaling vertex-level centrality scores by their maximum (i.e. it uses the ∞-norm). Other normalization choices, such as 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. |
|
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 of igraph_eigenvector_centrality() plus O(|V|), the number of vertices
for 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 centrality based on vertex degree.
There are two ways to call this function, the first is to supply a
graph as the graph argument, and then the number of
vertices is taken from this object, and its directedness is
considered as well. The nodes argument is ignored in
this case. The mode argument is also ignored if the
supplied graph is undirected.
The other way is to supply a null pointer as the graph
argument. In this case the nodes and mode
arguments are considered.
The most centralized structure is the star. More specifically, for undirected graphs it is the star, for directed graphs it is the in-star or the out-star.
Arguments:
|
A graph object or a null pointer, see the description above. |
|
The number of nodes. This is ignored if the
|
|
Constant, whether the calculation is based on in-degree
( |
|
Boolean, 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 centrality based on vertex betweenness.
There are two ways to call this function, the first is to supply a
graph as the graph argument, and then the number of
vertices is taken from this object, and its directedness is
considered as well. The nodes argument is ignored in
this case. The directed argument is also ignored if the
supplied graph is undirected.
The other way is to supply a null pointer as the graph
argument. In this case the nodes and directed
arguments are considered.
The most centralized structure is the star.
Arguments:
|
A graph object or a null pointer, see the description above. |
|
The number of nodes. This is ignored if the
|
|
Boolean, 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 centrality based on vertex closeness.
There are two ways to call this function, the first is to supply a
graph as the graph argument, and then the number of
vertices is taken from this object, and its directedness is
considered as well. The nodes argument is ignored in
this case. The mode argument is also ignored if the
supplied graph is undirected.
The other way is to supply a null pointer as the graph
argument. In this case the nodes and mode
arguments are considered.
The most centralized structure is the star.
Arguments:
|
A graph object or a null pointer, see the description above. |
|
The number of nodes. This is ignored if the
|
|
Constant, specifies what 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 centrality based on vertex eigenvector centrality.
There are two ways to call this function, the first is to supply a
graph as the graph argument, and then the number of
vertices is taken from this object, and its directedness is
considered as well. The nodes argument is ignored in
this case. The directed argument is also ignored if the
supplied graph is undirected.
The other way is to supply a null pointer as the graph
argument. In this case the nodes and directed
arguments are considered.
The most centralized directed structure is assumed to bethe in-star. The most centralized undirected structure is assumed to be the graph with a single edge. igraph continues to implement these choices for historical reason. Keep in mind that neither of these two structures is connected, which makes their use debatable in the context of eigenvector centrality calculations. Eigenvector centrality is not uniquely defined for disconnected structures.
Note that vertex-level eigenvector centrality scores do not have a natural scale. As with any eigenvector, their interpretation is invariant to scaling by a constant factor. However, due to how graph-level centralization is defined, its value depends on the specific scale/normalization used for vertex-level scores. Moreover, which of two graphs will have a higher eigenvector centralization also depends on the choice of normalization for centralities. This function makes the specific choice of scaling vertex-level centrality scores by their maximum (i.e. it uses the ∞-norm). Other normalization choices, 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 number
of other vertices they both cite, igraph_bibcoupling() calculates
this.
The bibliographic coupling score for each given vertex and all
other vertices in the graph will be calculated.
Arguments:
|
The graph object to analyze. |
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows is the same as the
number of vertex IDs in |
|
The vertex IDs of the vertices for which the calculation will be done. |
Returns:
Error code:
|
Time complexity: O(|V|d^2), |V| is the number of vertices in the graph, d is the (maximum) degree of the vertices in the graph.
See also:
Example 13.22. File examples/simple/igraph_cocitation.c
#include <igraph.h> #include <stdio.h> int main(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 of
them. igraph_cocitation() simply counts how many times two vertices are
cocited.
The cocitation score for each given vertex and all other vertices
in the graph will be calculated.
Arguments:
|
The graph object to analyze. |
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows is the same as the
number of vertex IDs in |
|
The vertex IDs of the vertices for which the calculation will be done. |
Returns:
Error code:
|
Time complexity: O(|V|d^2), |V| is the number of vertices in the graph, d is the (maximum) degree of the vertices in the graph.
See also:
Example 13.23. File examples/simple/igraph_cocitation.c
#include <igraph.h> #include <stdio.h> int main(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 common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for some (or all) of the vertices.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows and columns is the same
as the number of vertex IDs in |
||||||
|
The vertex IDs of the vertices for which the calculation will be done. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves in the neighbor sets. |
Returns:
|
Error code:
|
Time complexity: O(|V|^2 d), |V| is the number of vertices in the vertex iterator given, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.24. File examples/simple/igraph_similarity.c
#include <igraph.h> int main(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 common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for a list of vertex pairs.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a vector, the result of the calculation will
be stored here. The number of elements is the same as the number
of pairs in |
||||||
|
A vector that contains the pairs for which the similarity will be calculated. Each pair is defined by two consecutive elements, i.e. the first and second element of the vector specifies the first pair, the third and fourth element specifies the second pair and so on. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves in the neighbor sets. |
Returns:
|
Error code:
|
Time complexity: O(nd), n is the number of pairs in the given vector, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.25. File examples/simple/igraph_similarity.c
#include <igraph.h> int main(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 common neighbors divided by the number of vertices that are neighbors of at least one of the two vertices being considered. This function calculates the pairwise Jaccard similarities for the endpoints of edges in a given edge selector.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a vector, the result of the calculation will
be stored here. The number of elements is the same as the number
of edges in |
||||||
|
An edge selector that specifies the edges to be included in the result. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves in the neighbor sets. |
Returns:
|
Error code:
|
Time complexity: O(nd), n is the number of edges in the edge selector, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.26. File examples/simple/igraph_similarity.c
#include <igraph.h> int main(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 common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for some (or all) of the vertices.
Arguments:
|
The graph object to analyze. |
||||||
|
Pointer to a matrix, the result of the calculation will
be stored here. The number of its rows and columns is the same
as the number of vertex IDs in |
||||||
|
The vertex IDs of the vertices for which the calculation will be done. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves as their own neighbors. |
Returns:
|
Error code:
|
Time complexity: O(|V|^2 d), where |V| is the number of vertices in the vertex iterator given, and d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.27. File examples/simple/igraph_similarity.c
#include <igraph.h> int main(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 common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for a list of vertex pairs.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a vector, the result of the calculation will
be stored here. The number of elements is the same as the number
of pairs in |
||||||
|
A vector that contains the pairs for which the similarity will be calculated. Each pair is defined by two consecutive elements, i.e. the first and second element of the vector specifies the first pair, the third and fourth element specifies the second pair and so on. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves as their own neighbors. |
Returns:
|
Error code:
|
Time complexity: O(nd), n is the number of pairs in the given vector, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.28. File examples/simple/igraph_similarity.c
#include <igraph.h> int main(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 common neighbors divided by the sum of the degrees of the vertices. This function calculates the pairwise Dice similarities for the endpoints of edges in a given edge selector.
Arguments:
|
The graph object to analyze |
||||||
|
Pointer to a vector, the result of the calculation will
be stored here. The number of elements is the same as the number
of edges in |
||||||
|
An edge selector that specifies the edges to be included in the result. |
||||||
|
The type of neighbors to be used for the calculation in directed graphs. Possible values:
|
||||||
|
Whether to include the vertices themselves as their own neighbors. |
Returns:
|
Error code:
|
Time complexity: O(nd), n is the number of pairs in the given vector, d is the (maximum) degree of the vertices in the graph.
See also:
|
Example 13.29. File examples/simple/igraph_similarity.c
#include <igraph.h> int main(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 of their common neighbors, weighted by the inverse logarithm of their degrees. It is based on the assumption that two vertices should be considered more similar if they share a low-degree common neighbor, since high-degree common neighbors are more likely to appear even by pure chance.
Isolated vertices will have zero similarity to any other vertex. Self-similarities are not calculated.
Note that the presence of loop edges may yield counter-intuitive
results. A node with a loop edge is considered to be a neighbor of itself
twice (because there are two edge stems incident on the node). Adding a
loop edge to a node may decrease its similarity to other nodes, but it may
also increase it. For instance, if nodes A and B are connected but share
no common neighbors, their similarity is zero. However, if a loop edge is
added to B, then B itself becomes a common neighbor of A and B and thus the
similarity of A and B will be increased. Consider removing loop edges
explicitly before invoking this function using igraph_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 in the graph, d is the (maximum) degree of the vertices in the graph.
Example 13.30. File examples/simple/igraph_similarity.c
#include <igraph.h> int main(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 connected then its minimum spanning forest is returned. This is the set of the minimum spanning trees of each component.
Directed graphs are considered as undirected for this computation.
This function is deterministic, i.e. it always returns the same
spanning tree. See igraph_random_spanning_tree() for the uniform
random 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| the number of edges in the graph.
See also:
|
Example 13.31. File examples/simple/igraph_minimum_spanning_tree.c
#include <igraph.h> int main(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 new
code; use igraph_minimum_spanning_tree()
instead.
If the graph has more minimum spanning trees (this is always the case, except if it is a forest) this implementation returns only the same one.
Directed graphs are considered as undirected for this computation.
If the graph is not connected then its minimum spanning forest is returned. This is the set of the minimum spanning trees of each component.
Arguments:
|
The graph object. Edge directions will be ignored. |
|
The minimum spanning tree, another graph object. Do
not initialize this object before passing it to
this function, but be sure to call |
Returns:
Error code:
|
Time complexity: O(|V|+|E|), |V| is the number of vertices, |E| the number of edges in the graph.
See also:
|
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 new
code; use igraph_minimum_spanning_tree()
instead.
Finds a spanning tree or spanning forest for which the sum of edge weights is the smallest. This function uses Prim's method for carrying out the computation.
Directed graphs are considered as undirected for this computation.
Reference:
Prim, R.C.: Shortest connection networks and some generalizations, Bell System Technical Journal, 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.
Do not initialize this object before passing it to
this function, but be sure to call |
|
A vector containing the weights of the edges in the same order as the simple edge iterator visits them (i.e. in increasing order of edge IDs). |
Returns:
Error code:
|
Time complexity: O(|E| log |V|), |V| is the number of vertices, |E| the number of edges in the graph.
See also:
|
Example 13.32. File examples/simple/igraph_minimum_spanning_tree.c
#include <igraph.h> int main(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 sample its spanning trees. Edge directions are ignored.
Multi-graphs are supported, and edge multiplicities will affect the sampling
frequency. For example, consider the 3-cycle graph 1=2-3-1, with two edges
between vertices 1 and 2. Due to these parallel edges, the trees 1-2-3
and 3-1-2 will be sampled with multiplicity 2, while the tree
2-3-1 will be sampled with multiplicity 1.
Arguments:
|
The input graph. Edge directions are ignored. |
|
An initialized vector, the IDs of the edges that constitute
a spanning tree will be returned here. Use
|
|
This parameter is relevant if the graph is not connected. If negative, a random spanning forest of all components will be generated. Otherwise, it should be the ID of a vertex. A random spanning tree of the component containing the vertex will be generated. |
Returns:
Error code. |
See also:
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 edges
are oriented away from a root (out-tree or arborescence) or all edges
are oriented towards a root (in-tree or anti-arborescence).
This test can be controlled using the mode parameter.
By convention, the null graph (i.e. the graph with no vertices) is considered not to be connected, and therefore not a tree.
Arguments:
|
The graph object to analyze. |
|
Pointer to a logical variable, the result will be stored here. |
|
If not |
|
For a directed graph this specifies whether to test for an
out-tree, an in-tree or ignore edge directions. The respective
possible values are:
|
Returns:
Error code:
|
Time complexity: At most O(|V|+|E|), the number of vertices plus the number of edges in the graph.
See also:
Example 13.33. File examples/simple/igraph_kary_tree.c
#include <igraph.h> int main(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 each
tree are oriented away from the root (out-trees or arborescences) or all edges
are oriented towards the root (in-trees or anti-arborescences).
This test can be controlled using the mode parameter.
By convention, the null graph (i.e. the graph with no vertices) is considered to be a forest.
The res return value of this function is cached in the graph itself if
mode is set to IGRAPH_ALL or if the graph is undirected. Calling the
function multiple times with no modifications to the graph in between
will return a cached value in O(1) time if the roots are not requested.
Arguments:
|
The graph object to analyze. |
|
Pointer to a logical 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|), the number of vertices plus the number of edges in the graph.
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 associated with a labelled tree. A tree on n >= 2 vertices can be represented by a sequence of n-2 integers, each between 0 and n-1 (inclusive).
Arguments:
|
Pointer to an initialized graph object which must be a tree on n >= 2 vertices. |
|
A pointer to the integer vector that should hold the Prüfer sequence; the vector must be initialized and will be resized to n - 2. |
Returns:
|
Error code:
|
See also:
igraph_transitivity_undirected — Calculates the transitivity (clustering coefficient) of a graph.igraph_transitivity_local_undirected — 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 a vertex are connected. More precisely, this is the ratio of the triangles and connected triples in the graph, the result is a single real number. Directed graphs are considered as undirected ones and multi-edges are ignored.
Note that this measure is different from the local transitivity measure
(see igraph_transitivity_local_undirected() ) as it calculates a single
value for the whole graph.
Clustering coefficient is an alternative name for transitivity.
References:
S. Wasserman and K. Faust: Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
Arguments:
|
The graph object. Edge directions and multiplicites are ignored. |
|
Pointer to a real variable, the result will be stored here. |
|
Defines how to treat graphs with no connected triples.
|
Returns:
Error code:
|
See also:
Time complexity: O(|V|*d^2), |V| is the number of vertices in the graph, d is the average node degree.
Example 13.34. File examples/simple/igraph_transitivity.c
#include <igraph.h> int main(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 a vertex are connected. In case of the local transitivity, this probability is calculated separately for each vertex.
Note that this measure is different from the global transitivity measure
(see igraph_transitivity_undirected() ) as it calculates a transitivity
value for each vertex individually.
Clustering coefficient is an alternative name for transitivity.
References:
D. J. Watts and S. Strogatz: Collective dynamics of small-world networks. Nature 393(6684):440-442 (1998).
Arguments:
|
The input graph. Edge directions and multiplicities are ignored. |
|
Pointer to an initialized vector, the result will be stored here. It will be resized as needed. |
|
Vertex set, the vertices for which the local transitivity will be calculated. |
|
Defines how to treat vertices with degree less than two.
|
Returns:
Error code. |
See also:
Time complexity: O(n*d^2), n is the number of vertices for which the transitivity is calculated, d is the average vertex degree.
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 a
vertex are connected. In case of the average local transitivity,
this probability is calculated for each vertex and then the average
is taken. Vertices with less than two neighbors require special treatment,
they will either be left out from the calculation or they will be considered
as having zero transitivity, depending on the mode argument.
Edge directions and edge multiplicities are ignored.
Note that this measure is different from the global transitivity measure
(see igraph_transitivity_undirected() ) as it simply takes the
average local transitivity across the whole network.
Clustering coefficient is an alternative name for transitivity.
References:
D. J. Watts and S. Strogatz: Collective dynamics of small-world networks. Nature 393(6684):440-442 (1998).
Arguments:
|
The input graph. Edge directions and multiplicites are ignored. |
|
Pointer to a real variable, the result will be stored here. |
|
Defines how to treat vertices with degree less than two.
|
Returns:
Error code. |
See also:
Time complexity: O(|V|*d^2), |V| is the number of vertices in the graph and d is the average degree.
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 a
given vertex i, from all triangles in which it participates we
consider the weight of the edges incident on i. The transitivity
is the sum of these weights divided by twice the strength of the
vertex (see igraph_strength()) and the degree of the vertex
minus one. See equation (5) in Alain Barrat, Marc Barthelemy, Romualdo
Pastor-Satorras, Alessandro Vespignani: The architecture of complex
weighted networks, Proc. Natl. Acad. Sci. USA 101, 3747 (2004) at
https://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 does not work for non-simple graphs. |
|
Pointer to an initialized vector, the result will be stored here. It will be resized as needed. |
|
The vertices for which the calculation is performed. |
|
Edge weights. If this is a null pointer, then a
warning is given and |
|
Defines how to treat vertices with zero strength.
|
Returns:
Error code. |
Time complexity: O(|V|*d^2), |V| is the number of vertices in the graph, d is the average node degree.
See also:
|
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 the major version of igraph. Use it at your own risk.
The edge clustering coefficient C^(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 could
participate 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
For k=3, s^(k)_ij = min(d_i - 1, d_j - 1),
where d_i and d_j are the edge endpoint degrees.
For k=4, s^(k)_ij = (d_i - 1) (d_j - 1).
The normalize and offset parameters allow for skipping normalization
by s^(k) and offsetting the cycle count z^(k)
by one in the numerator of C^(k). Set both to true to
compute 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 of
cycles 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: When k is 3, O(|V| d log d + |E| d).
When k 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 number of 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 number of edges.
Example 13.35. File examples/simple/igraph_to_undirected.c
#include <igraph.h> int main(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 matrix L of a graph is defined as
L_ij = - A_ij when i != j and
L_ii = d_i - A_ii. Here A denotes the (possibly weighted)
adjacency matrix and d_i is the degree (or strength, if weighted)
of vertex i. In directed graphs, the mode parameter controls whether to use
out- or in-degrees. Correspondingly, the rows or columns will sum to zero.
In undirected graphs, A_ii is taken to be twice the number
(or total weight) of self-loops, ensuring that d_i = \sum_j A_ij.
Thus, the Laplacian of an undirected graph is the same as the Laplacian
of a directed one obtained by replacing each undirected edge with two reciprocal
directed ones.
More compactly, L = D - A where the D is a diagonal matrix
containing the degrees. The Laplacian matrix can also be normalized, with several
conventional normalization methods. See igraph_laplacian_normalization_t for
the 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. File examples/simple/igraph_get_laplacian.c
#include <igraph.h> int main(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
);
See igraph_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. File examples/simple/igraph_get_laplacian_sparse.c
#include <igraph.h> int test_laplacian(const igraph_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; } int main(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 for igraph_get_laplacian() and
igraph_get_laplacian_sparse(). In the following, A refers to the
(possibly weighted) adjacency matrix and D is a diagonal matrix containing
degrees (unweighted case) or strengths (weighted case). Out-, in- or total degrees
are used according to the mode 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 and multiple edges.
Arguments:
|
The input graph. |
|
Pointer to a boolean constant, the result is stored here. |
Returns:
Error code. |
See also:
|
Time complexity: O(|V|+|E|).
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. File examples/simple/igraph_is_loop.c
#include <igraph.h> void analyze_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"); } int main(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; calling the function multiple times with no modifications to the graph in between will return a cached value in O(1) time.
Arguments:
|
The input graph. |
|
Pointer to an initialized boolean vector for storing the result. |
See also:
|
Time complexity: O(e), the number of edges to check.
Example 13.39. File examples/simple/igraph_is_loop.c
#include <igraph.h> void analyze_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"); } int main(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 the major 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. File examples/simple/igraph_is_loop.c
#include <igraph.h> void analyze_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"); } int main(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 another edge with the same head and tail vertices in the graph.
Note that this function returns true only for the second or more appearances of the multiple edges.
Arguments:
|
The input graph. |
|
Pointer to a boolean vector, the result will be stored here. It will be resized as needed. |
|
The edges to check. Supply |
Returns:
Error code. |
See also:
Time complexity: O(e*d), e is the number of edges to check and d is the average degree (out-degree in directed graphs) of the vertices at the tail of the edges.
Example 13.41. File examples/simple/igraph_is_multiple.c
#include <igraph.h> void print_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"); } int main(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 another edge with the same head and tail vertices in the graph.
The return value of this function is cached in the graph itself; calling the function multiple times with no modifications to the graph in between will 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 the average degree (out-degree in directed graphs) of the vertices at the tail of the edges.
Example 13.42. File examples/simple/igraph_has_multiple.c
#include <igraph.h> int main(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 other edge between the same two vertices. The multiplicity of an edge is 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 the average degree (out-degree in directed graphs) of the vertices at the tail 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_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_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 different categories, this function calculates the assortativity coefficient of the graph. The assortativity coefficient is between minus one and one and it is one if all connections stay within categories, it is minus one, if the network is perfectly disassortative. For a randomly connected network it is (asymptotically) zero.
The unnormalized version, computed when normalized is set to false,
is identical to the modularity, and is defined as follows for
directed networks:
1/m sum_ij (A_ij - k^out_i k^in_j / m) d(i,j),
where m denotes the number of edges, A_ij is the adjacency matrix,
k^out and k^in are the out- and in-degrees,
and d(i,j) is one if vertices i and j are in the same
category and zero otherwise.
The normalized assortativity coefficient is obtained by dividing the previous 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-reciprocal edges. 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, see M. 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 the number of vertex types.
See also:
|
Example 13.43. File examples/simple/igraph_assortativity_nominal.c
#include <igraph.h> #include <stdio.h> int main(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 a
graph based on given values x_i for each vertex i. This type of
assortativity coefficient equals the Pearson correlation of the values
at the two ends of the edges.
The unnormalized covariance of values, computed when normalized is
set 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,
where m denotes the number of edges, A_ij is the adjacency matrix, and
k^out and k^in are the out- and in-degrees.
x_out and x_in refer to the sets of vertex values at the start and end of
the directed edges.
The normalized covariance, i.e. Pearson correlation, is obtained by dividing
the previous expression by
sqrt(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 edges are reciprocal. Therefore, self-loops are effectively considered 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 III and equation (21) for the definition, and equation (26) for performing 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 undirected graphs with the degrees as values.
For an educational overview of the concept of assortativity, see M. 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 the graph.
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 at
the documentation of igraph_assortativity() for details.
This function simply calls igraph_assortativity() with
the degrees as the vertex values and normalization enabled.
In the directed case, it uses out-degrees as out-values and
in-degrees as in-values.
For regular graphs, i.e. graphs in which all vertices have the same 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| is the number of vertices.
See also:
|
Example 13.44. File examples/simple/igraph_assortativity_degree.c
#include <igraph.h> #include <stdio.h> int main(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_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 the major version of igraph. Use it at your own risk.
Computes the mixing matrix M_ij, i.e. the joint distribution of vertex types
at the endpoints directed of edges. Categories are represented by non-negative integer
indices, passed in from_types and to_types. The row and column counts of m
will be one larger than the largest source and target type, respectively. Re-index type
vectors using igraph_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 vertices
have types i and j.
When there is a single categorization of vertices, i.e. from_types and to_types
are the same, M_ij is related to the modularity (igraph_modularity()) and nominal
assortativity (igraph_assortativity_nominal()). Let a_i = sum_j M_ij and
b_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 the
partitioning 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, with
categories 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. |
|
The mixing matrix M_ij will be stored here. |
|
A vector containing the weights of the edges. If passing a
|
|
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 the major version of igraph. Use it at your own risk.
Computes the joint degree distribution P_ij of a graph, used in the
study of degree correlations. P_ij is the probability that a randomly
chosen ordered pair of connected vertices have degrees i and j.
In directed graphs, directionally connected u -> v pairs
are considered. The joint degree distribution of an undirected graph is the
same as that of the corresponding directed graph in which all connection are
bidirectional, assuming that from_mode is IGRAPH_OUT, to_mode is
IGRAPH_IN and directed_neighbors is true.
When normalized is false, sum_ij P_ij gives the total
number of connections in a directed graph, or twice that value in an
undirected graph. The sum is taken over ordered (i,j) degree
pairs.
The joint degree distribution relates to other concepts used in the study of
degree correlations. If P_ij is normalized then the degree correlation
function k_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),
where q_i = sum_k P_ik and r_j = sum_k P_kj.
Note that the joint degree distribution P_ij is similar, but not identical
to the joint degree matrix J_ij computed by igraph_joint_degree_matrix().
If the graph is undirected, then the diagonal entries of an unnormalized P_ij
are double that of J_ij, as any undirected connection between same-degree vertices
is counted in both directions. In contrast to igraph_joint_degree_matrix(),
this function returns matrices which include the row and column corresponding
to zero degrees. In directed graphs, this row and column is not necessarily
zero when from_mode is different from IGRAPH_OUT or to_mode is different
from IGRAPH_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 sources? 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 the major version of igraph. Use it at your own risk.
In graph theory, the joint degree matrix J_ij of a graph gives the number
of edges, or sum of edge weights, between vertices of degree i and degree
j. This function stores J_ij into jdm[i-1, j-1].
Each edge, including self-loops, is counted precisely once, both in undirected
and 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 unordered
pairs in directed and undirected graphs, respectively. Thus J_ij / m
is the probability that an edge chosen at random (with probability proportional
to its weight) connects vertices with degrees i and j.
Note that J_ij is similar, but not identical to the joint degree
distribution, computed by igraph_joint_degree_distribution(),
which is defined for ordered (i, j) degree
pairs even in the undirected case. When considering undirected graphs, the
diagonal of the joint degree distribution is twice that of the joint
degree 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_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 vertex has at least degree k. (Degree here means the degree in the subgraph of course.). The coreness of a vertex is the highest order of a k-core containing the vertex.
This function implements the algorithm presented in Vladimir Batagelj, Matjaz Zaversnik: An O(m) Algorithm for Cores Decomposition of Networks. 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 least k-2 triangles
in the subgraph. The trussness of an edge indicates the highest k-truss that
the edge occurs in.
This function returns the highest k for each edge. If you are interested in
a particular k-truss subgraph, you can subset the graph to those edges
which are >= k because each k-truss is a subgraph of a (k–1)-truss
Thus, to get all 4-trusses, take k >= 4 because the 5-trusses, 6-trusses,
etc. need to be included.
The current implementation of this function iteratively decrements support
of each edge using O(|E|) space and O(|E|^1.5) time. The implementation does
not support multigraphs; use igraph_simplify() to collapse edges before
calling 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 will indicate the highest k-truss each edge occurs in. It will be resized as needed. |
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; calling the function multiple times with no modifications to the graph in between will 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 of vertices 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 ordering of its vertices where each vertex comes before all nodes to which it has edges. Every DAG has at least one topological sort, and may have many. This function returns one possible topological sort among them. If the graph 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 of vertices and edges in the original input graph.
See also:
|
Example 13.45. File examples/simple/igraph_topological_sorting.c
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t graph; igraph_vector_int_t res; /* Test graph taken from http://en.wikipedia.org/wiki/Topological_sorting * @ 05.03.2006 */ igraph_small(&graph, 8, IGRAPH_DIRECTED, 0, 3, 0, 4, 1, 3, 2, 4, 2, 7, 3, 5, 3, 6, 3, 7, 4, 6, -1); igraph_vector_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 in minimum feedback arc sets, i.e. sets of edges whose total weight is the smallest among all the feedback arc sets.
For undirected graphs, the solution is simple: one has to find a maximum weight
spanning tree and then remove all the edges not in the spanning tree. For directed
graphs, this is an NP-complete problem, and various heuristics are usually used to
find an approximate solution to the problem. This function implements both exact
methods and heuristics, selectable with the algo 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.46. File examples/simple/igraph_feedback_arc_set.c
#include <igraph.h> #include <string.h> int main(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.47. File examples/simple/igraph_feedback_arc_set_ip.c
#include <igraph.h> #include <string.h> int main(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 on algo, 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 the major version of igraph. Use it at your own risk.
A feedback vertex set is a set of vertices whose removal makes the graph acyclic. Finding a minimum feedback vertex set is an NP-complete problem, 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 on algo, 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 rank alpha for each vertex, such that visiting
vertices in decreasing rank order corresponds to always choosing
the vertex with the most already visited neighbors as the next one
to visit.
Maximum cardinality search is useful in deciding the chordality of a graph. A graph is chordal if and only if any two neighbors of a vertex which are higher in rank than it are connected to each other.
References:
Robert E Tarjan and Mihalis Yannakakis: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal of Computation 13, 566--579, 1984. https://doi.org/10.1137/0213035
Arguments:
|
The input graph. Edge directions will be ignored. |
|
Pointer to an initialized vector, the result is stored here.
It will be resized, as needed. Upon return it contains
the rank of the each vertex in the range 0 to |
|
Pointer to an initialized vector or a |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in terms of the number of vertices and edges.
See also:
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 nodes
has a chord, i.e. an edge joining two nodes that are not
adjacent in the cycle. An equivalent definition is that any
chordless cycles have at most three nodes.
If either alpha or alpham1 is given, then the other is
calculated by taking simply the inverse. If neither are given,
then igraph_maximum_cardinality_search() is called to calculate
them.
Arguments:
|
The input graph. Edge directions will be ignored. |
|
Either an alpha vector coming from
|
|
Either an inverse alpha vector coming from |
|
Pointer to a boolean. If not NULL the result is stored here. |
|
Pointer to an initialized vector, or a |
|
Pointer to an uninitialized graph, or a |
Returns:
Error code. |
Time complexity: O(n).
See also:
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 length matches the number of vertices in the given graph, its values are between -1 (inclusive) and the number of vertices (exclusive), and whether there exists a corresponding edge in the graph for every matched vertex pair. For bipartite graphs, it also verifies whether the matched vertices are in different parts of the graph.
Arguments:
|
The input graph. It can be directed but the edge directions will be ignored. |
|
If the graph is bipartite and you are interested in bipartite
matchings only, pass the vertex types here. If the graph is
non-bipartite, simply pass |
|
The matching itself. It must be a vector where element i contains the ID of the vertex that vertex i is matched to, or -1 if vertex i is unmatched. |
|
Pointer to a boolean variable, the result will be returned here. |
See also:
|
Time complexity: O(|V|+|E|) where |V| is the number of vertices and |E| is the number of edges.
Example 13.48. File examples/simple/igraph_maximum_bipartite_matching.c
#include <igraph.h> #include <stdio.h> int main(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 a graph such that one of its neighbors is also unmatched.
Arguments:
|
The input graph. It can be directed but the edge directions will be ignored. |
|
If the graph is bipartite and you are interested in bipartite
matchings only, pass the vertex types here. If the graph is
non-bipartite, simply pass |
|
The matching itself. It must be a vector where element i contains the ID of the vertex that vertex i is matched to, or -1 if vertex i is unmatched. |
|
Pointer to a boolean variable, the result will be returned here. |
See also:
|
Time complexity: O(|V|+|E|) where |V| is the number of vertices and |E| is the number of edges.
Example 13.49. File examples/simple/igraph_maximum_bipartite_matching.c
#include <igraph.h> #include <stdio.h> int main(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 vertices of the first kind to vertices of the second kind such that each vertex of the first kind is matched to at most one vertex of the second kind and vice 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 with larger cardinality. For weighted graphs, a maximum matching is a matching whose edges have the largest possible total weight among all possible matchings.
Maximum matchings in bipartite graphs are found by the push-relabel algorithm with greedy initialization and a global relabeling after every n/2 steps where n 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 and unit-capacity flow algorithms. ACM Journal of Experimental Algorithmics 3, 1998.
Kaya K, Langguth J, Manne F and Ucar B: Experiments on push-relabel-based maximum cardinality matching algorithms for bipartite graphs. Technical Report TR/PA/11/33 of the Centre Europeen de Recherche et de Formation Avancee 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 the technical report referenced above), O(|V||E|) for weighted graphs.
Example 13.50. File examples/simple/igraph_maximum_bipartite_matching.c
#include <igraph.h> #include <stdio.h> int main(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 replicating vertices 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_avg_nearest_neighbor_degree — Average neighbor degree.igraph_degree_correlation_vector — Degree correlation function.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_is_acyclic — Checks whether a graph is acyclic or not.
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 its
edges and the largest possible number of edges it could have.
The maximum number of edges depends on interpretation: are vertices
allowed to have a connection to themselves? This is controlled by the
loops parameter.
Note that density is ill-defined for graphs which have multiple edges
between some pairs of vertices. Consider calling igraph_simplify()
on such graphs. This function does not check whether the graph has
parallel 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. |
|
Logical 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 the major version of igraph. Use it at your own risk.
This is a convenience function that computes the average of all vertex degrees. In directed graphs, the average of out-degrees and in-degrees is the same; this is the number that is returned. For the null graph, which has 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 of
mutual connections. It is most commonly defined as the probability that the
opposite counterpart of a randomly chosen directed edge is also included in
the 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 own
separate reciprocal edge, in accordance with the above formula. This measure
is calculated if the mode argument is IGRAPH_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 the
probability of having mutual connections between a vertex pair if we know
that there is a (possibly non-mutual) connection between them. In other
words, (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 group
sizes (2)+(3). This measure is calculated if mode is
IGRAPH_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.51. File examples/simple/igraph_reciprocity.c
#include <igraph.h> #include <math.h> int main(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 Rob Claxton: Network Diversity and Economic Development, Science 328, 1029--1031, 2010.
It is simply the (normalized) Shannon entropy of the
incident edges' weights.
D(i) = H(i) / log(k[i]),
and
H(i) = -sum(p[i,j] log(p[i,j]), j=1..k[i]),
where p[i,j] = w[i,j] / sum(w[i,l], l=1..k[i]),
k[i] is the (total) degree of vertex i,
and w[i,j] is the weight of the edge(s) between
vertex i and j. The diversity of isolated vertices will be NaN
(not-a-number), while that of vertices with a single connection
will 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 using igraph_simplify(). If the graph is directed, convert it into an undirected
graph with igraph_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 contains
the (B,A) edge too. Whether directed self-loops are considered mutual
is controlled by the loops 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 be mutual.
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, d is the maximum in-degree of the vertices that are targets of the supplied 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 contains
the (B,A) edge too. Whether directed self-loops are considered mutual
is controlled by the loops parameter.
In undirected graphs, all edges are considered mutual by definition. Thus for undirected graph, this function returns false only when there are no edges.
To check whether a graph is an oriented graph, use this function in
conjunction with igraph_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_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), and
optionally, the same quantity as a function of the vertex degree (knnk).
For isolated vertices knn is set to NaN. The same is done in knnk for
vertex 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,
where s_u = sum_v w_uv is the sum of the incident edge weights
of vertex u, i.e. its strength.
The sum runs over the neighbors v of vertex u
as indicated by mode. w_uv denotes the weighted adjacency matrix
and k_v is the neighbors' degree, specified by neighbor_degree_mode.
This is equation (6) in the reference below.
When only the k_nn(k) degree correlation function is needed,
igraph_degree_correlation_vector() can be used as well. This function provides
more 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.
|
|
The vertices for which the calculation is performed. |
|
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 and edges.
Example 13.52. File examples/simple/igraph_avg_nearest_neighbor_degree.c
#include <igraph.h> int main(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 the major version of igraph. Use it at your own risk.
Computes the degree correlation function k_nn(k), defined as the
mean degree of the targets of directed edges whose source has degree k.
The averaging is done over all directed edges. The from_mode and to_mode
parameters control how the source and target vertex degrees are computed.
This way the out-in, out-out, in-in and in-out degree correlation functions
can all be computed.
In undirected graphs, edges are treated as if they were a pair of reciprocal directed ones.
If P_ij is the joint degree distribution of the graph, computable with
igraph_joint_degree_distribution(), then
k_nn(k) = (sum_j j P_kj) / (sum_j P_kj).
The function igraph_avg_nearest_neighbor_degree(), whose main purpose is to
calculate the average neighbor degree for each vertex separately, can also compute
k_nn(k). It differs from this function in that it can take a subset
of vertices to base the calculation on, but it does not allow the same fine-grained
control 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_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 matrix contains the number of edges connecting vertex i to vertex j in the unweighted case, or the total weight of edges connecting vertex i to vertex j in the weighted 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 an initialized 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:
|
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 is its adjacency matrix, normalized row-wise or column-wise, such that the 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. |
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 is its adjacency matrix, normalized row-wise or column-wise, such that the sum of each row (or column) is one.
Arguments:
|
The input graph. |
|
Pointer to an initialized sparse matrix, the result is stored here. The matrix will be resized as needed. |
|
Whether to normalize column-wise. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number of vertices and edges.
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. |
|
Logical, 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_error_t igraph_is_acyclic(const igraph_t *graph, igraph_bool_t *res);
This function checks whether a graph is acyclic or not.
Arguments:
|
The input graph. |
|
Pointer to a boolean constant, the result is stored here. |
Returns:
Error code. |
See also:
|
Time complexity: O(|V|+|E|), where |V| and |E| are the number of vertices and edges in the original input 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 new
code; use igraph_are_adjacent()
instead.
Decides whether there are any edges that have v1 and v2
as endpoints. This function is of course symmetric for undirected
graphs.
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 of v1 and d2 is the (in-)degree of v2.
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 new
code; use igraph_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 new
code; use igraph_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 new
code; use igraph_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 new
code; use igraph_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 of igraph_get_stochastic_sparse(),
but does not work in an identical way. This function takes an uninitialized
igraph_sparsemat_t while igraph_get_stochastic_sparse() takes
an already initialized one.
Arguments:
|
The input graph. |
|
Pointer to an uninitialized 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 new
code; use igraph_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 of igraph_get_adjacency_sparse(),
but does not work in an identical way. This function takes an uninitialized
igraph_sparsemat_t while igraph_get_adjacency_sparse() takes
an already initialized one.
Arguments:
|
The input graph. |
|
Pointer to an uninitialized sparse matrix. The result will be stored here. |
Returns:
Error code. |
Deprecated since version 0.10.0. Please do not use this function in new
code; use igraph_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 or
sparse format. When normalized is set to true, the type of normalization
used depends on the directnedness of the graph: symmetric normalization
is used for undirected graphs and left stochastic normalization for
directed 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 new
code; use igraph_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 new
code; use igraph_hub_and_authority_scores()
instead.
The hub scores of the vertices are defined as the principal
eigenvector of A A^T, where A is the adjacency
matrix of the graph, A^T is its transposed.
See the following reference on the meaning of this score: J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
Arguments:
|
The input graph. Can be directed and undirected. |
|
Pointer to an initialized vector, the result is stored here. If a null pointer then it is ignored. |
|
If not a null pointer then the eigenvalue corresponding to the calculated eigenvector is stored here. |
|
If not zero then the result will be scaled such that the absolute value of the maximum centrality is one. |
|
A null pointer (=no edge weights), or a vector giving the weights of the edges. |
|
Options to ARPACK. See |
Returns:
Error code. |
Time complexity: depends on the input graph, usually it is O(|V|), the number of vertices.
See also:
|
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 new
code; use igraph_hub_and_authority_scores()
instead.
The authority scores of the vertices are defined as the principal
eigenvector of A^T A, where A is the adjacency
matrix of the graph, A^T is its transposed.
See the following reference on the meaning of this score: J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076, May 1997.
Arguments:
|
The input graph. Can be directed and undirected. |
|
Pointer to an initialized vector, the result is stored here. If a null pointer then it is ignored. |
|
If not a null pointer then the eigenvalue corresponding to the calculated eigenvector is stored here. |
|
If not zero then the result will be scaled such that the absolute value of the maximum centrality is one. |
|
A null pointer (=no edge weights), or a vector giving the weights of the edges. |
|
Options to ARPACK. See |
Returns:
Error code. |
Time complexity: depends on the input graph, usually it is O(|V|), the number of vertices.
See also:
|
| ← Chapter 12. Graph, vertex and edge attributes | Chapter 14. Graph cycles → |