# 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 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` & `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 = """ """ # 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!