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

//! Generate the converse of a digraph.
//!
//! The converse of a digraph is a digraph with all arcs reversed.
//!
//! # Examples
//!
//! ```
//! use graaf::{
//!     adjacency_list::Digraph,
//!     gen::Circuit,
//!     op::{
//!         AddArc,
//!         Arcs,
//!         Converse,
//!     },
//! };
//!
//! // 0 -> {1}
//! // 1 -> {2}
//! // 2 -> {3}
//! // 3 -> {0}
//!
//! let digraph = Digraph::circuit(4);
//!
//! // 0 -> {3}
//! // 1 -> {0}
//! // 2 -> {1}
//! // 3 -> {2}
//!
//! let converse = digraph.converse();
//!
//! assert!(converse.arcs().eq([(0, 3), (1, 0), (2, 1), (3, 2)]));
//! ```

/// Generate the converse of a digraph.
///
/// # How do I implement `Converse`?
///
/// Provide an implementation of `converse` that returns a digraph with all
/// arcs reversed.
///
/// ```
/// use {
///     graaf::op::Converse,
///     std::collections::BTreeSet,
/// };
///
/// struct Digraph {
///     arcs: Vec<BTreeSet<usize>>,
/// }
///
/// impl Converse for Digraph {
///     fn converse(&self) -> Self {
///         let order = self.arcs.len();
///         let mut arcs = vec![BTreeSet::<usize>::new(); order];
///
///         for (u, set) in self.arcs.iter().enumerate() {
///             for &v in set {
///                 arcs[v].insert(u);
///             }
///         }
///
///         Self { arcs }
///     }
/// }
///
/// // 0 -> {1}
/// // 1 -> {2}
/// // 2 -> {3}
/// // 3 -> {0}
///
/// let digraph = Digraph {
///     arcs: vec![
///         BTreeSet::from([1]),
///         BTreeSet::from([2]),
///         BTreeSet::from([3]),
///         BTreeSet::from([0]),
///     ],
/// };
///
/// // 0 -> {3}
/// // 1 -> {0}
/// // 2 -> {1}
/// // 3 -> {2}
///
/// let converse = digraph.converse();
///
/// assert_eq!(
///     converse.arcs,
///     vec![
///         BTreeSet::from([3]),
///         BTreeSet::from([0]),
///         BTreeSet::from([1]),
///         BTreeSet::from([2]),
///     ],
/// );
/// ```
pub trait Converse {
    /// Generates the converse of the digraph.
    #[must_use]
    fn converse(&self) -> Self;
}