How to use the get_path() method when working with disconnected subgraphs in a network

[benjaminlanthier]

Hi @jcmgray,

I am currently trying to use the community_edge_betweenness method implemented in igraph to define it as a contraction path for a randomly generated tensor network. I have had some success with the following function where I define some variables to use later on in my defined class:

def get_community_edge_betweenness_tree(self):
    """
    Purpose
    -------
    Use the community edge betweenness method to find the network contraction tree.
    """
    # Create igraph object to use community betweenness
    inputs, output, indexSizes = self.network.get_inputs_output_size_dict()
    # Loaded inputs/outputs
    tensorNetworkGraph = cotengra.path_igraph.oe_to_igraph(
        inputs, output, indexSizes
    )
    # Created igraph tensor network
    dendrogram = tensorNetworkGraph.community_edge_betweenness()
    merges = dendrogram.merges
    self.tree = cotengra.core.ContractionTree.from_path(
        inputs, output, indexSizes, ssa_path=merges
    )
    # Setting this is crucial, it outputs the same path as igraph, but as a quimb object
    self.tree.set_surface_order_from_path(merges)
    self.contraction_path = self.tree.get_path(order="surface_order")

The only problem I found as of right now is that when I have a network that contains 2 or more disconnected "subgraphs", then I end up getting an error when calling the get_path(order=order) method. The error I receive is the following for a simple example :

KeyError: frozenset({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59})

In this case, I have a network that contains 60 tensors and 4 of the tensors form a small disconnected subgraph of their own, leaving the other 56 tensors as one big subgraph of the whole network. After some analysis, I think that I have found the variable that causes this problem, it seems to be self.children in cotengra.core._traverse_ordered() because this dictionary does not contain the combination of the 2 disconnected subgraphs.

I was wondering if there was a way to work around this issue or if there is already a method that can deal with those disconnected subgraphs?

[jcmgray]

Yes I'm guessing the dendrogram produced doesn't have merges for the disconnected subgraphs and thus the tree is not complete. One just needs to call tree.contract_nodes(parentless_nodes) where parentless_nodes are those nodes.. with no parents (i.e. the subgraphs). We could add an option to from_path that does this automatically, since during construction it already has this list of parentless nodes.

[jcmgray]

I've added this and some related functionality here: 6b5c173 and 85f15ce. Now by default it will autocomplete e.g. disconnected subgraphs but issue a warning that the path was incomplete. If instead you explicitly call .from_path(..., autocomplete=True) (as in path_igraph.py) it will do it without complaining.