129 lines
2.9 KiB
Rust
129 lines
2.9 KiB
Rust
use std::{
|
|
rc::Rc,
|
|
cell::RefCell,
|
|
fmt::{self, Debug},
|
|
hash::{Hash, Hasher},
|
|
};
|
|
|
|
#[derive(Default)]
|
|
pub struct Graph<T, W> {
|
|
pub nodes: Vec<Node<T, W>>,
|
|
}
|
|
|
|
impl<T, W> Graph<T, W>
|
|
where T: Eq + Clone,
|
|
W: Copy
|
|
{
|
|
pub fn add_edge(&mut self, edge: &(T, T, W)) {
|
|
let (a, b, w) = edge;
|
|
|
|
let mut node_a = {
|
|
match self.nodes.iter().find(|&node| *node == *a) {
|
|
Some(n) => n.to_owned(),
|
|
None => {
|
|
let new_node = Node::new(a.clone());
|
|
self.nodes.push(new_node.clone());
|
|
new_node
|
|
}
|
|
}
|
|
};
|
|
|
|
let mut node_b = {
|
|
match self.nodes.iter().find(|&node| *node == *b) {
|
|
Some(n) => n.to_owned(),
|
|
None => {
|
|
let new_node = Node::new(b.clone());
|
|
self.nodes.push(new_node.clone());
|
|
new_node
|
|
}
|
|
}
|
|
};
|
|
|
|
node_a.add_edge(node_b.clone(), *w);
|
|
node_b.add_edge(node_a, *w);
|
|
}
|
|
}
|
|
|
|
impl<T, W> Debug for Graph<T, W>
|
|
where T: Debug,
|
|
W: Debug
|
|
{
|
|
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
|
|
writeln!(f, "Graph {{")?;
|
|
for node in &self.nodes {
|
|
for (outgoing, weight) in &node.borrow().outgoing {
|
|
writeln!(f, " {:?} -- [{:?}] -- {:?}", node.borrow().data, weight, outgoing.borrow().data)?;
|
|
}
|
|
}
|
|
writeln!(f, "}}")
|
|
}
|
|
}
|
|
|
|
|
|
pub struct Node<T, W>(pub Rc<RefCell<InnerNode<T, W>>>);
|
|
|
|
impl<T, W> Node<T, W> {
|
|
pub fn new(data: T) -> Self {
|
|
let inner = InnerNode { outgoing: Vec::new(), data };
|
|
Self(Rc::new(RefCell::new(inner)))
|
|
}
|
|
|
|
pub fn add_edge(&mut self, node: Self, weight: W) {
|
|
self.0.borrow_mut().outgoing.push((node, weight));
|
|
}
|
|
|
|
pub fn borrow(&self) -> std::cell::Ref<'_, InnerNode<T, W>> {
|
|
self.0.borrow()
|
|
}
|
|
}
|
|
|
|
impl<T, W> Clone for Node<T, W> {
|
|
fn clone(&self) -> Self {
|
|
Self(self.0.clone())
|
|
}
|
|
}
|
|
|
|
impl<T, W> Hash for Node<T, W>
|
|
where T: Hash
|
|
{
|
|
fn hash<H: Hasher>(&self, hasher: &mut H) {
|
|
let this = self.borrow();
|
|
this.data.hash(hasher);
|
|
}
|
|
}
|
|
|
|
impl<T, W> PartialEq<T> for Node<T, W>
|
|
where T: PartialEq
|
|
{
|
|
fn eq(&self, other: &T) -> bool {
|
|
self.0.borrow().data == *other
|
|
}
|
|
}
|
|
|
|
impl<T, W> Eq for Node<T, W>
|
|
where T: Eq {}
|
|
|
|
impl<T, W> PartialEq for Node<T, W>
|
|
where T: PartialEq
|
|
{
|
|
fn eq(&self, other: &Self) -> bool {
|
|
self.0.borrow().data == other.0.borrow().data
|
|
}
|
|
}
|
|
|
|
impl<T, W> Debug for Node<T, W>
|
|
where T: Debug, W: Debug
|
|
{
|
|
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
|
|
f.debug_struct("Node")
|
|
.field("data", &self.0.borrow().data)
|
|
.finish()
|
|
}
|
|
}
|
|
|
|
|
|
pub struct InnerNode<T, W> {
|
|
pub data: T,
|
|
pub outgoing: Vec<(Node<T, W>, W)>,
|
|
}
|