# Graph Properties & Optimization

```elixir
Mix.install([
  {:yog_ex, "~> 0.98"},
  {:kino_vizjs, "~> 0.8.0"}
])
```

## Introduction

Graph properties help us understand the mathematical nature of a network. Can it be drawn on a flat surface without edges crossing? Does it have a path that visits every edge exactly once? How can we connect all points with the minimum amount of cable?

`Yog` provides expressive implementations for these classic graph theory problems.

## Minimum Spanning Tree (MST)

An MST connects all nodes in a weighted graph with the minimum possible total edge weight and no cycles. This is the foundation of network design (e.g., laying fiber optic cables).

```elixir
# Create a weighted network
g = Yog.from_edges(:undirected, [
    {:a, :b, 4}, {:a, :h, 8},
    {:b, :c, 8}, {:b, :h, 11},
    {:c, :d, 7}, {:c, :i, 2}, {:c, :f, 4},
    {:d, :e, 9}, {:d, :f, 14},
    {:e, :f, 10},
    {:f, :g, 2},
    {:g, :h, 1}, {:g, :i, 6},
    {:h, :i, 7}
  ])

# Find the MST using Kruskal's algorithm
{:ok, result} = Yog.MST.kruskal(in: g)

IO.puts "MST Total Weight: #{result.total_weight}"

# Visualize the MST (highlighting the edges)
mst_options = Yog.Render.DOT.mst_to_options(result)
dot = Yog.Render.DOT.to_dot(g, mst_options)
Kino.VizJS.render(dot, height: "600px")
```

## Eulerian Paths (Seven Bridges of Königsberg)

An **Eulerian Path** visits every edge exactly once. An **Eulerian Circuit** starts and ends at the same node.

```elixir
# 1. Build the Seven Bridges of Königsberg as a Multigraph
bridges = [
  {:north, :island, 1},
  {:north, :island, 2},
  {:south, :island, 3},
  {:south, :island, 4},
  {:east, :island, 5},
  {:north, :east, 6},
  {:south, :east, 7}
]

konigsberg =
  Enum.reduce(bridges, Yog.Multi.undirected(), fn {from, to, data}, g ->
    g
    |> Yog.Multi.add_node(from)
    |> Yog.Multi.add_node(to)
    |> Yog.Multi.add_edge(from, to, data)
    |> elem(0)
  end)

# 2. Check Eulerian circuit on multigraph using Yog.Multi
case Yog.Multi.find_eulerian_circuit(konigsberg) do
  {:ok, path} ->
    IO.puts("Eulerian circuit exists!")
    IO.inspect(path, label: "Circuit")

  :error ->
    IO.puts("No Eulerian circuit possible. (Euler was right!)")
end

# 3. Simple graphs work fine with Yog.Property.Eulerian
square = 
  Yog.undirected()
  |> Yog.add_nodes_from([:a, :b,  :c, :d])
  |> Yog.add_edges!([
    {:a, :b, 1}, {:b, :c, 1},
    {:c, :d, 1}, {:d, :a, 1}
  ])

case Yog.Property.Eulerian.eulerian_circuit(square) do
  {:ok, path} ->
    IO.puts("Square has an Eulerian circuit!")
    IO.inspect(path, label: "Circuit")

  {:error, _} ->
    IO.puts("No Eulerian circuit.")
end

opts = 
  Yog.Multi.DOT.default_options()
  |> Map.merge(%{
    splines: :curved,
    layout: :circo,
    edge_label: fn _edge_id, bridge_name -> bridge_name end,
    node_shape: :circle
  })

dot_source = Yog.Multi.DOT.to_dot(konigsberg, opts)
Kino.VizJS.render(dot_source)
```

## Graph Coloring

Graph coloring assigns a "color" to each node such that no two adjacent nodes share the same color. The goal is to use the minimum number of colors (**Chromatic Number**). This is often used for scheduling (nodes = tasks, edges = conflicts).

```elixir
g = Yog.Generator.Classic.petersen()

# Calculate a greedy coloring
{upper, colors} = Yog.Property.Coloring.coloring_greedy(g)
IO.puts "Greedy coloring used #{upper} colors."

# Try DSatur heuristic
{upper_dsatur, colors_dsatur} = Yog.Property.Coloring.coloring_dsatur(g)
IO.puts "DSatur used #{upper_dsatur} colors."

# Visualize with colors!
color_values = ["#6366f1", "#10b981", "#f59e0b", "#ef4444", "#8b5cf6"]

node_attrs = fn id, _data ->
  color = Enum.at(color_values, rem(Map.get(colors_dsatur, id, 0), length(color_values)))
  [{:fillcolor, color}, {:style, "filled"}]
end

dot = Yog.Render.DOT.to_dot(g, Yog.Render.DOT.theme(:minimal) |> Map.put(:node_attributes, node_attrs))
Kino.VizJS.render(dot, height: "600px")
```

## Planarity

A graph is **Planar** if it can be drawn in a plane without any edges crossing.

```elixir
# K5 (Complete graph with 5 nodes) is the smallest non-planar graph
k5 = Yog.Generator.Classic.complete(5)

if Yog.Property.Planarity.planar?(k5) do
  IO.puts "K5 is planar"
else
  IO.puts "K5 is NOT planar (as expected)"
end

# K3,3 (complete bipartite) is the other famous non-planar graph
k33 = Yog.Generator.Classic.complete_bipartite(3, 3)
IO.puts "K3,3 planar? #{Yog.Property.Planarity.planar?(k33)}"

# A grid graph IS planar
grid = Yog.Generator.Classic.grid_2d(4, 4)
IO.puts "Grid planar? #{Yog.Property.Planarity.planar?(grid)}"

# Get an embedding for the planar grid
{:ok, embedding} = Yog.Property.Planarity.planar_embedding(grid)
IO.inspect(map_size(embedding), label: "Embedding faces")
```

## Summary

Exploring graph properties allows you to:

1. **Optimize**: Find the cheapest way to connect components (MST).
2. **Verify**: Check if a solution exists for routing problems (Eulerian).
3. **Schedule**: Resolve conflicts using Coloring.
4. **Visualize**: Ensure layout feasibility with Planarity.

Next, explore **DAGs** to see how to manage dependencies and workflows!