SpanningTreeIterator fails for MultiGraphs

[jlportner]

From my layman understanding it seems as if the SpanningTreeIterator was written with MultiGraphs in mind.
However, trying it with a MultiGraph yields repeated output of the same spanning tree.

Current Behavior

Using the SpanningTreeIterator with a MultiGraph outputs many times the same spanning tree and not all possible spanning trees.

Consider the three cycle graph given by edges [(0,1),(1,2),(0,2)]. Then currently for this viewed as a multigraph it gives four times the spanning tree [(0,1), (0,2)].

Expected Behavior

Get all different spanning trees on the graph.

For the above example it should give the following 3 spanning trees:
[(0,1),(0,2)], [(0,2),(1,2)], [(0,1),(1,2)].

Steps to Reproduce

for g in nx.SpanningTreeIterator(nx.cycle_graph(3,create_using=nx.MultiGraph)):
    print(g.edges())

gives the wrong result whereas

for g in nx.SpanningTreeIterator(nx.cycle_graph(3,create_using=nx.Graph)):
    print(g.edges())

gives the expected result.

Environment

Python version: 3.12.3
NetworkX version: 3.3

[dschult]

I don't see anything in the docs indicating that it works for MultiGraphs.
(But it says that input G should be a directed graph when it should say undirected graph.)

Looking through the code, there is no handling of multiedges and their edge keys.
I can look into the history more, but first:

• can you describe why you think this should work for MultiGraphs?
• how would you expect it to handle two edges between the same two nodes?

[jlportner]

In the documentation of the __next__ function of the SpanningTreeIterator class it says it returns a "(multi)Graph" which I interpreted as that someone once wanted this to work with MultiGraphs too.

In anyway it would seem more consistent with the other spanning tree functions if it could also handle MultiGraphs.

If there are n edges between two vertices then it seems natural to me to return each spanning tree with each choice of one of these edges once (respecting the ordering of the weight) as two edges between the same vertices can have different weights.
So if we had the graph
[(0,1,0), (0,1,1),(1,2,0),(0,2,0)] I'd expect the following 5 spanning trees:
[(0,1,0),(1,2,0)]
[(0,1,1),(1,2,0)]
[(0,1,0),(0,2,0)]
[(0,1,1),(0,2,0)]
[(1,2,0),(0,2,0)]

[mjschwenne]

A couple of points on this:

• SpanningTreeIterator should only work with un-directed graphs. Directed graphs should use the ArboresenceIterator. That's a typo in the documentation.
• The spanning tree iterator isn't really designed to work with multi-graphs in mind.
• I wrote this class mostly to develop my understanding for the ArboresenceIterator class which I needed for the Asadpour TSP algorithm. That process does involve multi-graphs (since we have to contract vertices while tracking the total number of edges between them) so it's also possible that the reference to a multi-graph is a copy-paste error or something similar.
• I'm not aware of any particular reason why the underlying methodology shouldn't work for multi-graphs, although clearly it's not currently working as implemented right now.

I might take a crack at this later, but looking at what I've got going on this summer, I don't think it will happen before the end of June at the earliest.

[Aditya-Shandilya1182]

@mjschwenne @jlportner I can work on this. Can you please provide me with a headstart?

[jlportner]

I tried fixing it myself and changing the _write_partition function and the _clear_partition function (although I don't think changing _clear_partition is actually needed) to include keys seemed to fix it. However, I don't know how to make this then work for normal graphs which don't have keys. So somehow it should be united.

def _write_partition(self, partition):
    for u, v, k, d in self.G.edges(keys=True,data=True):
        if (u, v, k) in partition.partition_dict:
            d[self.partition_key] = partition.partition_dict[(u, v, k)]
        else:
            d[self.partition_key] = EdgePartition.OPEN

def _clear_partition(self, G):
    for u, v, k, d in G.edges(keys=True, data=True):
        if self.partition_key in d:
            del d[self.partition_key]

[dschult]

You might try creating the edges iterator before the for loop. Something like:

    partition_dict = partition.partition_dict
    partition_key = self.partition_key
    G = self.G
    edges = G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)

    for *e, d in edges:
        e = tuple(e)
        d[partition_key] = partition_dict[e] if e in partition_dict else EdgePartition.OPEN

def clear_partition(self, G):
    edges = G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
    for *e, d in edges:
        if self.partition_key in d:
            del d[self.partition_key]

[Aditya-Shandilya1182]

I have tried the following approach.

def _write_partition(self, partition):`
     
        partition_dict = partition.partition_dict
        partition_key = self.partition_key
        G = self.G

        #Handling multi-graphs
        if G.is_multigraph():
            for u, v, k, d in G.edges(keys= True, data = True):
                edge = (u, v, k)
                d[partition_key] = partition_dict.get(edge, EdgePartition.OPEN)
        
        else:
            for u, v, d in G.edges(data=True):
                edge = (u, v)
                d[partition_key] = partition_dict.get(edge, EdgePartition.OPEN)

def _clear_partition(self, G):
        """
        Removes partition data from the graph
        """
        partition_key = self.partition_key
        edges = G.edges(keys=True, data=True) if G.is_multigraph() else G.edges(data=True)
        for *e, d in edges:
            if partition_key in d:
                del d[partition_key]

This worked fine for some test cases I tried. I have opened a PR. Can you please review it?
Link: #7454
Thank You!