# YogEx Cheatsheet

## Data Structure {:.col-2}

### Internal Representation
The core graph is a dual-map adjacency structure designed for efficiency.

* A graph can be `:directed` or `:undirected`.
* A Node ID can be any term.
* Node and Edge can hold any `term()` as data.

```elixir
# Internal structure visualization (Nodes: 1-6)
%Yog.Graph{
  kind: :directed,
  nodes: %{1 => "A", 2 => "B", 3 => "C", 4 => "D", 5 => "E", 6 => "F"},
  out_edges: %{
    1 => %{2 => 10, 3 => 5},
    2 => %{4 => 8, 6 => 15},
    3 => %{4 => 7, 5 => 12},
    4 => %{5 => 10, 6 => 9},
    5 => %{1 => 14},
    6 => %{2 => 11}
  },
  in_edges: %{
    2 => %{1 => 10, 6 => 11},
    3 => %{1 => 5},
    4 => %{2 => 8, 3 => 7},
    5 => %{3 => 12, 4 => 10},
    6 => %{2 => 15, 4 => 9},
    1 => %{5 => 14}
  }
}
```

### Representation
<div class="graphviz">
digraph G {
  rankdir=LR;
  bgcolor="transparent";
  node [shape=circle, fontname="inherit"];
  edge [fontname="inherit", fontsize=10];
  1 [label="A"]; 2 [label="B"]; 3 [label="C"];
  4 [label="D"]; 5 [label="E"]; 6 [label="F"];
  1 -> 2 [label="10"]; 1 -> 3 [label="5"];
  2 -> 4 [label="8"]; 2 -> 6 [label="15"];
  3 -> 4 [label="7"]; 3 -> 5 [label="12"];
  4 -> 5 [label="10"]; 4 -> 6 [label="9"];
  5 -> 1 [label="14"];
  6 -> 2 [label="11"];
}
</div>

### Performance Profile
- **Storage**: O(V + E) memory.
- **Node Access**: O(1) lookup in `nodes` map.
- **Edge Check**: O(1) lookup in `out_edges`.
- **Successors**: O(1) lookup of neighbor map in `out_edges`.
- **Predecessors**: O(1) lookup of parent map in `in_edges`.
- **Transpose**: O(1) swapping of in_edges and out_edges
## Core Graph Operations {:.col-2}

### Creation
We can create a graph directly or from edges. 

`Yog` module contains helper functions to create graphs from edges and has 
`:directed` or `:undirected` as first arg.

- `weighted` - Weight is provided
- `unweighted` - Weight is not provided (`nil`)
- `simple` - Weight is one

```elixir
# Create directed graph
Yog.directed()

# Create undirected graph
Yog.undirected()

# Custom graph type
Yog.new(:directed)

# From edges
Yog.from_edges(:directed, [{1, 2, 10}, {2, 3, 20}])
Yog.from_unweighted_edges(:undirected, [{1, 2}, {2, 3}])
Yog.from_simple_edges(:undirected, [{1, 2}, {2, 3}])

```
* Refer to `Yog` and `Yog.Model` for more information.
* See `Yog.Builder` modules for more ways to create graphs.
* See `Yog.IO` for more ways to import/export graphs.
* See `Yog.Generator` for more ways to generate graphs.

### Modification

A node ID can be any term but it is recommended to use numbers and keep the information
as node data.

`add_edge` and `add_edges` return `{:ok, graph}` or `{:error, reason}`. Use `add_edge!` and `add_edges!` to 
raise an error if the edge cannot be added.

Please note that all modification functions return a new graph.

```elixir
# Add node with data
graph = Yog.add_node(graph, 1, %{name: "Center", lat: 0, lng: 0})

# Add edge - nodes must exist
{:ok, graph} = Yog.add_edge(graph, from: 1, to: 2, with: %{distance: 10, toll: false, speed_limit: 100})
{:ok, graph} = Yog.add_edges(graph, [{1, 2, 5}, {2, 3, 10}])

## Add edges - nodes are created if they don't exist
{:ok, graph} = Yog.add_edge_ensure(graph, from: 1, to: 0, with: 10, default: 0) # `nil` if default not provided
{:ok, graph} = Yog.add_edge_with(graph, 1, 0, 10, fn node_id -> DataStore.get(node_id) end)

# Remove node/edge
graph = Yog.remove_node(graph, 1)
graph = Yog.remove_edge(graph, 1, 2)
```
* See `Yog.Model` for more ways to add nodes and edges.

## Transform & Operations {:.col-2}

### Mapping & Filtering
Modify data or prune structure using functional primitives.

```elixir
# Transform node data
Yog.Transform.map_nodes(graph, &String.upcase/1)

# Transform edge weights
Yog.Transform.map_edges(graph, fn w -> w * 2 end)

# Prune structure
Yog.Transform.filter_nodes(graph, fn data -> data.active? end)
Yog.Transform.filter_edges(graph, fn u, v, _w -> u != v end)
```

### Graph Transformations
Topological mutations and re-orientations.

```elixir
# Reverse edge directions (O(1))
Yog.Transform.transpose(graph)

# Convert directionality
Yog.Transform.to_undirected(graph, &min/2)
Yog.Transform.to_directed(graph)
```

### Set Operations
Combine or compare graphs as sets of nodes and edges.

```elixir
# Operations from Yog.Operation
Yog.Operation.union(graph_a, graph_b)
Yog.Operation.intersection(graph_a, graph_b)
Yog.Operation.difference(graph_a, graph_b)
```
* See `Yog.Operation` for `composition` and `isomorphic?`.

## Pathfinding & Traversal {:.col-2}

### Pathfinding Options
Algorithms use **semiring** parameters for custom optimizations.

```elixir
# Dijkstra/A* options
opts = [
  from: 1, to: 10,
  zero: 0,                # Identity
  add: &+/2,              # Accumulator
  compare: &Yog.Utils.compare/2 # Relation
]
Yog.Pathfinding.shortest_path(graph, opts)
```

### Algorithms & Traversal
Standard search and exploration functions.

```elixir
# Standard Dijkstra / A*
Yog.Pathfinding.Dijkstra.shortest_path(graph, from: 1, to: 10)
Yog.Pathfinding.BFS.shortest_path(graph, from: 1, to: 10)

# Fold over structure (BFS/DFS)
Yog.Traversal.fold(graph, from: 1, initial: [], with: callback)
```

### Implicit Search & Traversal
Explore dynamic or infinite state spaces defined by logic.

```elixir
# Expansion-based search (A*)
Yog.Pathfinding.AStar.implicit_a_star(
  from: start_state,
  successors: fn s -> [{next, cost}] end,
  is_goal: fn s -> s == target end
)

# Walk over a virtual graph
Yog.Traversal.implicit_fold(
  from: 1, using: :breadth_first,
  successors_of: fn n -> [n + 1, n * 2] end,
  with: fn count, _id, _meta -> {:continue, count + 1} end
)
```

### Path Results & Hydration
Results return node IDs; "hydration" retrieves the associated data.

```elixir
# Result internal structure
%{nodes: [1, 5, 10], total_weight: 42.0, distance: 2}

# Map IDs to their associated data
path = Yog.Pathfinding.Dijkstra.shortest_path(graph, from: 1, to: 10)
Enum.map(path.nodes, &Yog.Model.node(graph, &1))
```

## Properties & Checks {:.col-2}

### Reachability
Check connectivity and extract components.

```elixir
# Path existence check
Yog.Connectivity.reachable?(graph, 1, 10)

# Strongly Connected Components
Yog.Connectivity.strongly_connected_components(graph)
```

### Invariants & Metrics
Verify structural properties and calculate health.

```elixir
# DAG & Bipartite checks
Yog.Property.Cyclicity.is_dag?(graph)
Yog.Property.Bipartite.bipartite?(graph)

# Walk-based analysis
Yog.Traversal.fold_walk(over: graph, from: 1, with: callback)
```
* See `Yog.Traversal` for lexicographical and acyclic-guaranteed walks.

## Algorithms & Metrics {:.col-2}

### Centrality & Rankings
Determine the relative importance of nodes within a network. 

- **Betweenness**: Nodes that act as bridges.
- **Closeness**: Nodes that can reach others quickly.
- **PageRank**: Probability-based ranking.

```elixir
# Measure node importance
Yog.Centrality.Brandes.betweenness_centrality(graph)

# Direct neighbor counts
Yog.Model.successors(graph, 1)
Yog.Model.predecessors(graph, 1)
```
* See `Yog.Centrality` for advanced sorting and weighting.

### Network Health
Measure the global structural quality and efficiency of the graph.

- **Diameter**: Longest shortest path (max separation).
- **Radius**: Min eccentricity (best central hub).
- **Assortativity**: Do hubs connect to hubs or leaves?

```elixir
# Check graph compactness
Yog.Health.diameter(graph)
Yog.Health.radius(graph)

# Social (positive) vs Bio (negative) patterns
assort = Yog.Health.assortativity(graph)
```
* Use `Yog.Health` for average path lengths and eccentricity.

### Community Detection
Partition nodes into densely connected modules (clusters).

- **Louvain/Leiden**: Fast, quality-guaranteed modularity optimization.
- **Label Propagation**: Linear-time, near-instant detection.
- **Modularity (Q)**: Metric for "strength" of the grouping.

```elixir
# Auto-detect clusters
res = Yog.Community.Louvain.detect(graph)

# Get metrics
Yog.Community.modularity(graph, res)
Yog.Community.sizes(res) # %{comm_id => count}
```
* See `Yog.Community` for hierarchical and local detection.

### Minimum Spanning Trees (MST)
Find a subset of edges that connects all nodes with the minimum (or maximum) total weight.

- **Prim/Kruskal**: Standards for minimizing edge weight.
- **Maximum MST**: Connect nodes using the heaviest edges (for redundancy/capacity).
- **Uniform Forest**: Sample a random spanning tree from all possible trees.

```elixir
# Standard Minimum Tree (Kruskal)
Yog.MST.kruskal(graph)

# Maximum Spanning Tree (MaxST)
Yog.MST.kruskal_max(graph)
Yog.MST.prim_max(graph, from: 1)

# Random Spanning Forest (Wilson's)
Yog.MST.uniform_spanning_tree(graph)
```
* Refer to `Yog.MST` for algorithm selection and weighted/unweighted variations.

### Connectivity & SCC
Analyze how nodes are grouped together in directed and undirected graphs.

- **SCC (Strongly Connected)**: For directed graphs (Tarjan/Kosaraju).
- **Critical Points**: Bridges and Articulation Points.

```elixir
# Find all Strongly Connected Components
Yog.Connectivity.scc(directed_graph)

# Analyze bridges and articulation points
results = Yog.Connectivity.analyze(undirected_graph)
results.bridges             # [{1, 2}, {3, 4}]
results.articulation_points  # [2, 5]
```
* See `Yog.Connectivity` for k-core and weakly connected components.

## DAG {:.col-2}

### Type Safety
Validate and wrap a directed graph as a `DAG` to guarantee it has no cycles.

```elixir
# Wrap a graph and prove acyclicity
{:ok, dag} = Yog.DAG.from_graph(graph)

# Convert back to general graph
Yog.DAG.to_graph(dag)
```
* Use `Yog.DAG.Model` for operations that maintain DAG invariants.

### Total Functions
Specialized algorithms that are guaranteed to succeed on a DAG without checking for cycles internally.

```elixir
# Linear time topological sort (Infallible)
sorted_nodes = Yog.DAG.topological_sort(dag)

# Find the longest path (Critical Path analysis)
path = Yog.DAG.longest_path(dag)
```
* See `Yog.DAG.Algorithm` for more DAG-specific logic.

## Maze & Grid {:.col-2}

### Grid Construction
Build 2D structures from nested lists with movement constraints.

- **Topologies**: `rook` (4-way), `queen` (8-way), `bishop` (diagonal).
- **Predicates**: `walkable` (only specific values), `avoiding` (all but values).

```elixir
maze_data = [
  [".", ".", "#"],
  [".", "#", "."],
  [".", ".", "G"]
]

# Create an undirected grid where "." is walkable
grid = Yog.Builder.Grid.from_2d_list(
  maze_data, 
  :undirected, 
  Yog.Builder.Grid.walkable(".")
)

# Convert to standard graph for pathfinding
graph = Yog.Builder.GridGraph.to_graph(grid)
```
* Use `Yog.Builder.Grid` for coordinate-to-node-ID mapping.

### Navigation & Heuristics
Estimate costs between grid cells for informed search (A*).

- **Manhattan**: Sum of cardinal steps (for Rook).
- **Chebyshev**: Max of row/col diffs (for Queen/8-way).
- **Octile**: Precise 8-way cost using √2 for diagonals.

```elixir
# Convert coordinates back and forth
id = Yog.Builder.Grid.coord_to_id(row, col, cols)
{r, c} = Yog.Builder.Grid.id_to_coord(id, cols)

# Distance estimate for A*
heuristic = fn a, b -> 
  Yog.Builder.Grid.manhattan_distance(a, b, cols)
end
```
* Refer to `Yog.Builder.Grid` for all distance formulas.

### Maze Generation
Create procedurally generated "perfect mazes" (spanning trees on a grid).

- **Recursive Backtracker**: Classic, twisty corridors.
- **Prim**: Radial texture, many dead ends.
- **Kruskal**: Well-balanced, uniform look.

```elixir
# Generate a 20x20 twisty maze
maze = Yog.Generator.Maze.recursive_backtracker(20, 20, seed: 123)

# Render to string for CLI output
IO.puts(Yog.Render.ASCII.grid_to_string(maze))
```
* See `Yog.Generator.Maze` for algorithm selection guide.

## IO & Serialization {:.col-2}

### Constructors
Import graphs from standard formats or data structures.

```elixir
# From adjacency lists/matrices
Yog.from_adjacency_list(:directed, [{"A", ["B", "C"]}])

# Parse external formats
Yog.IO.JSON.decode(json)
Yog.IO.GraphML.decode(xml)
```

### Export & Render
Serialize graphs for storage or visualization.

```elixir
# Export to basic list
Yog.to_adjacency_list(graph)

# Render to diagram strings
Yog.Render.Dot.render(graph)
Yog.Render.Mermaid.render(graph)
```
* See `Yog.IO` for LEDA, Pajek, and GDF support.

## Documentation & Navigation {:.col-2}

### Browser Shortcuts
- **`s`**: Open quick-search bar
- **`g`**: Go to Hex package docs
- **`?`**: Toggle shortcut help
- **`/`**: Focus search bar

### Linking Syntax (Backticks)
- `` `Module` ``: Link to a module
- `` `mod.fun/2` ``: Link to a function
- `` `t:mod.type/0` ``: Link to a type
- `` `c:mod.fun/1` ``: Link to a callback
- `` `[txt](`fun/1`)` ``: Custom link text