use std::collections::HashMap;
use crate::Error;
#[derive(Debug, Clone)]
pub struct AdjacencyListGraph<T: Clone + Eq + std::hash::Hash> {
adj: HashMap<T, Vec<T>>,
directed: bool,
}
impl<T: Clone + Eq + std::hash::Hash> AdjacencyListGraph<T> {
pub fn new(directed: bool) -> Self {
Self {
adj: HashMap::new(),
directed,
}
}
pub fn vertex_count(&self) -> usize {
self.adj.len()
}
pub fn is_empty(&self) -> bool {
self.adj.is_empty()
}
pub fn add_vertex(&mut self, vertex: T) {
self.adj.entry(vertex).or_insert_with(Vec::new);
}
pub fn remove_vertex(&mut self, vertex: &T) -> Result<(), Error> {
if !self.adj.contains_key(vertex) {
return Err(Error::NotFound);
}
for neighbors in self.adj.values_mut() {
if let Some(pos) = neighbors.iter().position(|v| v == vertex) {
neighbors.remove(pos);
}
}
self.adj.remove(vertex);
Ok(())
}
pub fn add_edge(&mut self, u: T, v: T) {
self.add_vertex(u.clone());
self.add_vertex(v.clone());
if !self.adj[&u].contains(&v) {
self.adj.get_mut(&u).unwrap().push(v.clone());
}
if !self.directed && !self.adj[&v].contains(&u) {
self.adj.get_mut(&v).unwrap().push(u);
}
}
pub fn remove_edge(&mut self, u: &T, v: &T) {
if let Some(neighbors) = self.adj.get_mut(u) {
if let Some(pos) = neighbors.iter().position(|x| x == v) {
neighbors.remove(pos);
}
}
if !self.directed {
if let Some(neighbors) = self.adj.get_mut(v) {
if let Some(pos) = neighbors.iter().position(|x| x == u) {
neighbors.remove(pos);
}
}
}
}
pub fn has_edge(&self, u: &T, v: &T) -> bool {
self.adj
.get(u)
.map(|neighbors| neighbors.contains(v))
.unwrap_or(false)
}
pub fn neighbors(&self, vertex: &T) -> Vec<T> {
self.adj.get(vertex).cloned().unwrap_or_default()
}
pub fn bfs(&self, start: &T) -> Vec<T> {
if !self.adj.contains_key(start) {
return Vec::new();
}
let mut visited = std::collections::HashSet::new();
visited.insert(start.clone());
let mut queue = vec![start.clone()];
let mut result = Vec::new();
while let Some(current) = queue.pop() {
result.push(current.clone());
for neighbor in &self.adj[¤t] {
if visited.insert(neighbor.clone()) {
queue.insert(0, neighbor.clone());
}
}
}
result
}
pub fn dfs(&self, start: &T) -> Vec<T> {
if !self.adj.contains_key(start) {
return Vec::new();
}
let mut visited = std::collections::HashSet::new();
let mut result = Vec::new();
self.dfs_visit(start, &mut visited, &mut result);
result
}
fn dfs_visit(&self, vertex: &T, visited: &mut std::collections::HashSet<T>, result: &mut Vec<T>) {
if !visited.insert(vertex.clone()) {
return;
}
result.push(vertex.clone());
for neighbor in &self.adj[vertex] {
self.dfs_visit(neighbor, visited, result);
}
}
}
#[derive(Debug, Clone)]
pub struct AdjacencyMatrixGraph<T: Clone + Eq + std::hash::Hash> {
vertices: Vec<T>,
index: HashMap<T, usize>,
matrix: Vec<Vec<i32>>,
directed: bool,
}
impl<T: Clone + Eq + std::hash::Hash> AdjacencyMatrixGraph<T> {
pub fn new(directed: bool) -> Self {
Self {
vertices: Vec::new(),
index: HashMap::new(),
matrix: Vec::new(),
directed,
}
}
pub fn vertex_count(&self) -> usize {
self.vertices.len()
}
pub fn is_empty(&self) -> bool {
self.vertices.is_empty()
}
pub fn add_vertex(&mut self, vertex: T) {
if self.index.contains_key(&vertex) {
return;
}
self.index.insert(vertex.clone(), self.vertices.len());
self.vertices.push(vertex);
for row in &mut self.matrix {
row.push(0);
}
self.matrix.push(vec![0; self.vertices.len()]);
}
pub fn remove_vertex(&mut self, vertex: &T) -> Result<(), Error> {
let idx = *self.index.get(vertex).ok_or(Error::NotFound)?;
self.vertices.remove(idx);
self.index.remove(vertex);
self.matrix.remove(idx);
for row in &mut self.matrix {
row.remove(idx);
}
for (i, v) in self.vertices.iter().enumerate() {
self.index.insert(v.clone(), i);
}
Ok(())
}
pub fn add_edge(&mut self, u: T, v: T, weight: i32) {
self.add_vertex(u.clone());
self.add_vertex(v.clone());
let ui = self.index[&u];
let vi = self.index[&v];
self.matrix[ui][vi] = weight;
if !self.directed {
self.matrix[vi][ui] = weight;
}
}
pub fn remove_edge(&mut self, u: &T, v: &T) {
if let (Some(&ui), Some(&vi)) = (self.index.get(u), self.index.get(v)) {
self.matrix[ui][vi] = 0;
if !self.directed {
self.matrix[vi][ui] = 0;
}
}
}
pub fn has_edge(&self, u: &T, v: &T) -> bool {
if let (Some(&ui), Some(&vi)) = (self.index.get(u), self.index.get(v)) {
return self.matrix[ui][vi] != 0;
}
false
}
pub fn weight(&self, u: &T, v: &T) -> Result<i32, Error> {
let ui = *self.index.get(u).ok_or(Error::NotFound)?;
let vi = *self.index.get(v).ok_or(Error::NotFound)?;
Ok(self.matrix[ui][vi])
}
pub fn neighbors(&self, vertex: &T) -> Vec<T> {
let idx = match self.index.get(vertex) {
Some(&i) => i,
None => return Vec::new(),
};
let mut result = Vec::new();
for (i, w) in self.matrix[idx].iter().enumerate() {
if *w != 0 {
result.push(self.vertices[i].clone());
}
}
result
}
pub fn bfs(&self, start: &T) -> Vec<T> {
if !self.index.contains_key(start) {
return Vec::new();
}
let mut visited = std::collections::HashSet::new();
visited.insert(start.clone());
let mut queue = vec![start.clone()];
let mut result = Vec::new();
while let Some(current) = queue.pop() {
result.push(current.clone());
for neighbor in self.neighbors(¤t) {
if visited.insert(neighbor.clone()) {
queue.insert(0, neighbor);
}
}
}
result
}
pub fn dfs(&self, start: &T) -> Vec<T> {
if !self.index.contains_key(start) {
return Vec::new();
}
let mut visited = std::collections::HashSet::new();
let mut result = Vec::new();
self.dfs_visit(start, &mut visited, &mut result);
result
}
fn dfs_visit(&self, vertex: &T, visited: &mut std::collections::HashSet<T>, result: &mut Vec<T>) {
if !visited.insert(vertex.clone()) {
return;
}
result.push(vertex.clone());
for neighbor in self.neighbors(vertex) {
self.dfs_visit(&neighbor, visited, result);
}
}
}