runmat_runtime/builtins/graph/

mod.rs

//! MATLAB-compatible graph and digraph data-type helpers.

use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap, VecDeque};
use std::sync::OnceLock;

use runmat_builtins::{
    Access, BuiltinCompletionPolicy, BuiltinDescriptor, BuiltinErrorDescriptor, BuiltinOutputMode,
    BuiltinParamArity, BuiltinParamDescriptor, BuiltinParamType, BuiltinSignatureDescriptor,
    ClassDef, MethodDef, ObjectInstance, PropertyDef, ResolveContext, StringArray, Tensor, Type,
    Value,
};
use runmat_macros::runtime_builtin;

use crate::builtins::common::tensor;
use crate::builtins::table::{table_from_columns, table_variables};
use crate::{build_runtime_error, gather_if_needed_async, BuiltinResult, RuntimeError};

const GRAPH_CLASS: &str = "graph";
const DIGRAPH_CLASS: &str = "digraph";
const NUM_NODES_PROPERTY: &str = "NumNodes";
const GRAPH_NAME: &str = "graph";
const DIGRAPH_NAME: &str = "digraph";

const INPUT_GRAPH: BuiltinParamDescriptor = BuiltinParamDescriptor {
    name: "G",
    ty: BuiltinParamType::Any,
    arity: BuiltinParamArity::Required,
    default: None,
    description: "Graph or digraph object.",
};
const INPUT_VALUE: BuiltinParamDescriptor = BuiltinParamDescriptor {
    name: "value",
    ty: BuiltinParamType::Any,
    arity: BuiltinParamArity::Required,
    default: None,
    description: "Input value.",
};
const INPUT_REST: BuiltinParamDescriptor = BuiltinParamDescriptor {
    name: "args",
    ty: BuiltinParamType::Any,
    arity: BuiltinParamArity::Variadic,
    default: None,
    description: "Additional arguments.",
};
const OUTPUT_VALUE: BuiltinParamDescriptor = BuiltinParamDescriptor {
    name: "value",
    ty: BuiltinParamType::Any,
    arity: BuiltinParamArity::Required,
    default: None,
    description: "Output value.",
};
const OUTPUTS_ONE: [BuiltinParamDescriptor; 1] = [OUTPUT_VALUE];
const INPUTS_CONSTRUCTOR: [BuiltinParamDescriptor; 2] = [INPUT_VALUE, INPUT_REST];
const INPUTS_GRAPH: [BuiltinParamDescriptor; 1] = [INPUT_GRAPH];
const INPUTS_GRAPH_REST: [BuiltinParamDescriptor; 2] = [INPUT_GRAPH, INPUT_REST];

const GRAPH_SIGNATURES: [BuiltinSignatureDescriptor; 3] = [
    BuiltinSignatureDescriptor {
        label: "G = graph(s, t)",
        inputs: &INPUTS_CONSTRUCTOR,
        outputs: &OUTPUTS_ONE,
    },
    BuiltinSignatureDescriptor {
        label: "G = graph(s, t, weights, names)",
        inputs: &INPUTS_CONSTRUCTOR,
        outputs: &OUTPUTS_ONE,
    },
    BuiltinSignatureDescriptor {
        label: "G = graph(A)",
        inputs: &INPUTS_CONSTRUCTOR,
        outputs: &OUTPUTS_ONE,
    },
];
const DIGRAPH_SIGNATURES: [BuiltinSignatureDescriptor; 2] = [
    BuiltinSignatureDescriptor {
        label: "G = digraph(s, t)",
        inputs: &INPUTS_CONSTRUCTOR,
        outputs: &OUTPUTS_ONE,
    },
    BuiltinSignatureDescriptor {
        label: "G = digraph(A)",
        inputs: &INPUTS_CONSTRUCTOR,
        outputs: &OUTPUTS_ONE,
    },
];
const UNARY_GRAPH_SIGNATURES: [BuiltinSignatureDescriptor; 1] = [BuiltinSignatureDescriptor {
    label: "value = f(G)",
    inputs: &INPUTS_GRAPH,
    outputs: &OUTPUTS_ONE,
}];
const GRAPH_QUERY_SIGNATURES: [BuiltinSignatureDescriptor; 1] = [BuiltinSignatureDescriptor {
    label: "value = f(G, args)",
    inputs: &INPUTS_GRAPH_REST,
    outputs: &OUTPUTS_ONE,
}];

const ERROR_INVALID_ARGUMENT: BuiltinErrorDescriptor = BuiltinErrorDescriptor {
    code: "RM.GRAPH.INVALID_ARGUMENT",
    identifier: Some("RunMat:graph:InvalidArgument"),
    when: "Graph arguments, node ids, node names, edge weights, or output counts are invalid.",
    message: "graph: invalid argument",
};
const ERROR_INTERNAL: BuiltinErrorDescriptor = BuiltinErrorDescriptor {
    code: "RM.GRAPH.INTERNAL",
    identifier: Some("RunMat:graph:Internal"),
    when: "RunMat cannot build the requested graph value or query output.",
    message: "graph: internal error",
};
const GRAPH_ERRORS: [BuiltinErrorDescriptor; 2] = [ERROR_INVALID_ARGUMENT, ERROR_INTERNAL];

pub const GRAPH_DESCRIPTOR: BuiltinDescriptor = BuiltinDescriptor {
    signatures: &GRAPH_SIGNATURES,
    output_mode: BuiltinOutputMode::Fixed,
    completion_policy: BuiltinCompletionPolicy::Public,
    errors: &GRAPH_ERRORS,
};
pub const DIGRAPH_DESCRIPTOR: BuiltinDescriptor = BuiltinDescriptor {
    signatures: &DIGRAPH_SIGNATURES,
    output_mode: BuiltinOutputMode::Fixed,
    completion_policy: BuiltinCompletionPolicy::Public,
    errors: &GRAPH_ERRORS,
};
pub const GRAPH_UNARY_DESCRIPTOR: BuiltinDescriptor = BuiltinDescriptor {
    signatures: &UNARY_GRAPH_SIGNATURES,
    output_mode: BuiltinOutputMode::Fixed,
    completion_policy: BuiltinCompletionPolicy::Public,
    errors: &GRAPH_ERRORS,
};
pub const GRAPH_QUERY_DESCRIPTOR: BuiltinDescriptor = BuiltinDescriptor {
    signatures: &GRAPH_QUERY_SIGNATURES,
    output_mode: BuiltinOutputMode::ByRequestedOutputCount,
    completion_policy: BuiltinCompletionPolicy::Public,
    errors: &GRAPH_ERRORS,
};

#[derive(Clone, Debug)]
struct GraphData {
    directed: bool,
    node_names: Option<Vec<String>>,
    edges: Vec<Edge>,
    node_count: usize,
}

#[derive(Clone, Debug)]
struct Edge {
    source: usize,
    target: usize,
    weight: f64,
}

#[derive(Clone, Copy, Debug)]
struct QueueItem {
    distance: f64,
    node: usize,
}

impl Eq for QueueItem {}

impl PartialEq for QueueItem {
    fn eq(&self, other: &Self) -> bool {
        self.node == other.node && self.distance.to_bits() == other.distance.to_bits()
    }
}

impl Ord for QueueItem {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .distance
            .partial_cmp(&self.distance)
            .unwrap_or(Ordering::Equal)
    }
}

impl PartialOrd for QueueItem {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn any_type(_args: &[Type], _ctx: &ResolveContext) -> Type {
    Type::Unknown
}

fn numeric_type(_args: &[Type], _ctx: &ResolveContext) -> Type {
    Type::tensor()
}

fn graph_error(name: &'static str, message: impl Into<String>) -> RuntimeError {
    error_from_descriptor(name, ERROR_INVALID_ARGUMENT, message)
}

fn internal_error(name: &'static str, message: impl Into<String>) -> RuntimeError {
    error_from_descriptor(name, ERROR_INTERNAL, message)
}

fn error_from_descriptor(
    name: &'static str,
    descriptor: BuiltinErrorDescriptor,
    message: impl Into<String>,
) -> RuntimeError {
    let builder = build_runtime_error(message).with_builtin(name);
    match descriptor.identifier {
        Some(identifier) => builder.with_identifier(identifier).build(),
        None => builder.build(),
    }
}

async fn gather_values(values: Vec<Value>) -> BuiltinResult<Vec<Value>> {
    let mut gathered = Vec::with_capacity(values.len());
    for value in values {
        gathered.push(gather_if_needed_async(&value).await?);
    }
    Ok(gathered)
}

#[runtime_builtin(
    name = "graph",
    category = "graph",
    summary = "Create an undirected graph object.",
    keywords = "graph,edges,nodes,network",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::GRAPH_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn graph_builtin(args: Vec<Value>) -> BuiltinResult<Value> {
    construct_graph(GRAPH_NAME, false, gather_values(args).await?)
}

#[runtime_builtin(
    name = "digraph",
    category = "graph",
    summary = "Create a directed graph object.",
    keywords = "digraph,directed graph,edges,nodes,network",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::DIGRAPH_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn digraph_builtin(args: Vec<Value>) -> BuiltinResult<Value> {
    construct_graph(DIGRAPH_NAME, true, gather_values(args).await?)
}

#[runtime_builtin(
    name = "numnodes",
    category = "graph",
    summary = "Return the number of nodes in a graph.",
    keywords = "numnodes,graph,nodes",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_UNARY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn numnodes_builtin(graph: Value) -> BuiltinResult<Value> {
    Ok(Value::Num(
        graph_data(&graph, "numnodes")?.node_count as f64,
    ))
}

#[runtime_builtin(
    name = "numedges",
    category = "graph",
    summary = "Return the number of edges in a graph.",
    keywords = "numedges,graph,edges",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_UNARY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn numedges_builtin(graph: Value) -> BuiltinResult<Value> {
    Ok(Value::Num(
        graph_data(&graph, "numedges")?.edges.len() as f64
    ))
}

#[runtime_builtin(
    name = "adjacency",
    category = "graph",
    summary = "Return a dense adjacency matrix for a graph.",
    keywords = "adjacency,graph,matrix",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_UNARY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn adjacency_builtin(graph: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "adjacency")?;
    Ok(Value::Tensor(adjacency_tensor(&graph, "adjacency")?))
}

#[runtime_builtin(
    name = "degree",
    category = "graph",
    summary = "Return graph node degree counts.",
    keywords = "degree,graph,nodes",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_UNARY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn degree_builtin(graph: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "degree")?;
    node_metric_value(degree_counts(&graph), "degree")
}

#[runtime_builtin(
    name = "indegree",
    category = "graph",
    summary = "Return node indegree counts.",
    keywords = "indegree,digraph,graph,nodes",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_UNARY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn indegree_builtin(graph: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "indegree")?;
    node_metric_value(indegree_counts(&graph), "indegree")
}

#[runtime_builtin(
    name = "outdegree",
    category = "graph",
    summary = "Return node outdegree counts.",
    keywords = "outdegree,digraph,graph,nodes",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_UNARY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn outdegree_builtin(graph: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "outdegree")?;
    node_metric_value(outdegree_counts(&graph), "outdegree")
}

#[runtime_builtin(
    name = "neighbors",
    category = "graph",
    summary = "Return neighboring graph nodes.",
    keywords = "neighbors,graph,nodes",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn neighbors_builtin(graph: Value, node: Value) -> BuiltinResult<Value> {
    neighbor_query(graph, node, NeighborMode::Undirected, "neighbors").await
}

#[runtime_builtin(
    name = "successors",
    category = "graph",
    summary = "Return successor nodes in a directed graph.",
    keywords = "successors,digraph,graph,nodes",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn successors_builtin(graph: Value, node: Value) -> BuiltinResult<Value> {
    neighbor_query(graph, node, NeighborMode::Successors, "successors").await
}

#[runtime_builtin(
    name = "predecessors",
    category = "graph",
    summary = "Return predecessor nodes in a directed graph.",
    keywords = "predecessors,digraph,graph,nodes",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn predecessors_builtin(graph: Value, node: Value) -> BuiltinResult<Value> {
    neighbor_query(graph, node, NeighborMode::Predecessors, "predecessors").await
}

#[runtime_builtin(
    name = "findedge",
    category = "graph",
    summary = "Find edge indices between graph nodes.",
    keywords = "findedge,graph,edges",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn findedge_builtin(graph: Value, source: Value, target: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "findedge")?;
    let source = node_index_from_value(&graph, &source, "findedge")?;
    let target = node_index_from_value(&graph, &target, "findedge")?;
    for (idx, edge) in graph.edges.iter().enumerate() {
        if edge_matches(edge, source, target, graph.directed) {
            return Ok(Value::Num((idx + 1) as f64));
        }
    }
    Ok(Value::Num(0.0))
}

#[runtime_builtin(
    name = "shortestpath",
    category = "graph",
    summary = "Compute a shortest path between graph nodes.",
    keywords = "shortestpath,graph,path,dijkstra",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn shortestpath_builtin(graph: Value, source: Value, target: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "shortestpath")?;
    let source = node_index_from_value(&graph, &source, "shortestpath")?;
    let target = node_index_from_value(&graph, &target, "shortestpath")?;
    let (distances, previous) = dijkstra(&graph, source);
    let path = reconstruct_path(source, target, &previous);
    let path_value = node_list_value(&graph, &path, "shortestpath")?;
    let distance = distances[target];
    match crate::output_count::current_output_count() {
        Some(0) => Ok(Value::OutputList(Vec::new())),
        Some(1) => Ok(Value::OutputList(vec![path_value])),
        Some(2) => Ok(Value::OutputList(vec![path_value, Value::Num(distance)])),
        Some(_) => Err(graph_error(
            "shortestpath",
            "shortestpath: too many output arguments; maximum is 2",
        )),
        None => Ok(path_value),
    }
}

#[runtime_builtin(
    name = "distances",
    category = "graph",
    summary = "Compute shortest-path distances between graph nodes.",
    keywords = "distances,graph,dijkstra",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn distances_builtin(graph: Value, rest: Vec<Value>) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "distances")?;
    let rest = gather_values(rest).await?;
    let sources = match rest.first() {
        Some(value) => node_indices_from_value(&graph, value, "distances")?,
        None => (0..graph.node_count).collect(),
    };
    let targets = match rest.get(1) {
        Some(value) => node_indices_from_value(&graph, value, "distances")?,
        None => (0..graph.node_count).collect(),
    };
    let mut data = vec![0.0; sources.len() * targets.len()];
    for (source_row, source) in sources.iter().copied().enumerate() {
        let (distances, _) = dijkstra(&graph, source);
        for (target_col, target) in targets.iter().copied().enumerate() {
            data[source_row + target_col * sources.len()] = distances[target];
        }
    }
    tensor_value(data, vec![sources.len(), targets.len()], "distances")
}

#[runtime_builtin(
    name = "conncomp",
    category = "graph",
    summary = "Return weak connected components for graph nodes.",
    keywords = "conncomp,graph,components",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_UNARY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn conncomp_builtin(graph: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "conncomp")?;
    let mut bins = vec![0.0; graph.node_count];
    let mut component = 0usize;
    for start in 0..graph.node_count {
        if bins[start] != 0.0 {
            continue;
        }
        component += 1;
        let mut queue = VecDeque::from([start]);
        bins[start] = component as f64;
        while let Some(node) = queue.pop_front() {
            for next in neighbors_for(&graph, node, NeighborMode::Undirected) {
                if bins[next] == 0.0 {
                    bins[next] = component as f64;
                    queue.push_back(next);
                }
            }
        }
    }
    tensor_value(bins, vec![1, graph.node_count], "conncomp")
}

#[runtime_builtin(
    name = "toposort",
    category = "graph",
    summary = "Return a topological ordering of a directed acyclic graph.",
    keywords = "toposort,digraph,directed acyclic graph",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::GRAPH_UNARY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn toposort_builtin(graph: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "toposort")?;
    if !graph.directed {
        return Err(graph_error(
            "toposort",
            "toposort: expected a digraph input",
        ));
    }
    let mut indegree = vec![0usize; graph.node_count];
    let adj = adjacency_lists(&graph, NeighborMode::Successors);
    for edge in &graph.edges {
        indegree[edge.target] += 1;
    }
    let mut queue = VecDeque::new();
    for (idx, degree) in indegree.iter().copied().enumerate() {
        if degree == 0 {
            queue.push_back(idx);
        }
    }
    let mut order = Vec::with_capacity(graph.node_count);
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &next in &adj[node] {
            indegree[next] -= 1;
            if indegree[next] == 0 {
                queue.push_back(next);
            }
        }
    }
    if order.len() != graph.node_count {
        return Err(graph_error("toposort", "toposort: graph contains a cycle"));
    }
    node_list_value(&graph, &order, "toposort")
}

#[runtime_builtin(
    name = "bfsearch",
    category = "graph",
    summary = "Return breadth-first search node order.",
    keywords = "bfsearch,graph,breadth first search",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn bfsearch_builtin(graph: Value, start: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "bfsearch")?;
    let start = node_index_from_value(&graph, &start, "bfsearch")?;
    let mut visited = vec![false; graph.node_count];
    let mut queue = VecDeque::from([start]);
    let mut order = Vec::new();
    visited[start] = true;
    while let Some(node) = queue.pop_front() {
        order.push(node);
        for next in neighbors_for(&graph, node, NeighborMode::Successors) {
            if !visited[next] {
                visited[next] = true;
                queue.push_back(next);
            }
        }
    }
    node_list_value(&graph, &order, "bfsearch")
}

#[runtime_builtin(
    name = "dfsearch",
    category = "graph",
    summary = "Return depth-first search node order.",
    keywords = "dfsearch,graph,depth first search",
    type_resolver(any_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn dfsearch_builtin(graph: Value, start: Value) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, "dfsearch")?;
    let start = node_index_from_value(&graph, &start, "dfsearch")?;
    let adj = adjacency_lists(&graph, NeighborMode::Successors);
    let mut visited = vec![false; graph.node_count];
    let mut stack = vec![start];
    let mut order = Vec::new();
    while let Some(node) = stack.pop() {
        if visited[node] {
            continue;
        }
        visited[node] = true;
        order.push(node);
        for &next in adj[node].iter().rev() {
            if !visited[next] {
                stack.push(next);
            }
        }
    }
    node_list_value(&graph, &order, "dfsearch")
}

#[runtime_builtin(
    name = "treelayout",
    category = "graph",
    summary = "Compute simple tree-layout coordinates from a parent vector.",
    keywords = "treelayout,tree,layout,graph",
    type_resolver(numeric_type),
    descriptor(crate::builtins::graph::GRAPH_QUERY_DESCRIPTOR),
    builtin_path = "crate::builtins::graph"
)]
async fn treelayout_builtin(parents: Value) -> BuiltinResult<Value> {
    let parents = gather_if_needed_async(&parents).await?;
    let parents = numeric_vector(&parents, "treelayout")?;
    if parents.is_empty() {
        return Ok(Value::OutputList(vec![
            tensor_value(Vec::new(), vec![1, 0], "treelayout")?,
            tensor_value(Vec::new(), vec![1, 0], "treelayout")?,
        ]));
    }
    let n = parents.len();
    let mut children = vec![Vec::<usize>::new(); n];
    let mut roots = Vec::new();
    for (idx, parent) in parents.iter().copied().enumerate() {
        if parent == 0 {
            roots.push(idx);
        } else if parent <= n {
            children[parent - 1].push(idx);
        } else {
            return Err(graph_error(
                "treelayout",
                "treelayout: parent indices must be zero or valid one-based node ids",
            ));
        }
    }
    let mut x = vec![0.0; n];
    let mut y = vec![0.0; n];
    let mut leaf_cursor = 1.0;
    for root in roots {
        assign_tree_positions(root, 0.0, &children, &mut leaf_cursor, &mut x, &mut y);
    }
    let x_value = tensor_value(x, vec![1, n], "treelayout")?;
    let y_value = tensor_value(y, vec![1, n], "treelayout")?;
    match crate::output_count::current_output_count() {
        Some(0) => Ok(Value::OutputList(Vec::new())),
        Some(1) => Ok(Value::OutputList(vec![x_value])),
        Some(2) => Ok(Value::OutputList(vec![x_value, y_value])),
        Some(_) => Err(graph_error(
            "treelayout",
            "treelayout: too many output arguments; maximum is 2",
        )),
        None => Ok(x_value),
    }
}

fn construct_graph(name: &'static str, directed: bool, args: Vec<Value>) -> BuiltinResult<Value> {
    if args.is_empty() {
        return graph_object(GraphData {
            directed,
            node_names: None,
            edges: Vec::new(),
            node_count: 0,
        });
    }
    if args.len() == 1 || is_adjacency_form(&args) {
        return graph_from_adjacency(name, directed, &args);
    }
    graph_from_edges(name, directed, &args)
}

fn is_adjacency_form(args: &[Value]) -> bool {
    matches!(args.first(), Some(Value::Tensor(t)) if t.rows == t.cols)
        && (args.len() == 1
            || args
                .get(1)
                .is_some_and(|arg| parse_string_vector(arg).is_ok() || scalar_text(arg).is_some()))
}

fn graph_from_adjacency(
    name: &'static str,
    directed: bool,
    args: &[Value],
) -> BuiltinResult<Value> {
    let Value::Tensor(matrix) = &args[0] else {
        return Err(graph_error(
            name,
            format!("{name}: expected adjacency matrix"),
        ));
    };
    if matrix.rows != matrix.cols {
        return Err(graph_error(
            name,
            format!("{name}: adjacency matrix must be square"),
        ));
    }
    let node_count = matrix.rows;
    let mut mode = TriangleMode::Full;
    let mut node_names = None;
    if let Some(arg) = args.get(1) {
        if let Some(text) = scalar_text(arg) {
            match canonical(&text).as_str() {
                "upper" => mode = TriangleMode::Upper,
                "lower" => mode = TriangleMode::Lower,
                _ => node_names = Some(parse_node_names(arg, node_count, name)?),
            }
        } else {
            node_names = Some(parse_node_names(arg, node_count, name)?);
        }
    }
    let mut edges = Vec::new();
    for col in 0..node_count {
        for row in 0..node_count {
            let weight = if directed {
                matrix.data[row + col * matrix.rows]
            } else {
                match mode {
                    TriangleMode::Full => {
                        if row > col {
                            continue;
                        }
                        let upper = matrix.data[row + col * matrix.rows];
                        if upper != 0.0 {
                            upper
                        } else if row == col {
                            0.0
                        } else {
                            matrix.data[col + row * matrix.rows]
                        }
                    }
                    TriangleMode::Upper => {
                        if row > col {
                            continue;
                        }
                        matrix.data[row + col * matrix.rows]
                    }
                    TriangleMode::Lower => {
                        if row < col {
                            continue;
                        }
                        matrix.data[row + col * matrix.rows]
                    }
                }
            };
            if weight != 0.0 {
                edges.push(Edge {
                    source: row,
                    target: col,
                    weight,
                });
            }
        }
    }
    graph_object(GraphData {
        directed,
        node_names,
        edges,
        node_count,
    })
}

fn graph_from_edges(name: &'static str, directed: bool, args: &[Value]) -> BuiltinResult<Value> {
    if args.len() < 2 {
        return Err(graph_error(
            name,
            format!("{name}: expected source and target node lists"),
        ));
    }
    let source_nodes = node_tokens(&args[0], name)?;
    let target_nodes = node_tokens(&args[1], name)?;
    if source_nodes.len() != target_nodes.len() {
        return Err(graph_error(
            name,
            format!("{name}: source and target lists must have the same length"),
        ));
    }
    let weights = match args.get(2) {
        Some(value) if looks_like_weights(value, source_nodes.len()) => {
            weights_from_value(value, source_nodes.len(), name)?
        }
        _ => vec![1.0; source_nodes.len()],
    };
    let names_arg = if args.len() >= 4 {
        args.get(3)
    } else if args.len() == 3 && !looks_like_weights(&args[2], source_nodes.len()) {
        args.get(2)
    } else {
        None
    };

    let mut node_names = names_arg
        .map(|value| parse_string_vector(value))
        .transpose()
        .map_err(|err| graph_error(name, format!("{name}: {err}")))?;
    let mut node_count = node_names.as_ref().map_or(0, Vec::len);
    let mut label_to_index = HashMap::<String, usize>::new();
    if let Some(names) = &node_names {
        for (idx, node_name) in names.iter().enumerate() {
            label_to_index.insert(node_name.clone(), idx);
        }
    }

    let mut edges = Vec::with_capacity(source_nodes.len());
    for ((source, target), weight) in source_nodes.into_iter().zip(target_nodes).zip(weights) {
        let source = resolve_node_token(
            source,
            &mut node_names,
            &mut label_to_index,
            &mut node_count,
            name,
        )?;
        let target = resolve_node_token(
            target,
            &mut node_names,
            &mut label_to_index,
            &mut node_count,
            name,
        )?;
        edges.push(Edge {
            source,
            target,
            weight,
        });
    }

    graph_object(GraphData {
        directed,
        node_names,
        edges,
        node_count,
    })
}

fn graph_object(graph: GraphData) -> BuiltinResult<Value> {
    ensure_graph_classes_registered();
    let class_name = if graph.directed {
        DIGRAPH_CLASS
    } else {
        GRAPH_CLASS
    };
    let mut object = ObjectInstance::new(class_name.to_string());
    object.properties.insert(
        NUM_NODES_PROPERTY.to_string(),
        Value::Num(graph.node_count as f64),
    );
    object
        .properties
        .insert("Edges".to_string(), edges_table(&graph)?);
    object
        .properties
        .insert("Nodes".to_string(), nodes_table(&graph)?);
    Ok(Value::Object(object))
}

fn edges_table(graph: &GraphData) -> BuiltinResult<Value> {
    let names = graph.node_names.as_ref();
    let end_nodes = if let Some(node_names) = names {
        let mut values = Vec::with_capacity(graph.edges.len() * 2);
        values.extend(
            graph
                .edges
                .iter()
                .map(|edge| node_names[edge.source].clone()),
        );
        values.extend(
            graph
                .edges
                .iter()
                .map(|edge| node_names[edge.target].clone()),
        );
        Value::StringArray(
            StringArray::new(values, vec![graph.edges.len(), 2])
                .map_err(|err| internal_error("graph", err))?,
        )
    } else {
        let mut values = Vec::with_capacity(graph.edges.len() * 2);
        values.extend(graph.edges.iter().map(|edge| (edge.source + 1) as f64));
        values.extend(graph.edges.iter().map(|edge| (edge.target + 1) as f64));
        tensor_value_raw(values, vec![graph.edges.len(), 2], "graph")?
    };
    let all_unit = graph.edges.iter().all(|edge| edge.weight == 1.0);
    if all_unit {
        table_from_columns(vec!["EndNodes".to_string()], vec![end_nodes])
    } else {
        let weights: Vec<f64> = graph.edges.iter().map(|edge| edge.weight).collect();
        table_from_columns(
            vec!["EndNodes".to_string(), "Weight".to_string()],
            vec![
                end_nodes,
                tensor_value_raw(weights, vec![graph.edges.len(), 1], "graph")?,
            ],
        )
    }
}

fn nodes_table(graph: &GraphData) -> BuiltinResult<Value> {
    if let Some(names) = &graph.node_names {
        table_from_columns(
            vec!["Name".to_string()],
            vec![Value::StringArray(
                StringArray::new(names.clone(), vec![graph.node_count, 1])
                    .map_err(|err| internal_error("graph", err))?,
            )],
        )
    } else {
        table_from_columns(
            vec!["Index".to_string()],
            vec![tensor_value_raw(
                (1..=graph.node_count).map(|idx| idx as f64).collect(),
                vec![graph.node_count, 1],
                "graph",
            )?],
        )
    }
}

fn graph_data(value: &Value, name: &'static str) -> BuiltinResult<GraphData> {
    let object = match value {
        Value::Object(object)
            if object.class_name == GRAPH_CLASS || object.class_name == DIGRAPH_CLASS =>
        {
            object
        }
        other => {
            return Err(graph_error(
                name,
                format!("{name}: expected graph or digraph object, got {other:?}"),
            ))
        }
    };
    let directed = object.class_name == DIGRAPH_CLASS;
    let node_count = match object.properties.get(NUM_NODES_PROPERTY) {
        Some(value) => positive_integer_scalar(value, name)?,
        None => infer_node_count_from_nodes(object, name)?,
    };
    let node_names = node_names_from_object(object, node_count, name)?;
    let edges = edges_from_object(object, node_names.as_deref(), directed, node_count, name)?;
    Ok(GraphData {
        directed,
        node_names,
        edges,
        node_count,
    })
}

fn node_names_from_object(
    object: &ObjectInstance,
    node_count: usize,
    name: &'static str,
) -> BuiltinResult<Option<Vec<String>>> {
    let Some(Value::Object(nodes)) = object.properties.get("Nodes") else {
        return Ok(None);
    };
    let variables = table_variables(nodes)
        .map_err(|err| graph_error(name, format!("{name}: invalid Nodes table: {err}")))?;
    let Some(value) = variables.fields.get("Name") else {
        return Ok(None);
    };
    let names = parse_string_vector(value).map_err(|err| graph_error(name, err))?;
    if names.len() != node_count {
        return Err(graph_error(
            name,
            format!("{name}: Nodes.Name length does not match graph node count"),
        ));
    }
    Ok(Some(names))
}

fn infer_node_count_from_nodes(
    object: &ObjectInstance,
    name: &'static str,
) -> BuiltinResult<usize> {
    let Some(Value::Object(nodes)) = object.properties.get("Nodes") else {
        return Ok(0);
    };
    crate::builtins::table::table_height(nodes)
        .map_err(|err| graph_error(name, format!("{name}: invalid Nodes table: {err}")))
}

fn edges_from_object(
    object: &ObjectInstance,
    node_names: Option<&[String]>,
    directed: bool,
    node_count: usize,
    name: &'static str,
) -> BuiltinResult<Vec<Edge>> {
    let Some(Value::Object(edges_table)) = object.properties.get("Edges") else {
        return Ok(Vec::new());
    };
    let variables = table_variables(edges_table)
        .map_err(|err| graph_error(name, format!("{name}: invalid Edges table: {err}")))?;
    let Some(endnodes) = variables.fields.get("EndNodes") else {
        return Ok(Vec::new());
    };
    let endpoint_pairs = edge_pairs_from_value(endnodes, node_names, node_count, name)?;
    let weights = match variables.fields.get("Weight") {
        Some(value) => weights_from_value(value, endpoint_pairs.len(), name)?,
        None => vec![1.0; endpoint_pairs.len()],
    };
    let mut edges = Vec::with_capacity(endpoint_pairs.len());
    for ((source, target), weight) in endpoint_pairs.into_iter().zip(weights) {
        if source >= node_count || target >= node_count {
            return Err(graph_error(
                name,
                format!("{name}: edge endpoint exceeds graph node count"),
            ));
        }
        edges.push(Edge {
            source,
            target,
            weight,
        });
    }
    if !directed {
        for edge in &edges {
            if edge.source >= node_count || edge.target >= node_count {
                return Err(graph_error(name, format!("{name}: invalid edge endpoint")));
            }
        }
    }
    Ok(edges)
}

fn edge_pairs_from_value(
    value: &Value,
    node_names: Option<&[String]>,
    node_count: usize,
    name: &'static str,
) -> BuiltinResult<Vec<(usize, usize)>> {
    match value {
        Value::Tensor(tensor) if tensor.cols == 2 => {
            let mut out = Vec::with_capacity(tensor.rows);
            for row in 0..tensor.rows {
                let source = node_index_from_f64(tensor.data[row], node_count, name)?;
                let target = node_index_from_f64(tensor.data[row + tensor.rows], node_count, name)?;
                out.push((source, target));
            }
            Ok(out)
        }
        Value::StringArray(array) if array.cols == 2 => {
            let Some(names) = node_names else {
                return Err(graph_error(
                    name,
                    format!("{name}: string EndNodes require Nodes.Name values"),
                ));
            };
            let lookup: HashMap<&str, usize> = names
                .iter()
                .enumerate()
                .map(|(idx, text)| (text.as_str(), idx))
                .collect();
            let mut out = Vec::with_capacity(array.rows);
            for row in 0..array.rows {
                let source = *lookup.get(array.data[row].as_str()).ok_or_else(|| {
                    graph_error(
                        name,
                        format!("{name}: unknown source node '{}'", array.data[row]),
                    )
                })?;
                let target = *lookup
                    .get(array.data[row + array.rows].as_str())
                    .ok_or_else(|| {
                        graph_error(
                            name,
                            format!(
                                "{name}: unknown target node '{}'",
                                array.data[row + array.rows]
                            ),
                        )
                    })?;
                out.push((source, target));
            }
            Ok(out)
        }
        other => Err(graph_error(
            name,
            format!(
                "{name}: Edges.EndNodes must be an m-by-2 numeric or string array, got {other:?}"
            ),
        )),
    }
}

fn node_tokens(value: &Value, name: &'static str) -> BuiltinResult<Vec<NodeToken>> {
    if let Ok(values) = numeric_vector(value, name) {
        return Ok(values.into_iter().map(NodeToken::Index).collect());
    }
    Ok(parse_string_vector(value)
        .map_err(|err| graph_error(name, format!("{name}: {err}")))?
        .into_iter()
        .map(NodeToken::Name)
        .collect())
}

#[derive(Debug)]
enum NodeToken {
    Index(usize),
    Name(String),
}

fn resolve_node_token(
    token: NodeToken,
    node_names: &mut Option<Vec<String>>,
    label_to_index: &mut HashMap<String, usize>,
    node_count: &mut usize,
    name: &'static str,
) -> BuiltinResult<usize> {
    match token {
        NodeToken::Index(index) => {
            if index == 0 {
                return Err(graph_error(
                    name,
                    format!("{name}: node indices are one-based"),
                ));
            }
            let zero = index - 1;
            *node_count = (*node_count).max(index);
            if let Some(names) = node_names {
                if zero >= names.len() {
                    return Err(graph_error(
                        name,
                        format!("{name}: numeric node index exceeds supplied node names"),
                    ));
                }
            }
            Ok(zero)
        }
        NodeToken::Name(label) => {
            if node_names.is_none() {
                *node_names = Some(Vec::new());
            }
            if let Some(&idx) = label_to_index.get(&label) {
                return Ok(idx);
            }
            let idx = node_names.as_ref().map_or(0, Vec::len);
            label_to_index.insert(label.clone(), idx);
            node_names.as_mut().expect("node names").push(label);
            *node_count = (*node_count).max(idx + 1);
            Ok(idx)
        }
    }
}

fn looks_like_weights(value: &Value, expected_len: usize) -> bool {
    match value {
        Value::Num(_) | Value::Int(_) => expected_len == 1,
        Value::Tensor(tensor) => tensor.data.len() == expected_len,
        _ => false,
    }
}

fn weights_from_value(value: &Value, len: usize, name: &'static str) -> BuiltinResult<Vec<f64>> {
    let values = numeric_f64_vector(value, name)?;
    if values.len() != len {
        return Err(graph_error(
            name,
            format!("{name}: weights must have one value per edge"),
        ));
    }
    for weight in &values {
        if !weight.is_finite() || *weight < 0.0 {
            return Err(graph_error(
                name,
                format!("{name}: edge weights must be finite nonnegative values"),
            ));
        }
    }
    Ok(values)
}

fn numeric_vector(value: &Value, name: &'static str) -> BuiltinResult<Vec<usize>> {
    let values = numeric_f64_vector(value, name)?;
    values
        .into_iter()
        .map(|value| {
            if !value.is_finite() || value < 0.0 || value.fract().abs() > 1e-9 {
                Err(graph_error(
                    name,
                    format!("{name}: node indices must be nonnegative integers"),
                ))
            } else {
                Ok(value as usize)
            }
        })
        .collect()
}

fn numeric_f64_vector(value: &Value, name: &'static str) -> BuiltinResult<Vec<f64>> {
    match value {
        Value::Num(n) => Ok(vec![*n]),
        Value::Int(i) => Ok(vec![i.to_f64()]),
        Value::Bool(b) => Ok(vec![if *b { 1.0 } else { 0.0 }]),
        Value::Tensor(tensor) => Ok(tensor.data.clone()),
        Value::LogicalArray(array) => Ok(array
            .data
            .iter()
            .map(|&v| if v != 0 { 1.0 } else { 0.0 })
            .collect()),
        other => Err(graph_error(
            name,
            format!("{name}: expected numeric vector, got {other:?}"),
        )),
    }
}

fn parse_node_names(
    value: &Value,
    expected_len: usize,
    name: &'static str,
) -> BuiltinResult<Vec<String>> {
    let names = parse_string_vector(value).map_err(|err| graph_error(name, err))?;
    if names.len() != expected_len {
        return Err(graph_error(
            name,
            format!("{name}: node name list length must match node count"),
        ));
    }
    Ok(names)
}

fn parse_string_vector(value: &Value) -> Result<Vec<String>, String> {
    match value {
        Value::String(text) => Ok(vec![text.clone()]),
        Value::StringArray(array) => Ok(array.data.clone()),
        Value::CharArray(chars) if chars.rows == 1 => Ok(vec![chars.data.iter().collect()]),
        Value::CharArray(chars) => Ok((0..chars.rows)
            .map(|row| {
                (0..chars.cols)
                    .map(|col| chars.data[row + col * chars.rows])
                    .collect::<String>()
                    .trim_end()
                    .to_string()
            })
            .collect()),
        Value::Cell(cell) => cell
            .data
            .iter()
            .map(|entry| {
                scalar_text(entry).ok_or_else(|| {
                    "expected cell array of string or character node names".to_string()
                })
            })
            .collect(),
        other => Err(format!(
            "expected string, character, or cellstr vector, got {other:?}"
        )),
    }
}

fn scalar_text(value: &Value) -> Option<String> {
    match value {
        Value::String(text) => Some(text.clone()),
        Value::StringArray(array) if array.data.len() == 1 => Some(array.data[0].clone()),
        Value::CharArray(chars) if chars.rows == 1 => Some(chars.data.iter().collect()),
        _ => None,
    }
}

fn canonical(text: &str) -> String {
    text.chars()
        .filter(|ch| *ch != '_' && *ch != '-' && !ch.is_whitespace())
        .flat_map(char::to_lowercase)
        .collect()
}

fn positive_integer_scalar(value: &Value, name: &'static str) -> BuiltinResult<usize> {
    let values = numeric_vector(value, name)?;
    if values.len() != 1 {
        return Err(graph_error(
            name,
            format!("{name}: expected scalar node count"),
        ));
    }
    Ok(values[0])
}

fn node_index_from_value(
    graph: &GraphData,
    value: &Value,
    name: &'static str,
) -> BuiltinResult<usize> {
    match value {
        Value::String(_) | Value::StringArray(_) | Value::CharArray(_) | Value::Cell(_) => {
            let labels = parse_string_vector(value).map_err(|err| graph_error(name, err))?;
            if labels.len() != 1 {
                return Err(graph_error(name, format!("{name}: expected one node")));
            }
            let Some(names) = &graph.node_names else {
                return Err(graph_error(
                    name,
                    format!("{name}: string node references require named graph nodes"),
                ));
            };
            names
                .iter()
                .position(|candidate| candidate == &labels[0])
                .ok_or_else(|| graph_error(name, format!("{name}: unknown node '{}'", labels[0])))
        }
        _ => {
            let idx = positive_integer_scalar(value, name)?;
            node_index_from_one_based(idx, graph.node_count, name)
        }
    }
}

fn node_indices_from_value(
    graph: &GraphData,
    value: &Value,
    name: &'static str,
) -> BuiltinResult<Vec<usize>> {
    match value {
        Value::String(_) | Value::StringArray(_) | Value::CharArray(_) | Value::Cell(_) => {
            let labels = parse_string_vector(value).map_err(|err| graph_error(name, err))?;
            let Some(names) = &graph.node_names else {
                return Err(graph_error(
                    name,
                    format!("{name}: string node references require named graph nodes"),
                ));
            };
            labels
                .into_iter()
                .map(|label| {
                    names
                        .iter()
                        .position(|candidate| candidate == &label)
                        .ok_or_else(|| graph_error(name, format!("{name}: unknown node '{label}'")))
                })
                .collect()
        }
        _ => numeric_vector(value, name)?
            .into_iter()
            .map(|idx| node_index_from_one_based(idx, graph.node_count, name))
            .collect(),
    }
}

fn node_index_from_f64(value: f64, node_count: usize, name: &'static str) -> BuiltinResult<usize> {
    if !value.is_finite() || value < 1.0 || value.fract().abs() > 1e-9 {
        return Err(graph_error(
            name,
            format!("{name}: edge endpoints must be positive integer node ids"),
        ));
    }
    node_index_from_one_based(value as usize, node_count, name)
}

fn node_index_from_one_based(
    value: usize,
    node_count: usize,
    name: &'static str,
) -> BuiltinResult<usize> {
    if value == 0 || value > node_count {
        return Err(graph_error(
            name,
            format!("{name}: node index is outside the graph"),
        ));
    }
    Ok(value - 1)
}

fn edge_matches(edge: &Edge, source: usize, target: usize, directed: bool) -> bool {
    (edge.source == source && edge.target == target)
        || (!directed && edge.source == target && edge.target == source)
}

fn adjacency_tensor(graph: &GraphData, name: &'static str) -> BuiltinResult<Tensor> {
    let n = graph.node_count;
    let mut data = vec![0.0; n * n];
    for edge in &graph.edges {
        data[edge.source + edge.target * n] += edge.weight;
        if !graph.directed && edge.source != edge.target {
            data[edge.target + edge.source * n] += edge.weight;
        }
    }
    Tensor::new(data, vec![n, n]).map_err(|err| internal_error(name, err))
}

fn degree_counts(graph: &GraphData) -> Vec<f64> {
    if graph.directed {
        outdegree_counts(graph)
            .into_iter()
            .zip(indegree_counts(graph))
            .map(|(out, incoming)| out + incoming)
            .collect()
    } else {
        let mut counts = vec![0.0; graph.node_count];
        for edge in &graph.edges {
            if edge.source == edge.target {
                counts[edge.source] += 2.0;
            } else {
                counts[edge.source] += 1.0;
                counts[edge.target] += 1.0;
            }
        }
        counts
    }
}

fn indegree_counts(graph: &GraphData) -> Vec<f64> {
    if !graph.directed {
        return degree_counts_undirected(graph);
    }
    let mut counts = vec![0.0; graph.node_count];
    for edge in &graph.edges {
        counts[edge.target] += 1.0;
    }
    counts
}

fn outdegree_counts(graph: &GraphData) -> Vec<f64> {
    if !graph.directed {
        return degree_counts_undirected(graph);
    }
    let mut counts = vec![0.0; graph.node_count];
    for edge in &graph.edges {
        counts[edge.source] += 1.0;
    }
    counts
}

fn degree_counts_undirected(graph: &GraphData) -> Vec<f64> {
    let mut counts = vec![0.0; graph.node_count];
    for edge in &graph.edges {
        counts[edge.source] += 1.0;
        if edge.source != edge.target {
            counts[edge.target] += 1.0;
        }
    }
    counts
}

fn node_metric_value(values: Vec<f64>, name: &'static str) -> BuiltinResult<Value> {
    let len = values.len();
    tensor_value(values, vec![len, 1], name)
}

#[derive(Clone, Copy)]
enum NeighborMode {
    Undirected,
    Successors,
    Predecessors,
}

async fn neighbor_query(
    graph: Value,
    node: Value,
    mode: NeighborMode,
    name: &'static str,
) -> BuiltinResult<Value> {
    let graph = graph_data(&graph, name)?;
    let node = gather_if_needed_async(&node).await?;
    let node = node_index_from_value(&graph, &node, name)?;
    let mut neighbors = neighbors_for(&graph, node, mode);
    neighbors.sort_unstable();
    neighbors.dedup();
    node_list_value(&graph, &neighbors, name)
}

fn neighbors_for(graph: &GraphData, node: usize, mode: NeighborMode) -> Vec<usize> {
    let mut out = Vec::new();
    for edge in &graph.edges {
        match mode {
            NeighborMode::Undirected => {
                if edge.source == node {
                    out.push(edge.target);
                }
                if edge.target == node && edge.source != node {
                    out.push(edge.source);
                }
            }
            NeighborMode::Successors => {
                if edge.source == node {
                    out.push(edge.target);
                }
                if !graph.directed && edge.target == node && edge.source != node {
                    out.push(edge.source);
                }
            }
            NeighborMode::Predecessors => {
                if edge.target == node {
                    out.push(edge.source);
                }
                if !graph.directed && edge.source == node && edge.target != node {
                    out.push(edge.target);
                }
            }
        }
    }
    out
}

fn adjacency_lists(graph: &GraphData, mode: NeighborMode) -> Vec<Vec<usize>> {
    let mut lists = vec![Vec::new(); graph.node_count];
    for node in 0..graph.node_count {
        let mut neighbors = neighbors_for(graph, node, mode);
        neighbors.sort_unstable();
        neighbors.dedup();
        lists[node] = neighbors;
    }
    lists
}

fn weighted_adjacency(graph: &GraphData) -> Vec<Vec<(usize, f64)>> {
    let mut lists = vec![Vec::new(); graph.node_count];
    for edge in &graph.edges {
        lists[edge.source].push((edge.target, edge.weight));
        if !graph.directed && edge.source != edge.target {
            lists[edge.target].push((edge.source, edge.weight));
        }
    }
    lists
}

fn dijkstra(graph: &GraphData, source: usize) -> (Vec<f64>, Vec<Option<usize>>) {
    let adjacency = weighted_adjacency(graph);
    let mut distances = vec![f64::INFINITY; graph.node_count];
    let mut previous = vec![None; graph.node_count];
    let mut heap = BinaryHeap::new();
    distances[source] = 0.0;
    heap.push(QueueItem {
        distance: 0.0,
        node: source,
    });
    while let Some(QueueItem { distance, node }) = heap.pop() {
        if distance > distances[node] {
            continue;
        }
        for &(next, weight) in &adjacency[node] {
            let candidate = distance + weight;
            if candidate < distances[next] {
                distances[next] = candidate;
                previous[next] = Some(node);
                heap.push(QueueItem {
                    distance: candidate,
                    node: next,
                });
            }
        }
    }
    (distances, previous)
}

fn reconstruct_path(source: usize, target: usize, previous: &[Option<usize>]) -> Vec<usize> {
    if source == target {
        return vec![source];
    }
    let mut path = Vec::new();
    let mut current = target;
    path.push(current);
    while let Some(parent) = previous[current] {
        current = parent;
        path.push(current);
        if current == source {
            path.reverse();
            return path;
        }
    }
    Vec::new()
}

fn node_list_value(graph: &GraphData, nodes: &[usize], name: &'static str) -> BuiltinResult<Value> {
    if let Some(names) = &graph.node_names {
        Ok(Value::StringArray(
            StringArray::new(
                nodes.iter().map(|&idx| names[idx].clone()).collect(),
                vec![nodes.len(), 1],
            )
            .map_err(|err| internal_error(name, err))?,
        ))
    } else {
        tensor_value(
            nodes.iter().map(|&idx| (idx + 1) as f64).collect(),
            vec![nodes.len(), 1],
            name,
        )
    }
}

fn assign_tree_positions(
    node: usize,
    depth: f64,
    children: &[Vec<usize>],
    leaf_cursor: &mut f64,
    x: &mut [f64],
    y: &mut [f64],
) {
    y[node] = -depth;
    if children[node].is_empty() {
        x[node] = *leaf_cursor;
        *leaf_cursor += 1.0;
        return;
    }
    for &child in &children[node] {
        assign_tree_positions(child, depth + 1.0, children, leaf_cursor, x, y);
    }
    let first = children[node].first().copied().unwrap();
    let last = children[node].last().copied().unwrap();
    x[node] = (x[first] + x[last]) / 2.0;
}

fn tensor_value(data: Vec<f64>, shape: Vec<usize>, name: &'static str) -> BuiltinResult<Value> {
    Ok(tensor::tensor_into_value(
        Tensor::new(data, shape).map_err(|err| internal_error(name, err))?,
    ))
}

fn tensor_value_raw(data: Vec<f64>, shape: Vec<usize>, name: &'static str) -> BuiltinResult<Value> {
    Ok(Value::Tensor(
        Tensor::new(data, shape).map_err(|err| internal_error(name, err))?,
    ))
}

#[derive(Clone, Copy)]
enum TriangleMode {
    Full,
    Upper,
    Lower,
}

fn ensure_graph_classes_registered() {
    static REGISTER: OnceLock<()> = OnceLock::new();
    REGISTER.get_or_init(|| {
        register_graph_class(GRAPH_CLASS);
        register_graph_class(DIGRAPH_CLASS);
    });
}

fn register_graph_class(name: &str) {
    let mut properties = HashMap::new();
    for property_name in ["Edges", "Nodes", NUM_NODES_PROPERTY] {
        properties.insert(
            property_name.to_string(),
            PropertyDef {
                name: property_name.to_string(),
                is_static: false,
                is_constant: false,
                is_dependent: false,
                get_access: Access::Public,
                set_access: Access::Public,
                default_value: None,
            },
        );
    }
    runmat_builtins::register_class(ClassDef {
        name: name.to_string(),
        parent: None,
        properties,
        methods: HashMap::<String, MethodDef>::new(),
    });
}

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

    fn numeric(data: Vec<f64>, rows: usize, cols: usize) -> Value {
        Value::Tensor(Tensor::new(data, vec![rows, cols]).expect("tensor"))
    }

    fn tensor_data(value: Value) -> Vec<f64> {
        match value {
            Value::Tensor(t) => t.data,
            Value::Num(n) => vec![n],
            other => panic!("expected numeric value, got {other:?}"),
        }
    }

    #[test]
    fn graph_constructor_builds_edges_nodes_and_adjacency() {
        let graph = block_on(graph_builtin(vec![
            numeric(vec![1.0, 2.0, 3.0], 3, 1),
            numeric(vec![2.0, 3.0, 1.0], 3, 1),
        ]))
        .expect("graph");
        assert_eq!(
            block_on(numnodes_builtin(graph.clone())).unwrap(),
            Value::Num(3.0)
        );
        assert_eq!(
            block_on(numedges_builtin(graph.clone())).unwrap(),
            Value::Num(3.0)
        );

        let adjacency = block_on(adjacency_builtin(graph)).expect("adjacency");
        assert_eq!(
            tensor_data(adjacency),
            vec![0.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 0.0]
        );
    }

    #[test]
    fn digraph_preserves_direction_for_neighbors_and_degree() {
        let graph = block_on(digraph_builtin(vec![
            numeric(vec![1.0, 1.0, 2.0], 3, 1),
            numeric(vec![2.0, 3.0, 3.0], 3, 1),
        ]))
        .expect("digraph");
        assert_eq!(
            tensor_data(block_on(outdegree_builtin(graph.clone())).unwrap()),
            vec![2.0, 1.0, 0.0]
        );
        assert_eq!(
            tensor_data(block_on(indegree_builtin(graph.clone())).unwrap()),
            vec![0.0, 1.0, 2.0]
        );
        assert_eq!(
            tensor_data(block_on(successors_builtin(graph.clone(), Value::Num(1.0))).unwrap()),
            vec![2.0, 3.0]
        );
        assert_eq!(
            tensor_data(block_on(predecessors_builtin(graph, Value::Num(3.0))).unwrap()),
            vec![1.0, 2.0]
        );
    }

    #[test]
    fn named_graph_returns_named_paths() {
        let names = Value::StringArray(
            StringArray::new(vec!["a".into(), "b".into(), "c".into()], vec![3, 1]).expect("names"),
        );
        let graph = block_on(graph_builtin(vec![
            numeric(vec![1.0, 2.0], 2, 1),
            numeric(vec![2.0, 3.0], 2, 1),
            numeric(vec![2.0, 1.0], 2, 1),
            names,
        ]))
        .expect("graph");
        let path = block_on(shortestpath_builtin(
            graph,
            Value::CharArray(runmat_builtins::CharArray::new_row("a")),
            Value::CharArray(runmat_builtins::CharArray::new_row("c")),
        ))
        .expect("path");
        let Value::StringArray(path) = path else {
            panic!("expected named path");
        };
        assert_eq!(path.data, vec!["a", "b", "c"]);
    }

    #[test]
    fn adjacency_constructor_and_distances_use_weights() {
        let graph = block_on(digraph_builtin(vec![numeric(
            vec![0.0, 0.0, 0.0, 2.0, 0.0, 0.0, 10.0, 1.0, 0.0],
            3,
            3,
        )]))
        .expect("digraph");
        let distances = block_on(distances_builtin(
            graph,
            vec![Value::Num(1.0), Value::Num(3.0)],
        ))
        .expect("distances");
        assert_eq!(distances, Value::Num(3.0));
    }

    #[test]
    fn undirected_adjacency_constructor_accepts_lower_triangle() {
        let graph =
            block_on(graph_builtin(vec![numeric(vec![0.0, 5.0, 0.0, 0.0], 2, 2)])).expect("graph");
        assert_eq!(
            block_on(numedges_builtin(graph.clone())).unwrap(),
            Value::Num(1.0)
        );
        assert_eq!(
            tensor_data(block_on(adjacency_builtin(graph)).unwrap()),
            vec![0.0, 5.0, 5.0, 0.0]
        );
    }

    #[test]
    fn treelayout_returns_single_or_pair_by_output_count() {
        let result = block_on(treelayout_builtin(numeric(vec![0.0, 1.0, 1.0, 2.0], 1, 4)))
            .expect("treelayout");
        assert_eq!(tensor_data(result).len(), 4);

        let _guard = crate::output_count::push_output_count(Some(2));
        let result = block_on(treelayout_builtin(numeric(vec![0.0, 1.0, 1.0, 2.0], 1, 4)))
            .expect("treelayout");
        let Value::OutputList(values) = result else {
            panic!("expected output list");
        };
        assert_eq!(values.len(), 2);
        assert_eq!(tensor_data(values[0].clone()).len(), 4);
        assert_eq!(tensor_data(values[1].clone()), vec![-0.0, -1.0, -1.0, -2.0]);
    }
}