simple-graph 0.1.1

use std::collections::{hash_map::DefaultHasher, HashMap, HashSet, VecDeque};
use std::hash::Hasher;

use linked_hash_map::LinkedHashMap;
use linked_hash_set::LinkedHashSet;

use super::{GraphOperationError, Label, Result};

/// Represents hash of vertex and is used to access the HashMap
#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Hash)]
pub struct VertexId(u64);

/// Directed graph data-structure with generic parameters
///
/// It is assumed that the user can specify the data types stored at each vertex and edge.
///
/// For example, if you want to make a structure like this:
/// `(town1) <----- 100 km -----> (town2)`
/// you can use [`Graph<String, u32>`] data type
///
/// ### Serialization to [`String`] in Trivial Graph Format
/// See [`impl<V, E> Display for Graph<V, E>`](#impl-Display-for-Graph<V%2C%20E>)
///
/// ### Deserialization from [`&str`] in Trivial Graph Format
/// See [`impl<V, E> FromStr for Graph<V, E>`](#impl-FromStr-for-Graph<V%2C%20E>)
///
/// ### Example
/// In this example, we will make several cities and link them together with specified distance in km
///
/// ```
/// use simple_graph::Graph;
/// use std::str::FromStr;
///
/// let mut graph = Graph::<String, u32>::new();
///
/// let moscow = graph.add_vertex("Moscow".into()).unwrap();
/// let vladimir = graph.add_vertex("Vladimir".into()).unwrap();
/// let yaroslavl = graph.add_vertex("Yaroslavl".into()).unwrap();
/// let novgorod = graph.add_vertex("Novgorod".into()).unwrap();
/// let vologda = graph.add_vertex("Vologda".into()).unwrap();
///
/// graph.add_edge(moscow, vladimir, 180).unwrap();
/// graph.add_edge(moscow, yaroslavl, 250).unwrap();
/// graph.add_edge(vladimir, novgorod, 225).unwrap();
/// graph.add_edge(yaroslavl, vologda, 175).unwrap();
///
/// let serialized = graph.to_string();
/// let expected = concat!(
///     "1 Moscow\n",
///     "2 Vladimir\n",
///     "3 Yaroslavl\n",
///     "4 Novgorod\n",
///     "5 Vologda\n",
///     "#\n",
///     "1 2 180\n",
///     "1 3 250\n",
///     "2 4 225\n",
///     "3 5 175\n",
/// );
/// assert_eq!(serialized, expected);
///
/// let mut graph_deserialized = Graph::from_str(&serialized).unwrap();
/// assert_eq!(graph, graph_deserialized);
/// ```
#[derive(Debug, Default, Eq, PartialEq)]
pub struct Graph<V: Label, E: Label> {
    pub(crate) vertices: LinkedHashMap<VertexId, LinkedHashSet<([VertexId; 2], E)>>,
    pub(crate) vertices_data: HashMap<VertexId, V>,
}

impl<V: Label, E: Label> Graph<V, E> {
    /// Creates new graph
    ///
    /// ```
    /// use simple_graph::Graph;
    ///
    /// let _: Graph<String, u32> = Graph::new();
    /// ```
    pub fn new() -> Self {
        Self::default()
    }

    /// Gets [`VertexId`] by it's value. It just creates hash of the `&V`, doesn't panics
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> = Graph::new();
    /// assert_ne!(graph.get_vertex_id(&"Moscow".into()), graph.get_vertex_id(&"Vladimir".into()));
    ///
    /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// let moscow = graph.get_vertex_id(&"Moscow".into());
    /// let vladimir = graph.get_vertex_id(&"Vladimir".into());
    ///
    /// assert_eq!(graph.get_edge_value(moscow, vladimir), Ok(&180));
    /// ```
    pub fn get_vertex_id(&self, vertex: &V) -> VertexId {
        let mut hasher = DefaultHasher::new();
        vertex.hash(&mut hasher);
        VertexId(hasher.finish())
    }

    /// Trying to add vertex to the graph, returns [`GraphOperationError::VertexAlreadyExists`]
    /// if can't do this
    ///
    ///
    /// ```
    /// use simple_graph::{Graph, GraphOperationError};
    ///
    /// let mut graph: Graph<String, u32> = Graph::new();
    ///
    /// assert!(graph.add_vertex("Moscow".into()).is_ok());
    /// assert_eq!(graph.add_vertex("Moscow".into()), Err(GraphOperationError::VertexAlreadyExists));
    /// ```
    pub fn add_vertex(&mut self, vertex: V) -> Result<VertexId> {
        let vertex_id = self.get_vertex_id(&vertex);
        if self
            .vertices
            .insert(vertex_id, LinkedHashSet::new())
            .is_some()
        {
            return Err(GraphOperationError::VertexAlreadyExists);
        }
        self.vertices_data.insert(vertex_id, vertex);
        Ok(vertex_id)
    }

    /// Trying to get vertex by id, returns [`GraphOperationError::VertexDoesNotExist`]
    /// if can't do this
    ///
    /// ```
    /// use simple_graph::{Graph, GraphOperationError};
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// assert!(graph.get_vertex(graph.get_vertex_id(&"Moscow".into())).is_ok());
    /// assert_eq!(graph.get_vertex(graph.get_vertex_id(&"New York".into())), Err(GraphOperationError::VertexDoesNotExist));
    /// ```
    pub fn get_vertex(&self, vertex: VertexId) -> Result<&V> {
        self.vertices_data
            .get(&vertex)
            .ok_or(GraphOperationError::VertexDoesNotExist)
    }

    /// Trying to remove vertex by id, returns [`GraphOperationError::VertexDoesNotExist`]
    /// if can't do this
    ///
    /// ```
    /// use simple_graph::{Graph, GraphOperationError};
    /// use std::str::FromStr;
    ///
    /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// assert!(graph.remove_vertex(graph.get_vertex_id(&"Moscow".into())).is_ok());
    /// assert_eq!(graph.remove_vertex(graph.get_vertex_id(&"New York".into())), Err(GraphOperationError::VertexDoesNotExist));
    ///
    /// assert_eq!(graph.vertices_count(), 4);
    /// ```
    pub fn remove_vertex(&mut self, target_vertex: VertexId) -> Result<()> {
        self.get_vertex(target_vertex)?;

        let mut pairs = Vec::new();
        for &other_vertex in self.vertices.keys() {
            if let Ok(edge) = self.get_edge(other_vertex, target_vertex).cloned() {
                pairs.push((other_vertex, edge));
            }
        }

        for (other_vertex, edge) in &pairs {
            if let Some(neighbours) = self.vertices.get_mut(other_vertex) {
                neighbours.remove(edge);
            }
        }

        self.vertices.remove(&target_vertex);
        self.vertices_data.remove(&target_vertex);

        Ok(())
    }

    /// Trying to add edge between two vertices, returns [`GraphOperationError::VertexDoesNotExist`]
    /// if can't do this
    ///
    /// ```
    /// use simple_graph::{Graph, GraphOperationError};
    /// use std::str::FromStr;
    ///
    /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// let novgorod = graph.get_vertex_id(&"Novgorod".into());
    /// let kazan = graph.add_vertex("Kazan".into()).unwrap();
    /// let new_york = graph.get_vertex_id(&"New York".into());
    ///
    /// assert!(graph.add_edge(novgorod, kazan, 325).is_ok());
    /// assert_eq!(graph.add_edge(new_york, kazan, 9000), Err(GraphOperationError::VertexDoesNotExist));
    /// ```
    pub fn add_edge(&mut self, from: VertexId, to: VertexId, edge: E) -> Result<()> {
        if self.vertices.get(&to).is_some() {
            if let Some(neighbours) = self.vertices.get_mut(&from) {
                neighbours.insert(([from, to], edge));
                return Ok(());
            }
        }
        Err(GraphOperationError::VertexDoesNotExist)
    }

    /// Trying to get edge between two vertices, returns [`GraphOperationError::EdgeDoesNotExist`]
    /// if can't do this
    ///
    /// ```
    /// use simple_graph::{Graph, GraphOperationError};
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// let moscow = graph.get_vertex_id(&"Moscow".into());
    /// let vladimir = graph.get_vertex_id(&"Vladimir".into());
    ///
    /// // Moscow -> Vladimir (ok)
    /// let ([_from, _to], value) = graph.get_edge(moscow, vladimir).unwrap();
    /// assert_eq!(value, &180);
    /// // Vladimir -> Moscow (err)
    /// assert_eq!(graph.get_edge(vladimir, moscow), Err(GraphOperationError::EdgeDoesNotExist));
    /// ```
    pub fn get_edge(&self, from: VertexId, to: VertexId) -> Result<&([VertexId; 2], E)> {
        if let Some(neighbours) = self.vertices.get(&from) {
            for edge in neighbours {
                let [_, destination_vertex] = edge.0;
                if destination_vertex == to {
                    return Ok(edge);
                }
            }
        }
        Err(GraphOperationError::EdgeDoesNotExist)
    }

    /// Trying to get edge **value** between two vertices, returns [`GraphOperationError::EdgeDoesNotExist`]
    /// if can't do this
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// let moscow = graph.get_vertex_id(&"Moscow".into());
    /// let vladimir = graph.get_vertex_id(&"Vladimir".into());
    ///
    /// assert_eq!(graph.get_edge_value(moscow, vladimir), Ok(&180));
    /// ```
    pub fn get_edge_value(&self, from: VertexId, to: VertexId) -> Result<&E> {
        let (_, value) = self.get_edge(from, to)?;
        Ok(value)
    }

    /// Trying to remove edge between two vertices, returns [`GraphOperationError::EdgeDoesNotExist`]
    /// if can't do this
    ///
    /// ```
    /// use simple_graph::{Graph, GraphOperationError};
    /// use std::str::FromStr;
    ///
    /// let mut  graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// let moscow = graph.get_vertex_id(&"Moscow".into());
    /// let vladimir = graph.get_vertex_id(&"Vladimir".into());
    ///
    /// assert!(graph.remove_edge(moscow, vladimir).is_ok());
    /// assert_eq!(graph.remove_edge(moscow, vladimir), Err(GraphOperationError::EdgeDoesNotExist));
    /// ```
    pub fn remove_edge(&mut self, from: VertexId, to: VertexId) -> Result<()> {
        if let Ok(edge) = self.get_edge(from, to).cloned() {
            if let Some(neighbours) = self.vertices.get_mut(&from) {
                neighbours.remove(&edge);
                return Ok(());
            }
        }
        Err(GraphOperationError::EdgeDoesNotExist)
    }

    /// Returns count of vertices in the graph
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    /// assert_eq!(graph.vertices_count(), 5);
    /// ```
    pub fn vertices_count(&self) -> usize {
        self.vertices.len()
    }

    /// Returns count of edges in the graph
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let mut graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    /// assert_eq!(graph.edges_count(), 4);
    /// ```
    pub fn edges_count(&self) -> usize {
        let mut count = 0;
        for (_, neighbours) in self.vertices.iter() {
            count += neighbours.len();
        }
        count
    }

    /// Returns [`Result<Vec<(&V, Vec<(&V, &E)>)>>`] which is vertices representation
    ///
    /// where
    /// - `&V` - vertex
    /// - `Vec<(&V, &E)>` - adjacent vertices
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// for (vertex, adjacent_vertices) in graph.vertices().unwrap() {
    ///     println!("{vertex}: {adjacent_vertices:?}");
    /// }
    ///
    /// //output looks like
    ///
    /// //Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]
    /// //Vladimir: [("Novgorod", 225)]
    /// //Yaroslavl: [("Vologda", 175)]
    /// //Novgorod: []
    /// //Vologda: []
    /// ```
    #[allow(clippy::type_complexity)]
    pub fn vertices(&self) -> Result<Vec<(&V, Vec<(&V, &E)>)>> {
        self.vertices
            .keys()
            .map(|&id| self.get_vertex_info(id))
            .collect::<Result<Vec<_>>>()
    }

    /// Returns [`Result<Vec<([&V; 2], &E)>>`] which is edges representation
    ///
    /// where
    /// - `[&V; 2]` - `[from, to]`
    /// - `&E` - edge data
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// for ([from, to], data) in graph.edges().unwrap() {
    ///    println!("{from} ---- [{data}] ----> {to}");
    /// }
    ///
    /// //output looks like
    ///
    /// //Moscow ---- [180] ----> Vladimir
    /// //Moscow ---- [250] ----> Yaroslavl
    /// //Vladimir ---- [225] ----> Novgorod
    /// //Yaroslavl ---- [175] ----> Vologda
    /// ```
    pub fn edges(&self) -> Result<Vec<([&V; 2], &E)>> {
        let mut edges = Vec::new();
        for (_, neighbours) in self.vertices.iter() {
            for ([from, to], edge) in neighbours {
                edges.push(([self.get_vertex(*from)?, self.get_vertex(*to)?], edge));
            }
        }
        Ok(edges)
    }

    /// Trying to get detailed information about the vertex
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> = Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// let moscow = graph.get_vertex_id(&"Moscow".into());
    ///
    /// let (vertex_data, adjacent_vertices) = graph.get_vertex_info(moscow).unwrap();
    /// assert_eq!(vertex_data, &String::from("Moscow"));
    /// assert_eq!(adjacent_vertices, vec![(&"Vladimir".into(), &180), (&"Yaroslavl".into(), &250)]);
    /// ```
    pub fn get_vertex_info(&self, vertex_id: VertexId) -> Result<(&V, Vec<(&V, &E)>)> {
        let vertex = self.get_vertex(vertex_id)?;

        let mut adjacent_vertices = Vec::new();
        if let Some(neighbours) = self.vertices.get(&vertex_id) {
            for ([_, vertex], edge) in neighbours {
                adjacent_vertices.push((self.get_vertex(*vertex)?, edge));
            }
        }

        Ok((vertex, adjacent_vertices))
    }

    /// Generic search algorithm for implementation BFS and DFS.
    /// It uses generic queue type and queue operations to prevent code duplication
    fn generic_search<
        QueueTy,
        QueueInitFn: Fn() -> QueueTy,
        QueueInsertFn: Fn(&mut QueueTy, VertexId),
        QueueRemoveFn: Fn(&mut QueueTy) -> Option<VertexId>,
        AccessFn: FnMut(&V, Vec<(&V, &E)>),
    >(
        &self,
        queue_init: QueueInitFn,
        queue_insert: QueueInsertFn,
        queue_remove: QueueRemoveFn,
        source: VertexId,
        mut access: AccessFn,
    ) -> Result<()> {
        let mut queue = queue_init();
        let mut visited = HashSet::new();

        queue_insert(&mut queue, source);
        visited.insert(source);

        while let Some(vertex) = queue_remove(&mut queue) {
            let (vertex, adjacent_vertices) = self.get_vertex_info(vertex)?;
            for (adjacent_vertex, _) in adjacent_vertices.iter() {
                let id = self.get_vertex_id(adjacent_vertex);
                if !visited.contains(&id) {
                    queue_insert(&mut queue, id);
                    visited.insert(id);
                }
            }
            access(vertex, adjacent_vertices);
        }

        Ok(())
    }

    /// Breadth-first search algorithm uses [`VecDeque`] for queue
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> =
    ///     Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// let moscow = graph.get_vertex_id(&"Moscow".into());
    ///
    /// let mut visited = Vec::new();
    /// graph
    ///     .bfs(moscow, |vertex, adjacent_vertices| {
    ///         visited.push(format!("{vertex}: {adjacent_vertices:?}"));
    ///     })
    ///     .expect("failed to perform BFS");
    ///
    /// //(1) Moscow ->
    /// //              (2) Vladimir  -> (4) Novgorod
    /// //              (3) Yaroslavl -> (5) Vologda
    /// let expected = vec![
    ///     r#"Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]"#, //1
    ///     r#"Vladimir: [("Novgorod", 225)]"#, //2
    ///     r#"Yaroslavl: [("Vologda", 175)]"#, //3
    ///     r#"Novgorod: []"#, //4
    ///     r#"Vologda: []"#, //5
    /// ];
    /// assert_eq!(visited, expected);
    /// ```
    pub fn bfs<F: FnMut(&V, Vec<(&V, &E)>)>(&self, source: VertexId, access: F) -> Result<()> {
        self.generic_search(
            VecDeque::new,
            |queue, vertex| queue.push_back(vertex),
            |queue| queue.pop_front(),
            source,
            access,
        )
    }

    /// Depth-first search algorithm uses [`Vec`] for stack
    ///
    /// ```
    /// use simple_graph::Graph;
    /// use std::str::FromStr;
    ///
    /// let graph: Graph<String, u32> =
    ///     Graph::from_str(include_str!("../test_input/moscow.tgf")).unwrap();
    ///
    /// let moscow = graph.get_vertex_id(&"Moscow".into());
    ///
    /// let mut visited = Vec::new();
    /// graph
    ///     .dfs(moscow, |vertex, adjacent_vertices| {
    ///         visited.push(format!("{vertex}: {adjacent_vertices:?}"));
    ///     })
    ///     .expect("failed to perform DFS");
    ///
    /// //(1) Moscow ->
    /// //              (2) Yaroslavl  -> (3) Vologda
    /// //              (4) Vladimir   -> (5) Novgorod
    /// let expected = vec![
    ///     r#"Moscow: [("Vladimir", 180), ("Yaroslavl", 250)]"#,
    ///     r#"Yaroslavl: [("Vologda", 175)]"#,
    ///     r#"Vologda: []"#,
    ///     r#"Vladimir: [("Novgorod", 225)]"#,
    ///     r#"Novgorod: []"#,
    /// ];
    /// assert_eq!(visited, expected);
    /// ```
    pub fn dfs<F: FnMut(&V, Vec<(&V, &E)>)>(&self, source: VertexId, access: F) -> Result<()> {
        self.generic_search(
            Vec::new,
            |stack, vertex| stack.push(vertex),
            |stack| stack.pop(),
            source,
            access,
        )
    }
}