YogEx Cheatsheet

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.

# 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

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

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

# 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.

# 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.

Mapping & Filtering

Modify data or prune structure using functional primitives.

# 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.

# 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.

# 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 Options

Algorithms use semiring parameters for custom optimizations.

# 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.

# 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.

# 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.

# 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))

Reachability

Check connectivity and extract components.

# 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.

# 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.

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.

# 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?

# 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.

# 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.

# 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.

# 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.

Type Safety

Validate and wrap a directed graph as a DAG to guarantee it has no cycles.

# 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.

# 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.

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).

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.

# 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.

# 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.

Constructors

Import graphs from standard formats or data structures.

# 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.

# 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.

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