gdsl 0.2.1

GDSL is a graph data-structure library including graph containers, connected node strutures and efficient algorithms on those structures. Nodes are independent of a graph container and can be used as connected smart pointers.
Documentation 
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
145
146

use super::*;
use crate::error::Error;

#[derive(Clone)]
pub struct WeakNode<K = usize, N = (), E = ()>
where
    K: Clone + Hash + Display + PartialEq + Eq,
    N: Clone,
    E: Clone,
{
    inner: WeakNodeInner<K, N, E>,
}

type WeakNodeInner<K, N, E> = Weak<(K, N, RwLock<Adjacent<K, N, E>>)>;

impl<K, N, E> WeakNode<K, N, E>
where
    K: Clone + Hash + Display + PartialEq + Eq,
    N: Clone,
    E: Clone,
{
    pub fn upgrade(&self) -> Option<Node<K, N, E>> {
        self.inner.upgrade().map(|inner| Node { inner })
    }

    pub fn downgrade(node: &Node<K, N, E>) -> Self {
        WeakNode {
            inner: Arc::downgrade(&node.inner),
        }
    }
}

pub struct Adjacent<K, N, E>
where
    K: Clone + Hash + PartialEq + Eq + Display,
    N: Clone,
    E: Clone,
{
    outbound: Vec<(WeakNode<K, N, E>, E)>,
    inbound: Vec<(WeakNode<K, N, E>, E)>,
}

impl<K, N, E> Adjacent<K, N, E>
where
    K: Clone + Hash + PartialEq + Eq + Display,
    N: Clone,
    E: Clone,
{
    pub fn new() -> RwLock<Self> {
        RwLock::new(Self {
            outbound: Vec::new(),
            inbound: Vec::new(),
        })
    }

    pub fn get_adjacent(&self, idx: usize) -> Option<(&WeakNode<K, N, E>, &E)> {
        match self.outbound.get(idx) {
            Some(edge) => Some((&edge.0, &edge.1)),
            None => self
                .inbound
                .get(idx - self.outbound.len())
                .map(|edge| (&edge.0, &edge.1)),
        }
    }

    pub fn find_outbound(&self, node: &K) -> Option<(&WeakNode<K, N, E>, &E)> {
        for edge in self.outbound.iter() {
            if edge.0.upgrade().unwrap().key() == node {
                return Some((&edge.0, &edge.1));
            }
        }
        None
    }

    pub fn find_inbound(&self, node: &K) -> Option<(&WeakNode<K, N, E>, &E)> {
        for edge in self.inbound.iter() {
            if edge.0.upgrade().unwrap().key() == node {
                return Some((&edge.0, &edge.1));
            }
        }
        None
    }

    pub fn find_adjacent(&self, node: &K) -> Option<(&WeakNode<K, N, E>, &E)> {
        match self.find_outbound(node) {
            Some(edge) => Some(edge),
            None => self.find_inbound(node),
        }
    }

    pub fn len_outbound(&self) -> usize {
        self.outbound.len()
    }

    pub fn len_inbound(&self) -> usize {
        self.inbound.len()
    }

    pub fn push_inbound(&mut self, edge: (Node<K, N, E>, E)) {
        self.inbound.push((WeakNode::downgrade(&edge.0), edge.1));
    }

    pub fn push_outbound(&mut self, edge: (Node<K, N, E>, E)) {
        self.outbound.push((WeakNode::downgrade(&edge.0), edge.1));
    }

    pub fn remove_inbound(&mut self, source: &K) -> Result<E, Error> {
        for (idx, edge) in self.inbound.iter().enumerate() {
            if edge.0.upgrade().unwrap().key() == source {
                return Ok(self.inbound.remove(idx).1);
            }
        }
        Err(Error::EdgeNotFound)
    }

    pub fn remove_outbound(&mut self, target: &K) -> Result<E, Error> {
        for (idx, edge) in self.outbound.iter().enumerate() {
            if edge.0.upgrade().unwrap().key() == target {
                return Ok(self.outbound.remove(idx).1);
            }
        }
        Err(Error::EdgeNotFound)
    }

    pub fn remove_undirected(&mut self, node: &K) -> Result<E, Error> {
        match self.remove_inbound(node) {
            Ok(edge) => Ok(edge),
            Err(_) => self.remove_outbound(node),
        }
    }

    pub fn clear_inbound(&mut self) {
        self.inbound.clear();
    }

    pub fn clear_outbound(&mut self) {
        self.outbound.clear();
    }

    pub fn sizeof(&self) -> usize {
        self.inbound.len()
            + self.outbound.len()
            * (std::mem::size_of::<Node<K, N, E>>() + std::mem::size_of::<E>())
            + std::mem::size_of::<Self>()
    }
}