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

2700

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

18

2700

where

19

2700

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

20

2700

    L: LTS,

21

22

    // The resulting order of states.

23

2700

    let mut stack = Vec::new();

24

25

2700

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

26

2700

    let mut depth_stack = Vec::new();

27

2700

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

28

29

431526

    for state_index in lts.iter_states() {

30

431526

        if marks[state_index].is_none()

31

431389

            && !sort_topological_visit(

32

431389

                lts,

33

431389

                &filter,

34

431389

                state_index,

35

431389

                &mut depth_stack,

36

431389

                &mut marks,

37

431389

                &mut visited,

38

431389

                &mut stack,

39

431389

40

41

20

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

42

20

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

43

431506

44

45

46

2680

    if !reverse {

47

180

        stack.reverse();

48

2500

49

2680

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

50

51

    // Turn the stack into a permutation.

52

2680

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

53

431506

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

54

431506

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

55

431506

56

57

2680

    debug_assert!(

58

1824395

        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

2680

    Ok(reorder)

63

2700

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

431389

fn sort_topological_visit<F, L>(

76

431389

    lts: &L,

77

431389

    filter: &F,

78

431389

    state_index: StateIndex,

79

431389

    depth_stack: &mut Vec<StateIndex>,

80

431389

    marks: &mut [Option<Mark>],

81

431389

    visited: &mut [bool],

82

431389

    stack: &mut Vec<StateIndex>,

83

431389

) -> bool

84

431389

where

85

431389

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

86

431389

    L: LTS,

87

88

    // Perform a depth first search.

89

431389

    depth_stack.push(state_index);

90

91

1294426

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

92

863057

        match marks[state] {

93

            None => {

94

431551

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

95

431551

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

96

431551

                for transition in lts

97

431551

                    .outgoing_transitions(state)

98

463234

                    .filter(|transition| filter(transition.label, transition.to))

99

100

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

101

98445

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

102

20

                        return false;

103

98425

104

98425

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

105

191

                        depth_stack.push(transition.to);

106

98234

107

108

109

431506

            Some(Mark::Temporary) => {

110

431506

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

111

431506

                visited[state] = true;

112

431506

                stack.push(state);

113

431506

114

            Some(Mark::Permanent) => {}

115

116

117

118

431369

    true

119

431389

120

121

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

122

2760

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

123

2760

where

124

2760

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

125

2760

    P: Fn(StateIndex) -> StateIndex,

126

2760

    L: LTS,

127

128

2760

    debug_assert!(is_valid_permutation(

129

1295169

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

130

2760

        lts.num_of_states()

131

));

132

133

    // Check that each vertex appears before its successors.

134

431723

    for state_index in lts.iter_states() {

135

431723

        let state_order = permutation(state_index);

136

431723

        for transition in lts

137

431723

            .outgoing_transitions(state_index)

138

463337

            .filter(|transition| filter(transition.label, transition.to))

139

140

98548

            if reverse {

141

97283

                if state_order <= permutation(transition.to) {

142

                    return false;

143

97283

144

1265

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

145

                return false;

146

1265

147

148

149

150

2760

    true

151

2760

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(rng, 10, 3, 2);

173

100

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

174

1045

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

175

20

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(rng, 10, 3, 2);

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

566

            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