rust_algorithms/graph/
core.rs

1//! Grafning o'zi: qo'shnilik ro'yxati asosidagi ifoda.
2
3/// Qirra: qayerga va qancha "narx" bilan.
4#[derive(Debug, Clone, Copy, PartialEq, Eq)]
5pub struct Edge {
6    /// Qirra olib boradigan tugun.
7    pub to: usize,
8    /// Og'irlik (masofa, narx, vaqt…). Og'irliksiz grafda 1.
9    pub weight: i64,
10}
11
12/// Qo'shnilik ro'yxati (adjacency list) asosidagi graf.
13///
14/// Tugunlar `0..n` butun sonlar bilan raqamlanadi. Nomlar bilan ishlash kerak bo'lsa,
15/// `HashMap<String, usize>` orqali nomni indeksga bog'lang.
16///
17/// # Misol
18/// ```
19/// use rust_algorithms::graph::Graph;
20///
21/// // yo'naltirilmagan, og'irlikli graf
22/// let mut g = Graph::new_undirected(4);
23/// g.add_edge(0, 1, 5);
24/// g.add_edge(0, 2, 2);
25/// g.add_edge(2, 3, 1);
26///
27/// assert_eq!(g.node_count(), 4);
28/// assert_eq!(g.edge_count(), 3);
29/// assert_eq!(g.degree(0), 2);
30/// assert!(g.has_edge(1, 0)); // yo'naltirilmagan — ikki tomonlama
31/// ```
32#[derive(Debug, Clone)]
33pub struct Graph {
34    adj: Vec<Vec<Edge>>,
35    directed: bool,
36    edge_count: usize,
37}
38
39impl Graph {
40    /// `n` tugunli **yo'naltirilmagan** graf (qirra ikki tomonga ham ishlaydi).
41    pub fn new_undirected(n: usize) -> Self {
42        Self {
43            adj: vec![Vec::new(); n],
44            directed: false,
45            edge_count: 0,
46        }
47    }
48
49    /// `n` tugunli **yo'naltirilgan** graf (qirra faqat bir tomonga).
50    pub fn new_directed(n: usize) -> Self {
51        Self {
52            adj: vec![Vec::new(); n],
53            directed: true,
54            edge_count: 0,
55        }
56    }
57
58    /// Og'irlikli qirra qo'shadi.
59    ///
60    /// # Panics
61    /// `from` yoki `to` tugun sonidan katta bo'lsa.
62    pub fn add_edge(&mut self, from: usize, to: usize, weight: i64) {
63        assert!(
64            from < self.adj.len() && to < self.adj.len(),
65            "tugun indeksi chegaradan tashqarida"
66        );
67        self.adj[from].push(Edge { to, weight });
68        if !self.directed && from != to {
69            self.adj[to].push(Edge { to: from, weight });
70        }
71        self.edge_count += 1;
72    }
73
74    /// Og'irliksiz qirra (og'irligi 1).
75    pub fn add_unweighted_edge(&mut self, from: usize, to: usize) {
76        self.add_edge(from, to, 1);
77    }
78
79    /// Tugunning qo'shnilari.
80    pub fn neighbors(&self, node: usize) -> &[Edge] {
81        &self.adj[node]
82    }
83
84    /// `from → to` qirra bormi?
85    pub fn has_edge(&self, from: usize, to: usize) -> bool {
86        self.adj[from].iter().any(|e| e.to == to)
87    }
88
89    /// Tugunning darajasi (chiquvchi qirralar soni).
90    pub fn degree(&self, node: usize) -> usize {
91        self.adj[node].len()
92    }
93
94    /// Tugunlar soni.
95    pub fn node_count(&self) -> usize {
96        self.adj.len()
97    }
98
99    /// Qirralar soni (yo'naltirilmaganda juftlik bir marta sanaladi).
100    pub fn edge_count(&self) -> usize {
101        self.edge_count
102    }
103
104    /// Graf yo'naltirilganmi?
105    pub fn is_directed(&self) -> bool {
106        self.directed
107    }
108
109    /// Barcha qirralar `(from, to, weight)` ko'rinishida.
110    /// Yo'naltirilmagan grafda har juftlik **bir marta** (from < to) qaytadi.
111    pub fn all_edges(&self) -> Vec<(usize, usize, i64)> {
112        let mut out = Vec::with_capacity(self.edge_count);
113        for (from, qirralar) in self.adj.iter().enumerate() {
114            for e in qirralar {
115                if self.directed || from <= e.to {
116                    out.push((from, e.to, e.weight));
117                }
118            }
119        }
120        out
121    }
122
123    /// Qirralar yo'nalishi teskari qilingan yangi graf (yo'naltirilgan graflar uchun).
124    ///
125    /// Kosaraju algoritmi va "kim menga bog'liq?" tipidagi savollarda kerak.
126    pub fn reversed(&self) -> Graph {
127        let mut g = if self.directed {
128            Graph::new_directed(self.node_count())
129        } else {
130            return self.clone();
131        };
132        for (from, qirralar) in self.adj.iter().enumerate() {
133            for e in qirralar {
134                g.add_edge(e.to, from, e.weight);
135            }
136        }
137        g
138    }
139}
140
141#[cfg(test)]
142mod tests {
143    use super::*;
144
145    #[test]
146    fn yonaltirilmagan_ikki_tomonlama() {
147        let mut g = Graph::new_undirected(3);
148        g.add_edge(0, 1, 7);
149        assert!(g.has_edge(0, 1));
150        assert!(g.has_edge(1, 0));
151        assert_eq!(g.degree(0), 1);
152        assert_eq!(g.degree(1), 1);
153        assert_eq!(g.edge_count(), 1);
154    }
155
156    #[test]
157    fn yonaltirilgan_bir_tomonlama() {
158        let mut g = Graph::new_directed(3);
159        g.add_edge(0, 1, 1);
160        assert!(g.has_edge(0, 1));
161        assert!(!g.has_edge(1, 0));
162        assert_eq!(g.degree(1), 0);
163    }
164
165    #[test]
166    fn barcha_qirralar() {
167        let mut g = Graph::new_undirected(4);
168        g.add_edge(0, 1, 5);
169        g.add_edge(2, 3, 2);
170        let mut e = g.all_edges();
171        e.sort();
172        assert_eq!(e, vec![(0, 1, 5), (2, 3, 2)]);
173    }
174
175    #[test]
176    fn teskarilash() {
177        let mut g = Graph::new_directed(3);
178        g.add_edge(0, 1, 1);
179        g.add_edge(1, 2, 2);
180        let r = g.reversed();
181        assert!(r.has_edge(1, 0));
182        assert!(r.has_edge(2, 1));
183        assert!(!r.has_edge(0, 1));
184    }
185
186    #[test]
187    fn ozini_ozi_bogash() {
188        let mut g = Graph::new_undirected(2);
189        g.add_edge(0, 0, 1); // sirtmoq (self-loop)
190        assert_eq!(g.degree(0), 1);
191        assert!(g.has_edge(0, 0));
192    }
193}
rust_algorithms/graph/core.rs

rust_algorithms/graph/
core.rs
