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

1100

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

18

1100

where

19

1100

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

20

1100

    L: LTS,

21

22

    // The resulting order of states.

23

1100

    let mut stack = Vec::new();

24

25

1100

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

26

1100

    let mut depth_stack = Vec::new();

27

1100

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

28

29

9179

    for state_index in lts.iter_states() {

30

9179

        if marks[state_index].is_none()

31

8982

            && !sort_topological_visit(

32

8982

                lts,

33

8982

                &filter,

34

8982

                state_index,

35

8982

                &mut depth_stack,

36

8982

                &mut marks,

37

8982

                &mut visited,

38

8982

                &mut stack,

39

8982

40

41

16

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

42

16

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

43

9163

44

45

46

1084

    if !reverse {

47

184

        stack.reverse();

48

900

49

1084

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

50

51

    // Turn the stack into a permutation.

52

1084

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

53

9163

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

54

9163

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

55

9163

56

57

1084

    debug_assert!(

58

44237

        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

1084

    Ok(reorder)

63

1100

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

8982

fn sort_topological_visit<F>(

76

8982

    lts: &impl LTS,

77

8982

    filter: &F,

78

8982

    state_index: StateIndex,

79

8982

    depth_stack: &mut Vec<StateIndex>,

80

8982

    marks: &mut [Option<Mark>],

81

8982

    visited: &mut [bool],

82

8982

    stack: &mut Vec<StateIndex>,

83

8982

) -> bool

84

8982

where

85

8982

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

86

87

    // Perform a depth first search.

88

8982

    depth_stack.push(state_index);

89

90

27325

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

91

18359

        match marks[state] {

92

            None => {

93

9196

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

94

9196

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

95

9196

                for transition in lts

96

9196

                    .outgoing_transitions(state)

97

16972

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

98

99

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

100

7626

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

101

16

                        return false;

102

7610

103

7610

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

104

222

                        depth_stack.push(transition.to);

105

7388

106

107

108

9163

            Some(Mark::Temporary) => {

109

9163

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

110

9163

                visited[state] = true;

111

9163

                stack.push(state);

112

9163

113

            Some(Mark::Permanent) => {}

114

115

116

117

8966

    true

118

8982

119

120

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

121

1168

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

122

1168

where

123

1168

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

124

1168

    P: Fn(StateIndex) -> StateIndex,

125

126

1168

    debug_assert!(is_valid_permutation(

127

28332

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

128

1168

        lts.num_of_states()

129

));

130

131

    // Check that each vertex appears before its successors.

132

9444

    for state_index in lts.iter_states() {

133

9444

        let state_order = permutation(state_index);

134

9444

        for transition in lts

135

9444

            .outgoing_transitions(state_index)

136

17196

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

137

138

7850

            if reverse {

139

6557

                if state_order <= permutation(transition.to) {

140

                    return false;

141

6557

142

1293

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

143

                return false;

144

1293

145

146

147

148

1168

    true

149

1168

150

151

#[cfg(test)]

152

mod tests {

153

154

    use merc_io::DumpFiles;

155

    use merc_lts::LabelledTransitionSystem;

156

    use merc_lts::random_lts;

157

    use merc_lts::write_aut;

158

    use merc_utilities::random_test;

159

    use rand::seq::SliceRandom;

160

    use test_log::test;

161

162

    use super::*;

163

164

    #[test]

165

    fn test_random_sort_topological_with_cycles() {

166

100

        random_test(100, |rng| {

167

100

            let lts = random_lts(rng, 10, 3, 2);

168

100

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

169

1389

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

170

16

171

100

});

172

173

174

    #[test]

175

    fn test_random_reorder_states() {

176

100

        random_test(100, |rng| {

177

100

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

178

179

100

            let lts = random_lts(rng, 10, 3, 2);

180

100

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

181

182

            // Generate a random permutation.

183

100

            let mut rng = rand::rng();

184

100

            let order: Vec<StateIndex> = {

185

100

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

186

100

                order.shuffle(&mut rng);

187

100

                order

188

};

189

190

397

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

191

100

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

192

193

100

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

194

100

});

195

196