Changelog

Copy Markdown View Source

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

0.98.3 - 2026-06-09

Fixed

  • Yog.Community.Walktrap.detect/1 — Now selects the modularity-maximizing level from the dendrogram instead of the trivial all-merged level. The default partition is meaningful for typical graphs.
  • Yog.Multi.Model.degree/2, out_degree/2, in_degree/2 — Now correctly count undirected self-loops as contributing 2 to a node's degree (matching standard graph theory). This also fixes false-negative Eulerian path/circuit detection on undirected multigraphs containing self-loops.
  • Yog.Multi.Eulerian.has_eulerian_circuit?/1, has_eulerian_path?/1, find_eulerian_circuit/1, find_eulerian_path/1 — Now correctly tolerate isolated nodes (nodes with zero degree). Connectivity is checked over non-isolated nodes only, and start-node selection skips isolated nodes, matching standard Eulerian theory and NetworkX's behavior.
  • Yog.Community.Louvain.detect/1 — Now runs full hierarchical Louvain (phase 1 + aggregation + recursion) instead of phase 1 only. The returned partition may differ from previous versions on graphs without strong community structure (e.g., scale-free networks) — both partitions are valid modularity local optima but the new one is the standard Louvain output.
  • Yog.Community.Louvain.detect_hierarchical/1 — Now stores raw community IDs at each level so that the dendrogram can be correctly flattened back to original node IDs. See Yog.Community.Dendrogram.flatten_to_original/1.
  • Yog.Community.Leiden.detect_hierarchical/1 — Updated docstrings to point at Yog.Community.Dendrogram.flatten_to_original/1 for obtaining final partitions over original node IDs. The dendrogram structure was already compatible after the Louvain fix.
  • Yog.Community.Infomap.detect/1 — Rewrote to implement the actual Map Equation optimization (Rosvall & Bergstrom 2008). Previously ran a single greedy pass with a flow heuristic that did not compute description length. Now computes L(M) = q↷ H(Q) + Σ p↻^i H(P^i), iterates to convergence, and minimizes description length as documented.
  • Yog.Community.GirvanNewman.detect/1 — Now defaults to the modularity-maximizing partition across the dendrogram instead of the trivial all-singletons partition. For users who specifically want the all-singletons partition, pass target_communities: Yog.node_count(graph) explicitly.

Added

[0.98.2] - 2026-06-06

Added

Changed

  • Yog.Approximate & Yog.Health Option Documentation — Normalized :to_float documentation to match the parsed :with_to_float option key.

  • Yog.Health & Yog.Approximate Option Parsing — DRYed up option parsing by sharing the internal parse_metric_opts/1 helper.

  • Yog.Builder.Grid & Yog.Builder.Toroidal — Extracted add_grid_edge/5 helper to comply with Credo nesting rules and avoid deep function nesting.

  • Yog.Utils Optimizations — Refactored norm_diff/3 to be completely allocation-free by using direct map folds, eliminating intermediate key list concatenations and temporary map allocations.

  • Yog.Transform Optimizations — Overhauled multiple transformer functions to eliminate dynamic protocol dispatch and intermediate list/tuple allocations during graph folding:

    • complement/2: Fetches the source node's out-edges once outside the inner loop (saving $O(V^2)$ lookups) and utilizes List.foldl/3 / Utils.map_fold/3.
    • to_undirected/2: Replaced list-comprehension based reduction with nested Utils.map_fold/3 loops.
    • relabel_nodes/2: Folds over nodes and out-edges directly via Utils.map_fold/3, avoiding full edge list allocations (Model.all_edges/1).
    • transitive_closure/1 & redirect_neighbors/5: Updated to fold over adjacency and reachability maps using Utils.map_fold/3 in-place.

  • Yog.Operation Optimizations — Upgraded several core graph join and product builders to completely bypass dynamic enumerable dispatch and intermediate lists:

    • symmetric_difference/2: Rewritten as a single-pass edge collection on the symmetric difference of nodes, completely removing three intermediate subgraph copy and union allocations.
    • isomorphic?/2 (mapping_valid?/5): Replaced linear-time list search checks (s in Map.keys(...)) with $O(1)$ constant-time Map.has_key?/2 lookups.
    • disjoint_union/2: Avoids flat-mapping/rebuilding intermediate edge lists by folding over out-edges directly via Utils.map_fold/3.
    • cartesian_product/4: Rewrote vertical, horizontal, and node product helpers to fold with Utils.map_fold/3 and List.foldl/3 instead of nested Enum.reduce/3 on maps.
    • line_graph/2: Optimized unique undirected edge extraction to filter in $O(E)$ during fold, eliminating expensive Enum.uniq_by/2 and Enum.map/2 stages. Bypassed enumerable reduction in edge-incident traversals.
    • power/3: Refactored distance closure iterations to utilize fast List.foldl/3 on lists.

  • Yog.PairingHeap — Optimized the internal combine helper to bypass creating %Empty{} structs when matching even number of children (size $\ge 2$), reducing allocation overhead during restructuring.

  • Yog.Model.add_node/3 — Defaulted the data parameter to nil, allowing nodes to be added to graphs and multigraphs without a data payload (e.g., Yog.add_node(graph, id)). Updated delegations in Yog.add_node/3 and Yog.Multi.add_node/3.

  • Yog.DisjointSet — Optimized find/2 and find_root_readonly/2 to eliminate redundant struct allocations during recursion. find_root_readonly/2 now operates directly on the parents map.

Fixed

[0.98.1] - 2026-05-23

Added

Multigraph Collapse Helpers

  • Yog.Multi.Model.to_simple_graph_max_edges/1 — New helper that collapses parallel edges keeping the maximum weight. Useful for widest-path and bottleneck algorithms.
  • Yog.Multi.Model.to_simple_graph_sum_edges/1 — New zero-argument helper that sums parallel edge weights using &Kernel.+/2. Complements the existing to_simple_graph_sum_edges/2 which accepts a custom combine function.
  • Yog.Multi — Added facade delegations for to_simple_graph_max_edges/1 and to_simple_graph_sum_edges/1.

Documentation

  • ALGORITHMS.md — Comprehensive audit and update:
    • Added missing algorithms: Brandes SSSP, Chinese Postman, Path Utilities, Distance Matrix, Hungarian matching, Blossom matching, Graph Coloring, Tree Decomposition, and maze generators (Kruskal's, Prim's simplified/true, Eller's, Growing Tree, Recursive Division).
    • Added missing categories: Random Graph Generation, Graph Builders, Functional Graphs (FGL-style), and Rendering.
    • Fixed incorrect module names: Yog.PriorityQueue → Yog.PairingHeap, Yog.Connectivity.Bridge / Articulation → Yog.Connectivity.Analysis.
    • Removed ghost algorithms: Capacity Scaling, Network Simplex.
    • Removed duplicate Dinic's entry in Flow & Cuts.
    • Moved maze generation algorithms out of Approximation Algorithms into Maze Generation.

Fixed

  • Yog.Multi.Model.to_simple_graph/1 — Now deterministic. Edges are sorted by edge_id before collapsing, guaranteeing that the earliest-added edge is always kept. Previously, iteration order over the edges map was undefined, making the result non-deterministic.

[0.98.0] - 2026-05-16

Added

Builder Modules

  • Yog.Builder.Labeled — Added convenience query functions:
    • has_label?/2 — Check if a label is registered.
    • has_edge?/3 — Check if an edge exists between two labels.
    • node_count/1 — Number of registered nodes.
    • edge_count/1 — Number of edges in the underlying graph.
  • Yog.Builder.Live — Added has_label?/2 for registry membership checks.

DAG Modules

Multigraph Facade

  • Yog.Multi — Filled facade gaps and added multigraph-native algorithms:
    • has_edge/2 — Check if a specific edge_id exists.
    • edge_count/3 — Count parallel edges between a node pair.
    • degree/2 — Total degree (in + out for directed, out-degree for undirected).
    • has_cycle?/1 — Detect cycles without manual collapsing.
    • topological_sort/1 — Returns {:ok, [node_id]} or {:error, :contains_cycle}.
    • to_simple_graph/1 — Collapse keeping only the first edge between each pair.
    • to_simple_graph_min_edges/1 — Collapse parallel edges keeping the minimum weight.
    • to_simple_graph_sum_edges/2 — Collapse parallel edges summing weights via a custom function.

Generators

  • Yog.Generator.Classic — Added missing _with_type variant:
    • prism_with_type/2 — Generate a prism (circular ladder) graph with a specified graph type.

Rendering

  • Yog.Multi.Mermaid — New Mermaid.js renderer for multigraphs (Yog.Multi.Graph).
    • Supports parallel edges between the same pair of nodes.
    • edge_id-based callbacks (edge_label/2, edge_attributes/4) for per-edge customization.
    • Highlighting by edge_id or {from, to} tuple.
    • Subgraphs, per-node styling, and all node shapes/directions.
    • theme/1 with :default, :dark, :minimal, :presentation presets.
    • Algorithm helpers: path_to_options/2, mst_to_options/2, community_to_options/2, cut_to_options/2, matching_to_options/2.
    • default_options_with_edge_formatter/1, default_options_with/1, default_options_without_labels/0.
  • Yog.Multi.DOT — Feature parity with Yog.Render.DOT:
    • theme/1 with all presets.
    • Algorithm helpers: path_to_options/2, mst_to_options/2, community_to_options/2, cut_to_options/2, matching_to_options/2.
    • default_options_with_edge_formatter/1, default_options_with/1, default_options_without_labels/0.
  • Yog.Render.Mermaid parity with Yog.Render.DOT:
    • node_attributes/2 callback for per-node inline styling (style node_id fill:...,stroke:...).
    • edge_attributes/3 callback for per-edge styling via linkStyle index ....
    • subgraphs option for Mermaid subgraph ... end blocks.
    • theme/1 — Presets: :default, :dark, :minimal, :presentation.
    • mst_to_options/2, community_to_options/2, cut_to_options/2, matching_to_options/2.
    • default_options_with_edge_formatter/1 and default_options_with/1.
    • Internal MapSet conversion for O(1) highlight membership checks.
  • Yog.Utils — Extracted shared rendering helpers to eliminate Credo duplication:
    • generate_palette/1, hsl_to_hex/3, mst_highlights/1, matching_highlights/1, path_to_edges/1.

Fixed

  • Mermaid themes now apply globally to all nodes/edges via classDef default and linkStyle (previously only affected highlighted elements).
  • Mermaid dark mode readability — Added default_font_color option for white text on dark backgrounds.
  • Mermaid undirected edge labels — Fixed invalid ---|1| syntax to correct -- 1 ---.
  • Mermaid per-node shapes — node_shape now accepts (id, data) -> shape function in addition to atom values.
  • Credo alias warnings in Yog.Multi.Mermaid.
  • Maze generator RNG state isolation — All maze algorithms (binary_tree/3, sidewinder/3, recursive_backtracker/3, hunt_and_kill/3, aldous_broder/3, wilson/3, kruskal/3, prim_simplified/3, prim_true/3, ellers/3, growing_tree/3, recursive_division/3) now restore the global :rand state after seeding, matching the behavior of Yog.Generator.Random. Previously, passing :seed permanently altered the global RNG state.
  • Removed accidental IO.puts debug output from test/yog/multi/dot_test.exs.

Builders

  • Yog.Builder.Live.sync_multi/2 — New function to sync pending changes to a multigraph (Yog.Multi.Graph).
    • add_edge creates parallel edges rather than overwriting existing ones.
    • remove_edge removes all parallel edges between the given node pair.
    • Supports incremental sync, unweighted/simple edges, node removal, and both directed/undirected multigraphs.

Documentation & Livebooks

  • All 11 livebooks reviewed and improved with better content and code coverage:
    • gallery/graph_catalog — Added Mermaid rendering, property checks (regularity, connectivity, diameter, girth), hypercube and binary tree generators.
    • guides/getting_started — Added Yog.Builder.Live example, community detection, Mermaid export, and more query examples.
    • guides/dag_analysis — Added cycle detection, transitive reduction with visualization, Mermaid rendering, and Yog.acyclic?/1.
    • guides/graph_properties — Fixed coloring visualization (now actually applies colors to DOT), added DSatur comparison, exact coloring, K3,3 planarity, and planar embedding.
    • guides/network_analysis — Fixed community detection API (.assignments instead of .communities), added degree/closeness centrality, articulation point/bridge visualization with per-element styling.
    • guides/network_flow — Added global min-cut (Stoer-Wagner), fixed bipartite matching example, removed broken min-cost max-flow placeholder.
    • guides/traversals_and_pathfinding — Added Bellman-Ford with negative weights, real A* grid example using Yog.Builder.GridGraph, Johnson's mention.
    • how_to/customizing_visualizations — Fixed old API usage (node_attributes as function, not keyword list), added Mermaid themes, per-node/edge styling, subgraphs, and algorithm helpers (path_to_options, mst_to_options, community_to_options, cut_to_options).
    • how_to/import_export — Added Graph6 and GDF format coverage.
    • how_to/maze_generation — Added Wilson's algorithm demonstration, algorithm property comparison table, path length analysis across algorithms.
    • how_to/multigraphs_and_collapsing — Added multigraph visualization (Yog.Multi.DOT and Yog.Multi.Mermaid), Yog.Builder.Live.sync_multi/2 example, per-edge styled rendering, Eulerian circuits on multigraphs, BFS/DFS traversals.