Struct Graph 

pub struct Graph<T> { /* private fields */ }

A simple undirected weighted graph stored as a sparse adjacency matrix.

The input is interpreted as undirected: whenever you add an edge (u, v) with u != v, we store it in both adjacency entries (u, v) and (v, u). Self-loops (u, u) are stored once as (u, u).

The Graph exposes two common “edge size” metrics that differ in meaning:

• edge_entry_count: counts adjacency entries (non-zero matrix entries in the upper-triangular part of the matrix, i.e. we count each undirected edge once).
• total_edge_weight: sums the weight values associated with those entries.

This distinction is important when edges can carry weights: many algorithms (and our quality metrics) need the total weight, not just the number of adjacency entries.

In particular, when we build an aggregated graph during Leiden (WeightedPartitionedGraph::aggregate), each “node” represents a set of original nodes (a community at the current level) and each adjacency weight represents the sum of weights of all original edges between the two sets. Therefore, edge_entry_count tells you only how many distinct neighbor-community pairs exist, while total_edge_weight preserves how strongly communities are connected.

Implementations

impl<T: EdgeWeight> Graph<T>

pub fn from_edges<I>(edges: I, num_nodes: NodeIdx) -> Self

where I: Iterator<Item = Edge<T>>,

pub fn from_adjacency_matrix(adjacency_matrix: CsMat<T>) -> Self

pub fn get_adjacency_matrix(&self) -> &CsMat<T>

pub fn get_num_nodes(&self) -> usize

pub fn get_edge_entry_count(&self) -> usize

Returns the number of undirected adjacency entries in the graph.

Each undirected edge contributes one entry (src <= dest), and self loops also contribute one entry.

pub fn get_total_edge_weight(&self) -> usize

Returns the sum of all undirected edge weights in the graph.

The sum is taken over the same set of undirected adjacency entries as Self::get_edge_entry_count (upper triangle src <= dest, including diagonal/self-loops).

For unweighted graphs where every edge has weight 1, this equals Self::get_edge_entry_count.

pub fn get_edge_weight(&self, src: NodeIdx, dst: NodeIdx) -> Option<T>

pub fn get_norm(&self) -> f64

pub fn get_degrees(&self) -> &Vec<usize>

pub fn neighbors(&self, node: NodeIdx) -> Vec<NodeIdx>

Returns a list of nodes connected to node. This does not include node even when it is connected to itself.

pub fn neighbors_iter( &self, node: NodeIdx, ) -> impl Iterator<Item = NodeIdx> + '_

Returns an iterator over node indices connected to node (excluding node itself).

This is the allocation-free counterpart of Self::neighbors, intended for tight loops.

pub fn get_edges_from(&self, node: NodeIdx) -> Vec<Edge<T>>

Returns a list of edge connected to node, including self edges looping back

pub fn edges_from_iter( &self, node: NodeIdx, ) -> impl Iterator<Item = Edge<T>> + '_

Returns an iterator over edges incident to node (including self-loops).

This is the allocation-free counterpart of Self::get_edges_from, intended for tight loops.

pub fn get_edges_iter(&self) -> impl Iterator<Item = Edge<T>>

Iterate over all edges of the graph

NB: this will iterate over edges in both directions

pub fn get_edges_in_selection( &self, selection: &HashSet<NodeIdx>, ) -> impl Iterator<Item = Edge<T>>

Get all edges where at least one of the nodes is in the selection Note that this will include edges that go outside the selection, and edges that loop back to the same node. Every egde will only be included once, i.e. (0,1) and (1,0) will not both be included as (0,1). The edges will be returned in arbitrary order.

pub fn connected_components(&self) -> impl Iterator<Item = HashSet<NodeIdx>>

Returns connected components of the graph

pub fn connected_components_by<F>( &self, filter: F, ) -> impl Iterator<Item = HashSet<NodeIdx>>

where F: Fn(NodeIdx, NodeIdx) -> bool,

Returns connected components where nodes in each components fulfill the filter criteria.

This criteria must be transitive, ie. filter(a, b) ∧ filter(b, c) ⇒ filter(a, c)

Trait Implementations

impl<T: Clone> Clone for Graph<T>

fn clone(&self) -> Graph<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl From<Graph<u8>> for Graph<usize>

fn from(graph: Graph<u8>) -> Graph<usize>

Converts to this type from the input type.