NeighborList Filters and SANN

[tommy-waltmann]

Description

This PR adds a new concept in freud, the NeighborList filter, and the SANN neighbor finding method implemented as a neighborlist filter. The SANN method finds neighbors based on solid angle occupied by each neighbor up to a total of 4pi. For more information, see https://aip.scitation.org/doi/10.1063/1.4729313

I have also added a method for sorting a NeighborList by either distance or point_index to the python API. It was needed for the SANN method implementation and I think it has general utility as well.

Motivation and Context

This is a useful way of finding neighbors, which was not previously available in freud.

How Has This Been Tested?

Tests have been added in test_locality_Filter.py. I would like to see some validation of the calculation on a real system before this PR can be merged.

Types of changes

• Bug fix (non-breaking change which fixes an issue)
• New feature (non-breaking change which adds or improves functionality)
• Breaking change (fix or feature that would cause existing functionality to change)
• Documentation improvement (updates to user guides, docstrings, or developer docs)

Checklist:

• I have read the CONTRIBUTING document.
• My code follows the code style of this project.
• I have updated the documentation (if relevant).
• I have added tests that cover my changes (if relevant).
• All new and existing tests passed.
• I have updated the credits.
• I have updated the Changelog.

[vyasr]

Originally the implementation that Simon, Bradley and I considered was based on iteratively performing ball queries until a sufficient number of neighbors was found to complete the sphere. I'm on board with the current approach of filtering, which circumvents some of the implementation complexity associated with that iterative procedure by pushing the burden of having an effective starting point onto the user, but I think we probably should help out users a bit more than we are now. In that vein, a few points:

• I don't think the all_pairs implementation is necessary, but since you've already added it I don't mind it being present either.
• I'm happy to see that the warning was added, but I am not sure if it is strict enough. Should the SANN calculation even be considered valid if not enough neighbors are present? I'm inclined to include an additional parameter allow_incomplete_shell = False that would control whether insufficient neighbors is considered a warning or an error, and default to error. Admittedly I am not the most familiar with SANN, so I don't know whether a warning or an error is a more appropriate default (or whether it is important enough to make such a change).
• What I think would be the most helpful is to add two new examples to our documentation:
  1. If a user is seeing the warning about too few neighbors, what is the best way to fix it? Manually increasing the thresholds and crossing your fingers is one option, but would be crucial to show IMO is an example of a Python script that iteratively runs ball queries until the threshold is large enough, then filters the final resulting NeighborList. I suspect that many users will end up doing something like this anyway, so we may as well codify a best practice here (along with strong warnings that users should make good informed choices for the initial r_min).
  2. In the case where there simply aren't enough neighbors in the system, show how replicate_system could be used. This case seems like it shouldn't occur too often in realistically sized systems, so I don't think it's critical.

[joaander]

2. In the case where there simply aren't enough neighbors in the system, show how replicate_system could be used. This case seems like it shouldn't occur too often in realistically sized systems, so I don't think it's critical.

Indeed. Users should use replication in small N, high density systems. For low density systems of any N, users should not use SANN at all. I presented that possibility above as a pathological case to demonstrate that is is not feasible to find a complete SANN list for any arbitrary system the user might provide, even with massive numbers of system replicates and using all pairs.

One could probably formulate a rule of thumb for the search radius needed in terms of the mean free path.

[tommy-waltmann]

I am on board with adding an extra argument as @vyasr suggested, and I think an error should be the default behavior. If we are going to have an iterative procedure for finding a good choice of query parameters, it will be necessary to have the ability to generate an error in FilterSANN to know when to try a different set of parameters.

I think the best iterative procedure would be a binary search with either r_max or num_neighbors, calling FilterSANN on each iteration and seeing if it fails or not. Using knowledge of the system, a user could probably make a good guess as to what the initial upper and lower bounds of the binary search should be so the iterative method converges quicker.

[tommy-waltmann]

I have added the code to raise an error if there are unfilled neighbor shells. I cannot, however, figure out how to get the error message to format properly when the exception is raised. Here is an example of what the user sees right now when the exception is raised:

test_locality_Filter.py::TestSANN::test_SANN_simple Fatal Python error: Aborted

Current thread 0x0000000112f59e00 (most recent call first):
  File "/Users/tomwalt/code/freud/tests/test_locality_Filter.py", line 137 in test_SANN_simple
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/python.py", line 195 in pytest_pyfunc_call
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_callers.py", line 39 in _multicall
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_manager.py", line 80 in _hookexec
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_hooks.py", line 265 in __call__
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/python.py", line 1789 in runtest
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/runner.py", line 167 in pytest_runtest_call
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_callers.py", line 39 in _multicall
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_manager.py", line 80 in _hookexec
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_hooks.py", line 265 in __call__
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/runner.py", line 260 in <lambda>
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/runner.py", line 339 in from_call
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/runner.py", line 259 in call_runtest_hook
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/runner.py", line 220 in call_and_report
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/runner.py", line 131 in runtestprotocol
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/runner.py", line 112 in pytest_runtest_protocol
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_callers.py", line 39 in _multicall
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_manager.py", line 80 in _hookexec
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_hooks.py", line 265 in __call__
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/main.py", line 349 in pytest_runtestloop
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_callers.py", line 39 in _multicall
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_manager.py", line 80 in _hookexec
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_hooks.py", line 265 in __call__
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/main.py", line 324 in _main
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/main.py", line 270 in wrap_session
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/main.py", line 317 in pytest_cmdline_main
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_callers.py", line 39 in _multicall
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_manager.py", line 80 in _hookexec
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/pluggy/_hooks.py", line 265 in __call__
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/config/__init__.py", line 167 in main
  File "/Users/tomwalt/miniconda3/lib/python3.9/site-packages/_pytest/config/__init__.py", line 190 in console_main
  File "/Users/tomwalt/miniconda3/bin/pytest", line 10 in <module>
Abort trap: 6
(base) tomwalt@cheme-blyleven ~/code/freud/tests $

Does anyone know how to get exceptions from C++ to format nicely in python output?

[joaander]

pybind11 translates c++ exceptions to Python ones :)

[vyasr]

Cython also translates C++ exceptions to Python ones :) All that you should need is the except + after the cdef extern of the compute method, which I see that you do have, so I'm not sure what's going on. Let me try to repro locally.

[vyasr]

@tommy-waltmann I cannot reproduce that traceback locally. If I set allow_incomplete_shells=False I get a Python exception as expected. I would try wiping your build directory, it is possible that in an earlier iteration of the code you did not have the except + in the pxd file. Cython is not great at regenerating certain parts of the code when all that changes is a declaration in a pxd, so perhaps your build was a bit stale for some reason and it didn't pick up on the exception handling.

[tommy-waltmann]

Do @b-butler or anyone else have more comments on this PR?

[b-butler]

Given the large discussion is another opinion warranted you think @tommy-waltmann?

[tommy-waltmann]

Given the large discussion is another opinion warranted you think @tommy-waltmann?

Just making sure everyone who is tagged for review gets a chance to provide their opinion.