graph_builder/graph/
adj_list.rs

1use crate::{
2    index::Idx, prelude::Direction, prelude::Edges, prelude::NodeValues as NodeValuesTrait,
3    CsrLayout, DirectedDegrees, DirectedNeighbors, DirectedNeighborsWithValues, Graph, Target,
4    UndirectedDegrees, UndirectedNeighbors, UndirectedNeighborsWithValues,
5};
6use crate::{EdgeMutation, EdgeMutationWithValues};
7
8use log::info;
9use std::sync::{RwLock, RwLockReadGuard};
10use std::time::Instant;
11
12use crate::graph::csr::NodeValues;
13use rayon::prelude::*;
14
15#[derive(Debug)]
16pub struct AdjacencyList<NI, EV> {
17    edges: Vec<RwLock<Vec<Target<NI, EV>>>>,
18    layout: CsrLayout,
19}
20
21const _: () = {
22    const fn is_send<T: Send>() {}
23    const fn is_sync<T: Sync>() {}
24
25    is_send::<AdjacencyList<u64, ()>>();
26    is_sync::<AdjacencyList<u64, ()>>();
27};
28
29impl<NI: Idx, EV> AdjacencyList<NI, EV> {
30    pub fn new(edges: Vec<Vec<Target<NI, EV>>>) -> Self {
31        Self::with_layout(edges, CsrLayout::Unsorted)
32    }
33
34    pub fn with_layout(edges: Vec<Vec<Target<NI, EV>>>, layout: CsrLayout) -> Self {
35        let edges = edges.into_iter().map(RwLock::new).collect::<_>();
36        Self { edges, layout }
37    }
38
39    #[inline]
40    pub(crate) fn node_count(&self) -> NI {
41        NI::new(self.edges.len())
42    }
43
44    #[inline]
45    pub(crate) fn edge_count(&self) -> NI
46    where
47        NI: Send + Sync,
48        EV: Send + Sync,
49    {
50        NI::new(self.edges.par_iter().map(|v| v.read().unwrap().len()).sum())
51    }
52
53    #[inline]
54    pub(crate) fn degree(&self, node: NI) -> NI {
55        NI::new(self.edges[node.index()].read().unwrap().len())
56    }
57
58    #[inline]
59    pub(crate) fn insert(&self, source: NI, target: Target<NI, EV>) {
60        let mut edges = self.edges[source.index()].write().unwrap();
61        Self::apply_layout(self.layout, &mut edges, target);
62    }
63
64    #[inline]
65    pub(crate) fn insert_mut(&mut self, source: NI, target: Target<NI, EV>) {
66        let edges = self.edges[source.index()].get_mut().unwrap();
67        Self::apply_layout(self.layout, edges, target);
68    }
69
70    #[inline]
71    fn check_bounds(&self, node: NI) -> Result<(), crate::Error> {
72        if node >= self.node_count() {
73            return Err(crate::Error::MissingNode {
74                node: format!("{}", node.index()),
75            });
76        };
77        Ok(())
78    }
79
80    #[inline]
81    fn apply_layout(layout: CsrLayout, edges: &mut Vec<Target<NI, EV>>, target: Target<NI, EV>) {
82        match layout {
83            CsrLayout::Sorted => match edges.binary_search(&target) {
84                Ok(i) => edges.insert(i, target),
85                Err(i) => edges.insert(i, target),
86            },
87            CsrLayout::Unsorted => edges.push(target),
88            CsrLayout::Deduplicated => match edges.binary_search(&target) {
89                Ok(_) => {}
90                Err(i) => edges.insert(i, target),
91            },
92        };
93    }
94}
95
96#[derive(Debug)]
97pub struct Targets<'slice, NI: Idx> {
98    targets: RwLockReadGuard<'slice, Vec<Target<NI, ()>>>,
99}
100
101impl<'slice, NI: Idx> Targets<'slice, NI> {
102    pub fn as_slice(&self) -> &'slice [NI] {
103        assert_eq!(
104            std::mem::size_of::<Target<NI, ()>>(),
105            std::mem::size_of::<NI>()
106        );
107        assert_eq!(
108            std::mem::align_of::<Target<NI, ()>>(),
109            std::mem::align_of::<NI>()
110        );
111        // SAFETY: The types Target<T, ()> and T are verified to have the same
112        //         size and alignment.
113        //         We can upcast the lifetime since the MutexGuard
114        //         is not exposed, so it is not possible to deref mutable.
115        unsafe { std::slice::from_raw_parts(self.targets.as_ptr().cast(), self.targets.len()) }
116    }
117}
118
119pub struct TargetsIter<'slice, NI: Idx> {
120    _targets: Targets<'slice, NI>,
121    slice: std::slice::Iter<'slice, NI>,
122}
123
124impl<'slice, NI: Idx> TargetsIter<'slice, NI> {
125    pub fn as_slice(&self) -> &'slice [NI] {
126        self.slice.as_slice()
127    }
128}
129
130impl<'slice, NI: Idx> IntoIterator for Targets<'slice, NI> {
131    type Item = &'slice NI;
132
133    type IntoIter = TargetsIter<'slice, NI>;
134
135    fn into_iter(self) -> Self::IntoIter {
136        let slice = self.as_slice();
137        TargetsIter {
138            _targets: self,
139            slice: slice.iter(),
140        }
141    }
142}
143
144impl<'slice, NI: Idx> Iterator for TargetsIter<'slice, NI> {
145    type Item = &'slice NI;
146
147    fn next(&mut self) -> Option<Self::Item> {
148        self.slice.next()
149    }
150}
151
152impl<NI: Idx> AdjacencyList<NI, ()> {
153    #[inline]
154    pub(crate) fn targets(&self, node: NI) -> Targets<'_, NI> {
155        let targets = self.edges[node.index()].read().unwrap();
156
157        Targets { targets }
158    }
159}
160
161#[derive(Debug)]
162pub struct TargetsWithValues<'slice, NI: Idx, EV> {
163    targets: RwLockReadGuard<'slice, Vec<Target<NI, EV>>>,
164}
165
166impl<'slice, NI: Idx, EV> TargetsWithValues<'slice, NI, EV> {
167    pub fn as_slice(&self) -> &'slice [Target<NI, EV>] {
168        // SAFETY: We can upcast the lifetime since the MutexGuard
169        // is not exposed, so it is not possible to deref mutable.
170        unsafe { std::slice::from_raw_parts(self.targets.as_ptr(), self.targets.len()) }
171    }
172}
173
174pub struct TargetsWithValuesIter<'slice, NI: Idx, EV> {
175    _targets: TargetsWithValues<'slice, NI, EV>,
176    slice: std::slice::Iter<'slice, Target<NI, EV>>,
177}
178
179impl<'slice, NI: Idx, EV> TargetsWithValuesIter<'slice, NI, EV> {
180    pub fn as_slice(&self) -> &'slice [Target<NI, EV>] {
181        self.slice.as_slice()
182    }
183}
184
185impl<'slice, NI: Idx, EV> IntoIterator for TargetsWithValues<'slice, NI, EV> {
186    type Item = &'slice Target<NI, EV>;
187
188    type IntoIter = TargetsWithValuesIter<'slice, NI, EV>;
189
190    fn into_iter(self) -> Self::IntoIter {
191        let slice = self.as_slice();
192        TargetsWithValuesIter {
193            _targets: self,
194            slice: slice.iter(),
195        }
196    }
197}
198
199impl<'slice, NI: Idx, EV> Iterator for TargetsWithValuesIter<'slice, NI, EV> {
200    type Item = &'slice Target<NI, EV>;
201
202    fn next(&mut self) -> Option<Self::Item> {
203        self.slice.next()
204    }
205}
206
207impl<NI: Idx, EV> AdjacencyList<NI, EV> {
208    #[inline]
209    pub(crate) fn targets_with_values(&self, node: NI) -> TargetsWithValues<'_, NI, EV> {
210        TargetsWithValues {
211            targets: self.edges[node.index()].read().unwrap(),
212        }
213    }
214}
215
216impl<NI, EV, E> From<(&'_ E, NI, Direction, CsrLayout)> for AdjacencyList<NI, EV>
217where
218    NI: Idx,
219    EV: Copy + Send + Sync,
220    E: Edges<NI = NI, EV = EV>,
221{
222    fn from(
223        (edge_list, node_count, direction, csr_layout): (&'_ E, NI, Direction, CsrLayout),
224    ) -> Self {
225        let start = Instant::now();
226        let thread_safe_vec = edge_list
227            .degrees(node_count, direction)
228            .into_par_iter()
229            .map(|degree| RwLock::new(Vec::with_capacity(degree.into_inner().index())))
230            .collect::<Vec<_>>();
231        info!("Initialized adjacency list in {:?}", start.elapsed());
232
233        let start = Instant::now();
234        edge_list.edges().for_each(|(s, t, v)| {
235            if matches!(direction, Direction::Outgoing | Direction::Undirected) {
236                thread_safe_vec[s.index()]
237                    .write()
238                    .unwrap()
239                    .push(Target::new(t, v));
240            }
241            if matches!(direction, Direction::Incoming | Direction::Undirected) {
242                thread_safe_vec[t.index()]
243                    .write()
244                    .unwrap()
245                    .push(Target::new(s, v));
246            }
247        });
248        info!("Grouped edge tuples in {:?}", start.elapsed());
249
250        let start = Instant::now();
251        let mut edges = Vec::with_capacity(node_count.index());
252        thread_safe_vec
253            .into_par_iter()
254            .map(|list| {
255                let mut list = list.into_inner().unwrap();
256
257                match csr_layout {
258                    CsrLayout::Sorted => list.sort_unstable_by_key(|t| t.target),
259                    CsrLayout::Unsorted => {}
260                    CsrLayout::Deduplicated => {
261                        list.sort_unstable_by_key(|t| t.target);
262                        list.dedup_by_key(|t| t.target)
263                    }
264                }
265
266                list
267            })
268            .collect_into_vec(&mut edges);
269
270        info!(
271            "Applied list layout and finalized edge list in {:?}",
272            start.elapsed()
273        );
274
275        AdjacencyList::with_layout(edges, csr_layout)
276    }
277}
278
279pub struct DirectedALGraph<NI: Idx, NV = (), EV = ()> {
280    node_values: NodeValues<NV>,
281    al_out: AdjacencyList<NI, EV>,
282    al_inc: AdjacencyList<NI, EV>,
283}
284
285impl<NI: Idx, NV, EV> DirectedALGraph<NI, NV, EV>
286where
287    NV: Send + Sync,
288    EV: Send + Sync,
289{
290    pub fn new(
291        node_values: NodeValues<NV>,
292        al_out: AdjacencyList<NI, EV>,
293        al_inc: AdjacencyList<NI, EV>,
294    ) -> Self {
295        let g = Self {
296            node_values,
297            al_out,
298            al_inc,
299        };
300
301        info!(
302            "Created directed graph (node_count = {:?}, edge_count = {:?})",
303            g.node_count(),
304            g.edge_count()
305        );
306
307        g
308    }
309}
310
311impl<NI: Idx, NV, EV> Graph<NI> for DirectedALGraph<NI, NV, EV>
312where
313    NV: Send + Sync,
314    EV: Send + Sync,
315{
316    delegate::delegate! {
317        to self.al_out {
318            fn node_count(&self) -> NI;
319            fn edge_count(&self) -> NI;
320        }
321    }
322}
323
324impl<NI: Idx, NV, EV> NodeValuesTrait<NI, NV> for DirectedALGraph<NI, NV, EV> {
325    fn node_value(&self, node: NI) -> &NV {
326        &self.node_values.0[node.index()]
327    }
328}
329
330impl<NI: Idx, NV, EV> DirectedDegrees<NI> for DirectedALGraph<NI, NV, EV> {
331    fn out_degree(&self, node: NI) -> NI {
332        self.al_out.degree(node)
333    }
334
335    fn in_degree(&self, node: NI) -> NI {
336        self.al_inc.degree(node)
337    }
338}
339
340impl<NI: Idx, NV> DirectedNeighbors<NI> for DirectedALGraph<NI, NV, ()> {
341    type NeighborsIterator<'a>
342        = TargetsIter<'a, NI>
343    where
344        NV: 'a;
345
346    fn out_neighbors(&self, node: NI) -> Self::NeighborsIterator<'_> {
347        self.al_out.targets(node).into_iter()
348    }
349
350    fn in_neighbors(&self, node: NI) -> Self::NeighborsIterator<'_> {
351        self.al_inc.targets(node).into_iter()
352    }
353}
354
355impl<NI: Idx, NV, EV> DirectedNeighborsWithValues<NI, EV> for DirectedALGraph<NI, NV, EV> {
356    type NeighborsIterator<'a>
357        = TargetsWithValuesIter<'a, NI, EV>
358    where
359        NV: 'a,
360        EV: 'a;
361
362    fn out_neighbors_with_values(&self, node: NI) -> Self::NeighborsIterator<'_> {
363        self.al_out.targets_with_values(node).into_iter()
364    }
365
366    fn in_neighbors_with_values(&self, node: NI) -> Self::NeighborsIterator<'_> {
367        self.al_inc.targets_with_values(node).into_iter()
368    }
369}
370
371impl<NI: Idx, NV> EdgeMutation<NI> for DirectedALGraph<NI, NV> {
372    fn add_edge(&self, source: NI, target: NI) -> Result<(), crate::Error> {
373        self.add_edge_with_value(source, target, ())
374    }
375
376    fn add_edge_mut(&mut self, source: NI, target: NI) -> Result<(), crate::Error> {
377        self.add_edge_with_value_mut(source, target, ())
378    }
379}
380
381impl<NI: Idx, NV, EV: Copy> EdgeMutationWithValues<NI, EV> for DirectedALGraph<NI, NV, EV> {
382    fn add_edge_with_value(&self, source: NI, target: NI, value: EV) -> Result<(), crate::Error> {
383        self.al_out.check_bounds(source)?;
384        self.al_inc.check_bounds(target)?;
385        self.al_out.insert(source, Target::new(target, value));
386        self.al_inc.insert(target, Target::new(source, value));
387
388        Ok(())
389    }
390
391    fn add_edge_with_value_mut(
392        &mut self,
393        source: NI,
394        target: NI,
395        value: EV,
396    ) -> Result<(), crate::Error> {
397        self.al_out.check_bounds(source)?;
398        self.al_inc.check_bounds(target)?;
399        self.al_out.insert_mut(source, Target::new(target, value));
400        self.al_inc.insert_mut(target, Target::new(source, value));
401
402        Ok(())
403    }
404}
405
406impl<NI, EV, E> From<(E, CsrLayout)> for DirectedALGraph<NI, (), EV>
407where
408    NI: Idx,
409    EV: Copy + Send + Sync,
410    E: Edges<NI = NI, EV = EV>,
411{
412    fn from((edge_list, csr_layout): (E, CsrLayout)) -> Self {
413        info!("Creating directed graph");
414        let node_count = edge_list.max_node_id() + NI::new(1);
415        let node_values = NodeValues::new(vec![(); node_count.index()]);
416
417        let start = Instant::now();
418        let al_out = AdjacencyList::from((&edge_list, node_count, Direction::Outgoing, csr_layout));
419        info!("Created outgoing adjacency list in {:?}", start.elapsed());
420
421        let start = Instant::now();
422        let al_inc = AdjacencyList::from((&edge_list, node_count, Direction::Incoming, csr_layout));
423        info!("Created incoming adjacency list in {:?}", start.elapsed());
424
425        DirectedALGraph::new(node_values, al_out, al_inc)
426    }
427}
428
429impl<NI, NV, EV, E> From<(NodeValues<NV>, E, CsrLayout)> for DirectedALGraph<NI, NV, EV>
430where
431    NI: Idx,
432    NV: Send + Sync,
433    EV: Copy + Send + Sync,
434    E: Edges<NI = NI, EV = EV>,
435{
436    fn from((node_values, edge_list, csr_layout): (NodeValues<NV>, E, CsrLayout)) -> Self {
437        info!("Creating directed graph");
438        let node_count = edge_list.max_node_id() + NI::new(1);
439
440        let start = Instant::now();
441        let al_out = AdjacencyList::from((&edge_list, node_count, Direction::Outgoing, csr_layout));
442        info!("Created outgoing adjacency list in {:?}", start.elapsed());
443
444        let start = Instant::now();
445        let al_inc = AdjacencyList::from((&edge_list, node_count, Direction::Incoming, csr_layout));
446        info!("Created incoming adjacency list in {:?}", start.elapsed());
447
448        DirectedALGraph::new(node_values, al_out, al_inc)
449    }
450}
451
452pub struct UndirectedALGraph<NI: Idx, NV = (), EV = ()> {
453    node_values: NodeValues<NV>,
454    al: AdjacencyList<NI, EV>,
455}
456
457impl<NI: Idx, NV, EV> UndirectedALGraph<NI, NV, EV>
458where
459    NV: Send + Sync,
460    EV: Send + Sync,
461{
462    pub fn new(node_values: NodeValues<NV>, al: AdjacencyList<NI, EV>) -> Self {
463        let g = Self { node_values, al };
464
465        info!(
466            "Created undirected graph (node_count = {:?}, edge_count = {:?})",
467            g.node_count(),
468            g.edge_count()
469        );
470
471        g
472    }
473}
474
475impl<NI: Idx, NV, EV> Graph<NI> for UndirectedALGraph<NI, NV, EV>
476where
477    NV: Send + Sync,
478    EV: Send + Sync,
479{
480    fn node_count(&self) -> NI {
481        self.al.node_count()
482    }
483
484    fn edge_count(&self) -> NI {
485        self.al.edge_count() / NI::new(2)
486    }
487}
488
489impl<NI: Idx, NV, EV> NodeValuesTrait<NI, NV> for UndirectedALGraph<NI, NV, EV> {
490    fn node_value(&self, node: NI) -> &NV {
491        &self.node_values.0[node.index()]
492    }
493}
494
495impl<NI: Idx, NV, EV> UndirectedDegrees<NI> for UndirectedALGraph<NI, NV, EV> {
496    fn degree(&self, node: NI) -> NI {
497        self.al.degree(node)
498    }
499}
500
501impl<NI: Idx, NV> UndirectedNeighbors<NI> for UndirectedALGraph<NI, NV, ()> {
502    type NeighborsIterator<'a>
503        = TargetsIter<'a, NI>
504    where
505        NV: 'a;
506
507    fn neighbors(&self, node: NI) -> Self::NeighborsIterator<'_> {
508        self.al.targets(node).into_iter()
509    }
510}
511
512impl<NI: Idx, NV, EV> UndirectedNeighborsWithValues<NI, EV> for UndirectedALGraph<NI, NV, EV> {
513    type NeighborsIterator<'a>
514        = TargetsWithValuesIter<'a, NI, EV>
515    where
516        NV: 'a,
517        EV: 'a;
518
519    fn neighbors_with_values(&self, node: NI) -> Self::NeighborsIterator<'_> {
520        self.al.targets_with_values(node).into_iter()
521    }
522}
523
524impl<NI: Idx, NV> EdgeMutation<NI> for UndirectedALGraph<NI, NV, ()> {
525    fn add_edge(&self, source: NI, target: NI) -> Result<(), crate::Error> {
526        self.add_edge_with_value(source, target, ())
527    }
528
529    fn add_edge_mut(&mut self, source: NI, target: NI) -> Result<(), crate::Error> {
530        self.add_edge_with_value_mut(source, target, ())
531    }
532}
533
534impl<NI: Idx, NV, EV: Copy> EdgeMutationWithValues<NI, EV> for UndirectedALGraph<NI, NV, EV> {
535    fn add_edge_with_value(&self, source: NI, target: NI, value: EV) -> Result<(), crate::Error> {
536        self.al.check_bounds(source)?;
537        self.al.check_bounds(target)?;
538        self.al.insert(source, Target::new(target, value));
539        self.al.insert(target, Target::new(source, value));
540
541        Ok(())
542    }
543
544    fn add_edge_with_value_mut(
545        &mut self,
546        source: NI,
547        target: NI,
548        value: EV,
549    ) -> Result<(), crate::Error> {
550        self.al.check_bounds(source)?;
551        self.al.check_bounds(target)?;
552        self.al.insert_mut(source, Target::new(target, value));
553        self.al.insert_mut(target, Target::new(source, value));
554
555        Ok(())
556    }
557}
558
559impl<NI, EV, E> From<(E, CsrLayout)> for UndirectedALGraph<NI, (), EV>
560where
561    NI: Idx,
562    EV: Copy + Send + Sync,
563    E: Edges<NI = NI, EV = EV>,
564{
565    fn from((edge_list, csr_layout): (E, CsrLayout)) -> Self {
566        info!("Creating undirected graph");
567        let node_count = edge_list.max_node_id() + NI::new(1);
568        let node_values = NodeValues::new(vec![(); node_count.index()]);
569
570        let start = Instant::now();
571        let al = AdjacencyList::from((&edge_list, node_count, Direction::Undirected, csr_layout));
572        info!("Created adjacency list in {:?}", start.elapsed());
573
574        UndirectedALGraph::new(node_values, al)
575    }
576}
577
578impl<NI, NV, EV, E> From<(NodeValues<NV>, E, CsrLayout)> for UndirectedALGraph<NI, NV, EV>
579where
580    NI: Idx,
581    NV: Send + Sync,
582    EV: Copy + Send + Sync,
583    E: Edges<NI = NI, EV = EV>,
584{
585    fn from((node_values, edge_list, csr_layout): (NodeValues<NV>, E, CsrLayout)) -> Self {
586        info!("Creating undirected graph");
587        let node_count = edge_list.max_node_id() + NI::new(1);
588
589        let start = Instant::now();
590        let al = AdjacencyList::from((&edge_list, node_count, Direction::Undirected, csr_layout));
591        info!("Created adjacency list in {:?}", start.elapsed());
592
593        UndirectedALGraph::new(node_values, al)
594    }
595}
596
597#[cfg(test)]
598mod test {
599    use super::*;
600    use crate::prelude::EdgeList;
601    use crate::GraphBuilder;
602    use tap::prelude::*;
603
604    #[test]
605    fn empty_list() {
606        let list = AdjacencyList::<u32, u32>::new(vec![]);
607        assert_eq!(list.node_count(), 0);
608        assert_eq!(list.edge_count(), 0);
609    }
610
611    #[test]
612    fn degree() {
613        let list = AdjacencyList::<u32, u32>::new(vec![
614            /* node 0 */ vec![Target::new(1, 42)],
615            /* node 1 */ vec![Target::new(0, 1337)],
616        ]);
617        assert_eq!(list.node_count(), 2);
618        assert_eq!(list.edge_count(), 2);
619        assert_eq!(list.degree(0), 1);
620        assert_eq!(list.degree(1), 1);
621    }
622
623    #[test]
624    fn targets_with_values() {
625        let list = AdjacencyList::<u32, u32>::new(vec![
626            /* node 0 */ vec![Target::new(1, 42)],
627            /* node 1 */ vec![Target::new(0, 1337)],
628        ]);
629
630        assert_eq!(
631            list.targets_with_values(0).as_slice(),
632            &[Target::new(1, 42)]
633        );
634        assert_eq!(
635            list.targets_with_values(1).as_slice(),
636            &[Target::new(0, 1337)]
637        );
638    }
639
640    #[test]
641    fn targets() {
642        let list = AdjacencyList::<u32, ()>::new(vec![
643            /* node 0 */ vec![Target::new(1, ())],
644            /* node 1 */ vec![Target::new(0, ())],
645        ]);
646
647        assert_eq!(list.targets(0).as_slice(), &[1]);
648        assert_eq!(list.targets(1).as_slice(), &[0]);
649    }
650
651    #[test]
652    fn from_edges_outgoing() {
653        let edges = vec![(0, 1, 42), (0, 2, 1337), (1, 0, 43), (2, 0, 1338)];
654        let edges = EdgeList::new(edges);
655        let list =
656            AdjacencyList::<u32, u32>::from((&edges, 3, Direction::Outgoing, CsrLayout::Unsorted));
657
658        assert_eq!(
659            list.targets_with_values(0)
660                .into_iter()
661                .collect::<Vec<_>>()
662                .tap_mut(|v| v.sort_by_key(|t| t.target)),
663            &[&Target::new(1, 42), &Target::new(2, 1337)]
664        );
665        assert_eq!(
666            list.targets_with_values(1).as_slice(),
667            &[Target::new(0, 84)]
668        );
669        assert_eq!(
670            list.targets_with_values(2).as_slice(),
671            &[Target::new(0, 1337)]
672        );
673    }
674
675    #[test]
676    fn from_edges_incoming() {
677        let edges = vec![(0, 1, 42), (0, 2, 1337), (1, 0, 43), (2, 0, 1338)];
678        let edges = EdgeList::new(edges);
679        let list =
680            AdjacencyList::<u32, u32>::from((&edges, 3, Direction::Incoming, CsrLayout::Unsorted));
681
682        assert_eq!(
683            list.targets_with_values(0)
684                .into_iter()
685                .collect::<Vec<_>>()
686                .tap_mut(|v| v.sort_by_key(|t| t.target)),
687            &[&Target::new(1, 42), &Target::new(2, 1337)]
688        );
689        assert_eq!(
690            list.targets_with_values(1).as_slice(),
691            &[Target::new(0, 42)]
692        );
693        assert_eq!(
694            list.targets_with_values(2).as_slice(),
695            &[Target::new(0, 1337)]
696        );
697    }
698
699    #[test]
700    fn from_edges_undirected() {
701        let edges = vec![(0, 1, 42), (0, 2, 1337), (1, 0, 43), (2, 0, 1338)];
702        let edges = EdgeList::new(edges);
703        let list = AdjacencyList::<u32, u32>::from((
704            &edges,
705            3,
706            Direction::Undirected,
707            CsrLayout::Unsorted,
708        ));
709
710        assert_eq!(
711            list.targets_with_values(0)
712                .into_iter()
713                .collect::<Vec<_>>()
714                .tap_mut(|v| v.sort_by_key(|t| t.target)),
715            &[
716                &Target::new(1, 42),
717                &Target::new(1, 43),
718                &Target::new(2, 1337),
719                &Target::new(2, 1338)
720            ]
721        );
722        assert_eq!(
723            list.targets_with_values(1)
724                .into_iter()
725                .collect::<Vec<_>>()
726                .tap_mut(|v| v.sort_by_key(|t| t.target)),
727            &[&Target::new(0, 42), &Target::new(0, 43)]
728        );
729        assert_eq!(
730            list.targets_with_values(2)
731                .into_iter()
732                .collect::<Vec<_>>()
733                .tap_mut(|v| v.sort_by_key(|t| t.target)),
734            &[&Target::new(0, 1337), &Target::new(0, 1338)]
735        );
736    }
737
738    #[test]
739    fn from_edges_sorted() {
740        let edges = vec![
741            (0, 1, ()),
742            (0, 3, ()),
743            (0, 2, ()),
744            (1, 3, ()),
745            (1, 2, ()),
746            (1, 0, ()),
747        ];
748        let edges = EdgeList::new(edges);
749        let list =
750            AdjacencyList::<u32, ()>::from((&edges, 3, Direction::Outgoing, CsrLayout::Sorted));
751
752        assert_eq!(list.targets(0).as_slice(), &[1, 2, 3]);
753        assert_eq!(list.targets(1).as_slice(), &[0, 2, 3]);
754    }
755
756    #[test]
757    fn from_edges_deduplicated() {
758        let edges = vec![
759            (0, 1, ()),
760            (0, 3, ()),
761            (0, 3, ()),
762            (0, 2, ()),
763            (0, 2, ()),
764            (1, 3, ()),
765            (1, 3, ()),
766            (1, 2, ()),
767            (1, 2, ()),
768            (1, 0, ()),
769            (1, 0, ()),
770        ];
771        let edges = EdgeList::new(edges);
772        let list = AdjacencyList::<u32, ()>::from((
773            &edges,
774            3,
775            Direction::Outgoing,
776            CsrLayout::Deduplicated,
777        ));
778
779        assert_eq!(list.targets(0).as_slice(), &[1, 2, 3]);
780        assert_eq!(list.targets(1).as_slice(), &[0, 2, 3]);
781    }
782
783    #[test]
784    fn directed_al_graph() {
785        let g = GraphBuilder::new()
786            .csr_layout(CsrLayout::Sorted)
787            .edges([(0, 1), (0, 2), (1, 2)])
788            .build::<DirectedALGraph<u32, ()>>();
789
790        assert_eq!(g.node_count(), 3);
791        assert_eq!(g.edge_count(), 3);
792        assert_eq!(g.out_degree(0), 2);
793        assert_eq!(g.out_neighbors(0).as_slice(), &[1, 2]);
794        assert_eq!(g.in_degree(2), 2);
795        assert_eq!(g.in_neighbors(2).as_slice(), &[0, 1]);
796    }
797
798    #[test]
799    fn directed_al_graph_with_node_values() {
800        let g = GraphBuilder::new()
801            .csr_layout(CsrLayout::Sorted)
802            .edges([(0, 1), (0, 2), (1, 2)])
803            .node_values(vec!["foo", "bar", "baz"])
804            .build::<DirectedALGraph<u32, &str>>();
805
806        assert_eq!(g.node_value(0), &"foo");
807        assert_eq!(g.node_value(1), &"bar");
808        assert_eq!(g.node_value(2), &"baz");
809    }
810
811    #[test]
812    fn directed_al_graph_add_edge_unsorted() {
813        let g = GraphBuilder::new()
814            .csr_layout(CsrLayout::Unsorted)
815            .edges([(0, 2), (1, 2)])
816            .build::<DirectedALGraph<u32>>();
817
818        assert_eq!(g.out_neighbors(0).as_slice(), &[2]);
819        g.add_edge(0, 1).expect("add edge failed");
820        assert_eq!(g.out_neighbors(0).as_slice(), &[2, 1]);
821        g.add_edge(0, 2).expect("add edge failed");
822        assert_eq!(g.out_neighbors(0).as_slice(), &[2, 1, 2]);
823    }
824
825    #[test]
826    fn directed_al_graph_add_edge_sorted() {
827        let g = GraphBuilder::new()
828            .csr_layout(CsrLayout::Sorted)
829            .edges([(0, 2), (1, 2)])
830            .build::<DirectedALGraph<u32>>();
831
832        assert_eq!(g.out_neighbors(0).as_slice(), &[2]);
833        g.add_edge(0, 1).expect("add edge failed");
834        assert_eq!(g.out_neighbors(0).as_slice(), &[1, 2]);
835        g.add_edge(0, 1).expect("add edge failed");
836        assert_eq!(g.out_neighbors(0).as_slice(), &[1, 1, 2]);
837    }
838
839    #[test]
840    fn directed_al_graph_add_edge_deduplicated() {
841        let g = GraphBuilder::new()
842            .csr_layout(CsrLayout::Deduplicated)
843            .edges([(0, 2), (1, 2), (1, 3)])
844            .build::<DirectedALGraph<u32>>();
845
846        assert_eq!(g.out_neighbors(0).as_slice(), &[2]);
847        g.add_edge(0, 1).expect("add edge failed");
848        assert_eq!(g.out_neighbors(0).as_slice(), &[1, 2]);
849        g.add_edge(0, 1).expect("add edge failed");
850        assert_eq!(g.out_neighbors(0).as_slice(), &[1, 2]);
851        g.add_edge(0, 3).expect("add edge failed");
852        assert_eq!(g.out_neighbors(0).as_slice(), &[1, 2, 3]);
853    }
854
855    #[test]
856    fn directed_al_graph_add_edge_with_value() {
857        let g = GraphBuilder::new()
858            .csr_layout(CsrLayout::Unsorted)
859            .edges_with_values([(0, 2, 4.2), (1, 2, 13.37)])
860            .build::<DirectedALGraph<u32, (), f32>>();
861
862        assert_eq!(
863            g.out_neighbors_with_values(0).as_slice(),
864            &[Target::new(2, 4.2)]
865        );
866        g.add_edge_with_value(0, 1, 19.84).expect("add edge failed");
867        assert_eq!(
868            g.out_neighbors_with_values(0).as_slice(),
869            &[Target::new(2, 4.2), Target::new(1, 19.84)]
870        );
871        g.add_edge_with_value(0, 2, 1.23).expect("add edge failed");
872        assert_eq!(
873            g.out_neighbors_with_values(0).as_slice(),
874            &[
875                Target::new(2, 4.2),
876                Target::new(1, 19.84),
877                Target::new(2, 1.23)
878            ]
879        );
880    }
881
882    #[test]
883    fn directed_al_graph_add_edge_missing_node() {
884        let g = GraphBuilder::new()
885            .csr_layout(CsrLayout::Unsorted)
886            .edges([(0, 2), (1, 2)])
887            .build::<DirectedALGraph<u32>>();
888
889        let err = g.add_edge(0, 3).unwrap_err();
890
891        assert!(matches!(err, crate::Error::MissingNode { node } if node == "3" ));
892    }
893
894    #[test]
895    fn directed_al_graph_add_edge_parallel() {
896        let g = GraphBuilder::new()
897            .csr_layout(CsrLayout::Unsorted)
898            .edges([(0, 1), (0, 2), (0, 3)])
899            .build::<DirectedALGraph<u32>>();
900
901        std::thread::scope(|scope| {
902            for _ in 0..4 {
903                scope.spawn(|| g.add_edge(0, 1));
904            }
905        });
906
907        assert_eq!(g.edge_count(), 7);
908    }
909
910    #[test]
911    fn undirected_al_graph_add_edge_unsorted() {
912        let g = GraphBuilder::new()
913            .csr_layout(CsrLayout::Unsorted)
914            .edges([(0, 2), (1, 2)])
915            .build::<UndirectedALGraph<u32>>();
916
917        assert_eq!(g.neighbors(0).as_slice(), &[2]);
918        assert_eq!(g.neighbors(1).as_slice(), &[2]);
919        g.add_edge(0, 1).expect("add edge failed");
920        assert_eq!(g.neighbors(0).as_slice(), &[2, 1]);
921        assert_eq!(g.neighbors(1).as_slice(), &[2, 0]);
922        g.add_edge(0, 2).expect("add edge failed");
923        assert_eq!(g.neighbors(0).as_slice(), &[2, 1, 2]);
924    }
925
926    #[test]
927    fn undirected_al_graph_add_edge_sorted() {
928        let g = GraphBuilder::new()
929            .csr_layout(CsrLayout::Sorted)
930            .edges([(0, 2), (1, 2)])
931            .build::<UndirectedALGraph<u32>>();
932
933        assert_eq!(g.neighbors(0).as_slice(), &[2]);
934        assert_eq!(g.neighbors(1).as_slice(), &[2]);
935        g.add_edge(0, 1).expect("add edge failed");
936        assert_eq!(g.neighbors(0).as_slice(), &[1, 2]);
937        assert_eq!(g.neighbors(1).as_slice(), &[0, 2]);
938        g.add_edge(0, 1).expect("add edge failed");
939        assert_eq!(g.neighbors(0).as_slice(), &[1, 1, 2]);
940    }
941
942    #[test]
943    fn undirected_al_graph_add_edge_deduplicated() {
944        let g = GraphBuilder::new()
945            .csr_layout(CsrLayout::Deduplicated)
946            .edges([(0, 2), (1, 2), (1, 3)])
947            .build::<UndirectedALGraph<u32>>();
948
949        assert_eq!(g.neighbors(0).as_slice(), &[2]);
950        assert_eq!(g.neighbors(1).as_slice(), &[2, 3]);
951        g.add_edge(0, 1).expect("add edge failed");
952        assert_eq!(g.neighbors(0).as_slice(), &[1, 2]);
953        assert_eq!(g.neighbors(1).as_slice(), &[0, 2, 3]);
954        g.add_edge(0, 1).expect("add edge failed");
955        assert_eq!(g.neighbors(0).as_slice(), &[1, 2]);
956        assert_eq!(g.neighbors(1).as_slice(), &[0, 2, 3]);
957        g.add_edge(0, 3).expect("add edge failed");
958        assert_eq!(g.neighbors(0).as_slice(), &[1, 2, 3]);
959    }
960
961    #[test]
962    fn undirected_al_graph_add_edge_with_value() {
963        let g = GraphBuilder::new()
964            .csr_layout(CsrLayout::Unsorted)
965            .edges_with_values([(0, 2, 4.2), (1, 2, 13.37)])
966            .build::<UndirectedALGraph<u32, (), f32>>();
967
968        assert_eq!(
969            g.neighbors_with_values(0).as_slice(),
970            &[Target::new(2, 4.2)]
971        );
972        assert_eq!(
973            g.neighbors_with_values(1).as_slice(),
974            &[Target::new(2, 13.37)]
975        );
976        g.add_edge_with_value(0, 1, 19.84).expect("add edge failed");
977        assert_eq!(
978            g.neighbors_with_values(0).as_slice(),
979            &[Target::new(2, 4.2), Target::new(1, 19.84)]
980        );
981        assert_eq!(
982            g.neighbors_with_values(1).as_slice(),
983            &[Target::new(2, 13.37), Target::new(0, 19.84)]
984        );
985        g.add_edge_with_value(0, 2, 1.23).expect("add edge failed");
986        assert_eq!(
987            g.neighbors_with_values(0).as_slice(),
988            &[
989                Target::new(2, 4.2),
990                Target::new(1, 19.84),
991                Target::new(2, 1.23)
992            ]
993        );
994    }
995
996    #[test]
997    fn undirected_al_graph_add_edge_missing_node() {
998        let g = GraphBuilder::new()
999            .csr_layout(CsrLayout::Unsorted)
1000            .edges([(0, 2), (1, 2)])
1001            .build::<UndirectedALGraph<u32>>();
1002
1003        let err = g.add_edge(0, 3).unwrap_err();
1004
1005        assert!(matches!(err, crate::Error::MissingNode { node } if node == "3" ));
1006    }
1007
1008    #[test]
1009    fn undirected_al_graph_add_edge_parallel() {
1010        let g = GraphBuilder::new()
1011            .csr_layout(CsrLayout::Unsorted)
1012            .edges([(0, 1), (0, 2), (0, 3)])
1013            .build::<UndirectedALGraph<u32>>();
1014
1015        std::thread::scope(|scope| {
1016            for _ in 0..4 {
1017                scope.spawn(|| g.add_edge(0, 1));
1018            }
1019        });
1020
1021        assert_eq!(g.edge_count(), 7);
1022    }
1023    #[test]
1024    fn undirected_al_graph() {
1025        let g = GraphBuilder::new()
1026            .csr_layout(CsrLayout::Sorted)
1027            .edges([(0, 1), (0, 2), (1, 2)])
1028            .build::<UndirectedALGraph<u32, ()>>();
1029
1030        assert_eq!(g.node_count(), 3);
1031        assert_eq!(g.edge_count(), 3);
1032        assert_eq!(g.degree(0), 2);
1033        assert_eq!(g.degree(2), 2);
1034        assert_eq!(g.neighbors(0).as_slice(), &[1, 2]);
1035        assert_eq!(g.neighbors(2).as_slice(), &[0, 1]);
1036    }
1037
1038    #[test]
1039    fn undirected_al_graph_cycle() {
1040        let g = GraphBuilder::new()
1041            .csr_layout(CsrLayout::Sorted)
1042            .edges([(0, 1), (1, 0)])
1043            .build::<UndirectedALGraph<u32, ()>>();
1044
1045        assert_eq!(g.node_count(), 2);
1046        assert_eq!(g.edge_count(), 2);
1047        assert_eq!(g.degree(0), 2);
1048        assert_eq!(g.degree(1), 2);
1049        assert_eq!(g.neighbors(0).as_slice(), &[1, 1]);
1050        assert_eq!(g.neighbors(1).as_slice(), &[0, 0]);
1051    }
1052
1053    #[test]
1054    fn undirected_al_graph_with_node_values() {
1055        let g = GraphBuilder::new()
1056            .csr_layout(CsrLayout::Sorted)
1057            .edges([(0, 1), (0, 2), (1, 2)])
1058            .node_values(vec!["foo", "bar", "baz"])
1059            .build::<UndirectedALGraph<u32, &str>>();
1060
1061        assert_eq!(g.node_value(0), &"foo");
1062        assert_eq!(g.node_value(1), &"bar");
1063        assert_eq!(g.node_value(2), &"baz");
1064    }
1065}
graph_builder/graph/adj_list.rs

graph_builder/graph/
adj_list.rs
