quimb.tensor.networking

Functionality for analyzing the structure of tensor networks, including finding paths, loops, connected components, hierarchical groupings and more.

Classes

NetworkPatch	A simple class to represent a patch of tensors and indices, storing
NetworkPath	A simple class to represent a path through a tensor network, storing
SweepScheduler	Schedule updates in sweeps over a graph, for belief propagation or

Functions

istree(tn)	Check if this tensor network has a tree structure, (treating
isconnected(tn)	Check whether this tensor network is connected, i.e. whether
subgraphs(tn[, virtual])	Split this tensor network into disconneceted subgraphs.
get_tree_span(tn, tids[, min_distance, max_distance, ...])	Generate a tree on the tensor network graph, fanning out from the
get_local_patch(tn, tids, max_distance[, include, exclude])	Get the local patch of tids that is within max_distance of
get_path_between_tids(tn, tida, tidb)	Find a shortest path between tida and tidb in this tensor
gen_all_paths_between_tids(tn, tida, tidb)	Generate all shortest paths between tida and tidb in this
gen_paths_loops(tn[, max_loop_length, intersect, ...])	Generate all paths, up to a specified length, that represent loops in
gen_sloops(tn[, max_loop_length, num_joins, ...])
gen_patches(tn, max_size[, tids, grow_from])	Generate groups of tids that represent 'patches' of the tensor network,
connected_bipartitions(tn)	Generate all connected bipartitions of this tensor network, i.e.
_get_two_core_tids(tn)	Get the tids of the 2-core of tn: the largest sub network in which
_parse_gloop_grow_from(grow_from, allow_dangling)	Check grow_from, mapping the old 'alldangle' and 'anydangle'
_gen_gloops_single(tn[, max_size, tids, grow_from, ...])
gen_gloops(tn[, max_size, tids, grow_from, num_joins, ...])	Generate sets of tids that represent 'generalized loops' where every
_gen_gloops_edge_induced_single(tn, region)	Generate all edge-induced loops that span exactly region.
gen_gloops_edge_induced(tn[, max_size, tids, ...])	Generate edge-induced loops as NetworkPatch objects. Unlike
gen_loops(tn[, max_loop_length])	Generate sequences of tids that represent loops in the TN.
get_loop_union(tn, tids[, max_size, grow_from, ...])	Find the union, in terms of tids, of all generalized loops that pass
gen_inds_connected(tn, max_length)	Generate all index 'patches' of size up to max_length.
tids_are_connected(tn, tids)	Check whether nodes tids are connected.
compute_shortest_distances(tn[, tids, exclude_inds])	Compute the minimum graph distances between all or some nodes
compute_hierarchical_linkage(tn[, tids, method, ...])
compute_hierarchical_ssa_path(tn[, tids, method, ...])	Compute a hierarchical grouping of tids, as a ssa_path.
compute_hierarchical_ordering(tn[, tids, method, ...])	Compute a hierarchical ordering of tids.
compute_hierarchical_grouping(tn, max_group_size[, ...])	Group tids (by default, all tensors) into groups of size
compute_centralities(tn)	Compute a simple centrality measure for each tensor in the network. The
most_central_tid(tn)	Find the most central tensor in the network.
least_central_tid(tn)	Find the least central tensor in the network.
compute_sweep_ranks(nodes, edges)	Rank nodes by a breadth first search over edges. Start each

Module Contents

class quimb.tensor.networking.NetworkPatch(tids, inds)

A simple class to represent a patch of tensors and indices, storing both the tensor identifies (tids) and indices (inds) it contains.

__slots__ = ('_inds', '_key', '_tids')

_tids

_inds

_key = None

classmethod from_sequence(it)

property tids

property num_tensors

property inds

property num_indices

__iter__()

property key

merge(other)

__contains__(x)

__hash__()

__eq__(other)

__repr__()

class quimb.tensor.networking.NetworkPath(tids, inds=())

Bases: NetworkPatch

A simple class to represent a path through a tensor network, storing both the tensor identifies (tids) and indices (inds) it passes through.

__slots__ = ('_inds', '_key', '_tids')

_tids

_inds = ()

_key = None

__len__()

__iter__()

extend(ind, tid)

Get a new path by extending this one with a new index and tensor id.

quimb.tensor.networking.istree(tn)

Check if this tensor network has a tree structure, (treating multibonds as a single edge).

Examples

>>> MPS_rand_state(10, 7).istree()
True

>>> MPS_rand_state(10, 7, cyclic=True).istree()
False

quimb.tensor.networking.isconnected(tn)

Check whether this tensor network is connected, i.e. whether there is a path between any two tensors, (including size 1 indices).

quimb.tensor.networking.subgraphs(tn, virtual=False)

Split this tensor network into disconneceted subgraphs.

Parameters:

virtual (bool, optional) – Whether the tensor networks should view the original tensors or not - by default take copies.

Return type:

list[TensorNetwork]

quimb.tensor.networking.get_tree_span(tn, tids, min_distance=0, max_distance=None, include=None, exclude=None, ndim_sort='max', distance_sort='min', sorter=None, weight_bonds=True, inwards=True)

Generate a tree on the tensor network graph, fanning out from the tensors identified by tids, up to a maximum of max_distance away. The tree can be visualized with draw_tree_span().

Parameters:

• tids (sequence of str) – The nodes that define the region to span out of.

• min_distance (int, optional) – Don’t add edges to the tree until this far from the region. For example, 1 will not include the last merges from neighboring tensors in the region defined by tids.

• max_distance (None or int, optional) – Terminate branches once they reach this far away. If None there is no limit,

• include (sequence of str, optional) – If specified, only tids specified here can be part of the tree.

• exclude (sequence of str, optional) – If specified, tids specified here cannot be part of the tree.

• ndim_sort ({'min', 'max', 'none'}, optional) – When expanding the tree, how to choose what nodes to expand to next, once connectivity to the current surface has been taken into account.

• distance_sort ({'min', 'max', 'none'}, optional) – When expanding the tree, how to choose what nodes to expand to next, once connectivity to the current surface has been taken into account.

• weight_bonds (bool, optional) – Whether to weight the ‘connection’ of a candidate tensor to expand out to using bond size as well as number of bonds.

Returns:

The ordered list of merges, each given as tuple (tid1, tid2, d) indicating merge tid1 -> tid2 at distance d.

Return type:

list[(str, str, int)]

See also

draw_tree_span

quimb.tensor.networking.get_local_patch(tn, tids, max_distance, include=None, exclude=None)

Get the local patch of tids that is within max_distance of the given tids. This is like an unordered version of get_tree_span.

Parameters:

• tn (TensorNetwork) – The tensor network to get the local patch from.

• tids (sequence of int) – The tensor ids to start from.

• max_distance (int) – The maximum distance from tids to include, in terms of graph distance. 0 corresponds to the original tids, 1 to nearest neighbors and so on.

• include (sequence of int, optional) – If specified, only tids from this set can be included in the patch.

• exclude (sequence of int, optional) – If specified, tids from this set cannot be included in the patch.

Return type:

tuple[int]

quimb.tensor.networking.get_path_between_tids(tn, tida, tidb)

Find a shortest path between tida and tidb in this tensor network. Returns a NetworkPath if a path is found, otherwise None.

Currently ignores dangling and hyper indices.

Parameters:

• tn (TensorNetwork) – The tensor network to find a path in.

• tida (int) – The tensor id to start from.

• tidb (int) – The tensor id to end at.

Return type:

NetworkPath or None

quimb.tensor.networking.gen_all_paths_between_tids(tn, tida, tidb)

Generate all shortest paths between tida and tidb in this tensor network. Returns a generator of NetworkPath objects, ignores dangling and hyper indices currently.

Parameters:

• tn (TensorNetwork) – The tensor network to find paths in.

• tida (int) – The tensor id to start from.

• tidb (int) – The tensor id to end at.

Yields:

NetworkPath

quimb.tensor.networking.gen_paths_loops(tn, max_loop_length=None, intersect=False, tids=None, inds=None, paths=None)

Generate all paths, up to a specified length, that represent loops in this tensor network. Unlike gen_loops this function will yield a NetworkPath objects, allowing one to differentiate between e.g. a double loop and a ‘figure of eight’ loop. Dangling and hyper indices are ignored.

Parameters:

• tn (TensorNetwork) – The tensor network to find loops in.

• max_loop_length (None or int) – Set the maximum number of indices that can appear in a loop. If None, wait until any loop is found and set that as the maximum length.

• intersect (bool, optional) – Whether to allow self-intersecting loops.

• tids (None or sequence of int, optional) – If supplied, only consider loops containing one of these tensor ids.

• inds (None or sequence of str, optional) – If supplied, only consider loops containing one of these indices.

• paths (None or sequence of NetworkPath, optional) – If supplied, only consider loops starting from these paths.

Yields:

NetworkPath

See also

gen_loops, gen_inds_connected

quimb.tensor.networking.gen_sloops(tn, max_loop_length=None, num_joins=1, intersect=False, tids=None, inds=None, paths=None)

quimb.tensor.networking.gen_patches(tn, max_size, tids=None, grow_from='all')

Generate groups of tids that represent ‘patches’ of the tensor network, where each patch is a connected subgraph of the tensor network. Unlike generalized loops, patches can contain dangling nodes.

Parameters:

• tn (TensorNetwork) – The tensor network to find patches in.

• max_size (int) – Set the maximum number of tensors that can appear in a region.

• tids (None or sequence of int, optional) – If supplied, only yield patches containing these tids, see grow_from.

• grow_from ({"all", "any"}, optional) – Whether to grow patches from all tids at once (“all”) or from any individual tid (“any”). The subsequent patches yielded will either contain all, or at least one of, tids specified respectively.

Yields:

tuple[int, …]

quimb.tensor.networking.connected_bipartitions(tn)

Generate all connected bipartitions of this tensor network, i.e. pairs of sets of tids (A, B) such that A U B is the full set of tids, A ∩ B = ∅, and both A and B are connected subgraphs.

Parameters:

tn (TensorNetwork) – The tensor network to find bipartitions in.

Returns:

The connected bipartitions found, each given as a tuple of frozensets of tids.

Return type:

tuple[(frozenset[int, …], frozenset[int, …]), …]

quimb.tensor.networking._get_two_core_tids(tn)

Get the tids of the 2-core of tn: the largest sub network in which every tensor has at least two bonds, found by repeatedly removing dangling tensors. Only these tids can appear in a generalized loop.

quimb.tensor.networking._parse_gloop_grow_from(grow_from, allow_dangling)

Check grow_from, mapping the old ‘alldangle’ and ‘anydangle’ options to allow_dangling.

quimb.tensor.networking._gen_gloops_single(tn, max_size=None, tids=None, grow_from='all', allow_dangling=False, two_core_tids=None)

quimb.tensor.networking.gen_gloops(tn, max_size=None, tids=None, grow_from='all', num_joins=1, join_overlap=2, allow_dangling=False)

Generate sets of tids that represent ‘generalized loops’ where every node is connected to at least two bonds, i.e. 2-degree connected subgraphs.

Parameters:

• tn (TensorNetwork) – The tensor network to find loops in.

• max_size (None, int or "min") – The maximum number of tensors that can appear in a region. If None, grow the regions until every target tid, i.e. tids or every tid, appears in at least one loop, then use that size. Targets that are not in a loop are ignored, with a warning if tids was given or the network is tree like. If "min", use the size of the first non-dangling loop found.

• tids (None or sequence of int, optional) – If supplied, only yield loops containing these tids, see grow_from.

• grow_from ({'all', 'any'}, optional) – Only if tids is specified, this determines how to filter loops. If ‘all’, only yield loops containing all of the tids in tids, if ‘any’, yield loops containing any of the tids in tids. 'alldangle' and 'anydangle' are old names for 'all' and 'any' that also set allow_dangling=True.

• num_joins (int, optional) – If larger than 1, repeatedly generate larger loops by joining together the initial set (individually with size up to max_size) of generalized loops. Each join combines loops that overlap on at least join_overlap tids. If tids are supplied, the base loops for each join are generated only around the current patches. An automatic max_size is resolved from the initial targeted loops and then held fixed.

• join_overlap ({1, 2}, optional) – When joining loops together, the minimum number of overlapping tids they must share. 1 allows merging on a single node, 2 requires sharing a bond, which leads to fewer but ‘denser’ loops.

• allow_dangling (bool, optional) – Whether the target tids can have fewer than two internal bonds in yielded regions. An automatic size is still taken from non-dangling loops, ignoring targets that are not in a loop. If no target is in a loop, warn and return the target region only. Ignored when tids is not supplied.

Yields:

tuple[int]

quimb.tensor.networking._gen_gloops_edge_induced_single(tn, region)

Generate all edge-induced loops that span exactly region.

Each NetworkPatch stores the tensors and retained bonds.

quimb.tensor.networking.gen_gloops_edge_induced(tn, max_size=None, tids=None, grow_from='all', num_joins=1, join_overlap=2, allow_dangling=False)

Generate edge-induced loops as NetworkPatch objects. Unlike gen_gloops, the same tensor regions can yield multiple patches, differing by whether certain internal bonds are included or not (for example removing the centeral span of an figure of eight).

Each patch stores the loop tensors in patch.tids and its bonds in patch.inds. gen_gloops() includes every bond between a set of tensors. This function also yields loops that omit bonds while remaining connected and keeping at least two bonds per tensor.

Parameters:

• tn (TensorNetwork) – Tensor network to search.

• max_size (None, int or "min") – Maximum tensors per region. See gen_gloops().

• tids (None or sequence of int, optional) – Only yield loops that contain these tids. See grow_from.

• grow_from ({'all', 'any'}, optional) – How to filter loops when tids is set. See gen_gloops().

• num_joins (int, optional) – Number of loops to join per result. See gen_gloops().

• join_overlap ({1, 2}, optional) – Minimum number of tids that joined loops must share.

• allow_dangling (bool, optional) – Whether target tids can dangle. See gen_gloops().

Yields:

NetworkPatch

See also

gen_gloops

quimb.tensor.networking.gen_loops(tn, max_loop_length=None)

Generate sequences of tids that represent loops in the TN.

Parameters:

max_loop_length (None or int) – Set the maximum number of tensors that can appear in a loop. If None, wait until any loop is found and set that as the maximum length.

Yields:

tuple[int]

See also

gen_paths_loops

quimb.tensor.networking.get_loop_union(tn, tids, max_size=None, grow_from='all', allow_dangling=False)

Find the union, in terms of tids, of all generalized loops that pass through either all or at least one of the given tids, depending on grow_from.

Parameters:

• tn (TensorNetwork) – The tensor network to find the loop union region in.

• tids (sequence of int) – The tensor ids to consider.

• max_size (None, int or "min", optional) – The maximum number of tensors that can appear in the region. If None, grow the regions until every tid in tids appears in at least one loop, then use that size. If "min", instead use the size of the first non-dangling loop found. See gen_gloops().

• grow_from ({'all', 'any'}, optional) – Only if tids is specified, this determines how to filter loops. If ‘all’, only take loops containing all of the tids in tids, if ‘any’, yield loops containing any of the tids in tids.

• allow_dangling (bool, optional) – Whether the target tids can have fewer than two internal bonds. See gen_gloops().

Return type:

tuple[int]

quimb.tensor.networking.gen_inds_connected(tn, max_length)

Generate all index ‘patches’ of size up to max_length.

Parameters:

max_length (int) – The maximum number of indices in the patch.

Yields:

tuple[str]

See also

gen_paths_loops

quimb.tensor.networking.tids_are_connected(tn, tids)

Check whether nodes tids are connected.

Parameters:

• tn (TensorNetwork) – The tensor network to check.

• tids (sequence of int) – Nodes to check.

Return type:

bool

quimb.tensor.networking.compute_shortest_distances(tn, tids=None, exclude_inds=())

Compute the minimum graph distances between all or some nodes tids.

Parameters:

• tn (TensorNetwork) – The tensor network to compute distances in.

• tids (None or sequence of int, optional) – If supplied, only compute distances between these nodes.

• exclude_inds (sequence of str, optional) – Exclude these indices when computing distances.

Return type:

dict[tuple[int, int], int]

quimb.tensor.networking.compute_hierarchical_linkage(tn, tids=None, method='weighted', optimal_ordering=True, exclude_inds=())

quimb.tensor.networking.compute_hierarchical_ssa_path(tn, tids=None, method='weighted', optimal_ordering=True, exclude_inds=(), are_sorted=False, linkage=None)

Compute a hierarchical grouping of tids, as a ssa_path.

quimb.tensor.networking.compute_hierarchical_ordering(tn, tids=None, method='weighted', optimal_ordering=True, exclude_inds=(), linkage=None)

Compute a hierarchical ordering of tids.

quimb.tensor.networking.compute_hierarchical_grouping(tn, max_group_size, tids=None, method='weighted', optimal_ordering=True, exclude_inds=(), linkage=None)

Group tids (by default, all tensors) into groups of size max_group_size or less, using a hierarchical clustering.

quimb.tensor.networking.compute_centralities(tn)

Compute a simple centrality measure for each tensor in the network. The values go from 0 to 1, with 1 being the most central tensor.

Parameters:

tn (TensorNetwork) – The tensor network to compute centralities for.

Return type:

dict[int, float]

quimb.tensor.networking.most_central_tid(tn)

Find the most central tensor in the network.

quimb.tensor.networking.least_central_tid(tn)

Find the least central tensor in the network.

quimb.tensor.networking.compute_sweep_ranks(nodes, edges)

Rank nodes by a breadth first search over edges. Start each connected component from its first unranked node in nodes. Except for starting nodes, each node has a higher rank than at least one neighbor. E.g. for a 2D grid starting at the corner:

0--1--3--6--...
|  |  |  |
2--4--7--...
|  |  |
5--8--...
|  |
...

Parameters:

• nodes (sequence of hashable) – All nodes, in the order to choose starting nodes.

• edges (sequence of tuple[hashable, hashable]) – The edges of the graph. A repeated edge counts as a loop.

Returns:

• ranks (dict[hashable, int]) – The rank of each node.

• is_tree (bool) – Whether the graph has no loops, i.e. is a tree (or forest).

class quimb.tensor.networking.SweepScheduler(nodes, edges, key_to_nodes, sweep_order='auto')

Schedule updates in sweeps over a graph, for belief propagation or simple gauging, defaulting to an efficient order when a tree is detected. Keys are hashable identifiers for updates, e.g. message keys, bond indices, or tensor ids. Nodes are graph vertices used to order these updates. key_to_nodes(key) returns the nodes for an update key.

Sort keys by their node ranks, see compute_sweep_ranks(). Yield each key at most once per sweep. Keys marked during a sweep join it if not yet yielded (except with sweep_order=None) this causes a local change to propagate fully along a chain for example.

Parameters:

• nodes (sequence of hashable) – Nodes, in the order to choose starting nodes. Rank these at initialization. Nodes later returned by key_to_nodes get the next unused rank if not already ranked.

• edges (sequence of tuple[hashable, hashable]) – The edges of the graph.

• key_to_nodes (callable) – Must accept an update key and return its graph nodes. Keys are ordered by the sorted ranks of these nodes.

• sweep_order ({'auto', 'alternate', 'fixed', None}, optional) –

  • ‘alternate’: reverse node rank order every other sweep, starting reversed. Undamped sequential BP on trees gives exact messages after two sweeps.

  • ’fixed’: use the same order every sweep, usually better with loops.

  • ’auto’: use ‘alternate’ for graphs with no loops, else ‘fixed’.

  • None: use reverse insertion order. Leave keys marked during a sweep for the next sweep.

touched

The keys to update in the next sweep.

Type:

oset

alternate

Whether the order is reversed every other sweep.

Type:

bool

Examples

Mark initial keys, perform a sweep, and mark affected keys:

sweeper = SweepScheduler(nodes, edges, key_to_nodes)
sweeper.touch(initial_keys)
for key in sweeper.sweep():
    affected_keys = update(key)
    sweeper.touch(affected_keys)

update(key) should perform the update and return keys that need an update as a result. Keys only yield once per sweep.

sweep_order = 'auto'

key_to_nodes

alternate

nsweeps = 0

touched

_heap = None

_yielded = None

_rank_sign = 1

_counter

_push_key(key)

touch(keys)

Mark keys for update. Add them to the current sweep if not yet updated in it, otherwise to the next. With sweep_order=None, always add them to the next sweep.

sweep()

Yield keys for one sweep. Keep keys marked again in touched.