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 https://github.com/guilgautier/DPPy/commit/5b8ed8ff718d72a0d5a8361beff3985cf5b89289 Does it work for you ?

[guilgautier]

@JohnnyDeuss ?

[JohnnyDeuss]

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