onlinematching/
bigraph.rs

1use std::collections::BTreeMap;
2
3type Edge<Key> = (Key, Key);
4
5#[derive(Debug, PartialEq)]
6pub struct Bigraph<Key> {
7    pub v_nodes: Vec<Key>,
8    pub u_nodes: Vec<Key>,
9    pub nodes_edges: Vec<Edge<Key>>,
10    nodes_edges_use_index: Vec<(usize, usize)>,
11    v_key2index: BTreeMap<Key, usize>,
12    u_key2index: BTreeMap<Key, usize>,
13    pub v_adjacency_list: Vec<Vec<usize>>,
14    pub u_adjacency_list: Vec<Vec<usize>>,
15}
16
17impl<Key: Ord + Copy + std::fmt::Debug> Bigraph<Key> {
18    pub fn new() -> Bigraph<Key> {
19        Bigraph {
20            v_nodes: vec![],
21            u_nodes: vec![],
22            nodes_edges: vec![],
23            nodes_edges_use_index: vec![],
24            v_key2index: BTreeMap::new(),
25            u_key2index: BTreeMap::new(),
26            v_adjacency_list: vec![],
27            u_adjacency_list: vec![],
28        }
29    }
30
31    pub fn from_edges(edges: &Vec<Edge<Key>>) -> Self {
32        let mut graph = Self::new();
33        for edge in edges {
34            assert!(
35                !graph.nodes_edges.contains(edge),
36                "edges should't contain the same edge: {:?}",
37                edge
38            );
39            let (u, v) = edge;
40
41            let v_index;
42            // It means a new v node has arrived
43            // so the adjacency_list and nodes list should be increased
44            if !graph.v_nodes.contains(v) {
45                v_index = graph.v_nodes.len();
46                graph.v_key2index.insert(v.clone(), v_index);
47                graph.v_nodes.push(v.clone());
48                graph.v_adjacency_list.push(vec![]);
49            } else {
50                v_index = graph.v_key2index[v];
51            }
52
53            // exactly the same as above
54            let u_index;
55            if !graph.u_nodes.contains(u) {
56                u_index = graph.u_nodes.len();
57                graph.u_key2index.insert(u.clone(), u_index);
58                graph.u_nodes.push(u.clone());
59                graph.u_adjacency_list.push(vec![]);
60            } else {
61                u_index = graph.u_key2index[u];
62            }
63
64            graph.nodes_edges.push(edge.clone());
65            graph.nodes_edges_use_index.push((u_index, v_index));
66
67            graph.v_adjacency_list[v_index].push(u_index);
68            graph.u_adjacency_list[u_index].push(v_index);
69        }
70        graph
71    }
72
73    pub fn insert_u(self: &mut Self, key: Key) -> Result<(), String> {
74        if self.u_nodes.contains(&key) {
75            Err("The u nodes already have this key".to_owned())
76        } else {
77            let u_index = self.u_nodes.len();
78            self.u_nodes.push(key);
79            self.u_adjacency_list.push(vec![]);
80            self.u_key2index.insert(key, u_index);
81            Ok(())
82        }
83    }
84
85    pub fn insert_v(self: &mut Self, key: Key) -> Result<(), String> {
86        if self.v_nodes.contains(&key) {
87            Err("The v nodes already have this key".to_owned())
88        } else {
89            let v_index = self.v_nodes.len();
90            self.v_nodes.push(key);
91            self.v_adjacency_list.push(vec![]);
92            self.v_key2index.insert(key, v_index);
93            Ok(())
94        }
95    }
96}
onlinematching/bigraph.rs

onlinematching/
bigraph.rs
