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

// SPDX-License-Identifier: Apache-2.0

//! Graph transposition demonstration
//!
//! This example demonstrates how to use the graph transposition algorithm
//! to reverse the direction of all edges in a directed graph.

use heapless_graphs::{
    algorithms::{transpose_graph, transpose_graph_inplace},
    edgelist::edge_list::EdgeList,
    graph::Graph,
};

fn main() {
    println!("Graph Transposition Demo");
    println!("========================");

    // Example 1: Dependency Analysis
    println!("\n1. Software Dependency Analysis");
    println!("Original dependencies: A->B, B->C, A->C");

    // Create a dependency graph: A depends on B, B depends on C, A depends on C
    let dependencies = EdgeList::<8, usize, _>::new([(0, 1), (1, 2), (0, 2)]); // A=0, B=1, C=2
    let mut reverse_deps = EdgeList::<8, usize, [Option<(usize, usize)>; 8]>::new([None; 8]);

    transpose_graph(&dependencies, &mut reverse_deps).unwrap();

    println!("Reverse dependencies (who depends on whom):");
    for (from, to) in reverse_deps.iter_edges().unwrap() {
        let from_name = match from {
            0 => "A",
            1 => "B",
            2 => "C",
            _ => "?",
        };
        let to_name = match to {
            0 => "A",
            1 => "B",
            2 => "C",
            _ => "?",
        };
        println!("  {} is depended on by {}", from_name, to_name);
    }

    // Example 2: Social Network
    println!("\n2. Social Network Analysis");
    println!("Original follows: Alice->Bob, Bob->Charlie, Alice->Charlie");

    let follows = EdgeList::<8, usize, _>::new([(0, 1), (1, 2), (0, 2)]); // Alice=0, Bob=1, Charlie=2
    let mut followers = EdgeList::<8, usize, [Option<(usize, usize)>; 8]>::new([None; 8]);

    transpose_graph(&follows, &mut followers).unwrap();

    println!("Follower relationships:");
    for (followed, follower) in followers.iter_edges().unwrap() {
        let followed_name = match followed {
            0 => "Alice",
            1 => "Bob",
            2 => "Charlie",
            _ => "?",
        };
        let follower_name = match follower {
            0 => "Alice",
            1 => "Bob",
            2 => "Charlie",
            _ => "?",
        };
        println!("  {} is followed by {}", followed_name, follower_name);
    }

    // Example 3: In-place transposition (atomic)
    println!("\n3. In-place Transposition (Atomic)");
    let mut graph = EdgeList::<8, usize, [Option<(usize, usize)>; 8]>::new([
        Some((0, 1)),
        Some((1, 2)),
        Some((2, 0)),
        None,
        None,
        None,
        None,
        None,
    ]);
    let mut buffer = [(0usize, 0usize); 8];

    println!("Before transpose:");
    for (from, to) in graph.iter_edges().unwrap() {
        println!("  {} -> {}", from, to);
    }

    // Safe version with validation (atomic) - either all changes succeed or graph remains unchanged
    transpose_graph_inplace(&mut graph, &mut buffer, true).unwrap();

    println!("After transpose:");
    for (from, to) in graph.iter_edges().unwrap() {
        println!("  {} -> {}", from, to);
    }

    // Example 4: Fast in-place transposition (no validation)
    println!("\n4. Fast In-place Transposition (No Validation)");
    let mut graph = EdgeList::<8, usize, [Option<(usize, usize)>; 8]>::new([
        Some((0, 1)),
        Some((1, 2)),
        Some((2, 0)),
        None,
        None,
        None,
        None,
        None,
    ]);
    let mut buffer = [(0usize, 0usize); 8];

    println!("Before fast transpose:");
    for (from, to) in graph.iter_edges().unwrap() {
        println!("  {} -> {}", from, to);
    }

    // Fast version without validation - maximum performance but no atomicity guarantee
    transpose_graph_inplace(&mut graph, &mut buffer, false).unwrap();

    println!("After fast transpose:");
    for (from, to) in graph.iter_edges().unwrap() {
        println!("  {} -> {}", from, to);
    }
}