Repository: dwavesystems/dwave-optimization (language: python)

Issue:
Consider adding `Any` symbol
We already support `ArraySymbol.all()`, so we should add its friend `ArraySymbol.any()`.


Discussion / hints:

Fix patch:
diff --git a/docs/reference/symbols.rst b/docs/reference/symbols.rst
index 0309f6c1..4613df8f 100644
--- a/docs/reference/symbols.rst
+++ b/docs/reference/symbols.rst
@@ -46,6 +46,7 @@ are inherited by the :ref:`model symbols <symbols_model_symbols>`.
     :toctree: generated/
 
     ~ArraySymbol.all
+    ~ArraySymbol.any
     ~ArraySymbol.has_state
     ~ArraySymbol.max
     ~ArraySymbol.maybe_equals
diff --git a/dwave/optimization/include/dwave-optimization/nodes/mathematical.hpp b/dwave/optimization/include/dwave-optimization/nodes/mathematical.hpp
index 2efea57f..0e88e135 100644
--- a/dwave/optimization/include/dwave-optimization/nodes/mathematical.hpp
+++ b/dwave/optimization/include/dwave-optimization/nodes/mathematical.hpp
@@ -283,6 +283,7 @@ class ReduceNode : public ScalarOutputMixin<ArrayNode> {
 // binary operations and reduce operations.
 // https://numpy.org/doc/stable/reference/routines.math.html
 using AllNode = ReduceNode<std::logical_and<double>>;
+using AnyNode = ReduceNode<std::logical_or<double>>;
 using MaxNode = ReduceNode<functional::max<double>>;
 using MinNode = ReduceNode<functional::min<double>>;
 using ProdNode = ReduceNode<std::multiplies<double>>;
diff --git a/dwave/optimization/libcpp/nodes.pxd b/dwave/optimization/libcpp/nodes.pxd
index f18414d3..8585cb15 100644
--- a/dwave/optimization/libcpp/nodes.pxd
+++ b/dwave/optimization/libcpp/nodes.pxd
@@ -98,6 +98,9 @@ cdef extern from "dwave-optimization/nodes/mathematical.hpp" namespace "dwave::o
     cdef cppclass AndNode(ArrayNode):
         pass
 
+    cdef cppclass AnyNode(ArrayNode):
+        pass
+
     cdef cppclass EqualNode(ArrayNode):
         pass
 
diff --git a/dwave/optimization/model.pyi b/dwave/optimization/model.pyi
index 802c7031..853431d2 100644
--- a/dwave/optimization/model.pyi
+++ b/dwave/optimization/model.pyi
@@ -172,6 +172,7 @@ class ArraySymbol(Symbol):
     def __pow__(self, exponent: int) -> ArraySymbol: ...
     def __sub__(self, rhs: ArraySymbol) -> Subtract: ...
     def all(self) -> All: ...
+    def any(self) -> Any: ...
     def max(self) -> Max: ...
     def min(self) -> Min: ...
     def ndim(self) -> int: ...
diff --git a/dwave/optimization/model.pyx b/dwave/optimization/model.pyx
index bfb37e0f..c2e4847c 100644
--- a/dwave/optimization/model.pyx
+++ b/dwave/optimization/model.pyx
@@ -1848,6 +1848,16 @@ cdef class ArraySymbol(Symbol):
         from dwave.optimization.symbols import All  # avoid circular import
         return All(self)
 
+    def any(self):
+        """Create an :class:`~dwave.optimization.symbols.Any` symbol.
+
+        The new symbol returns True when any elements evaluate to True.
+
+        .. versionadded:: 0.4.1
+        """
+        from dwave.optimization.symbols import Any  # avoid circular import
+        return Any(self)
+
     def max(self):
         """Create a :class:`~dwave.optimization.symbols.Max` symbol.
 
diff --git a/dwave/optimization/src/nodes/mathematical.cpp b/dwave/optimization/src/nodes/mathematical.cpp
index 19366426..9ac31831 100644
--- a/dwave/optimization/src/nodes/mathematical.cpp
+++ b/dwave/optimization/src/nodes/mathematical.cpp
@@ -1014,6 +1014,19 @@ struct ExtraData<std::logical_and<double>> {
     ssize_t old_num_zero = num_zero;
 };
 
+template<>
+struct ExtraData<std::logical_or<double>> {
+    explicit ExtraData(ssize_t num_nonzero) : num_nonzero(num_nonzero) {}
+
+    virtual ~ExtraData() = default;
+
+    void commit() { old_num_nonzero = num_nonzero; }
+    void revert() { num_nonzero = old_num_nonzero; }
+
+    ssize_t num_nonzero;  // num nonzero, following SciPy's naming
+    ssize_t old_num_nonzero = num_nonzero;
+};
+
 template <>
 struct ExtraData<std::multiplies<double>> {
     ExtraData(double nonzero, ssize_t num_zero) : nonzero(nonzero), num_zero(num_zero) {}
@@ -1072,6 +1085,9 @@ ReduceNode<BinaryOp>::ReduceNode(ArrayNode* node_ptr, double init)
 template <>
 ReduceNode<std::logical_and<double>>::ReduceNode(ArrayNode* array_ptr) : ReduceNode(array_ptr, 1) {}
 
+template <>
+ReduceNode<std::logical_or<double>>::ReduceNode(ArrayNode* array_ptr) : ReduceNode(array_ptr, 0) {}
+
 template <>
 ReduceNode<std::multiplies<double>>::ReduceNode(ArrayNode* array_ptr) : ReduceNode(array_ptr, 1) {}
 
@@ -1129,13 +1145,25 @@ void ReduceNode<std::logical_and<double>>::initialize_state(State& state) const
 
     ssize_t num_zero = init.value_or(1) ? 0 : 1;
     for (const double& value : array_ptr_->view(state)) {
-        if (value == 0) num_zero += 1;
+        num_zero += !value;
     }
 
-    double value = num_zero == 0;
+    state[index] = std::make_unique<ReduceNodeData<op>>(!num_zero, num_zero);
+}
 
-    // and then create the state
-    state[index] = std::make_unique<ReduceNodeData<op>>(value, num_zero);
+template <>
+void ReduceNode<std::logical_or<double>>::initialize_state(State& state) const {
+    int index = topological_index();
+    assert(index >= 0 && "must be topologically sorted");
+    assert(static_cast<int>(state.size()) > index && "unexpected state length");
+    assert(state[index] == nullptr && "already initialized state");
+
+    ssize_t num_nonzero = init.value_or(1) ? 1 : 0;
+    for (const double& value : array_ptr_->view(state)) {
+        num_nonzero += static_cast<bool>(value);
+    }
+
+    state[index] = std::make_unique<ReduceNodeData<op>>(num_nonzero > 0, num_nonzero);
 }
 
 template <>
@@ -1371,30 +1399,63 @@ void ReduceNode<std::logical_and<double>>::propagate(State& state) const {
 
     // count the change in the num_zero
     for (const Update& update : array_ptr_->diff(state)) {
-        if (update.placed() && update.value == 0) {
-            // added a zero
-            num_zero += 1;
-        } else if (update.placed()) {
-            assert(update.value != 0);
-        } else if (update.removed() && update.old == 0) {
-            // removed a 0
-            num_zero -= 1;
+        const auto& [_, old, value] = update;
+
+        if (update.placed()) {
+            // added a value to the array
+            num_zero += !value;
         } else if (update.removed()) {
-            assert(update.old != 0);
-        } else if (update.old == 0 && update.value == 0) {
-            // changed a 0 to a 0, nothing to do
-        } else if (update.old == 0) {
-            // changed a 0 to something else
+            // removed a value from the array
+            num_zero -= !old;
+        } else if (!old && value) {
+            // changed a 0 to a truthy value
             num_zero -= 1;
-        } else if (update.value == 0) {
-            // changed something else to a 0
+        } else if (old && !value) {
+            // changed a truthy value to a 0
             num_zero += 1;
         } else {
-            // something else to something else so no change
+            // otherwise we don't care because the net number of 0s hasn't changed
+            assert(static_cast<bool>(old) == static_cast<bool>(value));
+        }
+    }
+
+    assert(num_zero >= 0);  // should never go negative
+
+    ptr->values.value = num_zero < 1;
+    if (ptr->values.value != ptr->values.old) Node::propagate(state);
+}
+
+template <>
+void ReduceNode<std::logical_or<double>>::propagate(State& state) const {
+    auto ptr = data_ptr<ReduceNodeData<op>>(state);
+
+    ssize_t& num_nonzero = ptr->extra.num_nonzero;
+
+    // count the change in the num_nonzero
+    for (const Update& update : array_ptr_->diff(state)) {
+        const auto& [_, old, value] = update;
+
+        if (update.placed()) {
+            // added a value to the array
+            num_nonzero += static_cast<bool>(value);
+        } else if (update.removed()) {
+            // removed a value from the array
+            num_nonzero -= static_cast<bool>(old);
+        } else if (!old && value) {
+            // changed a 0 to a truthy value
+            num_nonzero += 1;
+        } else if (old && !value) {
+            // changed a truthy value to a 0
+            num_nonzero -= 1;
+        } else {
+            // otherwise we don't care because the net number of 0s hasn't changed
+            assert(static_cast<bool>(old) == static_cast<bool>(value));
         }
     }
 
-    ptr->values.value = num_zero > 0 ? 0 : 1;
+    assert(num_nonzero >= 0);  // should never go negative
+
+    ptr->values.value = num_nonzero > 0;
     if (ptr->values.value != ptr->values.old) Node::propagate(state);
 }
 
@@ -1561,6 +1622,7 @@ void ReduceNode<BinaryOp>::revert(State& state) const {
 template class ReduceNode<functional::max<double>>;
 template class ReduceNode<functional::min<double>>;
 template class ReduceNode<std::logical_and<double>>;
+template class ReduceNode<std::logical_or<double>>;
 template class ReduceNode<std::multiplies<double>>;
 template class ReduceNode<std::plus<double>>;
 
diff --git a/dwave/optimization/symbols.pyi b/dwave/optimization/symbols.pyi
index 3152d170..ffc8ac90 100644
--- a/dwave/optimization/symbols.pyi
+++ b/dwave/optimization/symbols.pyi
@@ -35,6 +35,10 @@ class And(ArraySymbol):
     ...
 
 
+class Any(ArraySymbol):
+    ...
+
+
 class AdvancedIndexing(ArraySymbol):
     ...
 
diff --git a/dwave/optimization/symbols.pyx b/dwave/optimization/symbols.pyx
index faf04661..4de30e39 100644
--- a/dwave/optimization/symbols.pyx
+++ b/dwave/optimization/symbols.pyx
@@ -47,6 +47,7 @@ from dwave.optimization.libcpp.nodes cimport (
     AddNode as cppAddNode,
     AllNode as cppAllNode,
     AndNode as cppAndNode,
+    AnyNode as cppAnyNode,
     AdvancedIndexingNode as cppAdvancedIndexingNode,
     ArrayValidationNode as cppArrayValidationNode,
     BasicIndexingNode as cppBasicIndexingNode,
@@ -95,6 +96,7 @@ __all__ = [
     "Add",
     "All",
     "And",
+    "Any",
     "AdvancedIndexing",
     "BasicIndexing",
     "BinaryVariable",
@@ -342,6 +344,47 @@ cdef class And(ArraySymbol):
 _register(And, typeid(cppAndNode))
 
 
+cdef class Any(ArraySymbol):
+    """Tests whether any elements evaluate to True.
+
+    Examples:
+        This example checks the elements of a binary array.
+
+        >>> from dwave.optimization.model import Model
+        >>> model = Model()
+        >>> model.states.resize(1)
+        >>> x = model.constant([True, False, False])
+        >>> a = x.any()
+        >>> with model.lock():
+        ...     assert a.state()
+
+        >>> y = model.constant([False, False, False])
+        >>> b = y.any()
+        >>> with model.lock():
+        ...     assert not b.state()
+
+    .. versionadded:: 0.4.1
+    """
+    def __init__(self, ArraySymbol array):
+        cdef Model model = array.model
+        self.ptr = model._graph.emplace_node[cppAnyNode](array.array_ptr)
+        self.initialize_arraynode(model, self.ptr)
+
+    @staticmethod
+    def _from_symbol(Symbol symbol):
+        cdef cppAnyNode* ptr = dynamic_cast_ptr[cppAnyNode](symbol.node_ptr)
+        if not ptr:
+            raise TypeError("given symbol cannot be used to construct a Any")
+        cdef Any s = Any.__new__(Any)
+        s.ptr = ptr
+        s.initialize_arraynode(symbol.model, ptr)
+        return s
+
+    cdef cppAnyNode* ptr
+
+_register(Any, typeid(cppAnyNode))
+
+
 cdef class _ArrayValidation(Symbol):
     def __init__(self, ArraySymbol array_node):
         cdef Model model = array_node.model
diff --git a/releasenotes/notes/any-symbol-4c6fdcd16a56e0aa.yaml b/releasenotes/notes/any-symbol-4c6fdcd16a56e0aa.yaml
new file mode 100644
index 00000000..8a6d6237
--- /dev/null
+++ b/releasenotes/notes/any-symbol-4c6fdcd16a56e0aa.yaml
@@ -0,0 +1,4 @@
+---
+features:
+  - Add C++ ``AnyNode``. See `#148 <https://github.com/dwavesystems/dwave-optimization/issues/148>`_.
+  - Add ``Any`` symbol and ``ArraySymbol.any()`` method. See `#148 <https://github.com/dwavesystems/dwave-optimization/issues/148>`_.


Test patch:
diff --git a/tests/cpp/nodes/mathematical/test_reduce.cpp b/tests/cpp/nodes/mathematical/test_reduce.cpp
index f30c1cb2..b33a74ff 100644
--- a/tests/cpp/nodes/mathematical/test_reduce.cpp
+++ b/tests/cpp/nodes/mathematical/test_reduce.cpp
@@ -193,8 +193,10 @@ TEST_CASE("PartialReduceNode - PartialSumNode") {
     }
 }
 
-TEMPLATE_TEST_CASE("ReduceNode", "", functional::max<double>, functional::min<double>,
-                   std::logical_and<double>, std::multiplies<double>, std::plus<double>) {
+TEMPLATE_TEST_CASE("ReduceNode", "",
+                   functional::max<double>, functional::min<double>,
+                   std::logical_and<double>, std::logical_or<double>,
+                   std::multiplies<double>, std::plus<double>) {
     auto graph = Graph();
 
     auto func = TestType();
@@ -355,6 +357,93 @@ TEMPLATE_TEST_CASE("ReduceNode", "", functional::max<double>, functional::min<do
     }
 }
 
+TEST_CASE("ReduceNode - AllNode/AnyNode") {
+    auto graph = Graph();
+
+    GIVEN("x = BinaryNode({5}), y = x.any()") {
+        auto x_ptr = graph.emplace_node<BinaryNode>(std::vector<ssize_t>{5});
+        auto y_ptr = graph.emplace_node<AllNode>(x_ptr);
+        auto z_ptr = graph.emplace_node<AnyNode>(x_ptr);
+
+        graph.emplace_node<ArrayValidationNode>(y_ptr);
+        graph.emplace_node<ArrayValidationNode>(z_ptr);
+
+        THEN("y,z are logical and scalar") {
+            CHECK(y_ptr->logical());
+            CHECK(y_ptr->ndim() == 0);
+            CHECK(z_ptr->logical());
+            CHECK(z_ptr->ndim() == 0);
+        }
+
+        WHEN("x == [0, 0, 0, 0, 0]") {
+            auto state = graph.empty_state();
+            x_ptr->initialize_state(state, {0, 0, 0, 0, 0});
+            graph.initialize_state(state);
+
+            THEN("y is false and z is false") {
+                CHECK(std::ranges::equal(y_ptr->view(state), std::vector{false}));
+                CHECK(std::ranges::equal(z_ptr->view(state), std::vector{false}));
+            }
+
+            AND_WHEN("x is updated to [0, 0, 1, 0, 0]") {
+                x_ptr->set_value(state, 2, 1);
+                graph.propagate(state, {x_ptr, y_ptr, z_ptr});
+
+                THEN("y is false and z is true") {
+                    CHECK(std::ranges::equal(y_ptr->view(state), std::vector{false}));
+                    CHECK(std::ranges::equal(z_ptr->view(state), std::vector{true}));
+                }
+
+                graph.commit(state, {x_ptr, y_ptr, z_ptr});
+
+                AND_WHEN("x is updated to [0, 0, 0, 0, 0]") {
+                    x_ptr->set_value(state, 2, 0);
+                    graph.propagate(state, {x_ptr, y_ptr, z_ptr});
+
+                    THEN("y is false and z is false") {
+                        CHECK(std::ranges::equal(y_ptr->view(state), std::vector{false}));
+                        CHECK(std::ranges::equal(z_ptr->view(state), std::vector{false}));
+                    }
+                }
+            }
+        }
+
+        WHEN("x == [0, 0, 1, 0, 0]") {
+            auto state = graph.empty_state();
+            x_ptr->initialize_state(state, {0, 0, 1, 0, 0});
+            graph.initialize_state(state);
+
+            THEN("y is false and z is true") {
+                CHECK(std::ranges::equal(y_ptr->view(state), std::vector{false}));
+                CHECK(std::ranges::equal(z_ptr->view(state), std::vector{true}));
+            }
+        }
+    }
+
+    GIVEN("x = [], y = x.all(), z = x.any()") {
+        auto x_ptr = graph.emplace_node<BinaryNode>(std::vector<ssize_t>{0});
+        auto y_ptr = graph.emplace_node<AllNode>(x_ptr);
+        auto z_ptr = graph.emplace_node<AnyNode>(x_ptr);
+
+        graph.emplace_node<ArrayValidationNode>(y_ptr);
+        graph.emplace_node<ArrayValidationNode>(z_ptr);
+
+        THEN("y,z are logical and scalar") {
+            CHECK(y_ptr->logical());
+            CHECK(y_ptr->ndim() == 0);
+            CHECK(z_ptr->logical());
+            CHECK(z_ptr->ndim() == 0);
+        }
+
+        auto state = graph.initialize_state();
+
+        THEN("y and not z") {
+            CHECK(std::ranges::equal(y_ptr->view(state), std::vector{true}));
+            CHECK(std::ranges::equal(z_ptr->view(state), std::vector{false}));
+        }
+    }
+}
+
 TEST_CASE("ReduceNode - MaxNode/MinNode") {
     auto graph = Graph();
 
diff --git a/tests/test_symbols.py b/tests/test_symbols.py
index ae9a98de..5a079570 100644
--- a/tests/test_symbols.py
+++ b/tests/test_symbols.py
@@ -413,11 +413,12 @@ class TestAll(utils.SymbolTests):
     def generate_symbols(self):
         model = Model()
         nodes = [
-            model.constant(0),
-            model.constant(1),
-            model.constant([0, 0]),
-            model.constant([0, 1]),
-            model.constant([1, 1]),
+            model.constant(0).all(),
+            model.constant(1).all(),
+            model.constant([]).all(),
+            model.constant([0, 0]).all(),
+            model.constant([0, 1]).all(),
+            model.constant([1, 1]).all(),
         ]
 
         model.lock()
@@ -511,6 +512,61 @@ def test_scalar_and(self):
             x = a.logical_and(b)
 
 
+class TestAny(utils.SymbolTests):
+    def generate_symbols(self):
+        model = Model()
+        nodes = [
+            model.constant(0).any(),
+            model.constant(1).any(),
+            model.constant([]).any(),
+            model.constant([0, 0]).any(),
+            model.constant([0, 1]).any(),
+            model.constant([1, 1]).any(),
+        ]
+
+        model.lock()
+        yield from nodes
+
+    def test_empty(self):
+        model = Model()
+        empty = model.constant([]).any()
+        model.lock()
+        model.states.resize(1)
+
+        self.assertFalse(empty.state())
+        self.assertEqual(empty.state(), np.asarray([]).any())  # confirm consistency with NumPy
+
+    def test_scalar(self):
+        model = Model()
+        model.states.resize(1)
+
+        for val in [0, .0001, 1, 7]:
+            with self.subTest(f"[{val}].all()"):
+                symbol = model.constant([val]).any()
+                model.lock()
+                np.testing.assert_array_equal(symbol.state(0), bool(val))
+                model.unlock()
+
+            with self.subTest(f"({val}).all()"):
+                symbol = model.constant(val).any()
+                model.lock()
+                np.testing.assert_array_equal(symbol.state(0), bool(val))
+                model.unlock()
+
+        for arr in [np.zeros(5), np.ones(5), np.asarray([0, 1])]:
+            with self.subTest(f"[{arr}].all()"):
+                symbol = model.constant([arr]).any()
+                model.lock()
+                np.testing.assert_array_equal(symbol.state(0), arr.any())
+                model.unlock()
+
+            with self.subTest(f"{val}.all()"):
+                symbol = model.constant(arr).any()
+                model.lock()
+                np.testing.assert_array_equal(symbol.state(0), arr.any())
+                model.unlock()
+
+
 class TestArrayValidation(utils.SymbolTests):
     def generate_symbols(self):
         model = Model()