luka 0.4.0

//! Library for working with graphs
//! # Example
//! ```rust
//! use luka::Graph;
//! use luka::utils;
//! use luka::algorithms;
//!
//! let mut graph = Graph::new(100);
//!
//! graph.add_edge(1, 2, 0).unwrap();
//! graph.add_edge(1, 3, 0).unwrap();
//! graph.add_edge(2, 4, 0).unwrap();
//! graph.add_edge(3, 4, 0).unwrap();
//! graph.add_edge(4, 5, 0).unwrap();
//!
//! let start = graph.get_vertex(1).unwrap();
//! let target = graph.get_vertex(17).unwrap();
//! let parents = algorithms::bfs(&graph, &start).unwrap();
//! match utils::find_path(&graph, &target, &parents).unwrap() {
//!     Some(path) => {
//!         assert_eq!(path.iter().map(|vertex|vertex.id()).collect::<Vec<usize>>(), vec![1, 2, 4, 8, 17]);
//!     }
//!     None => {
//!        println!("Path not found !!!")
//!     }
//! }
//! ```

use crate::error::{GraphError, ErrorKind};

pub mod error;
pub mod algorithms;
pub mod utils;
mod stack;
mod dsu;

pub struct Vertex <T> {
    id: usize,
    edges: Vec<Edge<T>>
}

impl <T> Vertex<T> {
    fn new(id: usize) -> Self {
        Vertex{ id, edges: vec![] }
    }

    /// Return identification (id) of vertex
    pub fn id(&self) -> usize {
        self.id
    }
}

struct Edge<T> {
    to: usize,
    #[allow(dead_code)]
    weight: T
}

impl <T> Edge<T> {
    fn new(to: usize, weight: T) -> Self {
        Edge{ to, weight }
    }
}

pub struct Graph <T> {
    adj: Vec<Vertex<T>>
}

impl <T> Graph<T> {
    /// Create a new graph, where n is the number of vertices in the graph
    ///```
    /// use luka::Graph;
    /// let mut graph: Graph<f32> = Graph::new(10);
    /// ```
    pub fn new(n: usize) -> Self {
        let mut vertices = Vec::with_capacity(n + 1);
        for id in 0..=n {
            vertices.push(Vertex::new(id));
        }
        Graph{
            adj: vertices
        }
    }
    /// Create a new edge
    ///```
    /// use luka::Graph;
    /// let mut graph = Graph::new(10);
    /// graph.add_edge(1, 2, 0u8).unwrap();
    /// ```
    pub fn add_edge(&mut self, from: usize, to: usize, weight: T) -> Result<(), GraphError> {
        let bound = self.adj.len() - 1;
        if from > bound || to > bound || from == 0 || to == 0 {
            return Err(GraphError::Regular(ErrorKind::UnableCreateEdge(from, to)))
        }
        self.adj[from].edges.push(Edge::new(to, weight));
        Ok(())
    }

    fn size(&self) -> usize {
        self.adj.len()
    }

    pub fn get_vertex(&self, id: usize) -> Result<&Vertex<T>, GraphError> {
        if id > self.size() - 1 || id == 0 {
            return Err(GraphError::Regular(ErrorKind::VertexNotFound(id)));
        }
        Ok(&self.adj[id])
    }
}