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.

12

///

13

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

14

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

15

///     - reverse: If true, the topological ordering is reversed, i.e. successors before the incoming state.

16

800

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

17

800

where

18

800

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

19

800

    L: LTS,

20

21

    // The resulting order of states.

22

800

    let mut stack = Vec::new();

23

24

800

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

25

800

    let mut depth_stack = Vec::new();

26

800

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

27

28

6688

    for state_index in lts.iter_states() {

29

6688

        if marks[state_index].is_none()

30

6562

            && !sort_topological_visit(

31

6562

                lts,

32

6562

                &filter,

33

6562

                state_index,

34

6562

                &mut depth_stack,

35

6562

                &mut marks,

36

6562

                &mut visited,

37

6562

                &mut stack,

38

6562

39

40

25

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

41

25

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

42

6663

43

44

45

775

    if !reverse {

46

175

        stack.reverse();

47

600

48

775

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

49

50

    // Turn the stack into a permutation.

51

775

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

52

6663

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

53

6663

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

54

6663

55

56

775

    debug_assert!(

57

31852

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

58

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

59

);

60

61

775

    Ok(reorder)

62

800

63

64

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

65

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

66

enum Mark {

67

    Temporary,

68

    Permanent,

69

70

71

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

72

///

73

/// Returns false if a cycle is detected.

74

6562

fn sort_topological_visit<F>(

75

6562

    lts: &impl LTS,

76

6562

    filter: &F,

77

6562

    state_index: StateIndex,

78

6562

    depth_stack: &mut Vec<StateIndex>,

79

6562

    marks: &mut [Option<Mark>],

80

6562

    visited: &mut [bool],

81

6562

    stack: &mut Vec<StateIndex>,

82

6562

) -> bool

83

6562

where

84

6562

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

85

86

    // Perform a depth first search.

87

6562

    depth_stack.push(state_index);

88

89

19920

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

90

13383

        match marks[state] {

91

            None => {

92

6720

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

93

6720

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

94

6720

                for transition in lts

95

6720

                    .outgoing_transitions(state)

96

13101

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

97

98

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

99

5283

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

100

25

                        return false;

101

5258

102

5258

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

103

184

                        depth_stack.push(transition.to);

104

5074

105

106

107

6663

            Some(Mark::Temporary) => {

108

6663

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

109

6663

                visited[state] = true;

110

6663

                stack.push(state);

111

6663

112

            Some(Mark::Permanent) => {}

113

114

115

116

6537

    true

117

6562

118

119

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

120

850

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

121

850

where

122

850

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

123

850

    P: Fn(StateIndex) -> StateIndex,

124

125

850

    debug_assert!(is_valid_permutation(

126

20592

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

127

850

        lts.num_of_states()

128

));

129

130

    // Check that each vertex appears before its successors.

131

6864

    for state_index in lts.iter_states() {

132

6864

        let state_order = permutation(state_index);

133

6864

        for transition in lts

134

6864

            .outgoing_transitions(state_index)

135

13174

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

136

137

5356

            if reverse {

138

4286

                if state_order <= permutation(transition.to) {

139

                    return false;

140

4286

141

1070

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

142

                return false;

143

1070

144

145

146

147

850

    true

148

850

149

150

#[cfg(test)]

151

mod tests {

152

153

    use merc_io::DumpFiles;

154

    use merc_lts::LabelledTransitionSystem;

155

    use merc_lts::random_lts;

156

    use merc_lts::write_aut;

157

    use merc_utilities::random_test;

158

    use rand::seq::SliceRandom;

159

    use test_log::test;

160

161

    use super::*;

162

163

    #[test]

164

    fn test_random_sort_topological_with_cycles() {

165

100

        random_test(100, |rng| {

166

100

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

167

100

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

168

960

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

169

25

170

100

});

171

172

173

    #[test]

174

    fn test_random_reorder_states() {

175

100

        random_test(100, |rng| {

176

100

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

177

178

100

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

179

100

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

180

181

            // Generate a random permutation.

182

100

            let mut rng = rand::rng();

183

100

            let order: Vec<StateIndex> = {

184

100

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

185

100

                order.shuffle(&mut rng);

186

100

                order

187

};

188

189

386

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

190

100

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

191

192

100

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

193

100

});

194

195