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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
use std::hash::Hash;
use std::collections::HashMap;

#[derive(Clone,Copy)]
pub struct Edge<V,L> {
    source: V,
    target: V,
    label: L
}

struct Edges<V,L> {
    outgoing: Vec<Edge<V,L>>,
    incoming: Vec<Edge<V,L>>
}

pub struct DiGraph<V,L> where
V: Hash + Eq + Copy,
L: Copy
{
    adjacencies: HashMap<V, Edges<V,L>>,
    nodes: Vec<V>
}

impl<V,L> DiGraph<V,L> where
V: Hash + Eq + Copy,
L: Copy
{
    pub fn new() -> Self {
        DiGraph {
            adjacencies: HashMap::new(),
            nodes: Vec::new()
        }
    }

    /// Adds a node to the graph, with no incoming or outgoing edges.
    ///
    /// # Panics
    ///
    /// if the the node is already present.
    pub fn add_node(&mut self, node: V) {
        if !self.adjacencies.contains_key(&node) {
            self.insert_node_if_absent(node);
        } else {
            panic!("Node already exists in graph");
        }
    }

    pub fn has_node(&self, node: V) -> bool {
        self.adjacencies.contains_key(&node)
    }

    pub fn nodes(&self) -> &[V] {
        self.nodes.as_slice()
    }

    /// Inserts a new edge into the graph.
    /// The source and target nodes are added to the graph if they were not previously recorded
    pub fn add_edge(&mut self, source: V, target: V, label: L) {
        self.insert_node_if_absent(source);
        self.insert_node_if_absent(target);

        let e = Edge { source, target, label };

        self.adjacencies.get_mut(&source).unwrap().outgoing.push(e);
        self.adjacencies.get_mut(&target).unwrap().incoming.push(e);
    }

    pub fn insert_node_if_absent(&mut self, node: V) {
        if !self.adjacencies.contains_key(&node ) {
            self.adjacencies.insert(node, Edges {
                outgoing: Vec::new(),
                incoming: Vec::new()
            });
            self.nodes.push(node)
        }
    }

    pub fn incoming_edges(&self, source: V) -> &[Edge<V,L>] {
        self.adjacencies
            .get(&source)
            .map(|es| es.incoming.as_slice())
            .unwrap_or(&[])
    }

    pub fn outgoing_edges(&self, target: V) -> &[Edge<V,L>] {
        self.adjacencies
            .get(&target)
            .map(|es| es.outgoing.as_slice())
            .unwrap_or(&[])
    }

}


#[cfg(test)]
mod tests {
    use crate::DiGraph;

    #[test]
    fn degrees() {
        let mut g = DiGraph::new();
        g.add_edge(1, 2, 10);
        g.add_edge(1, 2, 15);

        assert_eq!(g.incoming_edges(2).len(), 2);
        assert_eq!(g.outgoing_edges(2).len(), 0);

        assert_eq!(g.incoming_edges(7).len(), 0);
    }

    #[test]
    fn nodes() {
        let mut g = DiGraph::new();
        g.add_edge(1, 2, 10);
        g.add_edge(1, 2, 15);

        assert!(g.has_node(1));
        assert!(g.has_node(2));
        assert!(!g.has_node(0));
        assert!(!g.has_node(3));

        assert_eq!(g.nodes().len(), 2);
        assert_eq!(*g.nodes(), [1,2]);

        g.add_node(3);

        assert!(g.has_node(1));
        assert!(g.has_node(2));
        assert!(!g.has_node(0));
        assert!(g.has_node(3));
        assert_eq!(g.nodes().len(), 3);

        assert_eq!(*g.nodes(), [1,2,3]);
    }

    #[test]
    #[should_panic]
    fn node_added_more_than_once() {
        let mut g = DiGraph::<_,()>::new();
        g.add_node(1);
        g.add_node(1);
    }
}