# Getting Started with Yog

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

## What is Yog?

**যোগ** (*jōg*) means connection, link, or union.

`Yog` is a comprehensive graph algorithm library for Elixir. It provides efficient, immutable data structures and a wide array of algorithms for network analysis, pathfinding, and community detection.

## Creating your first Graph

In `Yog`, graphs are immutable structures. You can create an empty graph of a specific kind:

```elixir
# Create a directed graph
g = Yog.directed()

# Create an undirected graph
u = Yog.undirected()
```

By default, a graph consists of:

* `kind`: `:directed` or `:undirected`
* `nodes`: A map of `node_id => data`
* `edges`: Adjacency maps for fast lookups and `O(1)` transpose.

## Growing the Graph

We build graphs by adding nodes and edges. Since `Yog` is functional and immutable, every operation returns a **new** graph.

### Adding Nodes

Nodes can have any term as an ID and any term as data.

```elixir
g = 
  Yog.directed()
  |> Yog.add_node(1, %{label: "Start"})
  |> Yog.add_node(2, %{label: "End"})
  |> Yog.add_nodes_from([3, 4, 5]) # Adding multiple nodes with nil data
```

Now let's visualize the nodes. `Yog` supports both Dot and Mermaid for rendering graphs.

```elixir
Kino.Layout.tabs(
  Dot: Kino.VizJS.render(Yog.Render.DOT.to_dot(g), height: "100px"),
  Mermaid: Kino.Mermaid.new(Yog.Render.Mermaid.to_mermaid(g))
)
```

### Adding Edges

Edges connect nodes. In `Yog`, we provide several ways to add edges, depending on whether you want to ensure the nodes exist or handle missing nodes.

```elixir
# 1. add_edge! - Raises if nodes don't exist
g = g |> Yog.add_edge!(1, 2, 10)
IO.inspect(g)

# 2. add_edge_ensure - Automatically creates nodes if they are missing
g = g |> Yog.add_edge_ensure(2, 3, 5, %{label: "Auto-created"})
IO.inspect(g)

# 3. add_simple_edge - Adds an edge with weight 1
g = g |> Yog.add_simple_edge!(3, 1)
IO.inspect(g)
```

And this is how the graph looks like:

```elixir
Kino.Layout.tabs(
  Dot: Kino.VizJS.render(Yog.Render.DOT.to_dot(g)),
  Mermaid: Kino.Mermaid.new(Yog.Render.Mermaid.to_mermaid(g))
)
```

### LabeledBuilder and the Builder pattern

<!-- livebook:{"break_markdown":true} -->

Yog lets you define your graph with any data as node ID or edge weight.

```elixir
graph =
  Yog.directed()
  |> Yog.add_node({0, 0}, nil)
  |> Yog.add_node(:point, %{})
  |> Yog.add_edge!({0, 0}, :point, :unreachable)


Yog.all_edges(graph)
```

However, many algorithms or graph file formats are simplier when the Node IDs are integers. It also makes traversals and lookups faster. The `graph` above could look like:

```elixir
graph =
  Yog.directed()
  |> Yog.add_node(1, {{0, 0}, nil})
  |> Yog.add_node(2, {:point, %{}})
  |> Yog.add_edge!(1, 2, :unreachable)

Yog.all_edges(graph)
```

The example above is much cleaner. But it also come with an ergonomic tax. If consuming from a stream, one would need to keep a map of ID to Data, and Data to ID.

This is exactly where the `LabeledBuilder` becomes relevant.

Yog has a set of Builders that acts like a domain specific graph creation API - hides the implementation detail but creates Yog graph underneath. They can be added anywhere, but Yog provides a few builders to get you going.

The one we discuss here is the `LabeledBuilder`. This lets you build graphs with any data as NodeID but creates a graph with integer based ID.

Here's an example:

```elixir
builder =
  Yog.Builder.Labeled.directed()
  |> Yog.Builder.Labeled.add_edge("A", "B", 10)
  |> Yog.Builder.Labeled.add_edge("B", "C", 5)

IO.puts("These are the labels")
IO.inspect(builder |> Yog.Builder.Labeled.all_labels())

IO.puts("A registry that maps labels to Node IDs")
IO.inspect(builder |> Yog.Builder.Labeled.to_registry())

IO.puts("The underlying graph")
graph = builder |> Yog.Builder.Labeled.to_graph()
IO.inspect(Yog.node_ids(graph))

IO.puts("To query between NodeID and Label")
IO.inspect(Yog.Builder.Labeled.get_id(builder, "A"))
IO.inspect(Yog.Builder.Labeled.get_label(builder, 0))

```

There are a few other builders:

* `LiveBuilder` - superpowered `LabeledBuilder` instead of creating the whole builder, it lets you continuously add/remove nodes from builder and create graph via a WAL log lite.
* `GridGraph` &amp; `ToroidalGraph` - Creates graphs from 2D grid data. Toroidal wraps ends of rows and columns.

A use case for Yog builders is [Choreo](https://www.github.com/code-shoily/choreo) where builder pattern is used to add system design DSL on top of Yog.

## Examining the Graph

You can query the graph's structure using functions in the main `Yog` module or `Yog.Model`.

```elixir
IO.puts "Nodes: #{Yog.node_count(g)}"
IO.puts "Edges: #{Yog.edge_count(g)}"

# Get successors of node 2
IO.inspect(Yog.successors(g, 2), label: "Successors of 2")

# Get neighbors regardless of direction
IO.inspect(Yog.neighbors(g, 3), label: "Neighbors of 3")

# Check if the graph is cyclic
IO.puts("Is cyclic? #{Yog.cyclic?(g)}")
```

## Transformations

`Yog` excels at functional transformations. You can map or filter nodes and edges to create new graph versions.

```elixir
# Double all edge weights
high_weight_graph = Yog.Transform.map_edges(g, fn weight -> 
  if is_number(weight), do: weight * 2, else: weight 
end)

# Filter for nodes with numeric IDs
numeric_only = Yog.Transform.filter_nodes_indexed(g, fn id, _ -> is_integer(id) end)
```

## Comprehensive Algorithms

`Yog` comes with 223 registered algorithms, generators, and helper tools categorized across 22 areas

### Pathfinding

```elixir
cols = 6
grid_data = List.duplicate(List.duplicate(".", cols), cols)
grid_builder = Yog.Builder.Grid.from_2d_list(grid_data, :undirected, Yog.Builder.Grid.always())
graph = Yog.Builder.Grid.to_graph(grid_builder)

start_node = Yog.Builder.Grid.coord_to_id(0, 0, cols)
end_node = Yog.Builder.Grid.coord_to_id(5, 5, cols)

{:ok, path} = Yog.Pathfinding.Dijkstra.shortest_path(graph, start_node, end_node)

# Create base options with coordinate labels for nodes, and hide edge labels
base_opts = 
  Yog.Render.DOT.default_options()
  |> Map.put(:node_label, fn id, _data ->
    {r, c} = Yog.Builder.Grid.id_to_coord(id, cols)
    "#{r},#{c}"
  end)
  |> Map.put(:edge_label, fn _weight -> "" end)

# Pass base_opts to path_to_options to highlight path and retain custom labeling
opts = Yog.Render.DOT.path_to_options(path, base_opts)

Kino.VizJS.render(Yog.Render.DOT.to_dot(graph, opts), height: "800px")

```

### Community Detection

```elixir
# Generate a graph with 24 nodes, 3 communities, p_in = 0.7, p_out = 0.1
sbm = Yog.Generator.Random.sbm(24, 3, 0.7, 0.1, community_sizes: [8, 8, 8])
result = Yog.Community.Louvain.detect(sbm)

IO.puts("Detected #{result.num_communities} communities")
IO.inspect(result.assignments, label: "Node -> Community")

# Visualize with community colors
opts = Yog.Render.DOT.community_to_options(result)
Kino.VizJS.render(Yog.Render.DOT.to_dot(sbm, opts), engine: "circo", height: "1200px")
```

## Visualization Formats

`Yog` supports both Graphviz DOT and Mermaid.js output.

```elixir
# Graphviz DOT (rich, customizable)
dot = Yog.Render.DOT.to_dot(g)

# Mermaid.js (great for Markdown docs)
mermaid = Yog.Render.Mermaid.to_mermaid(g)


IO.puts("DOT")
IO.puts(dot)
IO.puts("Mermaid")
IO.puts(mermaid)

```

```elixir
Kino.Layout.tabs(
  Dot: Kino.VizJS.render(dot),
  Mermaid: Kino.Mermaid.new(mermaid)
)
```

## Serialization

You can easily import/export graphs in various formats like GraphML, JSON, GDF, Graph6, or DOT.

````elixir
xml = """
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
     http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
  <graph id="G" edgedefault="undirected">
    <node id="n0"/>
    <node id="n1"/>
    <node id="n2"/>
    <node id="n3"/>
    <node id="n4"/>
    <node id="n5"/>
    <node id="n6"/>
    <node id="n7"/>
    <node id="n8"/>
    <node id="n9"/>
    <node id="n10"/>
    <edge source="n0" target="n2"/>
    <edge source="n1" target="n2"/>
    <edge source="n2" target="n3"/>
    <edge source="n3" target="n5"/>
    <edge source="n3" target="n4"/>
    <edge source="n4" target="n6"/>
    <edge source="n6" target="n5"/>
    <edge source="n5" target="n7"/>
    <edge source="n6" target="n8"/>
    <edge source="n8" target="n7"/>
    <edge source="n8" target="n9"/>
    <edge source="n8" target="n10"/>
  </graph>
</graphml>
"""

# Let's load the graph
{:ok, graph} = Yog.IO.GraphML.deserialize(xml)

# Export to GDF (GUESS format)
gdf = Yog.IO.GDF.serialize(graph)
IO.puts String.slice(gdf, 0, 300) <> "..."

Kino.Layout.grid([
  Kino.Markdown.new("""
  ```text
  #{gdf}
  ```
  """),
  graph
  |> Yog.Render.DOT.to_dot()
  |> Kino.VizJS.render(height: "600px")
], columns: 2)
````

## Next Steps

Explore the [Algorithm Catalog](https://github.com/code-shoily/yog_ex/blob/main/ALGORITHMS.md) to see everything `Yog` can do!