FIX take into account mask in the ordering in grid_to_graph
diff --git a/doc/whats_new/v1.0.rst b/doc/whats_new/v1.0.rst
index 7d8175a3b5046..d9f63cc62add4 100644
--- a/doc/whats_new/v1.0.rst
+++ b/doc/whats_new/v1.0.rst
@@ -156,6 +156,7 @@ Changelog
   as `base_estimator` in ::class:`calibration.CalibratedClassifierCV`.
   :pr:`20087` by :user:`Clément Fauchereau <clement-f>`.
 
+
 :mod:`sklearn.cluster`
 ......................
 
@@ -764,6 +765,14 @@ Changelog
   for non-English characters. :pr:`18959` by :user:`Zero <Zeroto521>`
   and :user:`wstates <wstates>`.
 
+
+:mod:`sklearn.feature_extraction`
+..................................
+
+- |Fix| Fixed a bug in :func:`image._to_graph` where singleton
+    connected components were not handled properly, resulting in a wrong
+    vertex indexing.  :pr:`18964` by `Bertrand Thirion`_.
+
 - |Fix| Fixed a bug in :class:`tree.DecisionTreeClassifier`,
   :class:`tree.DecisionTreeRegressor` where a node could be split whereas it
   should not have been due to incorrect handling of rounding errors.
diff --git a/sklearn/feature_extraction/image.py b/sklearn/feature_extraction/image.py
index 154ec8701210d..7d71a2b5f2e32 100644
--- a/sklearn/feature_extraction/image.py
+++ b/sklearn/feature_extraction/image.py
@@ -82,7 +82,7 @@ def _mask_edges_weights(mask, edges, weights=None):
         maxval = edges.max()
     else:
         maxval = 0
-    order = np.searchsorted(np.unique(edges.ravel()), np.arange(maxval + 1))
+    order = np.searchsorted(np.flatnonzero(mask), np.arange(maxval + 1))
     edges = order[edges]
     if weights is None:
         return edges
diff --git a/sklearn/feature_extraction/tests/test_image.py b/sklearn/feature_extraction/tests/test_image.py
index 706d040637767..989d6bd2265b8 100644
--- a/sklearn/feature_extraction/tests/test_image.py
+++ b/sklearn/feature_extraction/tests/test_image.py
@@ -32,6 +32,21 @@ def test_img_to_graph():
     )
 
 
+def test_img_to_graph_sparse():
+    # Check that the edges are in the right position
+    #  when using a sparse image with a singleton component
+    mask = np.zeros((2, 3), dtype=bool)
+    mask[0, 0] = 1
+    mask[:, 2] = 1
+    x = np.zeros((2, 3))
+    x[0, 0] = 1
+    x[0, 2] = -1
+    x[1, 2] = -2
+    grad_x = img_to_graph(x, mask=mask).todense()
+    desired = np.array([[1, 0, 0], [0, -1, 1], [0, 1, -2]])
+    np.testing.assert_array_equal(grad_x, desired)
+
+
 def test_grid_to_graph():
     # Checking that the function works with graphs containing no edges
     size = 2
@@ -45,6 +60,14 @@ def test_grid_to_graph():
     A = grid_to_graph(n_x=size, n_y=size, mask=mask, return_as=np.ndarray)
     assert connected_components(A)[0] == 2
 
+    # check ordering
+    mask = np.zeros((2, 3), dtype=bool)
+    mask[0, 0] = 1
+    mask[:, 2] = 1
+    graph = grid_to_graph(2, 3, 1, mask=mask.ravel()).todense()
+    desired = np.array([[1, 0, 0], [0, 1, 1], [0, 1, 1]])
+    np.testing.assert_array_equal(graph, desired)
+
     # Checking that the function works whatever the type of mask is
     mask = np.ones((size, size), dtype=np.int16)
     A = grid_to_graph(n_x=size, n_y=size, n_z=size, mask=mask)

<!--
Thanks for contributing a pull request! Please ensure you have taken a look at
the contribution guidelines: https://github.com/scikit-learn/scikit-learn/blob/master/CONTRIBUTING.md#pull-request-checklist
-->

#### Reference Issues/PRs
Fixes #18963


#### What does this implement/fix? Explain your changes.
In `grid_to_graph` , index the vertices according to mask structure, not their occurrence in edge matrix.

#### Any other comments?


<!--
Please be aware that we are a loose team of volunteers so patience is
necessary; assistance handling other issues is very welcome. We value
all user contributions, no matter how minor they are. If we are slow to
review, either the pull request needs some benchmarking, tinkering,
convincing, etc. or more likely the reviewers are simply busy. In either
case, we ask for your understanding during the review process.
For more information, see our FAQ on this topic:
http://scikit-learn.org/dev/faq.html#why-is-my-pull-request-not-getting-any-attention.

Thanks for contributing!
-->
