Testing edge order is all that matters to make MSTs

mst.py

import random

import networkx as nx


def random_graph() -> nx.Graph:
    num_nodes = 20
    probability = 0.2

    return nx.erdos_renyi_graph(num_nodes, probability)


def add_weights(graph: nx.Graph):
    running_weight = 0
    for edge in graph.edges:
        running_weight += random.randint(0, 100)
        graph[edge[0]][edge[1]]["weight"] = running_weight


def get_mst_edges(graph: nx.Graph):
    tree = nx.minimum_spanning_tree(graph)
    return tree.edges


if __name__ == '__main__':
    for _ in range(10):
        G = random_graph()
        mst = None
        for _ in range(10):
            H = G.copy()
            add_weights(H)
            tree = get_mst_edges(H)

            if mst is None:
                mst = tree
            elif mst != tree:
                print("Edge weights matter!")