Aluode/PerceptionLabPortable

1"""Graph utilities and algorithms."""
2
3# Authors: The scikit-learn developers
4# SPDX-License-Identifier: BSD-3-Clause
5
6import numpy as np
7from scipy import sparse
8
9from ..metrics.pairwise import pairwise_distances
10from ._param_validation import Integral, Interval, validate_params
11
12
13###############################################################################
14# Path and connected component analysis.
15# Code adapted from networkx
16@validate_params(
17    {
18        "graph": ["array-like", "sparse matrix"],
19        "source": [Interval(Integral, 0, None, closed="left")],
20        "cutoff": [Interval(Integral, 0, None, closed="left"), None],
21    },
22    prefer_skip_nested_validation=True,
23)
24def single_source_shortest_path_length(graph, source, *, cutoff=None):
25    """Return the length of the shortest path from source to all reachable nodes.
26
27    Parameters
28    ----------
29    graph : {array-like, sparse matrix} of shape (n_nodes, n_nodes)
30        Adjacency matrix of the graph. Sparse matrix of format LIL is
31        preferred.
32
33    source : int
34       Start node for path.
35
36    cutoff : int, default=None
37        Depth to stop the search - only paths of length <= cutoff are returned.
38
39    Returns
40    -------
41    paths : dict
42        Reachable end nodes mapped to length of path from source,
43        i.e. `{end: path_length}`.
44
45    Examples
46    --------
47    >>> from sklearn.utils.graph import single_source_shortest_path_length
48    >>> import numpy as np
49    >>> graph = np.array([[ 0, 1, 0, 0],
50    ...                   [ 1, 0, 1, 0],
51    ...                   [ 0, 1, 0, 0],
52    ...                   [ 0, 0, 0, 0]])
53    >>> single_source_shortest_path_length(graph, 0)
54    {0: 0, 1: 1, 2: 2}
55    >>> graph = np.ones((6, 6))
56    >>> sorted(single_source_shortest_path_length(graph, 2).items())
57    [(0, 1), (1, 1), (2, 0), (3, 1), (4, 1), (5, 1)]
58    """
59    if sparse.issparse(graph):
60        graph = graph.tolil()
61    else:
62        graph = sparse.lil_matrix(graph)
63    seen = {}  # level (number of hops) when seen in BFS
64    level = 0  # the current level
65    next_level = [source]  # dict of nodes to check at next level
66    while next_level:
67        this_level = next_level  # advance to next level
68        next_level = set()  # and start a new list (fringe)
69        for v in this_level:
70            if v not in seen:
71                seen[v] = level  # set the level of vertex v
72                next_level.update(graph.rows[v])
73        if cutoff is not None and cutoff <= level:
74            break
75        level += 1
76    return seen  # return all path lengths as dictionary
77
78
79def _fix_connected_components(
80    X,
81    graph,
82    n_connected_components,
83    component_labels,
84    mode="distance",
85    metric="euclidean",
86    **kwargs,
87):
88    """Add connections to sparse graph to connect unconnected components.
89
90    For each pair of unconnected components, compute all pairwise distances
91    from one component to the other, and add a connection on the closest pair
92    of samples. This is a hacky way to get a graph with a single connected
93    component, which is necessary for example to compute a shortest path
94    between all pairs of samples in the graph.
95
96    Parameters
97    ----------
98    X : array of shape (n_samples, n_features) or (n_samples, n_samples)
99        Features to compute the pairwise distances. If `metric =
100        "precomputed"`, X is the matrix of pairwise distances.
101
102    graph : sparse matrix of shape (n_samples, n_samples)
103        Graph of connection between samples.
104
105    n_connected_components : int
106        Number of connected components, as computed by
107        `scipy.sparse.csgraph.connected_components`.
108
109    component_labels : array of shape (n_samples)
110        Labels of connected components, as computed by
111        `scipy.sparse.csgraph.connected_components`.
112
113    mode : {'connectivity', 'distance'}, default='distance'
114        Type of graph matrix: 'connectivity' corresponds to the connectivity
115        matrix with ones and zeros, and 'distance' corresponds to the distances
116        between neighbors according to the given metric.
117
118    metric : str
119        Metric used in `sklearn.metrics.pairwise.pairwise_distances`.
120
121    kwargs : kwargs
122        Keyword arguments passed to
123        `sklearn.metrics.pairwise.pairwise_distances`.
124
125    Returns
126    -------
127    graph : sparse matrix of shape (n_samples, n_samples)
128        Graph of connection between samples, with a single connected component.
129    """
130    if metric == "precomputed" and sparse.issparse(X):
131        raise RuntimeError(
132            "_fix_connected_components with metric='precomputed' requires the "
133            "full distance matrix in X, and does not work with a sparse "
134            "neighbors graph."
135        )
136
137    for i in range(n_connected_components):
138        idx_i = np.flatnonzero(component_labels == i)
139        Xi = X[idx_i]
140        for j in range(i):
141            idx_j = np.flatnonzero(component_labels == j)
142            Xj = X[idx_j]
143
144            if metric == "precomputed":
145                D = X[np.ix_(idx_i, idx_j)]
146            else:
147                D = pairwise_distances(Xi, Xj, metric=metric, **kwargs)
148
149            ii, jj = np.unravel_index(D.argmin(axis=None), D.shape)
150            if mode == "connectivity":
151                graph[idx_i[ii], idx_j[jj]] = 1
152                graph[idx_j[jj], idx_i[ii]] = 1
153            elif mode == "distance":
154                graph[idx_i[ii], idx_j[jj]] = D[ii, jj]
155                graph[idx_j[jj], idx_i[ii]] = D[ii, jj]
156            else:
157                raise ValueError(
158                    "Unknown mode=%r, should be one of ['connectivity', 'distance']."
159                    % mode
160                )
161
162    return graph
163