weavegraph 0.7.0

//! Optional petgraph compatibility layer.
//!
//! Converts Weavegraph's edge map to petgraph's [`DiGraph`], enabling petgraph's
//! algorithm library and DOT visualization. Requires the `petgraph-compat` feature.
//!
//! ```ignore
//! use weavegraph::graphs::GraphBuilder;
//! use weavegraph::types::NodeKind;
//! use petgraph::algo::is_cyclic_directed;
//!
//! let builder = GraphBuilder::new()
//!     .add_node(NodeKind::Custom("A".into()), my_node)
//!     .add_edge(NodeKind::Start, NodeKind::Custom("A".into()))
//!     .add_edge(NodeKind::Custom("A".into()), NodeKind::End);
//!
//! let pg = builder.to_petgraph();
//! assert!(!is_cyclic_directed(&pg.graph));
//! println!("{}", builder.to_dot());
//! ```

use crate::types::NodeKind;
use petgraph::graph::{DiGraph, NodeIndex};
use rustc_hash::{FxHashMap, FxHashSet};

/// Directed graph with `NodeKind` node weights and unit edge weights.
pub type WeaveDiGraph = DiGraph<NodeKind, ()>;

/// Maps each `NodeKind` to its petgraph [`NodeIndex`].
pub type NodeIndexMap = FxHashMap<NodeKind, NodeIndex>;

/// Result of a Weavegraph-to-petgraph conversion.
#[derive(Debug, Clone)]
pub struct PetgraphConversion {
    /// The converted directed graph.
    pub graph: WeaveDiGraph,
    /// Lookup map from `NodeKind` to petgraph index.
    pub index_map: NodeIndexMap,
}

impl PetgraphConversion {
    /// Returns the petgraph index for `node`, if present.
    #[must_use]
    pub fn index_of(&self, node: &NodeKind) -> Option<NodeIndex> {
        self.index_map.get(node).copied()
    }

    /// Returns the `NodeKind` at `index`, if present.
    #[must_use]
    pub fn node_at(&self, index: NodeIndex) -> Option<&NodeKind> {
        self.graph.node_weight(index)
    }
}

/// Converts a Weavegraph edge map to a petgraph [`DiGraph`].
///
/// Nodes are ordered deterministically: `Start` first, `End` last,
/// `Custom` nodes alphabetically between them.
pub(super) fn to_petgraph(edges: &FxHashMap<NodeKind, Vec<NodeKind>>) -> PetgraphConversion {
    let unique: FxHashSet<NodeKind> = edges
        .iter()
        .flat_map(|(from, tos)| std::iter::once(from).chain(tos))
        .cloned()
        .collect();

    let mut all_nodes: Vec<NodeKind> = unique.into_iter().collect();
    all_nodes.sort_by(|a, b| match (a, b) {
        (NodeKind::Start, _) => std::cmp::Ordering::Less,
        (_, NodeKind::Start) => std::cmp::Ordering::Greater,
        (NodeKind::End, _) => std::cmp::Ordering::Greater,
        (_, NodeKind::End) => std::cmp::Ordering::Less,
        (NodeKind::Custom(a), NodeKind::Custom(b)) => a.cmp(b),
    });

    let mut graph = DiGraph::new();
    let index_map: NodeIndexMap = all_nodes
        .into_iter()
        .map(|node| {
            let idx = graph.add_node(node.clone());
            (node, idx)
        })
        .collect();

    for (from, tos) in edges {
        let from_idx = index_map[from];
        for to in tos {
            graph.add_edge(from_idx, index_map[to], ());
        }
    }

    PetgraphConversion { graph, index_map }
}

/// Renders the graph to DOT format for Graphviz visualization.
///
/// `Start` and `End` nodes receive distinct fill colors. Output is
/// deterministic across calls because node indices are stable.
pub(super) fn to_dot(edges: &FxHashMap<NodeKind, Vec<NodeKind>>) -> String {
    use petgraph::visit::EdgeRef;
    use std::fmt::Write;

    let conversion = to_petgraph(edges);
    let mut out = String::new();

    writeln!(out, "digraph {{").unwrap();
    writeln!(out, "    rankdir=TB;").unwrap();
    writeln!(out, "    node [shape=box, style=rounded];").unwrap();

    for idx in conversion.graph.node_indices() {
        let node = &conversion.graph[idx];
        let (label, style) = match node {
            NodeKind::Start => ("Start", " style=\"filled\" fillcolor=\"lightgreen\""),
            NodeKind::End => ("End", " style=\"filled\" fillcolor=\"lightcoral\""),
            NodeKind::Custom(name) => (name.as_str(), ""),
        };
        writeln!(out, "    {} [ label=\"{}\"{} ];", idx.index(), label, style).unwrap();
    }

    writeln!(out).unwrap();

    for edge in conversion.graph.edge_references() {
        writeln!(
            out,
            "    {} -> {};",
            edge.source().index(),
            edge.target().index()
        )
        .unwrap();
    }

    writeln!(out, "}}").unwrap();
    out
}

/// Returns `true` if the graph contains a directed cycle.
#[must_use]
pub fn is_cyclic(edges: &FxHashMap<NodeKind, Vec<NodeKind>>) -> bool {
    petgraph::algo::is_cyclic_directed(&to_petgraph(edges).graph)
}

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

    fn make_linear_graph() -> FxHashMap<NodeKind, Vec<NodeKind>> {
        let mut edges = FxHashMap::default();
        edges.insert(NodeKind::Start, vec![NodeKind::Custom("A".into())]);
        edges.insert(NodeKind::Custom("A".into()), vec![NodeKind::End]);
        edges
    }

    fn make_cyclic_graph() -> FxHashMap<NodeKind, Vec<NodeKind>> {
        let mut edges = FxHashMap::default();
        edges.insert(NodeKind::Start, vec![NodeKind::Custom("A".into())]);
        edges.insert(
            NodeKind::Custom("A".into()),
            vec![NodeKind::Custom("B".into())],
        );
        edges.insert(
            NodeKind::Custom("B".into()),
            vec![NodeKind::Custom("A".into())],
        );
        edges
    }

    #[test]
    fn test_to_petgraph_linear() {
        let conversion = to_petgraph(&make_linear_graph());

        assert_eq!(conversion.graph.node_count(), 3);
        assert_eq!(conversion.graph.edge_count(), 2);
        assert!(conversion.index_of(&NodeKind::Start).is_some());
        assert!(conversion.index_of(&NodeKind::Custom("A".into())).is_some());
        assert!(conversion.index_of(&NodeKind::End).is_some());
    }

    #[test]
    fn test_is_cyclic_linear() {
        assert!(!is_cyclic(&make_linear_graph()));
    }

    #[test]
    fn test_is_cyclic_with_cycle() {
        assert!(is_cyclic(&make_cyclic_graph()));
    }

    #[test]
    fn test_to_dot_output() {
        let dot = to_dot(&make_linear_graph());
        assert!(dot.contains("digraph {"));
        assert!(dot.contains("Start"));
        assert!(dot.contains("End"));
        assert!(dot.contains("->"));
    }

    #[test]
    fn test_deterministic_indices() {
        let edges = make_linear_graph();
        let conv1 = to_petgraph(&edges);
        let conv2 = to_petgraph(&edges);

        assert_eq!(
            conv1.index_of(&NodeKind::Start),
            conv2.index_of(&NodeKind::Start)
        );
        assert_eq!(
            conv1.index_of(&NodeKind::Custom("A".into())),
            conv2.index_of(&NodeKind::Custom("A".into()))
        );
    }
}