Repository: dgasmith/opt_einsum

Issue:
Bug: Dynamic_programming path solver may return illegal contraction path
Tested on GitHub master HEAD.

```python
oem.paths.dynamic_programming([{0,1}, {}], {0, 1}, {0:2, 1:2})
[(1,), (0, 1)] # sth. wrong here
oem.paths.greedy([{0,1}, {}], {0, 1}, {0:2, 1:2})
[(0, 1)] # other solvers return correct result
```

Though such tensor contraction case is weird and a very corner case, it indeed can occur in https://github.com/google/TensorNetwork/blob/master/tensornetwork/quantum/quantum.py

Discussion:
codecov[bot]: # [Codecov](https://codecov.io/gh/dgasmith/opt_einsum/pull/174?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniel+Smith) Report
> Merging [#174](https://codecov.io/gh/dgasmith/opt_einsum/pull/174?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniel+Smith) (ae6fb35) into [master](https://codecov.io/gh/dgasmith/opt_einsum/commit/be2d3dcb9792016d3b7ed0afacfed70024698c9e?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Daniel+Smith) (be2d3dc) will **decrease** coverage by `7.04%`.
> The diff coverage is `100.00%`.



Patch:
diff --git a/README.md b/README.md
index 6cff408..98f5d16 100644
--- a/README.md
+++ b/README.md
@@ -31,7 +31,7 @@ information.
 The [`opt_einsum.contract`](https://dgasmith.github.io/opt_einsum/api_reference.html#opt_einsumcontract)
 function can often act as a drop-in replacement for `einsum`
 functions without further changes to the code while providing superior performance.
-Here, a tensor contraction is preformed with and without optimization:
+Here, a tensor contraction is performed with and without optimization:
 
 ```python
 import numpy as np
diff --git a/devtools/allowlist.txt b/devtools/allowlist.txt
index 0f6c883..00c766f 100644
--- a/devtools/allowlist.txt
+++ b/devtools/allowlist.txt
@@ -156,7 +156,7 @@ trac
 transpose
 uncomparable
 undoc
-unparseable
+unparsable
 v0
 VCS
 Vectordot
diff --git a/devtools/conda-recipe/meta.yaml b/devtools/conda-recipe/meta.yaml
index 15aaad4..2beff84 100644
--- a/devtools/conda-recipe/meta.yaml
+++ b/devtools/conda-recipe/meta.yaml
@@ -41,7 +41,7 @@ about:
     For example, let us examine the following index transformation:
     `M_{pqrs} = C_{pi} C_{qj} I_{ijkl} C_{rk} C_{sl}`
     
-    We can then develop two seperate implementations that produce the same result:
+    We can then develop two separate implementations that produce the same result:
     ```python
     N = 10
     C = np.random.rand(N, N)
diff --git a/docs/changelog.md b/docs/changelog.md
index 96a5b85..16720cb 100644
--- a/docs/changelog.md
+++ b/docs/changelog.md
@@ -97,7 +97,7 @@ decreasing the time to find paths for 50-200+ tensors. See `Path Overview <path_
 **Enhancements**
 
 - [\#48](https://github.com/dgasmith/opt_einsum/pull/48) Expressions are now mapped to non-unicode index set so that unicode input is support for all backends.
-- [\#54](https://github.com/dgasmith/opt_einsum/pull/54) General documenation update.
+- [\#54](https://github.com/dgasmith/opt_einsum/pull/54) General documentation update.
 
 **Bug fixes**
 
diff --git a/docs/getting_started/backends.md b/docs/getting_started/backends.md
index 7e1e224..224e816 100644
--- a/docs/getting_started/backends.md
+++ b/docs/getting_started/backends.md
@@ -200,7 +200,7 @@ all of which offer GPU support. Since `tensorflow` and `theano` both require
 compiling the expression, this functionality is encapsulated in generating a
 [`opt_einsum.ContractExpression`](../api_reference.md#opt_einsumcontractcontractexpression) using
 [`opt_einsum.contract_expression`](../api_reference.md#opt_einsumcontract_expression), which can then be called using numpy
-arrays whilst specifiying `backend='tensorflow'` etc.
+arrays whilst specifying `backend='tensorflow'` etc.
 Additionally, if arrays are marked as `constant`
 (see [`constants-section`](./reusing_paths.md#specifying-constants)), then these arrays will be kept on the device
 for optimal performance.
@@ -208,7 +208,7 @@ for optimal performance.
 
 ### Theano
 
-If `theano` is installed, using it as backend is as simple as specifiying
+If `theano` is installed, using it as backend is as simple as specifying
 `backend='theano'`:
 
 ```python
@@ -276,7 +276,7 @@ After which `opt_einsum` will automatically detect eager mode if
 Both [pytorch](https://pytorch.org) and [cupy](https://cupy.chainer.org/)
 offer numpy-like, GPU-enabled arrays which execute eagerly rather than
 requiring any compilation. If they are installed, no steps are required to
-utilize them other than specifiying the `backend` keyword:
+utilize them other than specifying the `backend` keyword:
 
 ```python
 expr(*xs, backend='torch')
diff --git a/docs/getting_started/install.md b/docs/getting_started/install.md
index e054305..2596302 100644
--- a/docs/getting_started/install.md
+++ b/docs/getting_started/install.md
@@ -10,7 +10,7 @@ You can update `opt_einsum` using [`conda`](https://www.anaconda.com/download/):
 conda install opt_einsum -c conda-forge
 ```
 
-This installs `opt_einsum` and the NumPy dependancy.
+This installs `opt_einsum` and the NumPy dependency.
 
 The `opt_einsum` package is maintained on the [conda-forge channel](https://conda-forge.github.io/).
 
diff --git a/docs/paths/introduction.md b/docs/paths/introduction.md
index 1ec9122..581d775 100644
--- a/docs/paths/introduction.md
+++ b/docs/paths/introduction.md
@@ -175,7 +175,7 @@ to find, `'greedy'`):
 
 ![Path Finding](../img/path_found_flops.png)
 
-One can see that the heirarchy of path qualities is:
+One can see that the hierarchy of path qualities is:
 
 1. `'optimal'` (used by auto for `n <= 4`)
 2. `'branch-all'` (used by auto for `n <= 6`)
diff --git a/opt_einsum/_version.py b/opt_einsum/_version.py
index bb4f184..0aafd20 100644
--- a/opt_einsum/_version.py
+++ b/opt_einsum/_version.py
@@ -275,7 +275,7 @@ def git_pieces_from_vcs(tag_prefix, root, verbose, run_command=run_command):
         # TAG-NUM-gHEX
         mo = re.search(r'^(.+)-(\d+)-g([0-9a-f]+)$', git_describe)
         if not mo:
-            # unparseable. Maybe git-describe is misbehaving?
+            # unparsable. Maybe git-describe is misbehaving?
             pieces["error"] = ("unable to parse git-describe output: '%s'" % describe_out)
             return pieces
 
diff --git a/opt_einsum/contract.py b/opt_einsum/contract.py
index 79afa2f..cf4d836 100644
--- a/opt_einsum/contract.py
+++ b/opt_einsum/contract.py
@@ -455,7 +455,7 @@ def contract(*operands, **kwargs):
 
     For contractions with just two tensors this function will attempt to use
     NumPy's built-in BLAS functionality to ensure that the given operation is
-    preformed optimally. When NumPy is linked to a threaded BLAS, potential
+    performed optimally. When NumPy is linked to a threaded BLAS, potential
     speedups are on the order of 20-100 for a six core machine.
     """
     optimize_arg = kwargs.pop('optimize', True)
diff --git a/opt_einsum/paths.py b/opt_einsum/paths.py
index 816e0e4..dbe9869 100644
--- a/opt_einsum/paths.py
+++ b/opt_einsum/paths.py
@@ -46,7 +46,7 @@ class PathOptimizer:
         return path
     ```
 
-    where `path` is a list of int-tuples specifiying a contraction order.
+    where `path` is a list of int-tuples specifying a contraction order.
     """
     def _check_args_against_first_call(self, inputs: List[TensorIndexType], output: TensorIndexType,
                                        size_dict: Dict[str, int]) -> None:
@@ -58,7 +58,7 @@ class PathOptimizer:
             # simply set the attribute as currently there is no global PathOptimizer init
             self._first_call_args = args
         elif args != self._first_call_args:
-            raise ValueError("The arguments specifiying the contraction that this path optimizer "
+            raise ValueError("The arguments specifying the contraction that this path optimizer "
                              "instance was called with have changed - try creating a new instance.")
 
     def __call__(self,
@@ -119,7 +119,7 @@ def calc_k12_flops(inputs: Tuple[FrozenSet[str]], output: FrozenSet[str], remain
     **Parameters:**
 
     - **inputs** - *(tuple[frozenset[str]])* The indices of each tensor in this contraction, note this includes
-        tensors unavaiable to contract as static single assignment is used ->
+        tensors unavailable to contract as static single assignment is used ->
         contracted tensors are not removed from the list.
     - **output** - *(frozenset[str])* The set of output indices for the whole contraction.
     - **remaining** - *(frozenset[int])* The set of indices (corresponding to ``inputs``) of tensors still available to contract.
@@ -644,7 +644,7 @@ def greedy(inputs: List[TensorIndexType],
     - **output** - *(set)* Set that represents the rhs side of the overall einsum subscript
     - **size_dict** - *(dictionary)* Dictionary of index sizes
     - **memory_limit** - *(int)* The maximum number of elements in a temporary array
-    - **choose_fn** - *(callable, optional)* A function that chooses which contraction to perform from the queu
+    - **choose_fn** - *(callable, optional)* A function that chooses which contraction to perform from the queue
     - **cost_fn** - *(callable, optional)* A function that assigns a potential contraction a cost.
 
     **Returns:**
@@ -861,7 +861,7 @@ def _dp_parse_out_single_term_ops(inputs, all_inds, ind_counts):
     inputs_parsed, inputs_done, inputs_contractions = [], [], []
     for j, i in enumerate(inputs):
         i_reduced = i - i_single
-        if not i_reduced:
+        if (not i_reduced) and (len(i) > 0):
             # input reduced to scalar already - remove
             inputs_done.append((j, ))
         else:
@@ -876,7 +876,7 @@ class DynamicProgramming(PathOptimizer):
     """
     Finds the optimal path of pairwise contractions without intermediate outer
     products based a dynamic programming approach presented in
-    Phys. Rev. E 90, 033315 (2014) (the corresponding preprint is publically
+    Phys. Rev. E 90, 033315 (2014) (the corresponding preprint is publicly
     available at https://arxiv.org/abs/1304.6112). This method is especially
     well-suited in the area of tensor network states, where it usually
     outperforms all the other optimization strategies.
@@ -1015,7 +1015,10 @@ class DynamicProgramming(PathOptimizer):
             else:
                 cost_cap = self.cost_cap
             # set the factor to increase the cost by each iteration (ensure > 1)
-            cost_increment = max(min(map(size_dict.__getitem__, subgraph_inds)), 2)
+            if len(subgraph_inds) == 0:
+                cost_increment = 2
+            else:
+                cost_increment = max(min(map(size_dict.__getitem__, subgraph_inds)), 2)
 
             while len(x[-1]) == 0:
                 for n in range(2, len(x[1]) + 1):
diff --git a/paper/paper.md b/paper/paper.md
index 61bb9c1..212a0ca 100644
--- a/paper/paper.md
+++ b/paper/paper.md
@@ -35,7 +35,7 @@ resulting in a dramatic increase in overall execution time.  Expressions with
 many tensors are particularly prevalent in many-body theories such as quantum
 chemistry, particle physics, and nuclear physics in addition to other fields
 such as machine learning.  At the extreme case, matrix product state theory can
-have thousands of tensors meaning that the computation cannot procede in a
+have thousands of tensors meaning that the computation cannot proceed in a
 naive fashion.
 
 The canonical NumPy ``einsum`` function considers expressions as a single unit
diff --git a/versioneer.py b/versioneer.py
index 64fea1c..d3db643 100644
--- a/versioneer.py
+++ b/versioneer.py
@@ -180,7 +180,7 @@ two common reasons why `setup.py` might not be in the root:
   `setup.cfg`, and `tox.ini`. Projects like these produce multiple PyPI
   distributions (and upload multiple independently-installable tarballs).
 * Source trees whose main purpose is to contain a C library, but which also
-  provide bindings to Python (and perhaps other langauges) in subdirectories.
+  provide bindings to Python (and perhaps other languages) in subdirectories.
 
 Versioneer will look for `.git` in parent directories, and most operations
 should get the right version string. However `pip` and `setuptools` have bugs
@@ -688,7 +688,7 @@ def git_pieces_from_vcs(tag_prefix, root, verbose, run_command=run_command):
         # TAG-NUM-gHEX
         mo = re.search(r'^(.+)-(\d+)-g([0-9a-f]+)$', git_describe)
         if not mo:
-            # unparseable. Maybe git-describe is misbehaving?
+            # unparsable. Maybe git-describe is misbehaving?
             pieces["error"] = ("unable to parse git-describe output: '%%s'"
                                %% describe_out)
             return pieces
@@ -1080,7 +1080,7 @@ def git_pieces_from_vcs(tag_prefix, root, verbose, run_command=run_command):
         # TAG-NUM-gHEX
         mo = re.search(r'^(.+)-(\d+)-g([0-9a-f]+)$', git_describe)
         if not mo:
-            # unparseable. Maybe git-describe is misbehaving?
+            # unparsable. Maybe git-describe is misbehaving?
             pieces["error"] = ("unable to parse git-describe output: '%s'"
                                % describe_out)
             return pieces


Test patch:
diff --git a/.github/workflows/Tests.yml b/.github/workflows/Tests.yml
index 77858eb..97b535d 100644
--- a/.github/workflows/Tests.yml
+++ b/.github/workflows/Tests.yml
@@ -14,6 +14,9 @@ jobs:
       matrix:
         python-version: [3.6, 3.7]
         environment: ["min-deps", "full", "min-ver"]
+        exclude:
+         - python-version: 3.6
+           environment: "full"
 
     runs-on: ubuntu-latest
 
diff --git a/opt_einsum/tests/test_blas.py b/opt_einsum/tests/test_blas.py
index 173dd38..c9ae730 100644
--- a/opt_einsum/tests/test_blas.py
+++ b/opt_einsum/tests/test_blas.py
@@ -1,5 +1,5 @@
 """
-Tests thte BLAS capability for the opt_einsum module.
+Tests the BLAS capability for the opt_einsum module.
 """
 
 import numpy as np
diff --git a/opt_einsum/tests/test_contract.py b/opt_einsum/tests/test_contract.py
index 8268e88..a3b5875 100644
--- a/opt_einsum/tests/test_contract.py
+++ b/opt_einsum/tests/test_contract.py
@@ -6,9 +6,14 @@ import numpy as np
 import pytest
 
 from opt_einsum import contract, contract_expression, contract_path, helpers
-from opt_einsum.paths import linear_to_ssa, ssa_to_linear
+from opt_einsum.paths import linear_to_ssa, ssa_to_linear, _PATH_OPTIONS
 
 tests = [
+    # Test scalar-like operations
+    'a,->a',
+    'ab,->ab',
+    ',ab,->ab',
+
     # Test hadamard-like products
     'a,ab,abc->abc',
     'a,b,ab->ab',
@@ -96,14 +101,9 @@ tests = [
     'aef,fbc,dca->bde',
 ]
 
-all_optimizers = [
-    'optimal', 'branch-all', 'branch-2', 'branch-1', 'greedy', 'random-greedy', 'random-greedy-128', 'dp', 'auto',
-    'auto-hq'
-]
-
 
 @pytest.mark.parametrize("string", tests)
-@pytest.mark.parametrize("optimize", all_optimizers)
+@pytest.mark.parametrize("optimize", _PATH_OPTIONS)
 def test_compare(optimize, string):
     views = helpers.build_views(string)
 
@@ -120,7 +120,7 @@ def test_drop_in_replacement(string):
 
 
 @pytest.mark.parametrize("string", tests)
-@pytest.mark.parametrize("optimize", all_optimizers)
+@pytest.mark.parametrize("optimize", _PATH_OPTIONS)
 def test_compare_greek(optimize, string):
     views = helpers.build_views(string)
 
@@ -134,7 +134,7 @@ def test_compare_greek(optimize, string):
 
 
 @pytest.mark.parametrize("string", tests)
-@pytest.mark.parametrize("optimize", all_optimizers)
+@pytest.mark.parametrize("optimize", _PATH_OPTIONS)
 def test_compare_blas(optimize, string):
     views = helpers.build_views(string)
 
@@ -144,7 +144,7 @@ def test_compare_blas(optimize, string):
 
 
 @pytest.mark.parametrize("string", tests)
-@pytest.mark.parametrize("optimize", all_optimizers)
+@pytest.mark.parametrize("optimize", _PATH_OPTIONS)
 def test_compare_blas_greek(optimize, string):
     views = helpers.build_views(string)
 
@@ -175,12 +175,12 @@ def test_printing():
 
 
 @pytest.mark.parametrize("string", tests)
-@pytest.mark.parametrize("optimize", all_optimizers)
+@pytest.mark.parametrize("optimize", _PATH_OPTIONS)
 @pytest.mark.parametrize("use_blas", [False, True])
 @pytest.mark.parametrize("out_spec", [False, True])
 def test_contract_expressions(string, optimize, use_blas, out_spec):
     views = helpers.build_views(string)
-    shapes = [view.shape for view in views]
+    shapes = [view.shape if hasattr(view, "shape") else tuple() for view in views]
     expected = contract(string, *views, optimize=False, use_blas=False)
 
     expr = contract_expression(string, *shapes, optimize=optimize, use_blas=use_blas)
@@ -220,7 +220,7 @@ def test_contract_expression_with_constants(string, constants):
     views = helpers.build_views(string)
     expected = contract(string, *views, optimize=False, use_blas=False)
 
-    shapes = [view.shape for view in views]
+    shapes = [view.shape if hasattr(view, "shape") else tuple() for view in views]
 
     expr_args = []
     ctrc_args = []
@@ -232,7 +232,6 @@ def test_contract_expression_with_constants(string, constants):
             ctrc_args.append(view)
 
     expr = contract_expression(string, *expr_args, constants=constants)
-    print(expr)
     out = expr(*ctrc_args)
     assert np.allclose(expected, out)
 
diff --git a/opt_einsum/tests/test_paths.py b/opt_einsum/tests/test_paths.py
index 1a6ec54..5815a40 100644
--- a/opt_einsum/tests/test_paths.py
+++ b/opt_einsum/tests/test_paths.py
@@ -51,6 +51,17 @@ path_edge_tests = [
     ['dp', 'dcc,fce,ea,dbf->ab', ((1, 2), (0, 2), (0, 1))],
 ]
 
+# note that these tests have no unique solution due to the chosen dimensions
+path_scalar_tests = [
+    [
+        'a,->a',
+        1,
+    ],
+    ['ab,->ab', 1],
+    [',a,->a', 2],
+    [',,a,->a', 3],
+]
+
 
 def check_path(test_output, benchmark, bypass=False):
     if not isinstance(test_output, list):
@@ -172,6 +183,17 @@ def test_path_edge_cases(alg, expression, order):
     assert check_path(path_ret[0], order)
 
 
+@pytest.mark.parametrize("expression,order", path_scalar_tests)
+@pytest.mark.parametrize("alg", oe.paths._PATH_OPTIONS)
+def test_path_scalar_cases(alg, expression, order):
+    views = oe.helpers.build_views(expression)
+
+    # Test tiny memory limit
+    path_ret = oe.contract_path(expression, *views, optimize=alg)
+    # print(path_ret[0])
+    assert len(path_ret[0]) == order
+
+
 def test_optimal_edge_cases():
 
     # Edge test5