Module adjlist 

Adjacency and incidence lists (igraph_adjlist.h).

Many algorithms visit the neighbors of every vertex over and over again (shortest paths from all sources, closeness, triangle counting, rewiring, …). For them it pays off to extract the graph once into a list of vectors, one per vertex, and work on that. igraph offers four such structures, all wrapped here as owned Rust types that free their memory on Drop:

Rust type	C type	contents of list v	built
AdjList	igraph_adjlist_t	neighbor vertex ids of v	eagerly, all vertices
IncList	igraph_inclist_t	incident edge ids of v	eagerly, all vertices
LazyAdjList	igraph_lazy_adjlist_t	neighbor vertex ids of v	on first access of v
LazyIncList	igraph_lazy_inclist_t	incident edge ids of v	on first access of v

AdjList and IncList are independent of the graph after creation: the graph may be modified or dropped, and the lists may be freely edited (each entry is a VectorInt, so it can grow and shrink) without affecting the graph. This makes them the ideal scratch representation for heavy structural edits: extract with Graph::adjlist_init, edit the lists in O(1) or O(d) per operation, then rebuild a graph with AdjList::to_graph (igraph_adjlist), paying O(|V|+|E|) only once.

The lazy variants instead borrow the graph (the borrow checker enforces that the graph outlives them and is not mutated meanwhile) and query the neighbors of a vertex only the first time it is asked for, caching the result. They are handy for algorithms that may visit only a small part of a large graph.

Rusty access

• al[v] gives the neighbors of vertex v as a &[i64] slice (Index), al[v][i] = x edits in place (IndexMut);
• AdjList::get_mut gives the underlying VectorInt to push, pop, sort or resize a list;
• AdjList::iter / for list in &al iterate over the lists;
• AdjList::to_vecs and Vec::<Vec<i64>>::from(al) convert to nested vectors, and AdjList::from(vec![...]) / .collect() build one from Rust data;
• Display prints one line per vertex, exactly like igraph’s igraph_adjlist_print.

Collapsing multi-edges

With multiple = false, Graph::adjlist_init and Graph::lazy_adjlist_init list each neighbor once. In igraph 1.0.0 and 1.0.1 this is buggy when neighbors are gathered in both directions (mode All, or undirected graphs): mutual pairs u -> w, w -> u and single self-loops are mistaken for multi-edges, which corrupts the graph’s cached Graph::has_multiple answer, and the lists themselves depend on that cache. These wrappers collapse such lists on the Rust side instead, so the result always matches Graph::neighbors_with and the cache stays correct.

Example

use igraph::prelude::*;
use igraph::adjlist::AdjList;

// A directed triangle 0 -> 1 -> 2 -> 0 with an extra edge 0 -> 2.
let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 0), (0, 2)], 3, true).unwrap();

let out = g.adjlist_init(NeighborMode::Out, Loops::Twice, true).unwrap();
assert_eq!(out.len(), 3);
assert_eq!(&out[0], &[1, 2]);
assert_eq!(out.to_vecs(), vec![vec![1, 2], vec![2], vec![0]]);

// Incoming neighbors, then the edge ids incident to each vertex.
let inc = g.adjlist_init(NeighborMode::In, Loops::Twice, true).unwrap();
assert_eq!(&inc[2], &[0, 1]);
let il = g.inclist_init(NeighborMode::Out, Loops::Twice).unwrap();
assert_eq!(&il[0], &[0, 3]);

// Edit the adjacency list and turn it back into a graph: drop 2 -> 0.
let mut al: AdjList = out.clone();
al.get_mut(2).unwrap().clear();
al.get_mut(0).unwrap().push(0); // and add a self-loop on 0
let h = al.to_graph(NeighborMode::Out, false).unwrap();
assert_eq!(h.ecount(), 4);
assert_eq!(h.neighbors(0, NeighborMode::Out).unwrap(), vec![0, 1, 2]);

// Lazy lists query the graph only when asked to.
let mut lazy = g.lazy_adjlist_init(NeighborMode::All, Loops::Twice, false).unwrap();
assert!(!lazy.has(0));
assert_eq!(lazy.get(0).unwrap(), &[1, 2]);
assert!(lazy.has(0));

// Zachary's karate club: the handshake lemma, and the two hubs.
let karate = Graph::famous("Zachary").unwrap();
let al = karate.adjlist_init(NeighborMode::All, Loops::Twice, true).unwrap();
assert_eq!(al.total_len(), 2 * karate.ecount());
assert_eq!((al[0].len(), al[33].len()), (16, 17));

Functions of igraph_adjlist.h

C function	Rust
igraph_adjlist_init	Graph::adjlist_init, AdjList::new
igraph_adjlist_init_empty	AdjList::init_empty
igraph_adjlist_init_complementer	Graph::adjlist_init_complementer, AdjList::complementer
igraph_adjlist_init_from_inclist	Graph::adjlist_init_from_inclist, AdjList::from_inclist
igraph_adjlist_destroy	Drop
igraph_adjlist_size	AdjList::len
igraph_adjlist_clear	AdjList::clear
igraph_adjlist_sort	AdjList::sort
igraph_adjlist_simplify	AdjList::simplify
igraph_adjlist_print / _fprint	AdjList::print, AdjList::fprint, Display
igraph_adjlist_has_edge	AdjList::has_edge
igraph_adjlist_replace_edge	AdjList::replace_edge
igraph_adjlist_get (macro)	Index, AdjList::get, AdjList::get_mut
igraph_adjlist	Graph::adjlist, AdjList::to_graph
igraph_inclist_init	Graph::inclist_init, IncList::new
igraph_inclist_init_empty	IncList::init_empty
igraph_inclist_destroy	Drop
igraph_inclist_size	IncList::len
igraph_inclist_clear	IncList::clear
igraph_inclist_print / _fprint	IncList::print, IncList::fprint, Display
igraph_inclist_get (macro)	Index, IncList::get, IncList::get_mut
igraph_lazy_adjlist_init	Graph::lazy_adjlist_init, LazyAdjList::new
igraph_lazy_adjlist_destroy	Drop
igraph_lazy_adjlist_clear	LazyAdjList::clear
igraph_lazy_adjlist_size	LazyAdjList::len
igraph_lazy_adjlist_has (macro)	LazyAdjList::has
igraph_lazy_adjlist_get (macro)	LazyAdjList::get, LazyAdjList::get_mut
igraph_lazy_inclist_init	Graph::lazy_inclist_init, LazyIncList::new
igraph_lazy_inclist_destroy	Drop
igraph_lazy_inclist_clear	LazyIncList::clear
igraph_lazy_inclist_size	LazyIncList::len
igraph_lazy_inclist_has (macro)	LazyIncList::has
igraph_lazy_inclist_get (macro)	LazyIncList::get, LazyIncList::get_mut

See also

• Graph::neighbors_with and Graph::incident query a single vertex directly on the graph, without building a whole list;
• Graph::get_adjacency gives the dense adjacency matrix and Graph::adjacency builds a graph from one, the matrix counterparts of Graph::adjlist_init and Graph::adjlist;
• Graph::complementer and Graph::simplify (operators) are the whole-graph counterparts of Graph::adjlist_init_complementer and AdjList::simplify;
• Graph::rewire implements degree-preserving rewiring on top of AdjList::has_edge / AdjList::replace_edge;
• Graph::bfs_simple and the other traversals of visitor walk the graph for you.

The igraph C documentation of adjacency lists describes the underlying structures.

Structs

Iter

Iterator over the per-vertex lists of an AdjList or IncList, yielding each list as a slice (returned by AdjList::iter and IncList::iter).

LazyAdjList

Lazy adjacency list (igraph_lazy_adjlist_t) borrowing a graph: the neighbors of each vertex are queried on first access and cached.

LazyIncList

Lazy incidence list (igraph_lazy_inclist_t) borrowing a graph: the incident edges of each vertex are queried on first access and cached.

Type Aliases

AdjList

Owned adjacency list (igraph_adjlist_t): for each vertex, a vector of its neighbor vertex ids. See the module docs.

IncList

Owned incidence list (igraph_inclist_t): for each vertex, a vector of the ids of its incident edges. See the module docs.