mod digraph;
mod graph;
pub use digraph::{DFOResult, DirectedGraph, dfo};
pub use graph::UndirectedGraph;
use crate::collections::Queue;
pub trait Graph {
#[must_use]
fn vertices(&self) -> usize;
#[must_use]
fn edges(&self) -> usize;
#[must_use]
fn degree(&self, v: usize) -> usize;
#[must_use]
fn adjacent(&self, v: usize) -> impl Iterator<Item = usize>;
fn add_edge(&mut self, v: usize, w: usize);
#[must_use]
fn to_dot(&self) -> String;
}
#[must_use = "Running Depth-First-Search without using the result is meaningless"]
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DFSResult(Vec<bool>, usize, usize);
impl DFSResult {
#[must_use]
pub fn marked(&self) -> &Vec<bool> {
&self.0
}
#[must_use]
pub fn start(&self) -> usize {
self.1
}
#[must_use]
pub fn amount(&self) -> usize {
self.2
}
#[must_use]
pub fn has_path_to(&self, w: usize) -> bool {
self.0.get(w).is_some_and(|&v| v)
}
}
pub fn dfs<T: Graph>(graph: &T, start: usize) -> DFSResult {
if graph.vertices() <= start {
panic!("start is not in vertex set")
}
let mut marked = vec![false; graph.vertices()];
let mut count = 0;
let mut stack = Vec::new();
stack.push(start);
while let Some(v) = stack.pop() {
count += 1;
marked[v] = true;
for w in graph.adjacent(v) {
if !marked[w] {
stack.push(w);
}
}
}
DFSResult(marked, start, count)
}
#[must_use = "Running Breadth-First-Search without using the result is meaningless"]
pub struct BFSResult(Vec<bool>, usize, usize);
impl BFSResult {
pub fn marked(&self) -> &Vec<bool> {
&self.0
}
pub fn start(&self) -> usize {
self.1
}
pub fn amount(&self) -> usize {
self.2
}
pub fn has_path_to(&self, w: usize) -> bool {
self.0.get(w).is_some_and(|&v| v)
}
}
pub fn bfs<T: Graph>(graph: &T, start: usize) -> BFSResult {
if graph.vertices() <= start {
panic!("start is not in vertex set")
}
let mut marked = vec![false; graph.vertices()];
let mut count = 0;
let mut queue = Queue::new();
queue.enqueue(start);
while let Some(v) = queue.dequeue() {
count += 1;
for w in graph.adjacent(v) {
if !marked[w] {
marked[w] = true;
queue.enqueue(w);
}
}
}
BFSResult(marked, start, count)
}