graphlang 0.1.3

use serde::{Deserialize, Serialize};

use crate::primitives::{Index, Label};
use crate::{Edge, Isomorphism, Node};

/// A `Graph` is in principle a owning tuple of Nodes and Edges.
#[derive(Serialize, Deserialize, Clone, Debug)]
pub struct Graph<I: Index, NL: Label, EL: Label> {
    pub nodes: Vec<Node<I, NL>>,
    pub edges: Vec<Edge<I, EL>>,
}

impl<I: Index, NL: Label, EL: Label> Graph<I, NL, EL> {
    pub fn contains_edge_with_ids(&self, edge: &(I, I)) -> bool {
        for e in &self.edges {
            if e.from == edge.0 && e.to == edge.1 {
                return true;
            }
        }
        false
    }

    pub fn contains_node_with_id(&self, node: &I) -> bool {
        for n in &self.nodes {
            if &n.id == node {
                return true;
            }
        }
        false
    }

    pub fn get_node_by_id(&self, idx: &I) -> Option<&Node<I, NL>> {
        for n in &self.nodes {
            if &n.id == idx {
                return Some(n);
            }
        }
        None
    }

    /// Returns all nodes connected to the given node id
    pub fn neighbours(&self, nodeid: &I) -> Vec<Node<I, NL>> {
        let mut neighbours = Vec::new();

        // Check if there exists a edge (node, id) or (id, node)
        for edge in &self.edges {
            if &edge.from == nodeid {
                let node = self
                    .get_node_by_id(&edge.to.clone())
                    .expect("Edges contain only valid node ids");
                if !neighbours.contains(node) {
                    neighbours.push(node.clone());
                }
            } else if &edge.to == nodeid {
                let node = self
                    .get_node_by_id(&edge.from.clone())
                    .expect("Edges contain only valid node ids");
                if !neighbours.contains(node) {
                    neighbours.push(node.clone());
                }
            }
        }
        neighbours
    }

    /// Removes edges that either come from or incident on invalid nodes.
    ///
    /// # Examples
    ///
    /// ```
    /// use graphlang::{Node,Edge,Graph,are_graphs_isomorph};
    /// let mut graph = Graph {
    ///         nodes: vec![ Node::new(0u32, "a"), Node::new(1, "a") ],
    ///         edges: vec![ Edge::new_unlabeled(0, 1), Edge::new_unlabeled(0, 2), Edge::new_unlabeled(2, 3) ] };
    /// let reference = Graph {
    ///         nodes: vec![ Node::new(0u32, "a"), Node::new(1, "a") ],
    ///         edges: vec![ Edge::new_unlabeled(0, 1) ] };
    ///
    /// graph.cleanup_edges();
    /// assert_eq!(&reference, &graph );
    /// ```
    pub fn cleanup_edges(&mut self) {
        self.edges = self
            .edges
            .iter()
            .filter(|e| {
                let mut found_src = false;
                let mut found_dst = false;
                for n in &self.nodes {
                    if n.id == e.from {
                        found_src = true;
                        if found_src && found_dst {
                            break;
                        }
                    } else if n.id == e.to {
                        found_dst = true;
                        if found_src && found_dst {
                            break;
                        }
                    }
                }
                found_src && found_dst
            })
            .cloned()
            .collect();
    }

    /// Assumes that the mapping between it and the graph is the identity.
    /// So Node(1) in g adds Node(1) in self. If this is not desired
    /// apply an isomorphism explicitly using `translate_copy`.
    /// If then node already exists it replaces the label.
    pub fn insert(&mut self, g: &Self) {
        // Add nodes
        for n in &g.nodes {
            if !self.nodes.contains(n) {
                self.nodes.push(n.clone());
            } // TODO: Replace otherwise?
        }
        // Add edges
        for e in &g.edges {
            if !self.edges.contains(e) {
                self.edges.push(e.clone());
            } // TODO: Replace otherwise?
        }
    }

    /// Assumes that the mapping between it and the graph is the identity.
    /// So Node(1) in g removes Node(1) in self. If this is not desired
    /// apply an isomorphism explicitly using `translate_copy`
    /// If then node does not exists it skips it.
    pub fn remove(&mut self, g: &Self) {
        // Remove nodes
        self.nodes = self
            .nodes
            .iter()
            .filter(|n| !g.nodes.contains(n))
            .cloned()
            .collect();

        // Remove edges
        self.cleanup_edges();
    }

    /// Modifies a graph inplace by translating all ids using an isomorphism. If it contains nodes that are not
    /// covered by the isomorphism they are not modified, which can lead to invalid graphs.
    /// This behaviour should be reconsidered.
    pub fn translate(&mut self, g: &Isomorphism<I>) -> bool {
        // Translate nodes:
        for node in &mut self.nodes {
            if let Some(id) = g.0.get(&node.id) {
                node.id = id.clone();
            } else {
                return false;
            }
        }
        for edge in &mut self.edges {
            if let (Some(from), Some(to)) = (g.0.get(&edge.from), g.0.get(&edge.to)) {
                edge.from = from.clone();
                edge.to = to.clone();
            } else {
                return false;
            }
        }
        true
    }

    /// Returns a graph, that gets translated by an isomorphism. If it contains nodes that are not
    /// covered by the isomorphism they are not modified, which can lead to invalid graphs.
    /// This behaviour should be reconsidered.
    #[must_use]
    pub fn translate_copy(&self, g: &Isomorphism<I>) -> Self {
        let mut s = self.clone();
        s.translate(g);
        s
    }
}

impl<I: Index> From<Graph<I, &str, ()>> for Graph<I, String, ()> {
    fn from(g: Graph<I, &str, ()>) -> Self {
        let nodes = g
            .nodes
            .iter()
            .map(|n| Node::new(n.id.clone(), n.label.to_owned()))
            .collect();
        Self {
            nodes,
            edges: g.edges,
        }
    }
}

impl<I: Index, NL: Label, EL: Label> core::ops::Add for Graph<I, NL, EL> {
    type Output = Self;
    fn add(mut self, rhs: Self) -> Self::Output {
        self.insert(&rhs);
        self
    }
}

impl<'a, I: Index, NL: Label, EL: Label> core::ops::Add<&'a Graph<I, NL, EL>>
    for &'a Graph<I, NL, EL>
{
    type Output = Graph<I, NL, EL>;
    fn add(self, rhs: Self) -> Self::Output {
        let mut s = self.clone();
        s.insert(rhs);
        s
    }
}

impl<I: Index, NL: Label, EL: Label> core::ops::Sub for Graph<I, NL, EL> {
    type Output = Self;
    fn sub(mut self, rhs: Self) -> Self::Output {
        self.remove(&rhs);
        self
    }
}

impl<'a, I: Index, NL: Label, EL: Label> core::ops::Sub<&'a Graph<I, NL, EL>>
    for &'a Graph<I, NL, EL>
{
    type Output = Graph<I, NL, EL>;
    fn sub(self, rhs: Self) -> Self::Output {
        let mut s = self.clone();
        s.remove(rhs);
        s
    }
}

impl<'a, I: Index, NL: Label, EL: Label> core::ops::Sub<&'a [I]> for &'a Graph<I, NL, EL> {
    type Output = Graph<I, NL, EL>;
    fn sub(self, rhs: &'a [I]) -> Self::Output {
        let nodes = self
            .nodes
            .iter()
            .filter(|n| !rhs.contains(&n.id))
            .cloned()
            .collect();
        let mut graph = Graph {
            nodes,
            edges: self.edges.clone(),
        };
        graph.cleanup_edges();
        graph
    }
}

impl<I: Index, NL: Label, EL: Label> PartialEq for Graph<I, NL, EL> {
    fn eq(&self, other: &Self) -> bool {
        // Compare nodes
        for n in &self.nodes {
            if !other.nodes.contains(n) {
                return false;
            }
        }
        for e in &self.edges {
            if !other.edges.contains(e) {
                return false;
            }
        }
        true
    }
}

//  ------------------------------ DOT FEATURE ------------------------------

use std::borrow::Cow;

impl<'a, I: Index, NL: Label, EL: Label> dot::Labeller<'a, Node<I, NL>, Edge<I, EL>>
    for Graph<I, NL, EL>
{
    fn graph_id(&'a self) -> dot::Id<'a> {
        log::warn!("Labelling graph");
        dot::Id::new("TODOGraphIdentifier").unwrap()
    }

    fn node_id(&'a self, n: &Node<I, NL>) -> dot::Id<'a> {
        log::warn!("Labelling node: {:?}", n);
        //dot::Id::new(format!("{:?}:{:?}", &n.id, &n.label)).unwrap()
        dot::Id::new(format!("N{:?}", &n.id)).unwrap()
    }
}

impl<'a, I: Index, NL: Label, EL: Label> dot::GraphWalk<'a, Node<I, NL>, Edge<I, EL>>
    for Graph<I, NL, EL>
{
    fn nodes(&'a self) -> dot::Nodes<'a, Node<I, NL>> {
        Cow::Borrowed(&self.nodes[..])
    }

    fn edges(&'a self) -> dot::Edges<'a, Edge<I, EL>> {
        Cow::Borrowed(&self.edges[..])
    }

    fn source(&self, e: &Edge<I, EL>) -> Node<I, NL> {
        self.get_node_by_id(&e.from).unwrap().clone()
    }

    fn target(&self, e: &Edge<I, EL>) -> Node<I, NL> {
        self.get_node_by_id(&e.to).unwrap().clone()
    }
}

impl<I: Index, NL: Label, EL: Label> Graph<I, NL, EL> {
    /// Write graph using the dot-format to `output`. It can be easily visualized using `graphviz`
    ///
    /// # Examples
    ///
    /// ```
    /// use graphlang::Graph;
    /// # fn create_graph_somehow() -> Graph<u32,&'static str,()> {
    /// #   graphlang::predefined::string_grammar().start_graph.clone()
    /// # }
    /// # fn test() -> std::io::Result<()> {
    /// let graph: Graph<_,_,_> = create_graph_somehow();
    /// let mut f = std::fs::File::create("Example.dot")?;
    /// graph.write_dot_to(&mut f)?;
    /// #   Ok(())
    /// # }
    /// # test().expect("Doc test for write_dot_to works");
    /// ```
    ///
    /// # Errors
    /// ...
    pub fn write_dot_to<W: std::io::Write>(&self, output: &mut W) -> std::io::Result<()> {
        dot::render(self, output)
    }
}

/// A nonowning `Graph`
//#[derive(Serialize, Clone, PartialEq, Debug)]
//pub struct Subgraph<'a, I: Index, NL: Label, EL: Label> {
//    pub nodes: Vec<&'a Node<I, NL>>,
//    pub edges: Vec<&'a Edge<I, EL>>,
//}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn insert() {
        let _ = pretty_env_logger::try_init_timed();
        let g = Graph {
            nodes: vec![Node::new(0u32, "a")],
            edges: vec![],
        };
        let h = Graph {
            nodes: vec![Node::new(1, "a")],
            edges: vec![Edge::new_unlabeled(0, 1)],
        };
        let r = Graph {
            nodes: vec![Node::new(0u32, "a"), Node::new(1, "a")],
            edges: vec![Edge::new_unlabeled(0, 1)],
        };
        assert_eq!(&g + &h, r.clone());
        assert_eq!(g.clone() + h.clone(), r.clone());
        let d = {
            let mut g = g.clone();
            g.insert(&h);
            g
        };
        assert_eq!(d, r);
    }

    #[test]
    fn remove() {
        let _ = pretty_env_logger::try_init_timed();
        let g = Graph {
            nodes: vec![Node::new(0u32, "a"), Node::new(1, "a")],
            edges: vec![Edge::new_unlabeled(0, 1)],
        };
        let h = Graph {
            nodes: vec![Node::new(1, "a")],
            edges: vec![Edge::new_unlabeled(0, 1)],
        };
        let r = Graph {
            nodes: vec![Node::new(0, "a")],
            edges: vec![],
        };
        assert_eq!(&g - &h, r.clone());
        assert_eq!(g.clone() - h.clone(), r.clone());
        let d = {
            let mut g = g.clone();
            g.remove(&h);
            g
        };
        assert_eq!(d, r);
    }

    #[test]
    fn cleanup_edges() {
        let _ = pretty_env_logger::try_init_timed();
        let mut g = Graph {
            nodes: vec![Node::new(0u32, "a")],
            edges: vec![Edge::new_unlabeled(0, 1), Edge::new_unlabeled(2, 3)],
        };
        g.cleanup_edges();
        let d = Graph {
            nodes: vec![Node::new(0u32, "a")],
            edges: vec![],
        };
        assert_eq!(g, d);
    }

    #[test]
    fn node_neighbours() {
        let _ = pretty_env_logger::try_init_timed();
        let g = Graph {
            nodes: vec![
                Node::new(0u32, "a"),
                Node::new(1, "a"),
                Node::new(2, "a"),
                Node::new(3, "a"),
            ],
            edges: vec![
                Edge::new_unlabeled(0, 1),
                Edge::new_unlabeled(1, 2),
                Edge::new_unlabeled(1, 3),
            ],
        };
        let reference: Vec<_> = [Node::new(0u32, "a"), Node::new(2, "a"), Node::new(3, "a")].into();
        assert_eq!(reference, g.neighbours(&1));
    }

    #[test]
    fn node_neighbours_extended() {
        let graph = Graph {
            nodes: vec![
                Node::new(0u32, "a"),
                Node::new(1, "a"),
                Node::new(2, "a"),
                Node::new(3, "a"),
            ],
            edges: vec![
                Edge::new_unlabeled(0, 1),
                Edge::new_unlabeled(1, 2),
                Edge::new_unlabeled(1, 3),
                Edge::new_unlabeled(3, 0),
            ],
        };
        assert_eq!(
            graph.neighbours(&1),
            vec![
                Node::new(0u32, "a"),
                Node::new(2u32, "a"),
                Node::new(3u32, "a"),
            ]
        );
        assert_eq!(graph.neighbours(&2), vec![Node::new(1u32, "a"),]);
        assert_eq!(
            graph.neighbours(&3),
            vec![Node::new(1u32, "a"), Node::new(0u32, "a"),]
        );
    }

    #[test]
    fn graph_difference_used_for_reduced_query_graph_gen() {
        let _ = pretty_env_logger::try_init_timed();
        let g = Graph {
            nodes: vec![
                Node::new(0u32, "a"),
                Node::new(1, "a"),
                Node::new(2, "a"),
                Node::new(3, "a"),
            ],
            edges: vec![
                Edge::new_unlabeled(0, 1),
                Edge::new_unlabeled(1, 2),
                Edge::new_unlabeled(1, 3),
                Edge::new_unlabeled(3, 0),
            ],
        };
        let nodes_to_remove = vec![1, 2];
        let reduced_query: Graph<_, _, _> = &g - &nodes_to_remove[..];

        let reference = Graph {
            nodes: vec![Node::new(0u32, "a"), Node::new(3, "a")],
            edges: vec![Edge::new_unlabeled(3, 0)],
        };
        assert_eq!(reference, reduced_query);
    }
}