///|
/// Node categories in the analysis graph.
pub enum GraphNodeKind {
  SignalNode
  ChangeNode
  WindowNode
  AssertionNode
  ProtocolNode
} derive(Debug, Eq)

///|
/// Relationship categories used for trace causality.
pub enum GraphEdgeKind {
  Temporal
  SameSignal
  SameTimestamp
  Dependency
  Containment
} derive(Debug, Eq)

///|
/// A graph node that points back to a waveform object.
pub struct GraphNode {
  id : String
  kind : GraphNodeKind
  label : String
  signal_id : String?
  time : Int64?
  weight : Int
} derive(Debug)

///|
/// A directed relationship between two analysis nodes.
pub struct GraphEdge {
  from : String
  to : String
  kind : GraphEdgeKind
  weight : Int
  evidence : String
} derive(Debug)

///|
/// A deterministic graph built from trace changes and declarations.
pub struct EventGraph {
  nodes : Array[GraphNode]
  edges : Array[GraphEdge]
  signal_nodes : Int
  change_nodes : Int
  temporal_edges : Int
  cross_signal_edges : Int
} derive(Debug)

///|
/// List graph node categories.
pub fn graph_node_kind_catalog() -> Array[GraphNodeKind] {
  [SignalNode, ChangeNode, WindowNode, AssertionNode, ProtocolNode]
}

///|
/// List graph edge categories.
pub fn graph_edge_kind_catalog() -> Array[GraphEdgeKind] {
  [Temporal, SameSignal, SameTimestamp, Dependency, Containment]
}

///|
/// Build a signal/change graph with temporal and same-timestamp evidence.
pub fn trace_event_graph(trace : Trace) -> EventGraph {
  let nodes : Array[GraphNode] = []
  let edges : Array[GraphEdge] = []
  let signal_ids : Array[String] = []
  for signal in trace.signals {
    let id = "signal:" + signal.id
    nodes.push({
      id,
      kind: SignalNode,
      label: signal_path(signal),
      signal_id: Some(signal.id),
      time: None,
      weight: 0,
    })
    signal_ids.push(signal.id)
  }
  let previous : Map[String, String] = Map([])
  let timestamp_nodes : Map[Int64, Array[String]] = Map([])
  for index, change in trace.changes {
    let id = "change:" + index.to_string()
    nodes.push({
      id,
      kind: ChangeNode,
      label: change.id + "=" + change.value.display(),
      signal_id: Some(change.id),
      time: Some(change.time),
      weight: 1,
    })
    edges.push({
      from: "signal:" + change.id,
      to: id,
      kind: Containment,
      weight: 1,
      evidence: "declared signal owns change",
    })
    match previous.get(change.id) {
      Some(before) =>
        edges.push({
          from: before,
          to: id,
          kind: Temporal,
          weight: 1,
          evidence: "next change for signal",
        })
      None => ()
    }
    previous[change.id] = id
    let at_time = match timestamp_nodes.get(change.time) {
      Some(value) => value
      None => []
    }
    at_time.push(id)
    timestamp_nodes[change.time] = at_time
  }
  for _, ids in timestamp_nodes {
    if ids.length() > 1 {
      for left_index in 0.. Array[GraphEdge] {
  self.edges.filter(fn(edge) { edge.from == node_id })
}

///|
/// Return the incoming edges for one node.
pub fn EventGraph::incoming(
  self : EventGraph,
  node_id : String,
) -> Array[GraphEdge] {
  self.edges.filter(fn(edge) { edge.to == node_id })
}

///|
/// Find a node by its stable identifier.
pub fn EventGraph::find_node(self : EventGraph, node_id : String) -> GraphNode? {
  for node in self.nodes {
    if node.id == node_id {
      return Some(node)
    }
  }
  None
}

///|
/// Return unique graph neighbors in edge order.
pub fn EventGraph::neighbors(
  self : EventGraph,
  node_id : String,
) -> Array[String] {
  let result : Array[String] = []
  for edge in self.edges {
    if edge.from == node_id && !result.contains(edge.to) {
      result.push(edge.to)
    }
    if edge.to == node_id && !result.contains(edge.from) {
      result.push(edge.from)
    }
  }
  result
}

///|
/// Calculate node degree pairs for graph ranking.
pub fn graph_degrees(graph : EventGraph) -> Array[(String, Int)] {
  graph.nodes.map(fn(node) {
    let degree = graph.edges
      .filter(fn(edge) { edge.from == node.id || edge.to == node.id })
      .length()
    (node.id, degree)
  })
}

///|
/// Return the highest-degree node, if any node exists.
pub fn graph_hub(graph : EventGraph) -> GraphNode? {
  graph.nodes.fold(init=None, fn(current, node) {
    let node_degree = graph.edges
      .filter(fn(edge) { edge.from == node.id || edge.to == node.id })
      .length()
    match current {
      Some(previous) => {
        let previous_degree = graph.edges
          .filter(fn(edge) {
            edge.from == previous.id || edge.to == previous.id
          })
          .length()
        if node_degree > previous_degree {
          Some(node)
        } else {
          Some(previous)
        }
      }
      None => Some(node)
    }
  })
}

///|
/// Find a bounded breadth-first path between two nodes.
pub fn graph_path(
  graph : EventGraph,
  start : String,
  goal : String,
  limit : Int,
) -> Array[String] {
  if start == goal {
    return [start]
  }
  let queue : Array[Array[String]] = [[start]]
  let visited : Array[String] = [start]
  let max_depth = Int::max(1, limit)
  while queue.length() > 0 {
    let path = queue[0]
    let _ = queue.remove(0)
    if path.length() > max_depth {
      continue
    }
    let last = path[path.length() - 1]
    for next in graph.neighbors(last) {
      if visited.contains(next) {
        continue
      }
      visited.push(next)
      let extended = path.copy()
      extended.push(next)
      if next == goal {
        return extended
      }
      queue.push(extended)
    }
  }
  []
}

///|
/// Return whether a path exists within a depth bound.
pub fn graph_reachable(
  graph : EventGraph,
  start : String,
  goal : String,
  limit : Int,
) -> Bool {
  graph_path(graph, start, goal, limit).length() > 0
}

///|
/// Export graph nodes and edges as Graphviz DOT.
pub fn EventGraph::to_dot(self : EventGraph) -> String {
  let out = StringBuilder()
  out.write_string("digraph trace {\n")
  for node in self.nodes {
    out.write_string(
      "  \"" +
      escape_text(node.id) +
      "\" [label=\"" +
      escape_text(node.label) +
      "\"];\n",
    )
  }
  for edge in self.edges {
    out.write_string(
      "  \"" +
      escape_text(edge.from) +
      "\" -> \"" +
      escape_text(edge.to) +
      "\" [label=\"" +
      graph_edge_kind_name(edge.kind) +
      "\"];\n",
    )
  }
  out.write_string("}\n")
  out.to_string()
}

///|
/// Export graph edges as CSV.
pub fn graph_edges_csv(edges : Array[GraphEdge]) -> String {
  let out = StringBuilder()
  out.write_string("from,to,kind,weight,evidence\n")
  for edge in edges {
    out.write_string(
      escape_text(edge.from) +
      "," +
      escape_text(edge.to) +
      "," +
      graph_edge_kind_name(edge.kind) +
      "," +
      edge.weight.to_string() +
      "," +
      escape_text(edge.evidence) +
      "\n",
    )
  }
  out.to_string()
}

///|
/// Render a compact graph summary.
pub fn EventGraph::to_text(self : EventGraph) -> String {
  "nodes=" +
  self.nodes.length().to_string() +
  " edges=" +
  self.edges.length().to_string() +
  " signals=" +
  self.signal_nodes.to_string() +
  " changes=" +
  self.change_nodes.to_string() +
  " temporal=" +
  self.temporal_edges.to_string() +
  " same_timestamp=" +
  self.cross_signal_edges.to_string()
}

///|
/// Render graph metadata and edge data as JSON.
pub fn EventGraph::to_json(self : EventGraph) -> String {
  let nodes = self.nodes.map(graph_node_json).join(",")
  let edges = self.edges.map(graph_edge_json).join(",")
  "{\"signals\":" +
  self.signal_nodes.to_string() +
  ",\"changes\":" +
  self.change_nodes.to_string() +
  ",\"nodes\":[" +
  nodes +
  "],\"edges\":[" +
  edges +
  "]}"
}

///|
/// Name a graph node category.
pub fn graph_node_kind_name(kind : GraphNodeKind) -> String {
  match kind {
    SignalNode => "signal"
    ChangeNode => "change"
    WindowNode => "window"
    AssertionNode => "assertion"
    ProtocolNode => "protocol"
  }
}

///|
/// Name a graph edge category.
pub fn graph_edge_kind_name(kind : GraphEdgeKind) -> String {
  match kind {
    Temporal => "temporal"
    SameSignal => "same-signal"
    SameTimestamp => "same-timestamp"
    Dependency => "dependency"
    Containment => "containment"
  }
}

///|
/// Encode a graph node.
fn graph_node_json(node : GraphNode) -> String {
  "{\"id\":\"" +
  escape_text(node.id) +
  "\",\"kind\":\"" +
  graph_node_kind_name(node.kind) +
  "\",\"label\":\"" +
  escape_text(node.label) +
  "\",\"time\":" +
  graph_optional_time(node.time) +
  ",\"weight\":" +
  node.weight.to_string() +
  "}"
}

///|
/// Encode a graph edge.
fn graph_edge_json(edge : GraphEdge) -> String {
  "{\"from\":\"" +
  escape_text(edge.from) +
  "\",\"to\":\"" +
  escape_text(edge.to) +
  "\",\"kind\":\"" +
  graph_edge_kind_name(edge.kind) +
  "\",\"weight\":" +
  edge.weight.to_string() +
  ",\"evidence\":\"" +
  escape_text(edge.evidence) +
  "\"}"
}

///|
/// Encode an optional graph timestamp.
fn graph_optional_time(value : Int64?) -> String {
  match value {
    Some(item) => item.to_string()
    None => "null"
  }
}