<jupyter_start><jupyter_text>Test on small graph of known structure<jupyter_code>adjacency_matrix = [
    [0, 3, 0], 
    [3, 0, 4], 
    [0, 4, 0]
]
graph = nx.from_numpy_matrix(np.matrix(adjacency_matrix))
nx.draw(graph)
nx.draw_networkx_labels(graph, pos=nx.circular_layout(graph))
nx.draw_networkx_edge_labels(graph, pos=nx.circular_layout(graph))
expected = nx.minimum_spanning_tree(graph, algorithm = 'prim')
actual_edges = cpp_prim.run_algorithm(adjacency_matrix)
actual = nx.Graph()
actual.add_edges_from(actual_edges)

print(sorted(expected.edges))
print(sorted(actual.edges))
assert nx.is_isomorphic(expected, actual)<jupyter_output>[(0, 1), (1, 2)]
[(0, 1), (1, 2)]<jupyter_text>Visualization:<jupyter_code>nx.draw_networkx(graph, pos=nx.circular_layout(graph))
nx.draw_networkx_edges(graph, pos=nx.circular_layout(graph), edgelist = expected.edges(), edge_color='red')
nx.draw_networkx(graph, pos=nx.circular_layout(graph))
nx.draw_networkx_edges(graph, pos=nx.circular_layout(graph), edgelist = actual.edges(), edge_color='red')<jupyter_output><empty_output><jupyter_text>Test on bigger graph of known structure<jupyter_code>adjacency_matrix = [
    [0, 1, 2, 4, 1], 
    [1, 0, 1, 3, 3], 
    [2, 1, 0, 1, 2], 
    [4, 3, 1, 0, 5], 
    [1, 3, 2, 5, 0]
]
graph = nx.from_numpy_matrix(np.matrix(adjacency_matrix))
nx.draw(graph)
nx.draw_networkx_labels(graph, pos=nx.circular_layout(graph))
nx.draw_networkx_edge_labels(graph, pos=nx.circular_layout(graph))
expected = nx.minimum_spanning_tree(graph, algorithm = 'prim')
actual_edges = cpp_prim.run_algorithm(adjacency_matrix)
actual = nx.Graph()
actual.add_edges_from(actual_edges)

print(sorted(expected.edges))
print(sorted(actual.edges))
assert nx.is_isomorphic(expected, actual)<jupyter_output>[(0, 1), (0, 4), (1, 2), (2, 3)]
[(0, 1), (0, 4), (1, 2), (2, 3)]<jupyter_text>Visualization:<jupyter_code>nx.draw_networkx(graph, pos=nx.circular_layout(graph))
nx.draw_networkx_edges(graph, pos=nx.circular_layout(graph), edgelist = expected.edges(), edge_color='red')
nx.draw_networkx(graph, pos=nx.circular_layout(graph))
nx.draw_networkx_edges(graph, pos=nx.circular_layout(graph), edgelist = actual.edges(), edge_color='red')<jupyter_output><empty_output><jupyter_text>Check corectness on random complete graphs<jupyter_code>def test(max_weight: int):
    isomorphic_cases = 0
    correct_cases = 0
    all_cases = 100
    
    for i in range(0, all_cases):
        graph = nx.complete_graph(50)
        for (start, end) in graph.edges:
            graph.edges[start, end]['weight'] = random.randrange(1, max_weight)

        expected = nx.minimum_spanning_tree(graph, algorithm = 'prim')
        sum_of_weights_expected = expected.size(weight='weight')

        adjacency_matrix = nx.to_numpy_array(graph, dtype='int32').tolist()

        actual_edges = cpp_prim.run_algorithm(adjacency_matrix)
        actual = graph.edge_subgraph(actual_edges)
        sum_of_weights_actual = actual.size(weight='weight')

        if nx.is_isomorphic(expected, actual):
            isomorphic_cases = isomorphic_cases + 1

        if nx.is_tree(actual) and actual.number_of_nodes() == graph.number_of_nodes() and sum_of_weights_expected == sum_of_weights_actual:
            correct_cases = correct_cases + 1
        
    print("Algorithm generated isomorphic graph in ", 100 * isomorphic_cases/all_cases, "% cases")        
    print("Algorithm run correctly in ", 100 * correct_cases/all_cases, "% cases")
random.seed(31)
test(max_weight = 100);<jupyter_output>Algorithm generated isomorphic graph in  2.0 % cases
Algorithm run correctly in  100.0 % cases<jupyter_text>The bigger is the probability of unique weights, the more likely there is only one possible MST, thus expected and actual graphs are isomorphic.<jupyter_code>random.seed(31)
test(max_weight = 1000)
random.seed(31)
test(max_weight = 10000)<jupyter_output>Algorithm generated isomorphic graph in  94.0 % cases
Algorithm run correctly in  100.0 % cases
{'fraction_non_alphanumeric': 0.13012836647369747, 'fraction_numerical': 0.027183488547696956, 'mean_word_length': 5.590381426202322, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '113764', 'license': 'MIT', 'n_tokens_mistral': 1497, 'n_tokens_neox': 1392, 'n_words': 268, 'path': 'test/cpp_unit_tests.ipynb', 'repo_name': 'Delebrith/prim-alg', 'size': '3973'}