payback/
graph.rs

1use itertools::Itertools;
2use log::debug;
3use std::collections::{HashMap, HashSet};
4use std::fmt::Display;
5use std::iter::zip;
6
7use crate::graph_parser::deserialize_string_to_graph;
8
9#[derive(Clone, Debug, PartialEq, Eq, Hash)]
10pub struct NamedNode {
11    pub(crate) id: usize,
12    pub(crate) name: String,
13    pub(crate) weight: i64,
14}
15
16#[derive(Clone, Debug, Hash, Eq, PartialEq)]
17pub struct Edge {
18    pub(crate) u: usize,
19    pub(crate) v: usize,
20}
21
22#[derive(Clone, Debug)]
23pub struct Graph {
24    pub(crate) vertices: Vec<NamedNode>,
25    pub(crate) edges: Vec<Edge>,
26}
27
28impl Ord for NamedNode {
29    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
30        match (self.weight, other.weight) {
31            (u, v) if u > v => std::cmp::Ordering::Greater,
32            (u, v) if u == v => std::cmp::Ordering::Equal,
33            (u, v) if u < v => std::cmp::Ordering::Less,
34            (_, _) => unreachable!(),
35        }
36    }
37}
38
39impl PartialOrd for NamedNode {
40    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
41        Some(self.cmp(other))
42    }
43}
44
45/// Parses a String and converts it to a graph.
46impl TryFrom<String> for Graph {
47    type Error = &'static str;
48
49    fn try_from(value: String) -> Result<Self, Self::Error> {
50        match deserialize_string_to_graph(&value) {
51            Ok(graph) => Ok(graph),
52            Err(err_tup) => {
53                debug!(
54                    "Unable to parse string '{}' into graph because of errors.\n1.{}\n2.{}",
55                    value, err_tup.0, err_tup.1
56                );
57                Err("Unable to parse string into graph.")
58            }
59        }
60    }
61}
62
63/// Functions to create Graphs from some vertices and there weight.
64impl FromIterator<i64> for Graph {
65    fn from_iter<T: IntoIterator<Item = i64>>(iter: T) -> Self {
66        let v = iter.into_iter().collect_vec();
67        Graph::from(v)
68    }
69}
70
71impl From<Vec<i64>> for Graph {
72    fn from(value: Vec<i64>) -> Self {
73        Graph::new((0..value.len()).map(|x| x.to_string()).collect(), value)
74    }
75}
76
77impl From<Vec<(String, i64)>> for Graph {
78    fn from(value: Vec<(String, i64)>) -> Self {
79        Graph::new(
80            value.iter().map(|x| x.0.clone()).collect(),
81            value.iter().map(|x| x.1).collect(),
82        )
83    }
84}
85
86impl From<HashMap<String, i64>> for Graph {
87    fn from(value: HashMap<String, i64>) -> Self {
88        Graph::new(
89            value.keys().map(|k| k.to_owned()).collect_vec(),
90            value.values().map(|w| w.to_owned()).collect_vec(),
91        )
92    }
93}
94
95impl From<Vec<NamedNode>> for Graph {
96    fn from(value: Vec<NamedNode>) -> Self {
97        let edges = value
98            .iter()
99            .permutations(2)
100            .map(|uv| {
101                let u = uv.first().unwrap();
102                let v = uv.get(1).unwrap();
103                Edge { u: u.id, v: v.id }
104            })
105            .collect();
106        Graph {
107            vertices: value,
108            edges,
109        }
110    }
111}
112
113impl From<Vec<&NamedNode>> for Graph {
114    fn from(value: Vec<&NamedNode>) -> Self {
115        let edges = value
116            .iter()
117            .permutations(2)
118            .map(|uv| {
119                let u = uv.first().unwrap();
120                let v = uv.get(1).unwrap();
121                Edge { u: u.id, v: v.id }
122            })
123            .collect();
124        Graph {
125            vertices: value.into_iter().map(|x| x.to_owned()).collect(),
126            edges,
127        }
128    }
129}
130
131/// Functions to create Graphs from weighted edges.
132impl From<HashMap<(String, String), i64>> for Graph {
133    fn from(value: HashMap<(String, String), i64>) -> Self {
134        let mut unique_v: HashSet<String> = HashSet::new();
135        value.keys().for_each(|(s1, s2)| {
136            unique_v.insert(s1.to_string());
137            unique_v.insert(s2.to_string());
138        });
139        let mut name_weight_tup: HashMap<String, i64> =
140            unique_v.clone().into_iter().map(|x| (x, 0_i64)).collect();
141        for uv in unique_v.into_iter().permutations(2) {
142            let u: &String = uv.first().unwrap();
143            let v: &String = uv.get(1).unwrap();
144            let weight = value.get(&(u.to_string(), v.to_string())).unwrap_or(&0);
145            if let Some(x) = name_weight_tup.get_mut(u) {
146                *x -= weight;
147            }
148            if let Some(x) = name_weight_tup.get_mut(v) {
149                *x += weight;
150            }
151        }
152        Graph::from(name_weight_tup)
153    }
154}
155
156impl From<Vec<((String, String), i64)>> for Graph {
157    fn from(value: Vec<((String, String), i64)>) -> Self {
158        let map: HashMap<(String, String), i64> = value.into_iter().collect();
159        Graph::from(map)
160    }
161}
162
163#[allow(clippy::manual_try_fold)]
164impl Display for Graph {
165    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
166        let mut out = self.vertices.iter().fold(Ok(()), |acc, v| {
167            acc.and_then(|_| write!(f, "{}: {}; ", &v.name, &v.weight))
168        });
169        out = out.and_then(|_| writeln!(f));
170        out = out.and_then(|_| write!(f, "Edges: "));
171        self.edges.iter().fold(out, |acc, e| {
172            acc.and_then(|_| write!(f, "{} -> {}; ", &e.u, &e.v))
173        })
174    }
175}
176
177impl Graph {
178    pub(crate) fn new(names: Vec<String>, weights: Vec<i64>) -> Self {
179        assert!(
180            names.len() == weights.len(),
181            "The length of the names and weights must be the same."
182        );
183        let mut vertices: Vec<NamedNode> = vec![];
184        let mut edges: Vec<Edge> = vec![];
185        let mut id = 0;
186        for (name, weight) in zip(names, weights) {
187            vertices.push(NamedNode { id, name, weight });
188            id += 1;
189        }
190        for uv in (0..id).permutations(2) {
191            let u: usize = *uv.first().unwrap();
192            let v: usize = *uv.get(1).unwrap();
193            edges.push(Edge { u, v });
194        }
195        let g = Graph { vertices, edges };
196        debug!("Created following graph:\n{}", g.to_string());
197        g
198    }
199
200    #[allow(dead_code)]
201    pub(crate) fn get_node_from_name(&self, s: String) -> Option<&NamedNode> {
202        self.vertices.iter().find(|v| v.name == s)
203    }
204
205    pub(crate) fn get_node_from_id(&self, id: usize) -> Option<&NamedNode> {
206        self.vertices.iter().find(|v| v.id == id)
207    }
208
209    pub(crate) fn get_node_name(&self, id: usize) -> Option<String> {
210        self.vertices
211            .iter()
212            .find(|v| v.id == id)
213            .map(|v| v.name.clone())
214    }
215
216    pub(crate) fn get_node_name_or(&self, id: usize, or: String) -> String {
217        self.get_node_name(id).unwrap_or(or)
218    }
219
220    pub(crate) fn get_average_vertex_weight(&self) -> f64 {
221        self.vertices.iter().map(|v| v.weight).sum::<i64>() as f64 / (self.vertices.len() as f64)
222    }
223}
payback/graph.rs

payback/
graph.rs
