Random Walk not working

[HekpoMaH]

First, some info:
pip freeze gives

absl-py==0.9.0
azure-common==1.1.24
azure-nspkg==3.0.2
azure-storage==0.36.0
beautifulsoup4==4.8.2
cachetools==4.0.0
certifi==2019.11.28
cffi==1.14.0
chardet==3.0.4
cryptography==2.8
cycler==0.10.0
decorator==4.4.1
docopt==0.6.2
dpu-utils==0.2.8
google==2.0.3
google-auth==1.11.2
google-auth-oauthlib==0.4.1
googledrivedownloader==0.4
grpcio==1.27.2
h5py==2.10.0
idna==2.8
imageio==2.6.1
isodate==0.6.0
joblib==0.14.1
kiwisolver==1.1.0
llvmlite==0.31.0
Markdown==3.2.1
matplotlib==3.1.3
more-itertools==8.2.0
networkx==2.4
numba==0.48.0
numpy==1.18.1
oauthlib==3.1.0
opt-einsum==3.1.0
overrides==2.8.0
pandas==1.0.1
Pillow==7.0.0
plyfile==0.7.1
protobuf==3.11.3
pyasn1==0.4.8
pyasn1-modules==0.2.8
pycparser==2.19
pyparsing==2.4.6
pyro-api==0.1.1
pyro-ppl==1.2.1
python-dateutil==2.8.1
pytz==2019.3
PyWavelets==1.1.1
rdflib==4.2.2
requests==2.22.0
requests-oauthlib==1.3.0
rsa==4.0
scikit-image==0.16.2
scikit-learn==0.22.1
scipy==1.4.1
seaborn==0.10.0
sentencepiece==0.1.85
SetSimilaritySearch==0.1.7
six==1.14.0
soupsieve==1.9.5
tensorboard==2.1.0
torch==1.4.0
torch-cluster==1.4.5
torch-geometric==1.4.1
torch-scatter==2.0.3
torch-sparse==0.5.1
tqdm==4.42.1
urllib3==1.25.8
Werkzeug==1.0.0

echo $PATH:
/home/dobrik/anaconda3/envs/geometric_new/bin:/usr/local/cuda-10.1/bin:/home/dobrik/anaconda3/bin:/home/dobrik/.local/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin

echo $CPATH:
/usr/local/cuda-10.1/include:

Tests are also passing:

========================================== test session starts ==========================================
platform linux -- Python 3.8.1, pytest-5.4.1, py-1.8.1, pluggy-0.13.1
rootdir: /home/dobrik/anaconda3/envs/geometric_new/lib/python3.8/site-packages/torch_cluster/pytorch_cluster, inifile: setup.cfg
plugins: cov-2.8.1
collected 77 items                                                                                      

test/test_fps.py ......
test/test_graclus.py ................
test/test_grid.py ................................
test/test_knn.py ........
test/test_nearest.py ....
test/test_radius.py ........
test/test_rw.py ..
test/test_sampler.py .

----------- coverage: platform linux, python 3.8.1-final-0 -----------
Name                        Stmts   Miss  Cover
-----------------------------------------------
torch_cluster/__init__.py      15      0   100%
torch_cluster/fps.py            2      0   100%
torch_cluster/graclus.py        2      0   100%
torch_cluster/grid.py           2      0   100%
torch_cluster/knn.py           40      0   100%
torch_cluster/nearest.py       23      0   100%
torch_cluster/radius.py        32      0   100%
torch_cluster/rw.py             3      0   100%
torch_cluster/sampler.py        1      0   100%
-----------------------------------------------
TOTAL                         120      0   100%


========================================== 77 passed in 3.12s ===========================================

However, the random walk does not 'respect' the adjacency matrix. A minimal example with a small bipartite undirected graph follows. I'm running the script on CPU, no CUDA involved (for now):

>>> rows
tensor([0, 1, 2, 1, 3, 4, 1, 2, 3, 3, 5, 5])
>>> cols
tensor([1, 2, 3, 3, 5, 5, 0, 1, 2, 1, 3, 4])
>>> torch_cluster.random_walk(rows, cols, torch.tensor(0), walk_length=3)
tensor([[0, 1, 3, 2]])
>>> torch_cluster.random_walk(rows, cols, torch.tensor(0), walk_length=3)
tensor([[0, 1, 3, 2]])
>>> torch_cluster.random_walk(rows, cols, torch.tensor(0), walk_length=3)
tensor([[0, 1, 2, 5]])
>>> torch_cluster.random_walk(rows, cols, torch.tensor(0), walk_length=3)
tensor([[0, 1, 3, 0]])

The last random walk is not valid. there is no edge between 3 and 0.

Am I misusing the API, by any chance?

[rusty1s]

random_walk expects sorted input, but that is not clear from the documentation. Sorry! You can pass coalesced=True to the random_walk function. I also changed the default argument to make this more intuitive.