heapless_graphs 0.2.3

Implementation of composable graphs for no_alloc environments
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

// SPDX-License-Identifier: Apache-2.0

//! Example demonstrating Kruskal's algorithm for finding minimum spanning trees

use heapless_graphs::{
    algorithms::kruskals,
    containers::maps::{staticdict::Dictionary, MapTrait},
    edgelist::edge_list::EdgeList,
    edges::EdgeValueStruct,
};

fn main() {
    println!("Kruskal's Algorithm - Minimum Spanning Tree");
    println!("==========================================");

    // Create a weighted graph representing a network of cities:
    //
    //     A(0) ---- 4 ---- B(1)
    //      |               |
    //      2               1
    //      |               |
    //     C(2) ---- 5 ---- D(3)
    //      |               |
    //      3               6
    //      |               |
    //     E(4) ---- 7 ---- F(5)
    //
    let edge_data = EdgeValueStruct([
        (0usize, 1usize, 4i32), // A-B weight 4
        (0, 2, 2),              // A-C weight 2
        (1, 3, 1),              // B-D weight 1
        (2, 3, 5),              // C-D weight 5
        (2, 4, 3),              // C-E weight 3
        (3, 5, 6),              // D-F weight 6
        (4, 5, 7),              // E-F weight 7
    ]);
    let graph = EdgeList::<16, _, _>::new(edge_data);

    // Set up data structures for Kruskal's algorithm
    let mut edge_storage = [(0usize, 0usize, 0i32); 32]; // Buffer for sorting edges
    let parent = Dictionary::<usize, usize, 16>::new(); // Union-find parent map
    let mut mst = [(0usize, 0usize, 0i32); 16]; // Output buffer for MST

    println!("Original graph edges:");
    println!("  A(0) - B(1): weight 4");
    println!("  A(0) - C(2): weight 2");
    println!("  B(1) - D(3): weight 1");
    println!("  C(2) - D(3): weight 5");
    println!("  C(2) - E(4): weight 3");
    println!("  D(3) - F(5): weight 6");
    println!("  E(4) - F(5): weight 7");
    println!();

    // Run Kruskal's algorithm
    match kruskals(&graph, &mut edge_storage, parent, &mut mst) {
        Ok(result) => {
            println!("Minimum Spanning Tree found!");
            println!("MST edges (in order found):");

            let city_names = ["A", "B", "C", "D", "E", "F"];
            let mut total_weight = 0;

            for (i, &(u, v, weight)) in result.iter().enumerate() {
                println!(
                    "  {}: {} - {} (weight: {})",
                    i + 1,
                    city_names[u],
                    city_names[v],
                    weight
                );
                total_weight += weight;
            }

            println!();
            println!("Total MST weight: {}", total_weight);
            println!("Number of edges in MST: {}", result.len());

            // Verify MST properties
            let num_nodes = 6;
            if result.len() == num_nodes - 1 {
                println!(
                    "✓ MST has correct number of edges (n-1 = {})",
                    num_nodes - 1
                );
            } else {
                println!("✗ MST has incorrect number of edges");
            }

            println!();
            println!("Visual representation of MST:");
            println!("     A(0) ---- 4 ---- B(1)");
            println!("      |               |");
            println!("      2               1");
            println!("      |               |");
            println!("     C(2)             D(3)");
            println!("      |");
            println!("      3");
            println!("      |");
            println!("     E(4)             F(5)");
            println!();
            println!("(F(5) is connected via D(3) with edge D-F weight 6)");
        }
        Err(e) => {
            println!("Kruskal's algorithm failed: {:?}", e);
        }
    }

    println!();
    println!("=== Testing with Disconnected Graph ===");

    // Test with a disconnected graph (two separate components)
    let disconnected_data = EdgeValueStruct([
        (0usize, 1usize, 10i32), // Component 1: A-B
        (1, 2, 15),              // Component 1: B-C
        (3, 4, 20),              // Component 2: D-E
        (4, 5, 25),              // Component 2: E-F
    ]);
    let disconnected_graph = EdgeList::<16, _, _>::new(disconnected_data);

    let mut edge_storage2 = [(0usize, 0usize, 0i32); 32];
    let parent2 = Dictionary::<usize, usize, 16>::new();
    let mut mst2 = [(0usize, 0usize, 0i32); 16];

    match kruskals(&disconnected_graph, &mut edge_storage2, parent2, &mut mst2) {
        Ok(result) => {
            println!("Minimum Spanning Forest found (disconnected graph):");
            let city_names = ["A", "B", "C", "D", "E", "F"];
            let mut total_weight = 0;

            for &(u, v, weight) in result {
                println!(
                    "  {} - {} (weight: {})",
                    city_names[u], city_names[v], weight
                );
                total_weight += weight;
            }

            println!("Total forest weight: {}", total_weight);
            println!(
                "Note: For disconnected graphs, Kruskal's produces a minimum spanning forest."
            );
        }
        Err(e) => {
            println!("Algorithm failed on disconnected graph: {:?}", e);
        }
    }
}