use std::collections::{HashMap, HashSet, VecDeque};
pub struct Node<T> {
name: String,
data: T,
next_idx: HashSet<usize>,
prev_idx: HashSet<usize>,
}
pub struct ArenaList<T> {
pub nodes_names: HashMap<String, usize>,
pub nodes: Vec<Node<T>>,
}
impl<T> ArenaList<T> {
fn new() -> Self {
Self {
nodes_names: HashMap::new(),
nodes: Vec::new(),
}
}
fn clear(&mut self) {
self.nodes_names.clear();
self.nodes.clear();
}
fn add_node(&mut self, name: &str, data: T) -> usize {
match self.nodes_names.get(name) {
Some(idx) => {
self.nodes[*idx].data = data;
*idx
}
None => {
let len = self.nodes.len();
self.nodes_names.insert(name.to_string(), len);
self.nodes.push(Node {
name: name.to_string(),
data,
next_idx: HashSet::new(),
prev_idx: HashSet::new(),
});
len
}
}
}
fn get_node(&self, idx: usize) -> &Node<T> {
return &self.nodes[idx];
}
fn get_idx_by_name(&self, name: &str) -> Option<&usize> {
self.nodes_names.get(name)
}
fn get_name_by_idx(&self, idx: usize) -> &str {
&self.nodes[idx].name
}
fn add_edge(&mut self, src_idx: usize, dst_idx: usize) {
self.nodes[src_idx].next_idx.insert(dst_idx);
self.nodes[dst_idx].prev_idx.insert(src_idx);
}
fn del_edge(&mut self, src_idx: usize, dst_idx: usize) -> bool {
let res = self.nodes[src_idx].next_idx.remove(&dst_idx);
self.nodes[dst_idx].next_idx.remove(&src_idx) && res
}
fn del_node(&mut self, idx: usize) -> bool {
if idx >= self.nodes.len() {
return false;
}
let last_idx = self.nodes.len() - 1;
let node_to_del = self.nodes.swap_remove(idx);
for src_idx in node_to_del.prev_idx {
if src_idx == last_idx {
self.nodes[idx].next_idx.remove(&idx);
} else {
self.nodes[src_idx].next_idx.remove(&idx);
}
}
for dst_idx in node_to_del.next_idx {
if dst_idx == last_idx {
self.nodes[idx].prev_idx.remove(&idx);
} else { self.nodes[dst_idx].prev_idx.remove(&idx); }
}
self.nodes_names.remove(&node_to_del.name);
if idx == last_idx {
return true;
}
for src_idx in self.nodes[idx].prev_idx.clone() {
if src_idx == last_idx { self.nodes[idx].next_idx.remove(&last_idx);
self.nodes[idx].next_idx.insert(idx);
} else {
self.nodes[src_idx].next_idx.remove(&last_idx);
self.nodes[src_idx].next_idx.insert(idx);
}
}
for dst_idx in self.nodes[idx].next_idx.clone() {
if dst_idx == last_idx {
self.nodes[idx].prev_idx.remove(&last_idx);
self.nodes[idx].prev_idx.insert(idx);
} else {
self.nodes[dst_idx].prev_idx.remove(&last_idx);
self.nodes[dst_idx].prev_idx.insert(idx);
}
}
match self.nodes_names.get_mut(&self.nodes[idx].name) {
None => { panic!("del_node 不应该出现的错误") }
Some(node_idx) => { *node_idx = idx }
}
true
}
}
pub struct Graph<'a, T> {
owner: &'a mut ArenaList<T>,
}
impl<'a, T> Graph<'a, T> {
fn new(arena_list: &'a mut ArenaList<T>) -> Self {
Self {
owner: arena_list
}
}
fn add_node(&mut self, name: &str, data: T) -> usize {
self.owner.add_node(name, data)
}
fn add_edge(&mut self, src_idx: usize, dst_idx: usize) {
self.owner.add_edge(src_idx, dst_idx);
}
fn add_node_and_edge(&mut self, src_name: &str, src_data: T, dst_name: &str, dst_data: T) {
let src_idx = self.add_node(src_name, src_data);
let dst_idx = self.add_node(dst_name, dst_data);
self.add_edge(src_idx, dst_idx);
}
fn get_node_by_idx(&self, idx: usize) -> &Node<T> {
return self.owner.get_node(idx);
}
fn get_name_by_idx(&self, idx: usize) -> &String {
return &self.get_node_by_idx(idx).name;
}
fn get_idx_by_name(&self, name: &str) -> Option<&usize> {
self.owner.get_idx_by_name(name)
}
fn get_all_edges(&self) -> Vec<(usize, usize)> {
let mut res = vec![];
for src_idx in 0..self.owner.nodes.len() {
for idx in &self.owner.nodes[src_idx].next_idx {
res.push((src_idx, *idx));
}
}
res
}
fn print_nodes(&self) {
println!("{:?}", self.owner.nodes.iter().map(|x| x.name.clone()).collect::<Vec<String>>());
}
fn print_edges(&self) {
let edges = self.get_all_edges();
for (src_idx, dst_idx) in edges {
println!("{:?}->{:?}", self.get_name_by_idx(src_idx), self.get_name_by_idx(dst_idx));
}
}
fn del_node_by_idx(&mut self, idx: usize) -> bool { self.owner.del_node(idx) }
fn del_edge_by_idx(&mut self, src_idx: usize, dst_idx: usize) -> bool { self.owner.del_edge(src_idx, dst_idx) }
fn del_node_by_name(&mut self, name: &str) -> bool {
match self.get_idx_by_name(name) {
None => { false }
Some(i) => { self.del_node_by_idx(*i) }
}
}
fn del_edge_by_name(&mut self, src_name: &str, dst_name: &str) -> bool {
let src_idx = self.get_idx_by_name(src_name);
let dst_idx = self.get_idx_by_name(dst_name);
if let (Some(src_idx), Some(dst_idx)) = (src_idx, dst_idx) {
self.del_edge_by_idx(*src_idx, *dst_idx)
} else { false }
}
fn clear(&mut self) { self.owner.clear() }
fn save(&self) {}
fn load(&mut self) {}
}
impl<'a, T> Graph<'a, T> {
fn get_downstream(&self, batch_idx: Vec<usize>, max_level: usize) -> HashMap<usize, Vec<usize>> {
let mut res: HashMap<usize, Vec<usize>> = HashMap::new();
let mut q: Vec<usize> = batch_idx.clone();
let mut searched = HashSet::new(); let mut level = 0;
while !q.is_empty() && level < max_level {
res.insert(level, q.clone());
searched.extend(q.clone());
q = q.iter().flat_map(|&node_idx| {
self.owner.nodes[node_idx].next_idx.iter()
.filter(|&next_idx| !searched.contains(next_idx)).copied()
}).collect();
level += 1;
}
res
}
fn get_shortest(&self, src_idx: usize, dst_idx: usize, max_level: usize) -> Option<usize> {
let mut q: Vec<usize> = vec![src_idx];
let mut searched = HashSet::new(); let mut level = 0;
while !q.is_empty() && level < max_level {
if q.contains(&dst_idx) {
return Some(level);
}
searched.extend(q.clone());
q = q.iter().flat_map(|&node_idx| {
self.owner.nodes[node_idx].next_idx.iter()
.filter(|&next_idx| !searched.contains(next_idx)).copied()
}).collect();
level += 1;
}
None
}
}
#[cfg(test)]
mod tests {
use std::collections::{HashMap, HashSet};
use crate::graph::{ArenaList, Graph};
#[test]
fn test1() {
let mut arena_list = ArenaList::new();
let mut graph = Graph::new(&mut arena_list);
let vec1 = vec![
("John", "Emma")
, ("Sophia", "Tom")
, ("Isabella", "Emma")
, ("Tom", "Isabella")
, ("Tom", "John")
, ("Tom", "Michael")
, ("John", "Emma")
, ("Tom", "Sophia")
, ("Oliver", "Emma")
, ("Michael", "Daniel")
, ("Michael", "Lucy")
, ("Sophia", "Michael")
, ("Oliver", "Lucy")
, ("Sophia", "Emily")
, ("Michael", "Daniel")
, ("Sophia", "Michael")
, ("Michael", "Sophia")
, ("John", "Emma")
, ("Tom", "Sophia")
, ("Sophia", "John")]
;
for (src_name, dst_name) in vec1 {
graph.add_node_and_edge(
src_name, src_name.to_string(),
dst_name, dst_name.to_string());
}
let edges = graph.get_all_edges();
graph.print_edges();
graph.print_nodes();
graph.del_edge_by_name("Michael", "Lucy");
println!("======after del edge [Sophia]-> [Lucy]:======");
graph.print_edges();
graph.del_node_by_name("Sophia");
println!("======after del node 【Sophia】:======");
graph.print_edges();
graph.clear();
}
#[test]
fn test2() {
let mut arena_list = ArenaList::new();
let mut graph = Graph::new(&mut arena_list);
let vec1 = vec![
("John", "Emma")
, ("Sophia", "Tom")
, ("Isabella", "Emma")
, ("Tom", "Isabella")
, ("Tom", "John")
, ("Tom", "Michael")
, ("John", "Emma")
, ("Tom", "Sophia")
, ("Oliver", "Emma")
, ("Michael", "Daniel")
, ("Michael", "Lucy")
, ("Sophia", "Michael")
, ("Oliver", "Lucy")
, ("Sophia", "Emily")
, ("Michael", "Daniel")
, ("Sophia", "Michael")
, ("Michael", "Sophia")
, ("John", "Emma")
, ("Tom", "Sophia")
, ("Sophia", "John")]
;
for (src_name, dst_name) in vec1 {
graph.add_node_and_edge(
src_name, src_name.to_string(),
dst_name, dst_name.to_string());
}
let idxes = vec![2];
let level_order = graph.get_downstream(idxes, 100000000);
for level in 0..level_order.len() {
println!("[level = {}], idx = {:?}", level, level_order.get(&level));
}
println!("=====print names=====");
for level in 0..level_order.len() {
let node_names: Vec<&String> =
level_order.get(&level).unwrap()
.iter().map(|idx| graph.get_name_by_idx(*idx))
.collect();
println!("[level = {}], names = {:?}", level, node_names);
}
println!("2 到 7 的最短路径长度为: {}",graph.get_shortest(2,7,1000000).unwrap());
}
}