Grcov report - sort_topological.rs

1

#![forbid(unsafe_code)]

2

3

use log::trace;

4

5

use merc_lts::LTS;

6

use merc_lts::LabelIndex;

7

use merc_lts::StateIndex;

8

use merc_utilities::MercError;

9

use merc_utilities::is_valid_permutation;

10

11

/// Returns a topological ordering of the states of the given LTS, ensuring that `s` occurs before

12

/// `t` if there is a transition from `s` to `t` that satisfies the filter.

13

///

14

/// An error is returned if the LTS contains a cycle.

15

///     - filter: Only transitions satisfying the filter are considered part of the graph.

16

///     - reverse: If true, the topological ordering is reversed, i.e. `t` before the state `s`.

17

5303

pub fn sort_topological<F, L>(lts: &L, filter: F, reverse: bool) -> Result<Vec<StateIndex>, MercError>

18

5303

where

19

5303

    F: Fn(LabelIndex, StateIndex) -> bool,

20

5303

    L: LTS,

21

22

    // The resulting order of states.

23

5303

    let mut stack = Vec::new();

24

25

5303

    let mut visited = vec![false; lts.num_of_states()];

26

5303

    let mut depth_stack = Vec::new();

27

5303

    let mut marks = vec![None; lts.num_of_states()];

28

29

1643161

    for state_index in lts.iter_states() {

30

1643161

        if marks[state_index].is_none()

31

1638384

            && !sort_topological_visit(

32

1638384

                lts,

33

1638384

                &filter,

34

1638384

                state_index,

35

1638384

                &mut depth_stack,

36

1638384

                &mut marks,

37

1638384

                &mut visited,

38

1638384

                &mut stack,

39

1638384

40

41

91

            trace!("There is a cycle from state {state_index} on path {stack:?}");

42

91

            return Err("Labelled transition system contains a cycle".into());

43

1643070

44

45

46

5212

    if !reverse {

47

109

        stack.reverse();

48

5103

49

5212

    trace!("Topological order: {stack:?}");

50

51

    // Turn the stack into a permutation.

52

5212

    let mut reorder = vec![StateIndex::new(0); lts.num_of_states()];

53

1640958

    for (i, &state_index) in stack.iter().enumerate() {

54

1640958

        reorder[state_index] = StateIndex::new(i);

55

1640958

56

57

5212

    debug_assert!(

58

7118396

        is_topologically_sorted(lts, filter, |i| reorder[i], reverse),

59

        "The permutation {reorder:?} is not a valid topological ordering for the states of the given LTS"

60

);

61

62

5212

    Ok(reorder)

63

5303

64

65

// The mark of a state in the depth first search.

66

#[derive(Debug, Clone, Copy, PartialEq, Eq)]

67

enum Mark {

68

    Temporary,

69

    Permanent,

70

71

72

/// Visits the given state in a depth first search.

73

///

74

/// Returns false if a cycle is detected.

75

1638384

fn sort_topological_visit<F, L>(

76

1638384

    lts: &L,

77

1638384

    filter: &F,

78

1638384

    state_index: StateIndex,

79

1638384

    depth_stack: &mut Vec<StateIndex>,

80

1638384

    marks: &mut [Option<Mark>],

81

1638384

    visited: &mut [bool],

82

1638384

    stack: &mut Vec<StateIndex>,

83

1638384

) -> bool

84

1638384

where

85

1638384

    F: Fn(LabelIndex, StateIndex) -> bool,

86

1638384

    L: LTS,

87

88

    // Perform a depth first search.

89

1638384

    depth_stack.push(state_index);

90

91

4943231

    while let Some(state) = depth_stack.pop() {

92

3304938

        match marks[state] {

93

            None => {

94

1652998

                marks[state] = Some(Mark::Temporary);

95

1652998

                depth_stack.push(state); // Re-add to stack to mark as permanent later

96

1652998

                for transition in lts

97

1652998

                    .outgoing_transitions(state)

98

1688712

                    .filter(|transition| state != transition.to && filter(transition.label, transition.to))

99

100

                    // If it was marked temporary, then a cycle is detected.

101

566563

                    if marks[transition.to] == Some(Mark::Temporary) {

102

91

                        return false;

103

566472

104

566472

                    if marks[transition.to].is_none() {

105

14957

                        depth_stack.push(transition.to);

106

551515

107

108

109

1651913

            Some(Mark::Temporary) => {

110

1651913

                marks[state] = Some(Mark::Permanent);

111

1651913

                visited[state] = true;

112

1651913

                stack.push(state);

113

1651913

114

27

            Some(Mark::Permanent) => {}

115

116

117

118

1638293

    true

119

1638384

120

121

/// Returns true if the given permutation is a topological ordering of the states of the given LTS.

122

5221

fn is_topologically_sorted<F, P, L>(lts: &L, filter: F, permutation: P, reverse: bool) -> bool

123

5221

where

124

5221

    F: Fn(LabelIndex, StateIndex) -> bool,

125

5221

    P: Fn(StateIndex) -> StateIndex,

126

5221

    L: LTS,

127

128

5221

    debug_assert!(is_valid_permutation(

129

4949874

        |i| permutation(StateIndex::new(i)).value(),

130

5221

        lts.num_of_states()

131

));

132

133

    // Check that each vertex appears before its successors.

134

1649958

    for state_index in lts.iter_states() {

135

1649958

        let state_order = permutation(state_index);

136

1649958

        for transition in lts

137

1649958

            .outgoing_transitions(state_index)

138

1685596

            .filter(|transition| state_index != transition.to && filter(transition.label, transition.to))

139

140

563448

            if reverse {

141

512346

                if state_order <= permutation(transition.to) {

142

                    return false;

143

512346

144

51102

            } else if state_order >= permutation(transition.to) {

145

                return false;

146

51102

147

148

149

150

5221

    true

151

5221

152

153

#[cfg(test)]

154

mod tests {

155

156

    use merc_io::DumpFiles;

157

    use merc_lts::LabelledTransitionSystem;

158

    use merc_lts::random_lts;

159

    use merc_lts::write_aut;

160

    use merc_utilities::random_test;

161

    use rand::seq::SliceRandom;

162

    use test_log::test;

163

164

    use super::LTS;

165

    use super::StateIndex;

166

    use super::is_topologically_sorted;

167

    use super::sort_topological;

168

169

    #[test]

170

    fn test_random_sort_topological_with_cycles() {

171

100

        random_test(100, |rng| {

172

100

            let lts = random_lts::<String, _>(rng, 1000, 3);

173

100

            if let Ok(order) = sort_topological(&lts, |_, _| true, false) {

174

44884

                assert!(is_topologically_sorted(&lts, |_, _| true, |i| order[i], false))

175

91

176

100

});

177

178

179

    #[test]

180

    fn test_random_reorder_states() {

181

100

        random_test(100, |rng| {

182

100

            let mut files = DumpFiles::new("test_random_reorder_states");

183

184

100

            let lts = random_lts::<String, _>(rng, 1000, 3);

185

100

            files.dump("input.aut", |f| write_aut(f, &lts)).unwrap();

186

187

            // Generate a random permutation.

188

100

            let mut rng = rand::rng();

189

100

            let order: Vec<StateIndex> = {

190

100

                let mut order: Vec<StateIndex> = (0..lts.num_of_states()).map(StateIndex::new).collect();

191

100

                order.shuffle(&mut rng);

192

100

                order

193

};

194

195

200257

            let new_lts = LabelledTransitionSystem::new_from_permutation(lts.clone(), |i| order[i]);

196

100

            files.dump("reordered.aut", |f| write_aut(f, &new_lts)).unwrap();

197

198

100

            assert_eq!(new_lts.num_of_labels(), lts.num_of_labels());

199

100

});

200

201