///|
/// Aggregate graph statistics for composition diagnostics.
pub(all) struct MotifGraphMetrics {
  node_count : Int
  edge_count : Int
  component_count : Int
  isolated_nodes : Int
  maximum_degree : Int
  average_degree : Double
  total_edge_length : Double
  bounds : Rect
} derive(Eq, Debug, ToJson)

///|
/// Parameters for deterministic force-directed graph layout.
pub(all) struct GraphLayoutOptions {
  bounds : Rect
  iterations : Int
  repulsion : Double
  attraction : Double
  damping : Double
  seed : UInt
} derive(Eq, Debug, ToJson)

///|
pub fn GraphLayoutOptions::new(bounds : Rect) -> GraphLayoutOptions {
  {
    bounds,
    iterations: 40,
    repulsion: 900.0,
    attraction: 0.08,
    damping: 0.82,
    seed: 1U,
  }
}

///|
pub fn GraphLayoutOptions::with_iterations(
  self : GraphLayoutOptions,
  iterations : Int,
) -> GraphLayoutOptions {
  { ..self, iterations: iterations.max(0) }
}

///|
pub fn GraphLayoutOptions::with_forces(
  self : GraphLayoutOptions,
  repulsion : Double,
  attraction : Double,
) -> GraphLayoutOptions {
  { ..self, repulsion: repulsion.max(0.0), attraction: attraction.max(0.0) }
}

///|
pub fn GraphLayoutOptions::with_damping(
  self : GraphLayoutOptions,
  damping : Double,
) -> GraphLayoutOptions {
  { ..self, damping: damping.max(0.0).min(1.0) }
}

///|
/// A graph layout result with node positions and edge paths.
pub(all) struct GraphLayout {
  positions : Array[Vec2]
  edges : Array[(Int, Int)]
  bounds : Rect
  energy : Double
  iterations : Int
} derive(Eq, Debug, ToJson)

///|
/// An edge measurement used by graph scoring and line styling.
pub(all) struct GraphEdgeMeasure {
  left : Int
  right : Int
  length : Double
  midpoint : Vec2
  direction : Double
} derive(Eq, Debug, ToJson)

///|
pub fn MotifGraph::node_count(self : MotifGraph) -> Int {
  self.nodes.length()
}

///|
pub fn MotifGraph::edge_count(self : MotifGraph) -> Int {
  self.edges.length()
}

///|
pub fn MotifGraph::has_edge(self : MotifGraph, left : Int, right : Int) -> Bool {
  for edge in self.edges {
    if (edge.0 == left && edge.1 == right) ||
      (edge.0 == right && edge.1 == left) {
      return true
    }
  }
  false
}

///|
/// Removes duplicate and self-loop edges without changing node order.
pub fn MotifGraph::normalized(self : MotifGraph) -> MotifGraph {
  let edges : Array[(Int, Int)] = []
  for edge in self.edges {
    if edge.0 != edge.1 &&
      !edges.contains((edge.0, edge.1)) &&
      !edges.contains((edge.1, edge.0)) {
      edges.push(edge)
    }
  }
  { nodes: self.nodes.copy(), edges }
}

///|
pub fn MotifGraph::degree(self : MotifGraph, node : Int) -> Int {
  self.neighbors(node).length()
}

///|
pub fn MotifGraph::degrees(self : MotifGraph) -> Array[Int] {
  let result = []
  for index in 0.. Array[Int] {
  let result = []
  for index in 0.. Array[Int] {
  let result = []
  if start >= 0 && start < self.nodes.length() {
    let visited = []
    for _ in 0.. Array[Int] {
  let result = []
  if start >= 0 && start < self.nodes.length() {
    let visited = []
    for _ in 0.. 0 {
      let node = stack.pop().unwrap()
      if !visited[node] {
        visited[node] = true
        result.push(node)
        for neighbor in self.neighbors(node) {
          if !visited[neighbor] {
            stack.push(neighbor)
          }
        }
      }
    }
  }
  result
}

///|
/// Finds a shortest unweighted path between two nodes.
pub fn MotifGraph::shortest_path(
  self : MotifGraph,
  start : Int,
  goal : Int,
) -> Array[Int]? {
  if start < 0 ||
    goal < 0 ||
    start >= self.nodes.length() ||
    goal >= self.nodes.length() {
    None
  } else {
    let previous : Array[Int?] = []
    let visited = []
    for _ in 0.. Bool {
  self.nodes.length() <= 1 || self.bfs(0).length() == self.nodes.length()
}

///|
/// Returns the graph's edge list as measured geometric records.
pub fn MotifGraph::edge_measurements(
  self : MotifGraph,
) -> Array[GraphEdgeMeasure] {
  let result = []
  for edge in self.edges {
    if edge.0 >= 0 &&
      edge.1 >= 0 &&
      edge.0 < self.nodes.length() &&
      edge.1 < self.nodes.length() {
      let left = self.nodes[edge.0].anchor
      let right = self.nodes[edge.1].anchor
      let difference = right.sub(left)
      result.push({
        left: edge.0,
        right: edge.1,
        length: difference.length(),
        midpoint: left.lerp(right, 0.5),
        direction: @math.atan2(difference.y, difference.x),
      })
    }
  }
  result
}

///|
pub fn MotifGraph::metrics(self : MotifGraph) -> MotifGraphMetrics {
  let degrees = self.degrees()
  let maximum = degrees.fold(init=0, fn(current, value) { current.max(value) })
  let total_degree = degrees.fold(init=0, fn(total, value) { total + value })
  let edges = self.edge_measurements()
  {
    node_count: self.node_count(),
    edge_count: self.edge_count(),
    component_count: self.connected_components().length(),
    isolated_nodes: self.isolated_nodes().length(),
    maximum_degree: maximum,
    average_degree: if degrees.length() == 0 {
      0.0
    } else {
      total_degree.to_double() / degrees.length().to_double()
    },
    total_edge_length: edges.fold(init=0.0, fn(total, edge) {
      total + edge.length
    }),
    bounds: self.bounds(),
  }
}

///|
/// Returns normalized degree centrality values.
pub fn MotifGraph::degree_centrality(self : MotifGraph) -> Array[Double] {
  let result = []
  let denominator = (self.nodes.length() - 1).max(1).to_double()
  for degree in self.degrees() {
    result.push(degree.to_double() / denominator)
  }
  result
}

///|
/// Returns the average shortest-path distance from a node.
pub fn MotifGraph::closeness(self : MotifGraph, node : Int) -> Double {
  let mut total = 0
  let mut reachable = 0
  if node >= 0 && node < self.nodes.length() {
    for target in 0.. {
          total += path.length() - 1
          reachable += 1
        }
        None => ()
      }
    }
  }
  if total == 0 {
    0.0
  } else {
    reachable.to_double() / total.to_double()
  }
}

///|
/// Places nodes evenly around an ellipse inside a canvas.
pub fn circular_graph_layout(
  graph : MotifGraph,
  bounds : Rect,
  phase : Double,
) -> GraphLayout {
  let positions = []
  let center = bounds.center()
  let radius = Vec2::new(bounds.width * 0.4, bounds.height * 0.4)
  for index in 0.. Array[Vec2] {
  let positions = []
  let random = Random::new(options.seed)
  for node in graph.nodes {
    let point = if node.anchor != Vec2::zero() {
      node.anchor
    } else {
      Vec2::new(
        random.range(options.bounds.x, options.bounds.right()),
        random.range(options.bounds.y, options.bounds.bottom()),
      )
    }
    positions.push(
      Vec2::new(
        point.x.max(options.bounds.x).min(options.bounds.right()),
        point.y.max(options.bounds.y).min(options.bounds.bottom()),
      ),
    )
  }
  positions
}

///|
fn graph_force_layout(
  graph : MotifGraph,
  positions : Array[Vec2],
  options : GraphLayoutOptions,
) -> (Array[Vec2], Double) {
  let next = positions.copy()
  let mut energy = 0.0
  let scale = options.repulsion.max(0.0)
  for left in 0..= 0 && other < positions.length() {
          let difference = positions[other].sub(positions[left])
          force = force.add(difference.scale(options.attraction))
        }
      }
    }
    let candidate = positions[left].add(force.scale(options.damping))
    next[left] = Vec2::new(
      candidate.x.max(options.bounds.x).min(options.bounds.right()),
      candidate.y.max(options.bounds.y).min(options.bounds.bottom()),
    )
    energy += force.length()
  }
  (next, energy)
}

///|
/// Runs a deterministic force-directed layout.
pub fn force_graph_layout(
  graph : MotifGraph,
  options : GraphLayoutOptions,
) -> GraphLayout {
  let mut positions = initial_graph_positions(graph, options)
  let mut energy = 0.0
  let mut completed = 0
  for _ in 0.. GraphLayout {
  let options = GraphLayoutOptions::new(self.bounds)
    .with_iterations(iterations)
    .with_forces(repulsion, attraction)
  let (positions, energy) = graph_force_layout(graph, self.positions, options)
  { ..self, positions, energy, iterations: self.iterations + iterations.max(0) }
}

///|
/// Converts graph edges to drawable paths using a layout result.
pub fn GraphLayout::edge_paths(self : GraphLayout) -> Array[Path] {
  let result = []
  for edge in self.edges {
    if edge.0 >= 0 &&
      edge.1 >= 0 &&
      edge.0 < self.positions.length() &&
      edge.1 < self.positions.length() {
      let left = self.positions[edge.0]
      let right = self.positions[edge.1]
      result.push(Path::new().move_to(left.x, left.y).line_to(right.x, right.y))
    }
  }
  result
}

///|
/// Returns node points from a graph layout.
pub fn GraphLayout::node_points(self : GraphLayout) -> Array[Vec2] {
  self.positions.copy()
}

///|
/// Measures how many edges leave a requested layout rectangle.
pub fn GraphLayout::out_of_bounds(self : GraphLayout) -> Int {
  let mut count = 0
  for point in self.positions {
    if !self.bounds.contains(point) {
      count += 1
    }
  }
  count
}

///|
/// Translates all positions by an offset.
pub fn GraphLayout::translate(self : GraphLayout, offset : Vec2) -> GraphLayout {
  let positions = []
  for point in self.positions {
    positions.push(point.add(offset))
  }
  { ..self, positions, }
}

///|
/// Fits layout points into a target rectangle while preserving aspect ratio.
pub fn GraphLayout::fit(self : GraphLayout, target : Rect) -> GraphLayout {
  {
    ..self,
    positions: fit_points(self.positions, target, true),
    bounds: target,
  }
}

///|
/// Renders a graph layout and motif styles to an SVG document.
pub fn graph_document(
  graph : MotifGraph,
  layout : GraphLayout,
  width : Double,
  height : Double,
  background : Color,
  edge_style : SvgStyle,
) -> SvgDocument {
  let document = SvgDocument::new(width, height)
  document.add(
    SvgElement::SvgPath(
      Path::rect(width, height),
      SvgStyle::new(fill=background.to_hex(), stroke="none"),
    ),
  )
  for path in layout.edge_paths() {
    document.add(SvgElement::SvgPath(path, edge_style))
  }
  for index, motif in graph.nodes {
    if index < layout.positions.length() {
      let point = layout.positions[index]
      let positioned = motif.placed(
        point.x,
        point.y,
        motif.scale,
        motif.rotation,
      )
      document.add(
        SvgElement::SvgPath(positioned.transformed_path(), positioned.style),
      )
    }
  }
  document
}

///|
/// Serializes graph connectivity as an adjacency matrix CSV.
pub fn graph_adjacency_csv(graph : MotifGraph) -> String {
  let builder = StringBuilder()
  for row in 0.. String {
  let metrics = graph.metrics()
  "nodes=\{metrics.node_count},edges=\{metrics.edge_count},components=\{metrics.component_count},isolated=\{metrics.isolated_nodes},max_degree=\{metrics.maximum_degree},average_degree=\{metrics.average_degree},edge_length=\{metrics.total_edge_length}"
}

///|
/// Builds a graph from motifs and a deterministic ring connection policy.
pub fn ring_graph(motifs : Array[Motif], connect_last : Bool) -> MotifGraph {
  let graph = MotifGraph::new()
  for motif in motifs {
    let _ = graph.add_node(motif)
  }
  if motifs.length() > 1 {
    for index in 0..<(motifs.length() - 1) {
      let _ = graph.connect(index, index + 1)
    }
    if connect_last {
      let _ = graph.connect(motifs.length() - 1, 0)
    }
  }
  graph
}

///|
/// Connects each motif to its nearest neighbors under a distance cap.
pub fn proximity_graph(
  motifs : Array[Motif],
  maximum_distance : Double,
) -> MotifGraph {
  let graph = MotifGraph::new()
  for motif in motifs {
    let _ = graph.add_node(motif)
  }
  for left in 0.. MotifGraph {
  let graph = MotifGraph::new()
  for motif in motifs {
    let _ = graph.add_node(motif)
  }
  for index in 1.. Array[Color] {
  let result = []
  for value in graph.degree_centrality() {
    result.push(low.mix(high, value))
  }
  result
}

///|
/// Returns paths for a graph's node anchors in layout order.
pub fn graph_anchor_path(graph : MotifGraph, closed : Bool) -> Path {
  polyline(graph.nodes.map(fn(motif) { motif.anchor }), closed~)
}