Implementation:Scikit learn Scikit learn GraphUtils

Knowledge Sources	Scikit_learn Scikit-learn Docs
Domains	Machine Learning, Graph Algorithms
Last Updated	2026-02-08 15:00 GMT

Overview

Concrete tool for providing graph utilities and algorithms for path analysis and connected components, provided by scikit-learn.

Description

The sklearn.utils.graph module provides graph utility functions used internally by scikit-learn. It includes single_source_shortest_path_length for computing shortest path lengths from a source node using BFS (adapted from NetworkX), and _fix_connected_components for adding connections to sparse graphs to ensure a single connected component by connecting closest pairs of samples between unconnected components.

Usage

Use these graph utilities when working with graph-based algorithms in scikit-learn, such as spectral clustering, Isomap, or other methods that require connected graphs or shortest path computations.

Code Reference

Source Location

• Repository: scikit-learn
• File: sklearn/utils/graph.py

Signature

@validate_params(...)
def single_source_shortest_path_length(graph, source, *, cutoff=None):

def _fix_connected_components(
    X, graph, n_connected_components, component_labels,
    mode="distance", metric="euclidean", **kwargs,
):

Import

from sklearn.utils.graph import single_source_shortest_path_length

I/O Contract

Inputs

Name	Type	Required	Description
graph	array-like or sparse matrix of shape (n_nodes, n_nodes)	Yes	Adjacency matrix of the graph
source	int	Yes	Start node for path computation
cutoff	int or None	No	Maximum depth for BFS search (default None means no limit)

Outputs

Name	Type	Description
paths	dict	Reachable end nodes mapped to path length from source: {end: path_length}

Usage Examples

Basic Usage

from sklearn.utils.graph import single_source_shortest_path_length
import numpy as np

graph = np.array([
    [0, 1, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 0],
])
paths = single_source_shortest_path_length(graph, 0)
print(paths)  # {0: 0, 1: 1, 2: 2}

Related Pages

• Principle:Scikit_learn_Scikit_learn_Clustering