Repository: scikit-learn/scikit-learn
Pull request: FIX take into account mask in the ordering in grid_to_graph
<!--
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!
-->


Problem statement:
sklearn.feature_extraction.grid_to_graph may reorder vertices

#### Describe the bug
In grid_to_graph, you expect the vertices  to correspond to the implicit order defined by the mask. This is not always the case, due to the occurrence of isolated vertices that are dismissed in the reindexing of the vertices.

#### Steps/Code to Reproduce

```python
import numpy as np
from sklearn.feature_extraction import grid_to_graph

mask = np.zeros((2, 3)).astype('bool')
mask[0, 0] = 1
mask[0, 2] = 1
mask[1, 2] = 1
print(grid_to_graph(2, 3, 1, mask.ravel()).todense())
```

#### Expected Results
[[1 0 0]
 [0 1 1]
 [0 1 1]]

#### Actual Results
[[1 1 0]
 [1 1 0]
 [0 0 1]]

#### Versions
System:
   machine: Linux-4.4.0-187-generic-x86_64-with-Ubuntu-16.04-xenial
    python: 3.5.2 (default, Oct  7 2020, 17:19:02)  [GCC 5.4.0 20160609]
executable: /usr/bin/python3

BLAS:
  lib_dirs: /usr/lib
    macros: HAVE_CBLAS=None
cblas_libs: openblas, openblas

Python deps:
     scipy: 1.1.0
    Cython: 0.29
       pip: 18.1
    pandas: 0.23.4
   sklearn: 0.22.dev0
setuptools: 40.4.3
     numpy: 1.15.4


<!-- Thanks for contributing! -->

Hints from issue discussion:
Hello, I'm new in contributing, is this open and does it need help ?
Hi @CryoFantom 
#18964 is taking care of it, it mostly needs a review.
Hi, Can I contribute to it , Is this open?

If you can review #18964...
Best,
B
@bthirion I am trying to figure out the issue here (I am not too familiar with graphs and the functionality). I would expect the following information regarding the vertices. It would give the current output. Could you give more details on what I should look at to spot what is wrong?

```
[[(0,0)-(0,0), (0,0)-(0,2), (0,0)-(1,2)],
 [(0,2)-(0,0), (0,2)-(0,2), (0,2)-(1,2)],
 [(1,2)-(0,0), (1,2)-(0,2), (1,2)-(1,2)]]
```
Oh sorry, I misread the title of the section "Actual results" and "Expected results". So I get the issue.
I will review the PR then :)
Hey, is this issue still open?

Commit message: removed np.bool

Patch to review:
diff --git a/doc/whats_new/v1.0.rst b/doc/whats_new/v1.0.rst
index 6a565b8d5e21b..17aee986ad1ba 100644
--- a/doc/whats_new/v1.0.rst
+++ b/doc/whats_new/v1.0.rst
@@ -45,6 +45,7 @@ Changelog
     :pr:`123456` by :user:`Joe Bloggs <joeongithub>`.
     where 123456 is the *pull request* number, not the issue number.
 
+
 :mod:`sklearn.cluster`
 ......................
 
@@ -200,6 +201,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`_.
+
+
 Code and Documentation Contributors
 -----------------------------------
 
diff --git a/sklearn/feature_extraction/image.py b/sklearn/feature_extraction/image.py
index 5cd692fd6aa4f..9c7b64205ed68 100644
--- a/sklearn/feature_extraction/image.py
+++ b/sklearn/feature_extraction/image.py
@@ -77,7 +77,8 @@ 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.unique(np.where(mask.ravel())),
+                            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 712eb840c63e2..0218da142e3ad 100644
--- a/sklearn/feature_extraction/tests/test_image.py
+++ b/sklearn/feature_extraction/tests/test_image.py
@@ -26,6 +26,21 @@ def test_img_to_graph():
                                   grad_y.data[grad_y.data > 0])
 
 
+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
@@ -39,6 +54,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)


Code review comments:
diff_hunk: @@ -77,7 +77,8 @@ 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.unique(np.where(mask.ravel())),
+                            np.arange(maxval + 1))
path: sklearn/feature_extraction/image.py
text: @user1:
```suggestion
    order = np.searchsorted(np.flatnonzero(mask), np.arange(maxval + 1))
```
More readable and probably faster.