cairo-lang-utils 2.18.0

General utilities for the Cairo compiler project.
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

use std::collections::HashSet;

use cairo_lang_test_utils::test;
use itertools::chain;
use test_case::test_case;

use super::GraphNode;
use crate::graph_algos::strongly_connected_components::compute_scc;

#[derive(PartialEq, Eq, Hash, Clone)]
struct IntegerNode {
    id: usize,
    /// The neighbors of each node.
    graph: Vec<Vec<usize>>,
}
impl GraphNode for IntegerNode {
    type NodeId = usize;

    fn get_neighbors(&self) -> Vec<Self> {
        self.graph[self.id]
            .iter()
            .map(|neighbor_id| IntegerNode { id: *neighbor_id, graph: self.graph.clone() })
            .collect()
    }

    fn get_id(&self) -> Self::NodeId {
        self.id
    }
}

#[test]
fn test_short_list() {
    let graph = vec![/* 0: */ vec![1], /* 1: */ vec![]];

    let scc = HashSet::<usize>::from_iter(compute_scc(&IntegerNode { id: 0, graph }));
    assert_eq!(scc, HashSet::from([0]));
}

#[test]
fn test_list() {
    // Nodes 0 to 9 have only one neighbor (i -> i + 1), and 10 is a leaf.
    let mut graph: Vec<Vec<usize>> = (0..10).map(|id| vec![id + 1]).collect();
    graph.push(vec![]);

    let scc = HashSet::<usize>::from_iter(compute_scc(&IntegerNode { id: 0, graph }));
    assert_eq!(scc, HashSet::from([0]));
}

#[test]
fn test_cycle() {
    // Each node has only one neighbor. i -> i + 1 for i = 0...8, and 9 -> 0.
    let graph: Vec<Vec<usize>> = (0..10).map(|id| vec![(id + 1) % 10]).collect();

    let scc = HashSet::<usize>::from_iter(compute_scc(&IntegerNode { id: 0, graph }));
    assert_eq!(scc, HashSet::from_iter(0..10));
}

#[test]
fn test_mesh() {
    // Each node has edges to all other nodes.
    let graph = (0..5).map(|i| (0..5).filter(|j| *j != i).collect::<Vec<usize>>()).collect();

    let scc = HashSet::<usize>::from_iter(compute_scc(&IntegerNode { id: 0, graph }));
    assert_eq!(scc, HashSet::from_iter(0..5));
}

#[test]
fn test_list_with_back_edges() {
    let graph = vec![
        // 0:
        vec![1],
        // 1:
        vec![2],
        // 2:
        vec![0, 3],
        // 3:
        vec![1],
    ];

    let scc = HashSet::<usize>::from_iter(compute_scc(&IntegerNode { id: 0, graph }));
    assert_eq!(scc, HashSet::from_iter(0..4));
}

#[test]
fn test_root_points_to_cycle() {
    // 0 to 9 form a cycle.
    let mut graph: Vec<Vec<usize>> = (0..10).map(|id| vec![(id + 1) % 10]).collect();
    // And 10 (the root) has and edge to 0.
    graph.push(/* 10: */ vec![0]);

    // Note 10 is used as a root.
    let scc = HashSet::<usize>::from_iter(compute_scc(&IntegerNode { id: 10, graph }));
    assert_eq!(scc, HashSet::from([10]));
}

#[test_case(true; "root_in_first_cycle")]
#[test_case(false; "root_in_second_cycle")]
fn test_connected_cycles(root_in_first_cycle: bool) {
    // 0 to 4 form one cycle and 5 to 9 form another cycle.
    let mut graph: Vec<Vec<usize>> =
        chain!((0..5).map(|id| vec![(id + 1) % 5]), (0..5).map(|id| vec![5 + (id + 1) % 5]))
            .collect();

    // Add an edge between 4 and 5 to connect the cycles. Determine the direction according to
    // root_in_first_cycle.
    if root_in_first_cycle {
        graph[4].push(5);
    } else {
        graph[5].push(4);
    }

    let scc = HashSet::<usize>::from_iter(compute_scc(&IntegerNode { id: 0, graph }));
    assert_eq!(scc, HashSet::from_iter(0..5));
}

#[test]
fn test_tangent_cycles() {
    // 0 to 3 form one cycle and 3 to 6 form another cycle. Note 3 is in both.
    // 0 -> 1 -> 2 ->  3  -> 4 -> 6
    // ^______________| ^_________|
    let graph: Vec<Vec<usize>> = chain!(
        (0..3).map(|id| vec![id + 1]),
        // 3:
        vec![vec![0, 4]].into_iter(),
        (0..3).map(|id| vec![3 + (id + 2) % 4])
    )
    .collect();

    let scc = HashSet::<usize>::from_iter(compute_scc(&IntegerNode { id: 0, graph }));
    assert_eq!(scc, HashSet::from_iter(0..7));
}