UST only works for simple node labels

[JohnnyDeuss]

Describe the bug
All the UST algorithms assume simple enumerated node labels, i.e. 0, 1, 2, ... This isn't always the case and is an unnecessary limitation. I personally ran into this making a maze generator.

To Reproduce
Steps to reproduce the behavior:

g = nx.grid_2d_graph(30, 20)
ust = UST(g)
ust.sample("Wilson")
st = ust.list_of_samples[0]

This will fail because nx.grid_2d_graph(30, 20) uses (x, y) as labels, since they are more meaningful in grid graphs.

My current workaround seems to confirm my suspicion that the UST algorithms break due to the complex node labels; it maps the complex labels to enumerated labels and then maps them back in the resulting spanning tree.

def invert_dict(d):
    return {v: k for k, v in d.items()}

g = nx.grid_2d_graph(w, h)
mapping = dict(enumerate(g.nodes))
g = nx.relabel_nodes(g, invert_dict(mapping))
ust = UST(g)
ust.sample("Wilson")
st = ust.list_of_samples[0]
nx.relabel_nodes(st, mapping, copy=False)

Expected behavior
The resulting spanning tree should represent a maze, but the UST algorithms break.

[guilgautier]

Hi @JohnnyDeuss!

Thanks for raising this issue.
I'll have a look at it next week and keep you posted 😉

FYI, another variant of the implementation can be found in the branch https://github.com/guilgautier/DPPy/tree/GML_Project_Berenice

[guilgautier]

Hi @JohnnyDeuss,
I've pushed a fix in the fix_ust branch with 5b8ed8f
Does it work for you ?

[guilgautier]

@JohnnyDeuss ?

[JohnnyDeuss]

Works perfectly! Deals with complex labels without having to do a workaround.