Module structural 

Basic structural properties of graphs (igraph_structural.h).

This module binds the functions declared in igraph’s igraph_structural.h header, as further methods of Graph. They answer the everyday questions one asks about a network:

• how big and how dense is it? (density, mean_degree, maxdegree, strength);
• is it a simple graph? (loops, multi-edges and mutual edges);
• what kind of graph is it? (tree, forest, acyclic, complete, chordal, perfect; cliques and independent sets);
• how are degrees correlated? (average nearest neighbor degree, k_nn(k), rich-club density sequence);
• which spanning trees does it have? (minimum and uniformly random);
• what does its Laplacian look like? (dense and sparse).

Example

use igraph::prelude::*;

// A 5-cycle with a chord, plus a pendant vertex.
let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2), (4, 5)], 6, false)?;
assert_eq!(g.mean_degree(true)?, 14.0 / 6.0);
assert_eq!(g.maxdegree(.., NeighborMode::All, Loops::Twice)?, 3);
assert!((g.density(None, false)? - 7.0 / 15.0).abs() < 1e-12);
assert!(g.is_simple(true)?);
assert_eq!(g.girth()?, Some(3));
assert!(!g.is_tree(NeighborMode::All)?);
assert!(g.is_clique(&[0, 1, 2], false)?);
assert!(g.is_independent_vertex_set(&[1, 3, 5])?);

// A spanning tree of a connected graph has n - 1 edges.
let mst = g.minimum_spanning_tree(None, MstAlgorithm::Automatic)?;
assert_eq!(mst.len(), 5);

// Zachary's karate club: 34 members, 78 friendships, and the two leaders
// (vertices 0 and 33) are the best connected members.
let karate = Graph::famous("Zachary")?;
assert_eq!(karate.maxdegree(.., NeighborMode::All, Loops::Twice)?, 17);
let hubs = karate.sort_vertex_ids_by_degree(.., NeighborMode::All, Loops::Twice, Order::Descending, false)?;
assert_eq!(&hubs[..2], &[33, 0]);

Provided functionality

Topic	Methods of Graph
Adjacency	are_adjacent, subcomponent
Density and degrees	density, mean_degree, maxdegree, strength, sort_vertex_ids_by_degree, diversity
Loops and multi-edges	has_loop, count_loops, is_loop, has_multiple, is_multiple, count_multiple, count_multiple_1, is_simple
Reciprocity	reciprocity, is_mutual, has_mutual
Graph classes	is_tree, tree_root, is_forest, forest_roots, is_acyclic, is_complete, is_perfect, is_chordal, is_chordal_with, maximum_cardinality_search
Vertex sets	is_clique, is_independent_vertex_set
Cycles	girth, girth_with_cycle
Spanning trees	minimum_spanning_tree, random_spanning_tree, unfold_tree
Degree correlations	avg_nearest_neighbor_degree, degree_correlation_vector, rich_club_sequence
Spectral	get_laplacian, get_laplacian_sparse, get_laplacian_sparsemat, LaplacianNormalization

All the functions of the header are covered.

See also

• Degrees and neighbors: Graph::degree, Graph::neighbors (core); removing loops and multi-edges: Graph::simplify (operators).
• Connectivity: Graph::connected_components, Graph::is_connected, Graph::count_reachable (components).
• Cycles and DAGs: Graph::find_cycle, Graph::minimum_cycle_basis, Graph::is_dag, Graph::topological_sorting (cycles).
• Cliques, independent sets and colorings: Graph::largest_cliques, Graph::clique_number, Graph::independence_number, Graph::vertex_coloring_greedy (cliques).
• Degree correlations as a single number: Graph::assortativity_degree, Graph::joint_degree_matrix (mixing).
• Matrices of a graph: Graph::get_adjacency, Graph::get_adjacency_sparse (conversion); spectra of the Laplacian with lapack_dsyevr and Graph::laplacian_spectral_embedding (linalg).
• Trees: Graph::kary_tree (constructors), Graph::tree_game (games), Graph::to_prufer (conversion), Graph::bfs (visitor).

Notes on igraph 1.0.0 and 1.0.1

A few wrappers work around behaviours of the C library that are present in both igraph 1.0.0 and 1.0.1 (the source files involved are unchanged in 1.0.1), so that the Rust API is consistent and memory safe:

• count_multiple_1 validates the edge id and reports an undirected self-loop once, like count_multiple;
• get_laplacian_sparse (and get_laplacian_sparsemat) ignore edge directions with NeighborMode::All, like the dense get_laplacian;
• is_chordal_with checks that the given vertex orders are permutations (igraph only checks their lengths);
• diversity recomputes the value of degree-one vertices, which igraph derives from the weight of edge 0 instead of the vertex’s own edge.

One wrapper differs from the C calling convention on purpose: random_spanning_tree spells igraph’s documented “negative vertex id means all components” as None, and rejects negative ids instead of silently spanning all components.

Structs

CardinalitySearch

Result of Graph::maximum_cardinality_search.

Chordality

Result of Graph::is_chordal_with.

NeighborDegree

Result of Graph::avg_nearest_neighbor_degree.

UnfoldedTree

Result of Graph::unfold_tree.

Enums

LaplacianNormalization

Normalization of the Laplacian matrix (igraph_laplacian_normalization_t), used by Graph::get_laplacian, Graph::get_laplacian_sparse and Graph::get_laplacian_sparsemat.