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

use crate::index::{AtomicIdx, Idx};

use rayon::prelude::*;
use std::{
    ops::{Deref, DerefMut},
    sync::atomic::Ordering::AcqRel,
};

pub mod binary;
#[cfg(feature = "dotgraph")]
pub mod dotgraph;
pub mod edgelist;

pub struct InputPath<P>(pub(crate) P);

pub trait InputCapabilities<Node: Idx> {
    type GraphInput;
}

#[derive(Debug, Clone, Copy)]
pub enum Direction {
    Outgoing,
    Incoming,
    Undirected,
}

pub struct EdgeList<Node: Idx>(Box<[(Node, Node)]>);

impl<Node: Idx> AsRef<[(Node, Node)]> for EdgeList<Node> {
    fn as_ref(&self) -> &[(Node, Node)] {
        &self.0
    }
}

impl<Node: Idx> Deref for EdgeList<Node> {
    type Target = [(Node, Node)];

    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl<Node: Idx> DerefMut for EdgeList<Node> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl<Node: Idx> EdgeList<Node> {
    pub fn new(edges: Vec<(Node, Node)>) -> Self {
        Self(edges.into_boxed_slice())
    }

    pub(crate) fn max_node_id(&self) -> Node {
        self.par_iter()
            .map(|(s, t)| Node::max(*s, *t))
            .reduce(Node::zero, Node::max)
    }

    pub(crate) fn degrees(&self, node_count: Node, direction: Direction) -> Vec<Node::Atomic> {
        let mut degrees = Vec::with_capacity(node_count.index());
        degrees.resize_with(node_count.index(), Node::Atomic::zero);

        if matches!(direction, Direction::Outgoing | Direction::Undirected) {
            self.par_iter().for_each(|(s, _)| {
                degrees[s.index()].get_and_increment(AcqRel);
            });
        }

        if matches!(direction, Direction::Incoming | Direction::Undirected) {
            self.par_iter().for_each(|(_, t)| {
                degrees[t.index()].get_and_increment(AcqRel);
            });
        }

        degrees
    }
}

impl<Node: Idx> From<&gdl::Graph> for EdgeList<Node> {
    fn from(gdl_graph: &gdl::Graph) -> Self {
        let edges = gdl_graph
            .relationships()
            .into_iter()
            .map(|r| {
                let source = gdl_graph.get_node(r.source()).unwrap().id();
                let target = gdl_graph.get_node(r.target()).unwrap().id();

                (Node::new(source), Node::new(target))
            })
            .collect::<Vec<_>>();

        EdgeList::new(edges)
    }
}