We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
add dynamic programming contractor of opt_einsum
We should update this asap

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `tensornetwork/contractors/opt_einsum_paths/path_contractors.py`
Content:
```
1 # pylint: disable=cyclic-import
2 # Copyright 2019 The TensorNetwork Authors
3 #
4 # Licensed under the Apache License, Version 2.0 (the "License");
5 # you may not use this file except in compliance with the License.
6 # You may obtain a copy of the License at
7 #
8 #      http://www.apache.org/licenses/LICENSE-2.0
9 #
10 # Unless required by applicable law or agreed to in writing, software
11 # distributed under the License is distributed on an "AS IS" BASIS,
12 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 # See the License for the specific language governing permissions and
14 # limitations under the License.
15 """Contractors based on `opt_einsum`'s path algorithms."""
16 
17 import functools
18 import opt_einsum
19 # pylint: disable=line-too-long
20 from tensornetwork.network_operations import check_connected, get_all_edges, get_subgraph_dangling
21 # pylint: disable=line-too-long
22 from tensornetwork.network_components import get_all_nondangling, contract_parallel, contract_between
23 from tensornetwork.network_components import Edge, AbstractNode
24 from tensornetwork.contractors.opt_einsum_paths import utils
25 from typing import Any, Optional, Sequence, Iterable
26 
27 #TODO (martin): add return types of functions back once TensorNetwork is gone
28 #               remove _base_network
29 #               _base_nodes -> base
30 
31 
32 def base(nodes: Iterable[AbstractNode],
33          algorithm: utils.Algorithm,
34          output_edge_order: Optional[Sequence[Edge]] = None,
35          ignore_edge_order: bool = False) -> AbstractNode:
36   """Base method for all `opt_einsum` contractors.
37 
38   Args:
39     nodes: A collection of connected nodes.
40     algorithm: `opt_einsum` contraction method to use.
41     output_edge_order: An optional list of edges. Edges of the
42       final node in `nodes_set`
43       are reordered into `output_edge_order`;
44       if final node has more than one edge,
45       `output_edge_order` must be pronvided.
46     ignore_edge_order: An option to ignore the output edge
47       order.
48 
49   Returns:
50     Final node after full contraction.
51   """
52   nodes_set = set(nodes)
53   edges = get_all_edges(nodes_set)
54   #output edge order has to be determinded before any contraction
55   #(edges are refreshed after contractions)
56 
57   if not ignore_edge_order:
58     if output_edge_order is None:
59       output_edge_order = list(get_subgraph_dangling(nodes))
60       if len(output_edge_order) > 1:
61         raise ValueError("The final node after contraction has more than "
62                          "one remaining edge. In this case `output_edge_order` "
63                          "has to be provided.")
64 
65     if set(output_edge_order) != get_subgraph_dangling(nodes):
66       raise ValueError("output edges are not equal to the remaining "
67                        "non-contracted edges of the final node.")
68 
69   for edge in edges:
70     if not edge.is_disabled:  #if its disabled we already contracted it
71       if edge.is_trace():
72         nodes_set.remove(edge.node1)
73         nodes_set.add(contract_parallel(edge))
74 
75   if len(nodes_set) == 1:
76     # There's nothing to contract.
77     if ignore_edge_order:
78       return list(nodes_set)[0]
79     return list(nodes_set)[0].reorder_edges(output_edge_order)
80 
81   # Then apply `opt_einsum`'s algorithm
82   path, nodes = utils.get_path(nodes_set, algorithm)
83   for a, b in path:
84     new_node = contract_between(nodes[a], nodes[b], allow_outer_product=True)
85     nodes.append(new_node)
86     nodes = utils.multi_remove(nodes, [a, b])
87 
88   # if the final node has more than one edge,
89   # output_edge_order has to be specified
90   final_node = nodes[0]  # nodes were connected, we checked this
91   if not ignore_edge_order:
92     final_node.reorder_edges(output_edge_order)
93   return final_node
94 
95 
96 def optimal(nodes: Iterable[AbstractNode],
97             output_edge_order: Optional[Sequence[Edge]] = None,
98             memory_limit: Optional[int] = None,
99             ignore_edge_order: bool = False) -> AbstractNode:
100   """Optimal contraction order via `opt_einsum`.
101 
102   This method will find the truly optimal contraction order via
103   `opt_einsum`'s depth first search algorithm. Since this search is
104   exhaustive, if your network is large (n>10), then the search may
105   take longer than just contracting in a suboptimal way.
106 
107   Args:
108     nodes: an iterable of Nodes
109     output_edge_order: An optional list of edges.
110       Edges of the final node in `nodes_set`
111       are reordered into `output_edge_order`;
112       if final node has more than one edge,
113       `output_edge_order` must be provided.
114     memory_limit: Maximum number of elements in an array during contractions.
115     ignore_edge_order: An option to ignore the output edge order.
116 
117   Returns:
118     The final node after full contraction.
119   """
120   alg = functools.partial(opt_einsum.paths.optimal, memory_limit=memory_limit)
121   return base(nodes, alg, output_edge_order, ignore_edge_order)
122 
123 
124 def branch(nodes: Iterable[AbstractNode],
125            output_edge_order: Optional[Sequence[Edge]] = None,
126            memory_limit: Optional[int] = None,
127            nbranch: Optional[int] = None,
128            ignore_edge_order: bool = False) -> AbstractNode:
129   """Branch contraction path via `opt_einsum`.
130 
131   This method uses the DFS approach of `optimal` while sorting potential
132   contractions based on a heuristic cost, in order to reduce time spent
133   in exploring paths which are unlikely to be optimal.
134   More details on `branching path`_.
135 
136   .. _branching path:
137     https://optimized-einsum.readthedocs.io/en/latest/branching_path.html
138 
139   Args:
140     nodes: an iterable of Nodes
141     output_edge_order: An optional list of edges.
142       Edges of the final node in `nodes_set`
143       are reordered into `output_edge_order`;
144       if final node has more than one edge,
145       `output_edge_order` must be provided.
146     memory_limit: Maximum number of elements in an array during contractions.
147     nbranch: Number of best contractions to explore.
148       If None it explores all inner products starting with those that
149       have the best cost heuristic.
150     ignore_edge_order: An option to ignore the output edge order.
151 
152   Returns:
153     The final node after full contraction.
154   """
155   alg = functools.partial(
156       opt_einsum.paths.branch, memory_limit=memory_limit, nbranch=nbranch)
157   return base(nodes, alg, output_edge_order, ignore_edge_order)
158 
159 
160 def greedy(nodes: Iterable[AbstractNode],
161            output_edge_order: Optional[Sequence[Edge]] = None,
162            memory_limit: Optional[int] = None,
163            ignore_edge_order: bool = False) -> AbstractNode:
164   """Greedy contraction path via `opt_einsum`.
165 
166   This provides a more efficient strategy than `optimal` for finding
167   contraction paths in large networks. First contracts pairs of tensors
168   by finding the pair with the lowest cost at each step. Then it performs
169   the outer products. More details on `greedy path`_.
170 
171   ..  _greedy path:
172     https://optimized-einsum.readthedocs.io/en/latest/greedy_path.html
173 
174   Args:
175     nodes: an iterable of Nodes
176     output_edge_order: An optional list of edges.
177       Edges of the final node in `nodes_set`
178       are reordered into `output_edge_order`;
179       if final node has more than one edge,
180       `output_edge_order` must be provided.
181     memory_limit: Maximum number of elements in an array during contractions.
182     ignore_edge_order: An option to ignore the output edge order.
183 
184   Returns:
185     The final node after full contraction.
186   """
187   alg = functools.partial(opt_einsum.paths.greedy, memory_limit=memory_limit)
188   return base(nodes, alg, output_edge_order, ignore_edge_order)
189 
190 
191 # pylint: disable=too-many-return-statements
192 def auto(nodes: Iterable[AbstractNode],
193          output_edge_order: Optional[Sequence[Edge]] = None,
194          memory_limit: Optional[int] = None,
195          ignore_edge_order: bool = False) -> AbstractNode:
196   """Chooses one of the above algorithms according to network size.
197 
198   Default behavior is based on `opt_einsum`'s `auto` contractor.
199 
200   Args:
201     nodes: A collection of connected nodes.
202     output_edge_order: An optional list of edges.
203       Edges of the final node in `nodes_set`
204       are reordered into `output_edge_order`;
205       if final node has more than one edge,
206       `output_edge_order` must be provided.
207     memory_limit: Maximum number of elements in an array during contractions.
208     ignore_edge_order: An option to ignore the output edge order.
209 
210   Returns:
211     Final node after full contraction.
212   """
213 
214   n = len(list(nodes))  #pytype thing
215   _nodes = nodes
216   if n <= 0:
217     raise ValueError("Cannot contract empty tensor network.")
218   if n == 1:
219     if not ignore_edge_order:
220       if output_edge_order is None:
221         output_edge_order = list(
222             (get_all_edges(_nodes) - get_all_nondangling(_nodes)))
223         if len(output_edge_order) > 1:
224           raise ValueError(
225               "The final node after contraction has more than "
226               "one dangling edge. In this case `output_edge_order` "
227               "has to be provided.")
228 
229     edges = get_all_nondangling(_nodes)
230     if edges:
231       final_node = contract_parallel(edges.pop())
232     else:
233       final_node = list(_nodes)[0]
234     final_node.reorder_edges(output_edge_order)
235     if not ignore_edge_order:
236       final_node.reorder_edges(output_edge_order)
237     return final_node
238 
239   if n < 5:
240     return optimal(nodes, output_edge_order, memory_limit, ignore_edge_order)
241   if n < 7:
242     return branch(
243         nodes,
244         output_edge_order=output_edge_order,
245         memory_limit=memory_limit,
246         ignore_edge_order=ignore_edge_order)
247   if n < 9:
248     return branch(
249         nodes,
250         output_edge_order=output_edge_order,
251         memory_limit=memory_limit,
252         nbranch=2,
253         ignore_edge_order=ignore_edge_order)
254   if n < 15:
255     return branch(
256         nodes,
257         output_edge_order=output_edge_order,
258         nbranch=1,
259         ignore_edge_order=ignore_edge_order)
260   return greedy(nodes, output_edge_order, memory_limit, ignore_edge_order)
261 
262 
263 def custom(nodes: Iterable[AbstractNode],
264            optimizer: Any,
265            output_edge_order: Sequence[Edge] = None,
266            memory_limit: Optional[int] = None,
267            ignore_edge_order: bool = False) -> AbstractNode:
268   """Uses a custom path optimizer created by the user to calculate paths.
269 
270   The custom path optimizer should inherit `opt_einsum`'s `PathOptimizer`.
271   See `custom paths`_.
272 
273   .. _custom paths:
274     https://optimized-einsum.readthedocs.io/en/latest/custom_paths.html
275 
276   Args:
277     nodes: an iterable of Nodes
278     output_edge_order: An optional list of edges.
279       Edges of the final node in `nodes_set`
280       are reordered into `output_edge_order`;
281       if final node has more than one edge,
282       output_edge_order` must be provided.
283     optimizer: A custom `opt_einsum.PathOptimizer` object.
284     memory_limit: Maximum number of elements in an array during contractions.
285     ignore_edge_order: An option to ignore the output edge order.
286 
287   Returns:
288     Final node after full contraction.
289   """
290   alg = functools.partial(optimizer, memory_limit=memory_limit)
291   return base(nodes, alg, output_edge_order, ignore_edge_order)
292
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/tensornetwork/contractors/opt_einsum_paths/path_contractors.py b/tensornetwork/contractors/opt_einsum_paths/path_contractors.py
--- a/tensornetwork/contractors/opt_einsum_paths/path_contractors.py
+++ b/tensornetwork/contractors/opt_einsum_paths/path_contractors.py
@@ -117,7 +117,8 @@
   Returns:
     The final node after full contraction.
   """
-  alg = functools.partial(opt_einsum.paths.optimal, memory_limit=memory_limit)
+  alg = functools.partial(
+      opt_einsum.paths.dynamic_programming, memory_limit=memory_limit)
   return base(nodes, alg, output_edge_order, ignore_edge_order)

{"golden_diff": "diff --git a/tensornetwork/contractors/opt_einsum_paths/path_contractors.py b/tensornetwork/contractors/opt_einsum_paths/path_contractors.py\n--- a/tensornetwork/contractors/opt_einsum_paths/path_contractors.py\n+++ b/tensornetwork/contractors/opt_einsum_paths/path_contractors.py\n@@ -117,7 +117,8 @@\n   Returns:\n     The final node after full contraction.\n   \"\"\"\n-  alg = functools.partial(opt_einsum.paths.optimal, memory_limit=memory_limit)\n+  alg = functools.partial(\n+      opt_einsum.paths.dynamic_programming, memory_limit=memory_limit)\n   return base(nodes, alg, output_edge_order, ignore_edge_order)\n", "issue": "add dynamic programming contractor of opt_einsum\nWe should update this asap\n", "before_files": [{"content": "# pylint: disable=cyclic-import\n# Copyright 2019 The TensorNetwork Authors\n#\n# Licensed under the Apache License, Version 2.0 (the \"License\");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#      http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an \"AS IS\" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n\"\"\"Contractors based on `opt_einsum`'s path algorithms.\"\"\"\n\nimport functools\nimport opt_einsum\n# pylint: disable=line-too-long\nfrom tensornetwork.network_operations import check_connected, get_all_edges, get_subgraph_dangling\n# pylint: disable=line-too-long\nfrom tensornetwork.network_components import get_all_nondangling, contract_parallel, contract_between\nfrom tensornetwork.network_components import Edge, AbstractNode\nfrom tensornetwork.contractors.opt_einsum_paths import utils\nfrom typing import Any, Optional, Sequence, Iterable\n\n#TODO (martin): add return types of functions back once TensorNetwork is gone\n#               remove _base_network\n#               _base_nodes -> base\n\n\ndef base(nodes: Iterable[AbstractNode],\n         algorithm: utils.Algorithm,\n         output_edge_order: Optional[Sequence[Edge]] = None,\n         ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Base method for all `opt_einsum` contractors.\n\n  Args:\n    nodes: A collection of connected nodes.\n    algorithm: `opt_einsum` contraction method to use.\n    output_edge_order: An optional list of edges. Edges of the\n      final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be pronvided.\n    ignore_edge_order: An option to ignore the output edge\n      order.\n\n  Returns:\n    Final node after full contraction.\n  \"\"\"\n  nodes_set = set(nodes)\n  edges = get_all_edges(nodes_set)\n  #output edge order has to be determinded before any contraction\n  #(edges are refreshed after contractions)\n\n  if not ignore_edge_order:\n    if output_edge_order is None:\n      output_edge_order = list(get_subgraph_dangling(nodes))\n      if len(output_edge_order) > 1:\n        raise ValueError(\"The final node after contraction has more than \"\n                         \"one remaining edge. In this case `output_edge_order` \"\n                         \"has to be provided.\")\n\n    if set(output_edge_order) != get_subgraph_dangling(nodes):\n      raise ValueError(\"output edges are not equal to the remaining \"\n                       \"non-contracted edges of the final node.\")\n\n  for edge in edges:\n    if not edge.is_disabled:  #if its disabled we already contracted it\n      if edge.is_trace():\n        nodes_set.remove(edge.node1)\n        nodes_set.add(contract_parallel(edge))\n\n  if len(nodes_set) == 1:\n    # There's nothing to contract.\n    if ignore_edge_order:\n      return list(nodes_set)[0]\n    return list(nodes_set)[0].reorder_edges(output_edge_order)\n\n  # Then apply `opt_einsum`'s algorithm\n  path, nodes = utils.get_path(nodes_set, algorithm)\n  for a, b in path:\n    new_node = contract_between(nodes[a], nodes[b], allow_outer_product=True)\n    nodes.append(new_node)\n    nodes = utils.multi_remove(nodes, [a, b])\n\n  # if the final node has more than one edge,\n  # output_edge_order has to be specified\n  final_node = nodes[0]  # nodes were connected, we checked this\n  if not ignore_edge_order:\n    final_node.reorder_edges(output_edge_order)\n  return final_node\n\n\ndef optimal(nodes: Iterable[AbstractNode],\n            output_edge_order: Optional[Sequence[Edge]] = None,\n            memory_limit: Optional[int] = None,\n            ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Optimal contraction order via `opt_einsum`.\n\n  This method will find the truly optimal contraction order via\n  `opt_einsum`'s depth first search algorithm. Since this search is\n  exhaustive, if your network is large (n>10), then the search may\n  take longer than just contracting in a suboptimal way.\n\n  Args:\n    nodes: an iterable of Nodes\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be provided.\n    memory_limit: Maximum number of elements in an array during contractions.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    The final node after full contraction.\n  \"\"\"\n  alg = functools.partial(opt_einsum.paths.optimal, memory_limit=memory_limit)\n  return base(nodes, alg, output_edge_order, ignore_edge_order)\n\n\ndef branch(nodes: Iterable[AbstractNode],\n           output_edge_order: Optional[Sequence[Edge]] = None,\n           memory_limit: Optional[int] = None,\n           nbranch: Optional[int] = None,\n           ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Branch contraction path via `opt_einsum`.\n\n  This method uses the DFS approach of `optimal` while sorting potential\n  contractions based on a heuristic cost, in order to reduce time spent\n  in exploring paths which are unlikely to be optimal.\n  More details on `branching path`_.\n\n  .. _branching path:\n    https://optimized-einsum.readthedocs.io/en/latest/branching_path.html\n\n  Args:\n    nodes: an iterable of Nodes\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be provided.\n    memory_limit: Maximum number of elements in an array during contractions.\n    nbranch: Number of best contractions to explore.\n      If None it explores all inner products starting with those that\n      have the best cost heuristic.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    The final node after full contraction.\n  \"\"\"\n  alg = functools.partial(\n      opt_einsum.paths.branch, memory_limit=memory_limit, nbranch=nbranch)\n  return base(nodes, alg, output_edge_order, ignore_edge_order)\n\n\ndef greedy(nodes: Iterable[AbstractNode],\n           output_edge_order: Optional[Sequence[Edge]] = None,\n           memory_limit: Optional[int] = None,\n           ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Greedy contraction path via `opt_einsum`.\n\n  This provides a more efficient strategy than `optimal` for finding\n  contraction paths in large networks. First contracts pairs of tensors\n  by finding the pair with the lowest cost at each step. Then it performs\n  the outer products. More details on `greedy path`_.\n\n  ..  _greedy path:\n    https://optimized-einsum.readthedocs.io/en/latest/greedy_path.html\n\n  Args:\n    nodes: an iterable of Nodes\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be provided.\n    memory_limit: Maximum number of elements in an array during contractions.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    The final node after full contraction.\n  \"\"\"\n  alg = functools.partial(opt_einsum.paths.greedy, memory_limit=memory_limit)\n  return base(nodes, alg, output_edge_order, ignore_edge_order)\n\n\n# pylint: disable=too-many-return-statements\ndef auto(nodes: Iterable[AbstractNode],\n         output_edge_order: Optional[Sequence[Edge]] = None,\n         memory_limit: Optional[int] = None,\n         ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Chooses one of the above algorithms according to network size.\n\n  Default behavior is based on `opt_einsum`'s `auto` contractor.\n\n  Args:\n    nodes: A collection of connected nodes.\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be provided.\n    memory_limit: Maximum number of elements in an array during contractions.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    Final node after full contraction.\n  \"\"\"\n\n  n = len(list(nodes))  #pytype thing\n  _nodes = nodes\n  if n <= 0:\n    raise ValueError(\"Cannot contract empty tensor network.\")\n  if n == 1:\n    if not ignore_edge_order:\n      if output_edge_order is None:\n        output_edge_order = list(\n            (get_all_edges(_nodes) - get_all_nondangling(_nodes)))\n        if len(output_edge_order) > 1:\n          raise ValueError(\n              \"The final node after contraction has more than \"\n              \"one dangling edge. In this case `output_edge_order` \"\n              \"has to be provided.\")\n\n    edges = get_all_nondangling(_nodes)\n    if edges:\n      final_node = contract_parallel(edges.pop())\n    else:\n      final_node = list(_nodes)[0]\n    final_node.reorder_edges(output_edge_order)\n    if not ignore_edge_order:\n      final_node.reorder_edges(output_edge_order)\n    return final_node\n\n  if n < 5:\n    return optimal(nodes, output_edge_order, memory_limit, ignore_edge_order)\n  if n < 7:\n    return branch(\n        nodes,\n        output_edge_order=output_edge_order,\n        memory_limit=memory_limit,\n        ignore_edge_order=ignore_edge_order)\n  if n < 9:\n    return branch(\n        nodes,\n        output_edge_order=output_edge_order,\n        memory_limit=memory_limit,\n        nbranch=2,\n        ignore_edge_order=ignore_edge_order)\n  if n < 15:\n    return branch(\n        nodes,\n        output_edge_order=output_edge_order,\n        nbranch=1,\n        ignore_edge_order=ignore_edge_order)\n  return greedy(nodes, output_edge_order, memory_limit, ignore_edge_order)\n\n\ndef custom(nodes: Iterable[AbstractNode],\n           optimizer: Any,\n           output_edge_order: Sequence[Edge] = None,\n           memory_limit: Optional[int] = None,\n           ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Uses a custom path optimizer created by the user to calculate paths.\n\n  The custom path optimizer should inherit `opt_einsum`'s `PathOptimizer`.\n  See `custom paths`_.\n\n  .. _custom paths:\n    https://optimized-einsum.readthedocs.io/en/latest/custom_paths.html\n\n  Args:\n    nodes: an iterable of Nodes\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      output_edge_order` must be provided.\n    optimizer: A custom `opt_einsum.PathOptimizer` object.\n    memory_limit: Maximum number of elements in an array during contractions.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    Final node after full contraction.\n  \"\"\"\n  alg = functools.partial(optimizer, memory_limit=memory_limit)\n  return base(nodes, alg, output_edge_order, ignore_edge_order)\n", "path": "tensornetwork/contractors/opt_einsum_paths/path_contractors.py"}], "after_files": [{"content": "# pylint: disable=cyclic-import\n# Copyright 2019 The TensorNetwork Authors\n#\n# Licensed under the Apache License, Version 2.0 (the \"License\");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#      http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an \"AS IS\" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n\"\"\"Contractors based on `opt_einsum`'s path algorithms.\"\"\"\n\nimport functools\nimport opt_einsum\n# pylint: disable=line-too-long\nfrom tensornetwork.network_operations import check_connected, get_all_edges, get_subgraph_dangling\n# pylint: disable=line-too-long\nfrom tensornetwork.network_components import get_all_nondangling, contract_parallel, contract_between\nfrom tensornetwork.network_components import Edge, AbstractNode\nfrom tensornetwork.contractors.opt_einsum_paths import utils\nfrom typing import Any, Optional, Sequence, Iterable\n\n#TODO (martin): add return types of functions back once TensorNetwork is gone\n#               remove _base_network\n#               _base_nodes -> base\n\n\ndef base(nodes: Iterable[AbstractNode],\n         algorithm: utils.Algorithm,\n         output_edge_order: Optional[Sequence[Edge]] = None,\n         ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Base method for all `opt_einsum` contractors.\n\n  Args:\n    nodes: A collection of connected nodes.\n    algorithm: `opt_einsum` contraction method to use.\n    output_edge_order: An optional list of edges. Edges of the\n      final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be pronvided.\n    ignore_edge_order: An option to ignore the output edge\n      order.\n\n  Returns:\n    Final node after full contraction.\n  \"\"\"\n  nodes_set = set(nodes)\n  edges = get_all_edges(nodes_set)\n  #output edge order has to be determinded before any contraction\n  #(edges are refreshed after contractions)\n\n  if not ignore_edge_order:\n    if output_edge_order is None:\n      output_edge_order = list(get_subgraph_dangling(nodes))\n      if len(output_edge_order) > 1:\n        raise ValueError(\"The final node after contraction has more than \"\n                         \"one remaining edge. In this case `output_edge_order` \"\n                         \"has to be provided.\")\n\n    if set(output_edge_order) != get_subgraph_dangling(nodes):\n      raise ValueError(\"output edges are not equal to the remaining \"\n                       \"non-contracted edges of the final node.\")\n\n  for edge in edges:\n    if not edge.is_disabled:  #if its disabled we already contracted it\n      if edge.is_trace():\n        nodes_set.remove(edge.node1)\n        nodes_set.add(contract_parallel(edge))\n\n  if len(nodes_set) == 1:\n    # There's nothing to contract.\n    if ignore_edge_order:\n      return list(nodes_set)[0]\n    return list(nodes_set)[0].reorder_edges(output_edge_order)\n\n  # Then apply `opt_einsum`'s algorithm\n  path, nodes = utils.get_path(nodes_set, algorithm)\n  for a, b in path:\n    new_node = contract_between(nodes[a], nodes[b], allow_outer_product=True)\n    nodes.append(new_node)\n    nodes = utils.multi_remove(nodes, [a, b])\n\n  # if the final node has more than one edge,\n  # output_edge_order has to be specified\n  final_node = nodes[0]  # nodes were connected, we checked this\n  if not ignore_edge_order:\n    final_node.reorder_edges(output_edge_order)\n  return final_node\n\n\ndef optimal(nodes: Iterable[AbstractNode],\n            output_edge_order: Optional[Sequence[Edge]] = None,\n            memory_limit: Optional[int] = None,\n            ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Optimal contraction order via `opt_einsum`.\n\n  This method will find the truly optimal contraction order via\n  `opt_einsum`'s depth first search algorithm. Since this search is\n  exhaustive, if your network is large (n>10), then the search may\n  take longer than just contracting in a suboptimal way.\n\n  Args:\n    nodes: an iterable of Nodes\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be provided.\n    memory_limit: Maximum number of elements in an array during contractions.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    The final node after full contraction.\n  \"\"\"\n  alg = functools.partial(\n      opt_einsum.paths.dynamic_programming, memory_limit=memory_limit)\n  return base(nodes, alg, output_edge_order, ignore_edge_order)\n\n\ndef branch(nodes: Iterable[AbstractNode],\n           output_edge_order: Optional[Sequence[Edge]] = None,\n           memory_limit: Optional[int] = None,\n           nbranch: Optional[int] = None,\n           ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Branch contraction path via `opt_einsum`.\n\n  This method uses the DFS approach of `optimal` while sorting potential\n  contractions based on a heuristic cost, in order to reduce time spent\n  in exploring paths which are unlikely to be optimal.\n  More details on `branching path`_.\n\n  .. _branching path:\n    https://optimized-einsum.readthedocs.io/en/latest/branching_path.html\n\n  Args:\n    nodes: an iterable of Nodes\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be provided.\n    memory_limit: Maximum number of elements in an array during contractions.\n    nbranch: Number of best contractions to explore.\n      If None it explores all inner products starting with those that\n      have the best cost heuristic.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    The final node after full contraction.\n  \"\"\"\n  alg = functools.partial(\n      opt_einsum.paths.branch, memory_limit=memory_limit, nbranch=nbranch)\n  return base(nodes, alg, output_edge_order, ignore_edge_order)\n\n\ndef greedy(nodes: Iterable[AbstractNode],\n           output_edge_order: Optional[Sequence[Edge]] = None,\n           memory_limit: Optional[int] = None,\n           ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Greedy contraction path via `opt_einsum`.\n\n  This provides a more efficient strategy than `optimal` for finding\n  contraction paths in large networks. First contracts pairs of tensors\n  by finding the pair with the lowest cost at each step. Then it performs\n  the outer products. More details on `greedy path`_.\n\n  ..  _greedy path:\n    https://optimized-einsum.readthedocs.io/en/latest/greedy_path.html\n\n  Args:\n    nodes: an iterable of Nodes\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be provided.\n    memory_limit: Maximum number of elements in an array during contractions.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    The final node after full contraction.\n  \"\"\"\n  alg = functools.partial(opt_einsum.paths.greedy, memory_limit=memory_limit)\n  return base(nodes, alg, output_edge_order, ignore_edge_order)\n\n\n# pylint: disable=too-many-return-statements\ndef auto(nodes: Iterable[AbstractNode],\n         output_edge_order: Optional[Sequence[Edge]] = None,\n         memory_limit: Optional[int] = None,\n         ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Chooses one of the above algorithms according to network size.\n\n  Default behavior is based on `opt_einsum`'s `auto` contractor.\n\n  Args:\n    nodes: A collection of connected nodes.\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      `output_edge_order` must be provided.\n    memory_limit: Maximum number of elements in an array during contractions.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    Final node after full contraction.\n  \"\"\"\n\n  n = len(list(nodes))  #pytype thing\n  _nodes = nodes\n  if n <= 0:\n    raise ValueError(\"Cannot contract empty tensor network.\")\n  if n == 1:\n    if not ignore_edge_order:\n      if output_edge_order is None:\n        output_edge_order = list(\n            (get_all_edges(_nodes) - get_all_nondangling(_nodes)))\n        if len(output_edge_order) > 1:\n          raise ValueError(\n              \"The final node after contraction has more than \"\n              \"one dangling edge. In this case `output_edge_order` \"\n              \"has to be provided.\")\n\n    edges = get_all_nondangling(_nodes)\n    if edges:\n      final_node = contract_parallel(edges.pop())\n    else:\n      final_node = list(_nodes)[0]\n    final_node.reorder_edges(output_edge_order)\n    if not ignore_edge_order:\n      final_node.reorder_edges(output_edge_order)\n    return final_node\n\n  if n < 5:\n    return optimal(nodes, output_edge_order, memory_limit, ignore_edge_order)\n  if n < 7:\n    return branch(\n        nodes,\n        output_edge_order=output_edge_order,\n        memory_limit=memory_limit,\n        ignore_edge_order=ignore_edge_order)\n  if n < 9:\n    return branch(\n        nodes,\n        output_edge_order=output_edge_order,\n        memory_limit=memory_limit,\n        nbranch=2,\n        ignore_edge_order=ignore_edge_order)\n  if n < 15:\n    return branch(\n        nodes,\n        output_edge_order=output_edge_order,\n        nbranch=1,\n        ignore_edge_order=ignore_edge_order)\n  return greedy(nodes, output_edge_order, memory_limit, ignore_edge_order)\n\n\ndef custom(nodes: Iterable[AbstractNode],\n           optimizer: Any,\n           output_edge_order: Sequence[Edge] = None,\n           memory_limit: Optional[int] = None,\n           ignore_edge_order: bool = False) -> AbstractNode:\n  \"\"\"Uses a custom path optimizer created by the user to calculate paths.\n\n  The custom path optimizer should inherit `opt_einsum`'s `PathOptimizer`.\n  See `custom paths`_.\n\n  .. _custom paths:\n    https://optimized-einsum.readthedocs.io/en/latest/custom_paths.html\n\n  Args:\n    nodes: an iterable of Nodes\n    output_edge_order: An optional list of edges.\n      Edges of the final node in `nodes_set`\n      are reordered into `output_edge_order`;\n      if final node has more than one edge,\n      output_edge_order` must be provided.\n    optimizer: A custom `opt_einsum.PathOptimizer` object.\n    memory_limit: Maximum number of elements in an array during contractions.\n    ignore_edge_order: An option to ignore the output edge order.\n\n  Returns:\n    Final node after full contraction.\n  \"\"\"\n  alg = functools.partial(optimizer, memory_limit=memory_limit)\n  return base(nodes, alg, output_edge_order, ignore_edge_order)\n", "path": "tensornetwork/contractors/opt_einsum_paths/path_contractors.py"}]}