nm_tagrewriter/

graph.rs

use std::collections::BTreeSet;

use derive_more::derive::{AsRef, Deref, From};
use graph_cycles::Cycles;
use itertools::Itertools;
use petgraph::{
    Graph,
    algo::dijkstra,
    dot::Dot,
    graph::{EdgeIndex, NodeIndex},
};

use crate::{
    common::{Arrow, Imply, LabelledArrow, Quiver},
    state::EffectiveState,
};

/// A types that holds the data for a graph
#[derive(Clone)]
pub struct GraphDataMap {
    nodes_graph: Vec<NodeIndex>,
    nodes_object: Vec<EffectiveState>,

    edges_graph: Vec<EdgeIndex>,
    edges_object: Vec<LabelledArrow>,
}

impl GraphDataMap {
    fn get_state_at_index(&self, index: &NodeIndex) -> Option<&EffectiveState> {
        self.nodes_object
            .get(self.nodes_graph.iter().position(|i| i == index)?)
    }

    fn get_edge_at_index(&self, index: &EdgeIndex) -> Option<&LabelledArrow> {
        self.edges_object
            .get(self.edges_graph.iter().position(|i| i == index)?)
    }

    fn get_edges_from_bounds(
        &self,
        source: &EffectiveState,
        target: &EffectiveState,
    ) -> Vec<&LabelledArrow> {
        self.edges_object
            .iter()
            .filter(|x| ((**x).arrow.source == *source) && ((**x).arrow.target() == *target))
            .collect_vec()
    }

    fn get_edges_from_indexes(
        &self,
        source: &NodeIndex,
        target: &NodeIndex,
    ) -> Vec<&LabelledArrow> {
        let source_object = self.get_state_at_index(source);
        let target_object = self.get_state_at_index(target);

        if let (Some(s), Some(t)) = (source_object, target_object) {
            self.get_edges_from_bounds(s, t)
        } else {
            vec![]
        }
    }
}

type InnerGraph = Graph<String, String>;
/// A wrapper around a graph
#[derive(Deref, Clone, AsRef, From)]
pub struct RewriteGraph(InnerGraph);

/// A graph with all its data
pub struct GraphWithData {
    pub data: GraphDataMap,
    pub graph: RewriteGraph,
}

// TODO: Likely inefficient, too much data is copied
impl GraphWithData {
    /// Construct a graph from a quiver of arrows.
    pub fn from_arrow_list(q: Quiver) -> Self {
        let arrows = q.clone();
        let mut arrows_to_visit = arrows.clone();
        let mut visited_arrows = BTreeSet::new();
        let mut nodes = BTreeSet::new();
        let mut edges = BTreeSet::new();

        while let Some(arrow) = arrows_to_visit.pop_first() {
            let source = arrow.arrow.source.clone();
            let target = arrow.arrow.target();

            for ar in arrows.iter() {
                let ar_source = ar.arrow.source.clone();
                let ar_target = ar.arrow.target();

                if source.implies(&ar_source) && !(source.implies(&ar_target)) {
                    // x_1 -> x_2 and y_1 -> y2 and y_1 => x_1
                    // Then the rule x_1 -> x_2 applies to y_1

                    let new_arrow = ar.move_base_point(source.clone());
                    if visited_arrows.get(&new_arrow).is_none() {
                        arrows_to_visit.insert(new_arrow);
                    }
                }
                if target.implies(&ar_source) && !(target.implies(&ar_target)) {
                    let new_arrow = ar.move_base_point(target.clone());
                    if visited_arrows.get(&new_arrow).is_none() {
                        arrows_to_visit.insert(new_arrow);
                    }
                }
            }
            nodes.insert(source.clone());
            nodes.insert(target.clone());
            edges.insert((source.clone(), target.clone(), arrow.clone()));
            visited_arrows.insert(arrow.clone());
        }
        let mut graph: Graph<String, String> = Graph::new();
        let nodes_list = Vec::from_iter(nodes);
        let edges_list = Vec::from_iter(edges);
        let nodes_graph_elements: Vec<_> = nodes_list
            .iter()
            .map(|s| graph.add_node(s.to_string()))
            .collect();
        let edges_graph_elements: Vec<_> = edges_list
            .iter()
            .map(|(s, t, a)| {
                let si = nodes_list.iter().position(|x| x == s).unwrap();
                let ti = nodes_list.iter().position(|x| x == t).unwrap();

                graph.add_edge(
                    nodes_graph_elements[si],
                    nodes_graph_elements[ti],
                    a.name.clone(),
                )
            })
            .collect();

        let graph_data = GraphDataMap {
            nodes_graph: nodes_graph_elements,
            nodes_object: nodes_list,
            edges_graph: edges_graph_elements,
            edges_object: edges_list.iter().map(|(_, _, a)| a.clone()).collect(),
        };
        GraphWithData {
            data: graph_data,
            graph: graph.into(),
        }
    }

    /// Get a graphviz representation of this graph
    pub fn dot<'a>(&'a self) -> Dot<'a, &'a InnerGraph> {
        let g = self.graph.as_ref();
        Dot::new(g)
    }

    pub fn find_cycles<'a>(&'a self) -> Vec<Cycle<'a>> {
        let raw_cycles = self.graph.as_ref().cycles();
        let cycles = raw_cycles
            .iter()
            .map(|c| Cycle::from_node_indices(self, c.clone()))
            .collect_vec();
        cycles
    }

    pub fn has_cycles(&self) -> bool {
        self.graph.cycles().iter().len() > 0
    }

    /// Find nodes with in-degree 0
    pub fn sources(&self) -> Vec<&NodeIndex> {
        self.data
            .nodes_graph
            .iter()
            .filter(|n| {
                self.graph
                    .neighbors_directed(**n, petgraph::Direction::Incoming)
                    .next()
                    .is_none()
            })
            .collect_vec()
    }

    /// Find nodes with out-degree 0
    pub fn sinks(&self) -> Vec<&NodeIndex> {
        self.data
            .nodes_graph
            .iter()
            .filter(|n| {
                self.graph
                    .neighbors_directed(**n, petgraph::Direction::Outgoing)
                    .next()
                    .is_none()
            })
            .collect_vec()
    }

    fn sinks_from_node(&self, node: &NodeIndex) -> Vec<NodeIndex> {
        let shortest_paths = dijkstra(self.graph.as_ref(), *node, None, |_| 1);
        shortest_paths
            .iter()
            .filter_map(|(i, _)| {
                if self
                    .graph
                    .neighbors_directed(*i, petgraph::Direction::Outgoing)
                    .next()
                    .is_none()
                {
                    Some(i.clone())
                } else {
                    None
                }
            })
            .collect_vec()
    }

    /// Find extremal paths
    fn longest_paths(&self) -> Vec<(NodeIndex, NodeIndex)> {
        let sources = self.sources();
        sources
            .iter()
            .flat_map(|x| {
                self.sinks_from_node(*x)
                    .iter()
                    .map(|y| ((*x).clone(), y.clone()))
                    .collect_vec()
            })
            .collect_vec()
    }

    /// Find transformations to apply
    pub fn find_transformations(&self) -> Vec<Arrow> {
        self.longest_paths()
            .iter()
            .map(|(s, t)| {
                let source = self
                    .data
                    .get_state_at_index(s)
                    .expect("The state should exist.");
                let target = self
                    .data
                    .get_state_at_index(t)
                    .expect("The state should exist.");

                source.compute_vector(target)
            })
            .collect_vec()
    }
}

pub struct Cycle<'a> {
    arrows: Vec<&'a LabelledArrow>,
    nodes: Vec<&'a EffectiveState>,
}

impl<'a> Cycle<'a> {
    fn from_node_indices(g: &'a GraphWithData, cycle: Vec<NodeIndex>) -> Self {
        let previous_index = cycle.last().expect("Cycles have length at most one.");
        let mut previous = g
            .data
            .get_state_at_index(previous_index)
            .expect("No user data in input, so this should always succeed.");

        let mut nodes = Vec::new();
        let mut arrows = Vec::new();
        for element in cycle {
            let node = g
                .data
                .get_state_at_index(&element)
                .expect("Should always succeed.");
            nodes.push(node);
            let arrows_between = g.data.get_edges_from_bounds(previous, node);
            arrows.extend(arrows_between);
            previous = node;
        }

        Cycle { arrows, nodes }
    }

    const LONG_CYCLE: usize = 5;
    const INDENT: &'static str = "  ";

    fn as_string_cycle_node(&self) -> String {
        let separator = if self.nodes.iter().len() >= Self::LONG_CYCLE {
            let indent = Self::INDENT;
            format!("\n{indent}-> ")
        } else {
            " -> ".to_string()
        };

        let inner_string = self.nodes.iter().map(ToString::to_string).join(&separator);
        format!("Cycle … -> {inner_string} -> …")
    }

    fn as_string_cycle_arrows(&self) -> String {
        format!(
            "Induced by rules: {}",
            self.arrows.iter().map(|ar| &ar.name).join(", ")
        )
    }

    pub fn as_string(&self) -> String {
        format!(
            "{}\n{}",
            self.as_string_cycle_node(),
            self.as_string_cycle_arrows()
        )
    }
}