xgraph 3.0.0

//! Graphviz DOT export, written once against [`GraphView`].
//!
//! Any view can be rendered, including a filtered one, so "draw only the rail routes" is a
//! filter away rather than a separate export path.
//!
//! This exists because the repository shipped two Python scripts whose only job was to
//! read a graph back out of CSV and hand it to NetworkX for drawing. A DOT file goes
//! straight into Graphviz, and into every tool that reads it.

use crate::core::view::{EdgeId, GraphView, NodeId};
use std::fmt::Write as _;

/// How a node or edge should be labelled and styled in the output.
///
/// Returned by the [`DotStyle`] hooks. Attributes are written in the order given, and
/// values are quoted and escaped, so they may contain anything.
#[derive(Debug, Clone, Default)]
pub struct DotAttributes {
    attributes: Vec<(String, String)>,
}

impl DotAttributes {
    /// An empty attribute list.
    pub fn new() -> Self {
        Self::default()
    }

    /// Sets an attribute, replacing any previous value for the same key.
    pub fn set(mut self, key: impl Into<String>, value: impl Into<String>) -> Self {
        let key = key.into();
        let value = value.into();
        match self.attributes.iter_mut().find(|(k, _)| *k == key) {
            Some(slot) => slot.1 = value,
            None => self.attributes.push((key, value)),
        }
        self
    }

    /// Convenience for the most common attribute.
    pub fn label(self, label: impl Into<String>) -> Self {
        self.set("label", label)
    }

    /// Whether anything has been set.
    pub fn is_empty(&self) -> bool {
        self.attributes.is_empty()
    }

    /// Renders as a DOT attribute list, without the surrounding brackets.
    fn render(&self) -> String {
        self.attributes
            .iter()
            .map(|(key, value)| format!("{}={}", key, quote(value)))
            .collect::<Vec<_>>()
            .join(", ")
    }
}

/// Decides how each node and edge is drawn.
///
/// The blanket implementation below labels everything with its identifier, which is enough
/// to see the shape of a graph. Implement this to add the data a particular graph carries;
/// the concrete graph types provide implementations that do.
pub trait DotStyle: GraphView {
    /// Attributes for one node.
    fn node_attributes(&self, node: NodeId) -> DotAttributes {
        DotAttributes::new().label(node.to_string())
    }

    /// Attributes for one edge.
    fn edge_attributes(&self, _edge: EdgeId) -> DotAttributes {
        DotAttributes::new()
    }

    /// Attributes applied to the graph as a whole.
    fn graph_attributes(&self) -> DotAttributes {
        DotAttributes::new()
    }
}

/// DOT rendering, available on every [`GraphView`].
pub trait ToDot: GraphView {
    /// Renders the graph as a DOT document, using `style` to decide how it is drawn.
    ///
    /// The document is named `name`, which Graphviz uses as the title.
    fn to_dot_with<S: DotStyle>(&self, name: &str, style: &S) -> String
    where
        Self: Sized,
    {
        // `digraph`/`graph` and `->`/`--` must agree, or the file will not parse.
        let (keyword, connector) = if self.is_directed() {
            ("digraph", "->")
        } else {
            ("graph", "--")
        };

        let mut out = String::new();
        let _ = writeln!(out, "{} {} {{", keyword, quote(name));

        let graph_attributes = style.graph_attributes();
        if !graph_attributes.is_empty() {
            let _ = writeln!(out, "    graph [{}];", graph_attributes.render());
        }

        for node in self.node_ids() {
            let attributes = style.node_attributes(node);
            if attributes.is_empty() {
                let _ = writeln!(out, "    {};", node.index());
            } else {
                let _ = writeln!(out, "    {} [{}];", node.index(), attributes.render());
            }
        }

        // Edges are walked per node so that a filtered view is honoured, and each
        // undirected edge is emitted once by taking it from its lower-numbered end.
        for node in self.node_ids() {
            for link in self.links(node) {
                if !self.is_directed() && link.target < node {
                    continue;
                }
                let attributes = style.edge_attributes(link.edge);
                let line = format!("    {} {} {}", node.index(), connector, link.target.index());
                if attributes.is_empty() {
                    let _ = writeln!(out, "{};", line);
                } else {
                    let _ = writeln!(out, "{} [{}];", line, attributes.render());
                }
            }
        }

        out.push_str("}\n");
        out
    }

    /// Renders the graph as a DOT document with identifiers for labels.
    fn to_dot(&self, name: &str) -> String
    where
        Self: Sized + DotStyle,
    {
        self.to_dot_with(name, self)
    }
}

impl<G: GraphView + ?Sized> ToDot for G {}

/// Wraps a value in double quotes, escaping what DOT would otherwise misread.
fn quote(value: &str) -> String {
    let mut out = String::with_capacity(value.len() + 2);
    out.push('"');
    for c in value.chars() {
        match c {
            '"' => out.push_str("\\\""),
            '\\' => out.push_str("\\\\"),
            '\n' => out.push_str("\\n"),
            _ => out.push(c),
        }
    }
    out.push('"');
    out
}

#[cfg(test)]
#[cfg(feature = "graph")]
mod tests {
    use super::*;
    use crate::core::EdgeFiltered;
    use crate::graph::Graph;

    #[test]
    fn test_an_undirected_graph_uses_the_undirected_syntax() {
        let mut graph = Graph::<u32, &str, &str>::new(false);
        let a = graph.add_node("A");
        let b = graph.add_node("B");
        graph.add_edge(a, b, 1, "rail").unwrap();

        let dot = graph.to_dot("routes");
        assert!(dot.starts_with("graph \"routes\" {\n"));
        assert!(dot.contains("0 -- 1"));
        assert!(!dot.contains("->"));
        assert!(dot.ends_with("}\n"));
    }

    #[test]
    fn test_a_directed_graph_uses_arrows() {
        let mut graph = Graph::<u32, &str, &str>::new(true);
        let a = graph.add_node("A");
        let b = graph.add_node("B");
        graph.add_edge(a, b, 1, "rail").unwrap();

        let dot = graph.to_dot("flow");
        assert!(dot.starts_with("digraph \"flow\" {\n"));
        assert!(dot.contains("0 -> 1"));
    }

    /// An undirected edge appears from both ends in the adjacency, and must still be drawn
    /// once.
    #[test]
    fn test_each_undirected_edge_is_emitted_once() {
        let mut graph = Graph::<u32, &str, &str>::new(false);
        let a = graph.add_node("A");
        let b = graph.add_node("B");
        graph.add_edge(a, b, 1, "rail").unwrap();

        let dot = graph.to_dot("routes");
        assert_eq!(dot.matches("--").count(), 1);
    }

    #[test]
    fn test_parallel_edges_are_all_drawn() {
        let mut graph = Graph::<u32, &str, &str>::new(false);
        let a = graph.add_node("A");
        let b = graph.add_node("B");
        graph.add_edge(a, b, 1, "rail").unwrap();
        graph.add_edge(a, b, 2, "road").unwrap();

        assert_eq!(graph.to_dot("routes").matches("0 -- 1").count(), 2);
    }

    #[test]
    fn test_labels_are_quoted_and_escaped() {
        let mut graph = Graph::<u32, String, String>::new(false);
        let a = graph.add_node("say \"hi\"".into());
        let b = graph.add_node("two\nlines".into());
        graph.add_edge(a, b, 1, "a\\b".into()).unwrap();

        let dot = graph.to_dot_with("routes", &graph);
        assert!(dot.contains(r#"\"hi\""#), "{}", dot);
        assert!(dot.contains(r"two\nlines"), "{}", dot);
        assert!(dot.contains(r"a\\b"), "{}", dot);
    }

    #[test]
    fn test_a_filtered_view_renders_only_what_it_admits() {
        let mut graph = Graph::<u32, &str, &str>::new(false);
        let a = graph.add_node("A");
        let b = graph.add_node("B");
        let c = graph.add_node("C");
        let rail = graph.add_edge(a, b, 1, "rail").unwrap();
        graph.add_edge(b, c, 1, "road").unwrap();

        let rail_only = EdgeFiltered::new(&graph, move |edge| edge == rail);
        let dot = rail_only.to_dot_with("rail", &graph);
        assert_eq!(dot.matches("--").count(), 1);
        // Nodes are still listed, so an isolated one is visible in the drawing.
        assert!(dot.contains("    2 ["));
    }

    #[test]
    fn test_an_empty_graph_still_produces_a_valid_document() {
        let graph = Graph::<u32, &str, &str>::new(false);
        assert_eq!(graph.to_dot("empty"), "graph \"empty\" {\n}\n");
    }
}