yog_ex

defmodule Yog.Graph do
  @moduledoc """
  Core graph data structure.

  A graph is represented as a struct with four fields:
  - `kind`: Either `:directed` or `:undirected`
  - `nodes`: Map of node_id => node_data
  - `out_edges`: Map of node_id => %{neighbor_id => weight}
  - `in_edges`: Map of node_id => %{neighbor_id => weight}

  The dual-map representation (storing both out_edges and in_edges) enables:
  - O(1) graph transpose (just swap out_edges ↔ in_edges)
  - Efficient predecessor queries without traversing the entire graph
  - Fast bidirectional edge lookups

  ## Examples

      iex> %Yog.Graph{
      ...>   kind: :directed,
      ...>   nodes: %{1 => "A", 2 => "B"},
      ...>   out_edges: %{1 => %{2 => 10}},
      ...>   in_edges: %{2 => %{1 => 10}}
      ...> }

  ## Protocols

  `Yog.Graph` implements the `Enumerable` and `Inspect` protocols:

  - **Enumerable**: Iterates over nodes as `{id, data}` tuples
  - **Inspect**: Compact representation showing graph type and statistics

  ## Visual Showcase

  <div class="graphviz">
  digraph G {
    rankdir=LR;
    bgcolor="transparent";
    node [fontname="inherit", shape=box, style=rounded, penwidth=1.5];
    edge [fontname="inherit", fontsize=10, penwidth=1.2];

    subsystem [label="Core System", shape=hexagon, color="#6366f1"];
    node1 [label="Logic A", color="#10b981"];
    node2 [label="Logic B", color="#10b981"];
    node3 [label="Logic C", color="#10b981"];
    storage [label="Storage", shape=cylinder, color="#f59e0b"];
    user [label="User", shape=doublecircle, color="#ef4444"];

    subsystem -> node1 [label="invokes", color="#6366f1"];
    subsystem -> node2 [label="invokes", color="#6366f1"];
    node1 -> node3 [label="calls", style=dashed, color="#10b981"];
    node2 -> node3 [label="calls", style=dashed, color="#10b981"];
    node3 -> storage [label="writes", color="#f59e0b"];
    user -> subsystem [label="triggers", color="#ef4444", penwidth=2.5];
  }
  </div>

      iex> graph = Yog.directed()
      ...> |> Yog.add_edge_ensure("User", "Core System", "triggers")
      ...> |> Yog.add_edge_ensure("Core System", "Logic A", "invokes")
      ...> |> Yog.add_edge_ensure("Core System", "Logic B", "invokes")
      ...> |> Yog.add_edge_ensure("Logic A", "Logic C", "calls")
      ...> |> Yog.add_edge_ensure("Logic B", "Logic C", "calls")
      ...> |> Yog.add_edge_ensure("Logic C", "Storage", "writes")
      iex> Yog.node_count(graph)
      6
      iex> Yog.edge_count(graph)
      6
  """

  @typedoc "Type representing the unique identifier for a node."
  @type node_id :: term()

  @typedoc "Type representing whether a graph is directed or undirected."
  @type kind :: :directed | :undirected

  @typedoc "Type representing the Yog.Graph structure."
  @type t :: %__MODULE__{
          kind: kind(),
          nodes: %{node_id() => any()},
          out_edges: %{node_id() => %{node_id() => number()}},
          in_edges: %{node_id() => %{node_id() => number()}}
        }

  @enforce_keys [:kind, :nodes, :out_edges, :in_edges]
  defstruct [:kind, :nodes, :out_edges, :in_edges]

  @doc """
  Creates a new empty graph of the given type.

  ## Example

      iex> Yog.Graph.new(:directed)
      %Yog.Graph{kind: :directed, in_edges: %{}, nodes: %{}, out_edges: %{}}

      iex> Yog.Graph.new(:undirected)
      %Yog.Graph{kind: :undirected, in_edges: %{}, nodes: %{}, out_edges: %{}}

  """
  @spec new(kind()) :: t()
  def new(kind) when kind in [:directed, :undirected] do
    %__MODULE__{
      kind: kind,
      nodes: %{},
      out_edges: %{},
      in_edges: %{}
    }
  end

  @doc """
  Returns the total number of edges in the graph.

  For undirected graphs, this counts each edge once (not twice).

  ## Performance Note

  This function traverses all nodes' outgoing edges, making it O(V) where V is
  the number of vertices. If you need the edge count multiple times, consider
  caching the result:

      edge_count = Yog.Graph.edge_count(graph)
      # Use edge_count in subsequent calculations...

  ## Example

      iex> graph = Yog.Graph.new(:directed)
      ...> |> Yog.add_node(1, "A")
      ...> |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
      ...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
      iex> Yog.Graph.edge_count(graph)
      2

      iex> graph = Yog.Graph.new(:undirected)
      ...> |> Yog.add_node(1, "A")
      ...> |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
      ...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
      iex> Yog.Graph.edge_count(graph)
      2
  """
  @spec edge_count(t()) :: non_neg_integer()
  def edge_count(%__MODULE__{} = graph) do
    case graph.kind do
      :directed ->
        Enum.reduce(graph.out_edges, 0, fn {_src, targets}, acc ->
          acc + map_size(targets)
        end)

      :undirected ->
        {total, self_loops} =
          Enum.reduce(graph.out_edges, {0, 0}, fn {src, targets}, {acc_total, acc_self} ->
            new_total = acc_total + map_size(targets)
            new_self = if Map.has_key?(targets, src), do: acc_self + 1, else: acc_self
            {new_total, new_self}
          end)

        div(total - self_loops, 2) + self_loops
    end
  end

  @doc """
  Returns the number of nodes in the graph.

  ## Example

      iex> graph = Yog.Graph.new(:directed)
      ...> |> Yog.add_node(1, "A")
      ...> |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
      ...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
      iex> Yog.Graph.node_count(graph)
      3

      iex> graph = Yog.Graph.new(:undirected)
      ...> |> Yog.add_node(1, "A")
      ...> |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
      ...> |> Yog.add_edge_ensure(from: 1, to: 3, with: 20)
      iex> Yog.Graph.node_count(graph)
      3
  """
  @spec node_count(t()) :: non_neg_integer()
  def node_count(%__MODULE__{} = graph) do
    map_size(graph.nodes)
  end
end

defimpl Enumerable, for: Yog.Graph do
  @moduledoc """
  Enumerable implementation for `Yog.Graph`.

  Iterates over nodes as `{id, data}` tuples, similar to `Map.to_list/1`.

  ## Examples

      iex> graph =
      ...>   Yog.directed()
      ...>   |> Yog.add_node(1, "A")
      ...>   |> Yog.add_node(2, "B")
      iex> Enum.to_list(graph)
      [{1, "A"}, {2, "B"}]
      iex> Enum.count(graph)
      2
      iex> Enum.map(graph, fn {_id, data} -> data end)
      ["A", "B"]
  """

  def count(%Yog.Graph{nodes: nodes}) do
    {:ok, map_size(nodes)}
  end

  @doc """
  Checks if a node exists in the graph.

  ## Example

      iex> graph = Yog.Graph.new(:directed)
      ...> |> Yog.add_node(1, "A")
      ...> |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
      iex> Enum.member?(graph, {1, "A"})
      true
      iex> Enum.member?(graph, {1, "B"})
      false
      iex> Enum.member?(graph, :not_a_tuple)
      false
  """
  def member?(%Yog.Graph{nodes: nodes}, {id, data}) do
    {:ok, Map.get(nodes, id) == data}
  end

  def member?(%Yog.Graph{}, _) do
    {:ok, false}
  end

  @doc """
  Reduces the graph to a single value.

  ## Example

      iex> graph = Yog.Graph.new(:directed)
      ...> |> Yog.add_node(1, "A")
      ...> |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
      iex> Enum.reduce(graph, 0, fn {id, _data}, acc -> acc + id end)
      3
  """
  def reduce(%Yog.Graph{nodes: nodes}, acc, fun) do
    Enumerable.reduce(nodes, acc, fun)
  end

  @doc """
  Slices the graph into a list of nodes.

  ## Example

      iex> graph = Yog.Graph.new(:directed)
      ...> |> Yog.add_node(1, "A")
      ...> |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
      iex> Enum.slice(graph, 0, 1)
      [{1, "A"}]
  """
  def slice(%Yog.Graph{nodes: nodes}) do
    {:ok, map_size(nodes),
     fn start, length, _step ->
       nodes
       |> :maps.to_list()
       |> Enum.slice(start, length)
     end}
  end
end

defimpl Inspect, for: Yog.Graph do
  @moduledoc """
  Inspect implementation for `Yog.Graph`.

  Provides a compact representation showing graph type, node count, and edge count.

  ## Examples

      iex> graph = Yog.directed() |> Yog.add_node(1, "A")
      iex> inspect(graph)
      "#Yog.Graph<:directed, 1 node, 0 edges>"
      iex> graph = Yog.undirected() |> Yog.add_node(1, "A") |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 5)
      iex> inspect(graph)
      "#Yog.Graph<:undirected, 2 nodes, 1 edge>"

  """

  import Inspect.Algebra

  @doc """
  Inspects the graph.

  ## Example

      iex> graph = Yog.Graph.new(:directed)
      ...> |> Yog.add_node(1, "A")
      ...> |> Yog.add_node(2, "B")
      ...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 10)
      iex> inspect(graph)
      "#Yog.Graph<:directed, 2 nodes, 1 edge>"
  """
  def inspect(%Yog.Graph{} = graph, opts) do
    node_count = map_size(graph.nodes)
    edge_count = Yog.Graph.edge_count(graph)

    node_str = if node_count == 1, do: "node", else: "nodes"
    edge_str = if edge_count == 1, do: "edge", else: "edges"

    concat([
      "#Yog.Graph<",
      to_doc(graph.kind, opts),
      ", ",
      "#{node_count} #{node_str}, ",
      "#{edge_count} #{edge_str}",
      ">"
    ])
  end
end