roaring_graphs/
digraph.rs

1/// Unlike with [`DirectedAcyclicGraph`] data type, it is *not* the case that edges go from smaller
2/// integers to bigger!
3use std::{collections::VecDeque, io::Write};
4
5use proptest::prelude::*;
6use roaring::RoaringBitmap;
7
8use crate::{dag::DirectedAcyclicGraph, TraversableDirectedGraph, Vertex};
9
10pub type BitmapIndex = u32;
11
12/// A mutable, single-threaded directed graph.
13#[derive(Clone)]
14pub struct DirectedGraph {
15    vertex_count: Vertex,
16    adjacency_matrix: RoaringBitmap,
17}
18
19impl std::fmt::Debug for DirectedGraph {
20    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
21        let ones: Vec<(Vertex, Vertex)> = self.iter_edges().collect();
22        write!(
23            f,
24            "DirectedGraph::from_edges_iter({}, vec!{:?}.iter().cloned())",
25            self.get_vertex_count(),
26            ones
27        )?;
28        Ok(())
29    }
30}
31
32impl TraversableDirectedGraph for DirectedGraph {
33    fn extend_with_children(&self, u: Vertex, children: &mut Vec<Vertex>) {
34        self.extend_with_children(u, children)
35    }
36
37    fn extend_with_parents(&self, v: Vertex, parents: &mut Vec<Vertex>) {
38        self.extend_with_parents(v, parents)
39    }
40}
41
42#[inline]
43fn index_from_row_column(i: Vertex, j: Vertex, size: Vertex) -> BitmapIndex {
44    (i * size + j).into()
45}
46
47#[inline]
48fn row_column_from_index(index: BitmapIndex, size: Vertex) -> (Vertex, Vertex) {
49    let row = Vertex::try_from(index / BitmapIndex::from(size)).unwrap();
50    let column = Vertex::try_from(index % BitmapIndex::from(size)).unwrap();
51    (row, column)
52}
53
54impl DirectedGraph {
55    /// Constructs a new graph without any edges having at most `vertex_count` vertices.
56    pub fn new(vertex_count: Vertex) -> Self {
57        Self {
58            vertex_count,
59            adjacency_matrix: RoaringBitmap::new(),
60        }
61    }
62
63    pub fn has_edges(&self) -> bool {
64        !self.adjacency_matrix.is_empty()
65    }
66
67    pub fn from_edges_iter<I>(vertex_count: Vertex, edges: I) -> Self
68    where
69        I: Iterator<Item = (Vertex, Vertex)>,
70    {
71        let mut adjacency_matrix = RoaringBitmap::new();
72        for (from, to) in edges {
73            let index = index_from_row_column(from, to, vertex_count);
74            adjacency_matrix.insert(index);
75        }
76        Self {
77            vertex_count,
78            adjacency_matrix,
79        }
80    }
81
82    pub fn from_dag(dag: &DirectedAcyclicGraph) -> Self {
83        Self::from_edges_iter(
84            dag.get_vertex_count(),
85            dag.iter_edges()
86                .map(|(u, v)| (u, v)),
87        )
88    }
89
90    pub fn get_vertex_count(&self) -> Vertex {
91        self.vertex_count
92    }
93
94    fn index_from_row_column(&self, i: Vertex, j: Vertex) -> BitmapIndex {
95        assert!(i < self.vertex_count);
96        assert!(j < self.vertex_count);
97        index_from_row_column(i, j, self.vertex_count)
98    }
99
100    pub fn iter_edges(&self) -> impl Iterator<Item = (Vertex, Vertex)> + '_ {
101        self.adjacency_matrix.iter().map(|index| row_column_from_index(index, self.vertex_count))
102    }
103
104    pub fn get_edge(&self, parent: Vertex, child: Vertex) -> bool {
105        assert_ne!(parent, child);
106        assert!(parent < self.get_vertex_count());
107        assert!(child < self.get_vertex_count());
108        let index = self.index_from_row_column(parent, child);
109        self.adjacency_matrix.contains(index)
110    }
111
112    pub fn set_edge(&mut self, parent: Vertex, child: Vertex) {
113        assert_ne!(parent, child);
114        assert!(parent < self.get_vertex_count());
115        assert!(child < self.get_vertex_count());
116        let index = self.index_from_row_column(parent, child);
117        self.adjacency_matrix.insert(index);
118    }
119
120    pub fn clear_edge(&mut self, parent: Vertex, child: Vertex) {
121        assert_ne!(parent, child);
122        assert!(parent < self.get_vertex_count());
123        assert!(child < self.get_vertex_count());
124        let index = self.index_from_row_column(parent, child);
125        self.adjacency_matrix.remove(index);
126    }
127
128    /// Returns `None` if the graph has more than connected component or there's no root.
129    pub fn find_tree_root(&self) -> Option<Vertex> {
130        let mut candidates = RoaringBitmap::new();
131        candidates.insert_range(0..u32::from(self.vertex_count));
132        for (_, to) in self.iter_edges() {
133            candidates.remove(to.into());
134        }
135        if candidates.len() != 1 {
136            return None;
137        }
138        let root = Vertex::try_from(candidates.select(0).unwrap()).unwrap();
139        Some(root)
140    }
141
142    /// Pushes vertices `v` at the end of `children` such that there's an edge `(u, v)` in the graph.
143    pub fn extend_with_children(&self, u: Vertex, children: &mut Vec<Vertex>) {
144        assert!(u < self.vertex_count);
145        let mut index = u * self.vertex_count;
146        for v in 0..self.vertex_count {
147            if self.adjacency_matrix.contains(index.into()) {
148                children.push(v);
149            }
150            index += 1;
151        }
152    }
153
154    /// Pushes vertices `u` at the end of `parents` such that there's an edge `(u, v)` in the graph.
155    pub fn extend_with_parents(&self, v: Vertex, parents: &mut Vec<Vertex>) {
156        assert!(v < self.vertex_count);
157        let mut index = v;
158        for u in 0..self.vertex_count {
159            if self.adjacency_matrix.contains(index.into()) {
160                parents.push(u);
161            }
162            index += self.vertex_count;
163        }
164    }
165
166    /// Visit all vertices reachable from `vertex` in a depth-first-search (DFS)
167    /// order.
168    pub fn iter_descendants_dfs(&self, start_vertex: Vertex) -> Box<dyn Iterator<Item = Vertex> + '_> {
169        let iter = DfsDescendantsIterator {
170            digraph: self,
171            visited: RoaringBitmap::new(),
172            to_visit: vec![start_vertex],
173        };
174        let iter = iter.filter(move |vertex| *vertex != start_vertex);
175        Box::new(iter)
176    }
177
178    pub fn iter_ancestors_dfs(&self, start_vertex: Vertex) -> Box<dyn Iterator<Item = Vertex> + '_> {
179        let iter = DfsAncestorsIterator {
180            digraph: self,
181            visited: RoaringBitmap::new(),
182            to_visit: vec![start_vertex],
183        };
184        let iter = iter.filter(move |vertex| *vertex != start_vertex);
185        Box::new(iter)
186    }
187
188    /// Visit all vertices of a DAG in a depth-first-search postorder, i.e. emitting
189    /// vertices only after all their descendants have been emitted first.
190    pub fn iter_vertices_dfs_post_order(&self, start_vertices: &[Vertex]) -> Box<dyn Iterator<Item = Vertex> + '_> {
191        let iter = DfsPostOrderVerticesIterator {
192            digraph: self,
193            visited: RoaringBitmap::new(),
194            to_visit: start_vertices.to_vec(),
195        };
196        Box::new(iter)
197    }
198
199    /// Visit nodes in a depth-first-search (DFS) emitting edges in postorder, i.e.
200    /// each node is emitted only after all its descendants have been emitted.
201    pub fn iter_edges_dfs_post_order(&self, start_vertices: &[Vertex]) -> Box<dyn Iterator<Item = (Vertex, Vertex)> + '_> {
202        let iter = DfsPostOrderEdgesIterator {
203            digraph: self,
204            inner: self.iter_vertices_dfs_post_order(start_vertices),
205            seen_vertices: RoaringBitmap::new(),
206            buffer: Default::default(),
207        };
208        Box::new(iter)
209    }
210
211    /// Returns "seed" vertices of a DAG from which a traversal may start so that the process
212    /// covers all vertices in the graph.
213    pub fn get_vertices_without_incoming_edges(&self) -> Vec<Vertex> {
214        let incoming_edges_count = {
215            let mut incoming_edges_count: Vec<Vertex> =
216                vec![0; self.get_vertex_count().into()];
217            for (_, v) in self.iter_edges() {
218                incoming_edges_count[usize::try_from(v).unwrap()] += 1;
219            }
220            incoming_edges_count
221        };
222
223        let vertices_without_incoming_edges: Vec<Vertex> = incoming_edges_count
224            .into_iter()
225            .enumerate()
226            .filter(|(_, indegree)| *indegree == 0)
227            .map(|(vertex, _)| vertex.try_into().unwrap())
228            .collect();
229
230        vertices_without_incoming_edges
231    }
232
233    /// Return a sequence of topologically ordered vertices of a digraph, or `None` if the digraph
234    /// has a cycle.
235    pub fn get_topologically_ordered_vertices(&self) -> Option<Vec<Vertex>> {
236        let mut starting_vertices = self.get_vertices_without_incoming_edges();
237        if starting_vertices.is_empty() && self.has_edges() {
238            // If there are no vertices without incoming edges and yet there are some edges in the
239            // graph, we have a highly cyclic graph.
240            cov_mark::hit!(nonempty_graph_without_starting_vertices_graph_is_cyclic);
241            return None;
242        }
243
244        #[derive(Debug, Clone, Copy)]
245        enum VisitStep {
246            VertexChild(Vertex),
247            OutOfVertexChildren(Vertex), // this marker is used as an indicator when to pop from the visitation stack
248        }
249
250        let mut result: Vec<Vertex> = Default::default();
251        let mut visited = RoaringBitmap::new();
252        while let Some(starting_vertex) = starting_vertices.pop() {
253            let mut to_visit: Vec<VisitStep> = vec![VisitStep::VertexChild(starting_vertex)];
254            let mut marked = RoaringBitmap::new();
255            while let Some(vertex) = to_visit.pop() {
256                match vertex {
257                    VisitStep::VertexChild(vertex) => {
258                        if marked.contains(vertex.into()) {
259                            // We have a cycle
260                            return None;
261                        }
262                        if visited.contains(vertex.into()) {
263                            // We have something homeomorphic to a diamond
264                            continue;
265                        }
266                        marked.insert(vertex.into());
267                        to_visit.push(VisitStep::OutOfVertexChildren(vertex));
268                        let mut children: Vec<Vertex> = Default::default();
269                        self.extend_with_children(vertex, &mut children);
270                        for child in children {
271                            to_visit.push(VisitStep::VertexChild(child));
272                        }
273                        visited.insert(vertex.into());
274                    }
275                    VisitStep::OutOfVertexChildren(vertex) => {
276                        marked.remove(vertex.into());
277                        result.push(vertex);
278                    }
279                };
280            }
281        }
282        result.reverse();
283        Some(result)
284    }
285
286    /// Computes a mapping: vertex -> set of vertices that are descendants of vertex.
287    fn get_descendants(&self) -> Vec<RoaringBitmap> {
288        let mut descendants: Vec<RoaringBitmap> =
289            vec![RoaringBitmap::default(); self.get_vertex_count().into()];
290
291        let mut children = Vec::with_capacity(self.get_vertex_count().into());
292        for u in (0..self.get_vertex_count()).rev() {
293            children.clear();
294            self.extend_with_children(u, &mut children);
295            let mut u_descendants = RoaringBitmap::default();
296            for &v in &children {
297                u_descendants |= descendants[usize::try_from(v).unwrap()].clone();
298                u_descendants.insert(v.into());
299            }
300            descendants[usize::try_from(u).unwrap()] = u_descendants;
301        }
302
303        descendants
304    }
305
306    /// Returns a new DAG that is a [transitive
307    /// reduction](https://en.wikipedia.org/wiki/Transitive_reduction) of a DAG.
308    pub fn transitive_reduction(&self) -> DirectedGraph {
309        let mut result = self.clone();
310
311        let mut children = Vec::with_capacity(self.get_vertex_count().into());
312        let descendants = self.get_descendants();
313        for u in 0..self.get_vertex_count() {
314            children.clear();
315            self.extend_with_children(u, &mut children);
316            for &v in &children {
317                for w in descendants[usize::from(v)].iter() {
318                    let w = Vertex::try_from(w).unwrap();
319                    if w == v {
320                        continue;
321                    }
322                    result.clear_edge(u, w);
323                }
324            }
325        }
326        result
327    }
328
329    /// Outputs the DAG in the [Graphviz DOT](https://graphviz.org/) format.
330    pub fn to_dot<W: Write>(&self, output: &mut W) -> std::result::Result<(), std::io::Error> {
331        writeln!(output, "digraph tree_{} {{", self.get_vertex_count())?;
332
333        for elem in 0..self.get_vertex_count() {
334            writeln!(output, "\t_{}[label=\"{}\"];", elem, elem)?;
335        }
336
337        writeln!(output, "\n")?;
338
339        for (left, right) in self.iter_edges() {
340            writeln!(output, "\t_{} -> _{};", left, right)?;
341        }
342
343        writeln!(output, "}}")?;
344        Ok(())
345    }
346
347    pub fn to_dot_file<P: AsRef<std::path::Path>>(
348        &self,
349        path: P,
350    ) -> std::result::Result<(), std::io::Error> {
351        let mut file = std::fs::File::create(path)?;
352        self.to_dot(&mut file)?;
353        Ok(())
354    }
355}
356
357pub fn arb_prufer_sequence(vertex_count: Vertex) -> BoxedStrategy<Vec<Vertex>> {
358    assert!(vertex_count >= 2); // trees smaller than this have to be enumerated by hand
359    proptest::collection::vec(0..vertex_count, usize::try_from(vertex_count - 2).unwrap()).boxed()
360}
361
362// https://www.geeksforgeeks.org/random-tree-generator-using-prufer-sequence-with-examples/
363// https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence#Algorithm_to_convert_a_Pr%C3%BCfer_sequence_into_a_tree
364pub fn random_tree_from_prufer_sequence(prufer_sequence: &[Vertex]) -> DirectedGraph {
365    let nvertices = prufer_sequence.len() + 2;
366
367    let mut degree: Vec<Vertex> = Vec::with_capacity(nvertices);
368    degree.resize(nvertices, 1);
369
370    let mut tree = DirectedGraph::new(nvertices.try_into().unwrap());
371
372    // Number of occurrences of vertex in code
373    for i in prufer_sequence {
374        degree[usize::try_from(*i).unwrap()] += 1;
375    }
376
377    // Find the smallest label not present in prufer_sequence[]
378    for i in prufer_sequence {
379        for j in 0..nvertices {
380            if degree[j] == 1 {
381                tree.set_edge(*i, Vertex::try_from(j).unwrap());
382                degree[usize::try_from(*i).unwrap()] -= 1;
383                degree[j] -= 1;
384                break;
385            }
386        }
387    }
388
389    let (u, v) = {
390        let mut u: Option<Vertex> = None;
391        let mut v: Option<Vertex> = None;
392        for i in 0..nvertices {
393            if degree[i] == 1 {
394                if u == None {
395                    u = Some(i.try_into().unwrap());
396                } else {
397                    v = Some(i.try_into().unwrap());
398                    break;
399                }
400            }
401        }
402        (u.unwrap(), v.unwrap())
403    };
404    tree.set_edge(u, v);
405
406    tree
407}
408
409pub fn arb_nonempty_tree(max_vertex_count: Vertex) -> BoxedStrategy<DirectedGraph> {
410    (2..max_vertex_count)
411        .prop_flat_map(|vertex_count| {
412            arb_prufer_sequence(vertex_count).prop_flat_map(move |prufer_sequence| {
413                let tree = random_tree_from_prufer_sequence(&prufer_sequence);
414                Just(tree).boxed()
415            })
416        })
417        .boxed()
418}
419
420pub fn arb_tree(max_vertex_count: Vertex) -> BoxedStrategy<DirectedGraph> {
421    prop_oneof![
422        1 => Just(DirectedGraph::new(max_vertex_count)).boxed(),
423        99 => arb_nonempty_tree(max_vertex_count),
424    ]
425    .boxed()
426}
427
428/// See [`iter_vertices_dfs`].
429pub(crate) struct DfsDescendantsIterator<'a, G: TraversableDirectedGraph> {
430    pub(crate) digraph: &'a G,
431    pub(crate) visited: RoaringBitmap,
432    pub(crate) to_visit: Vec<Vertex>,
433}
434
435impl<'a, G: TraversableDirectedGraph> Iterator for DfsDescendantsIterator<'a, G> {
436    type Item = Vertex;
437
438    fn next(&mut self) -> Option<Self::Item> {
439        while let Some(u) = self.to_visit.pop() {
440            if self.visited.contains(u.into()) {
441                continue;
442            }
443            self.digraph.extend_with_children(u, &mut self.to_visit);
444            self.visited.insert(u.into());
445            return Some(u);
446        }
447        None
448    }
449}
450
451pub(crate) struct DfsAncestorsIterator<'a, G: TraversableDirectedGraph> {
452    pub(crate) digraph: &'a G,
453    pub(crate) visited: RoaringBitmap,
454    pub(crate) to_visit: Vec<Vertex>,
455}
456
457impl<'a, G: TraversableDirectedGraph> Iterator for DfsAncestorsIterator<'a, G> {
458    type Item = Vertex;
459
460    fn next(&mut self) -> Option<Self::Item> {
461        while let Some(u) = self.to_visit.pop() {
462            if self.visited.contains(u.into()) {
463                continue;
464            }
465            self.digraph.extend_with_parents(u, &mut self.to_visit);
466            self.visited.insert(u.into());
467            return Some(u);
468        }
469        None
470    }
471}
472
473/// See [`iter_vertices_dfs_post_order`].
474pub(crate) struct DfsPostOrderVerticesIterator<'a, G: TraversableDirectedGraph> {
475    pub(crate) digraph: &'a G,
476    pub(crate) visited: RoaringBitmap,
477    pub(crate) to_visit: Vec<Vertex>,
478}
479
480impl<'a, G: TraversableDirectedGraph> Iterator for DfsPostOrderVerticesIterator<'a, G> {
481    type Item = Vertex;
482
483    fn next(&mut self) -> Option<Self::Item> {
484        loop {
485            let u = match self.to_visit.last().copied() {
486                Some(u) => u,
487                None => return None,
488            };
489            if self.visited.contains(u.into()) {
490                self.to_visit.pop();
491                continue;
492            }
493            let unvisited_neighbours: Vec<Vertex> = {
494                let mut neighbours: Vec<Vertex> = Default::default();
495                self.digraph.extend_with_children(u, &mut neighbours);
496                neighbours.retain(|v| !self.visited.contains((*v).into()));
497                neighbours
498            };
499            if unvisited_neighbours.is_empty() {
500                // We have visited all the descendants of u.  We can now emit u
501                // from the iterator.
502                self.to_visit.pop();
503                self.visited.insert(u.into());
504                return Some(u);
505            }
506            self.to_visit.extend(unvisited_neighbours);
507        }
508    }
509}
510
511/// See [`iter_edges_dfs_post_order`].
512pub(crate) struct DfsPostOrderEdgesIterator<'a, G: TraversableDirectedGraph> {
513    pub(crate) digraph: &'a G,
514    pub(crate) inner: Box<dyn Iterator<Item = Vertex> + 'a>,
515    pub(crate) seen_vertices: RoaringBitmap,
516    pub(crate) buffer: VecDeque<(Vertex, Vertex)>,
517}
518
519impl<'a, G: TraversableDirectedGraph> Iterator for DfsPostOrderEdgesIterator<'a, G> {
520    type Item = (Vertex, Vertex);
521
522    fn next(&mut self) -> Option<Self::Item> {
523        loop {
524            if let Some((u, v)) = self.buffer.pop_front() {
525                return Some((u, v));
526            }
527
528            let u = self.inner.next()?;
529
530            let mut children: Vec<Vertex> = Default::default();
531            self.digraph.extend_with_children(u, &mut children);
532            for v in children {
533                if self.seen_vertices.contains(v.into()) {
534                    self.buffer.push_back((u, v));
535                }
536            }
537            self.seen_vertices.insert(u.into());
538        }
539    }
540}
541
542#[cfg(test)]
543mod tests {
544    use crate::dag::arb_dag;
545
546    use super::*;
547
548    #[test]
549    fn empty_graph_has_no_cycle() {
550        let digraph = DirectedGraph::from_edges_iter(1, vec![].into_iter());
551        assert_eq!(digraph.get_topologically_ordered_vertices().unwrap(), [0]);
552    }
553
554    #[test]
555    fn diamond_has_no_cycle() {
556        let diamond =
557            DirectedGraph::from_edges_iter(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)].into_iter());
558        assert_eq!(diamond.get_topologically_ordered_vertices().unwrap(), [0, 1, 2, 3]);
559    }
560
561    #[test]
562    fn simple_cyclic_digraph_has_cycle() {
563        let digraph = DirectedGraph::from_edges_iter(2, vec![(0, 1), (1, 0)].into_iter());
564        cov_mark::check!(nonempty_graph_without_starting_vertices_graph_is_cyclic);
565        assert!(digraph.get_topologically_ordered_vertices().is_none());
566    }
567
568    #[test]
569    fn triangle_has_cycle() {
570        let digraph = DirectedGraph::from_edges_iter(3, vec![(0, 1), (1, 2), (2, 0)].into_iter());
571        assert!(digraph.get_topologically_ordered_vertices().is_none());
572    }
573
574    proptest! {
575        #[test]
576        fn arb_tree_has_exactly_one_root(tree in arb_nonempty_tree(100)) {
577            prop_assert!(tree.find_tree_root().is_some());
578        }
579
580        #[test]
581        fn arb_tree_has_no_cycle(tree in arb_tree(100)) {
582            prop_assert!(tree.get_topologically_ordered_vertices().is_some());
583        }
584
585        #[test]
586        fn arb_dag_has_no_cycle(dag in arb_dag(0..100, 0.5)) {
587            let digraph = DirectedGraph::from_dag(&dag);
588            prop_assert!(digraph.get_topologically_ordered_vertices().is_some());
589        }
590    }
591
592    #[test]
593    fn simple_topological_order() {
594        // 0: 1, 2, 3, 4
595        // 1: 3
596        // 2: 3, 4
597        // 3: 4
598        let digraph = DirectedGraph::from_edges_iter(5, [(0, 1), (0, 2), (0, 3), (0, 4), (1, 3), (2, 3), (2, 4), (3, 4)].into_iter());
599        assert_eq!(digraph.get_topologically_ordered_vertices().unwrap(), [0, 1, 2, 3, 4]);
600    }
601}
roaring_graphs/digraph.rs

roaring_graphs/
digraph.rs
