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.97.0] - 2026-04-18

Note: No more breaking changes. The focus will be on performance, documentation, and bug fixes in preparation for 1.0.0 in early 2027.

Added

Core API

DAG Algorithms

Transformations

Pathfinding

Property & Structure

  • Yog.Property.Coloring suite:
    • coloring_greedy/1 — Welsh-Powell (O(V²)).
    • coloring_dsatur/1 — DSatur heuristic.
    • coloring_exact/2 — Backtracking exact coloring with optional timeout.
  • Yog.Property.Structure planarity suite:
    • planar?/1 — Exact LR-test (O(V²)).
    • planar_embedding/1 — Combinatorial embedding.
    • kuratowski_witness/1 — Minimal non-planar subgraph witness.
  • Yog.Property.forest?/1, branching?/1, isomorphic?/2, hash/2.

Network Flow

Matching

Rendering

Approximation Algorithms

  • Yog.Approximate module:
    • treewidth_upper_bound/2, tree_decomposition/2.
    • diameter/2, betweenness/2, average_path_length/2, global_efficiency/2, transitivity/2.
    • vertex_cover/1, max_clique/1.

Classic Graph Generators

I/O

Fixed

Optimized

  • Yen's Algorithm: Reduced memory pressure via List.starts_with?/2 for path prefix validation. Fixed PairingHeap comparator binding.
  • HITS Centrality: Reduced iteration from O(V log V) to O(V) via pre-computed flat adjacency lists.
  • Health Metrics: average_local_efficiency/2 reweights once (O(V)) instead of per-node (O(V²)).

[0.96.0] - 2026-04-12

Added

Classic Graph Generators

  • Platonic Solids (#102): tetrahedron/0, cube/0, octahedron/0, dodecahedron/0, icosahedron/0.
  • General Trees (#103): kary_tree/2, complete_kary/2, caterpillar/2.
  • Ladders (#104): circular_ladder/1 (prism), mobius_ladder/1, prism/1.
  • Friendship & Windmill (#105): friendship/1, windmill/2, book/1.
  • Crown Graph (#106): crown/1.
  • Maze Generators (#120): aldous_broder/3, wilson/3, kruskal/3, ellers/3, growing_tree/3, recursive_division/3, prim_simplified/3, prim_true/3.

Random Graph Generators

  • Configuration Model (#110): configuration_model/2, randomize_degree_sequence/2, power_law_graph/2.
  • Kronecker Graphs (#109): kronecker/3, rmat/7, kronecker_general/3.
  • Geometric Graphs (#107): geometric/2, geometric_nd/2, waxman/2.

Pathfinding

Community Metrics

Centrality

Health Metrics

  • Network Efficiency: global_efficiency/2, local_efficiency/3, average_local_efficiency/2.
    • Well-defined for disconnected graphs (unreachable pairs contribute 0.0).
    • Parallelized via Task.async_stream.

Other

  • Johnson's algorithm added to Matrix auto-selection for sparse graphs with many POIs.

Changed

  • Dijkstra: Delegates shortest_path/6 and implicit_dijkstra/6 to AStar with zero heuristic.
  • Bellman-Ford: Early termination when no distances change. 13-24x faster on typical graphs.
  • Bidirectional BFS: O(1) queue size tracking; uses :queue module.
  • Johnson's: Early termination in Bellman-Ford phase.
  • Bidirectional Dijkstra: Proper two-queue implementation with meeting point detection.

Breaking

  • Removed Yog.Pathfinding.Utils. Merged into Yog.Pathfinding.Path:
    • Utils.path/2 → Path.new/2
    • Utils.nodes/1 → path.nodes
    • Utils.total_weight/1 → path.weight

[0.95.0] - 2026-04-04

Added

  • Yog.Pathfinding.all_pair_shortest_path_unweighted/1 — BFS-based APSP for unweighted graphs.
  • Yog.Operation.line_graph/2 — Line graph / line digraph construction.
  • Yog.IO.Libgraph — Bidirectional conversion with the libgraph library.

Changed

  • Priority Queue Restructure: Split into Yog.PairingHeap (O(1) push) and Yog.BalancedTree (O(log n) both).
  • Generators: Added Yog.Generator.Random.sbm/5, sbm_with_labels/5 (Stochastic Block Model).
  • MST Result: kruskal/2 and prim/2 now return {:ok, %Yog.MST.Result{}}.
  • Prim: Added :from option for starting node.
  • Renamed: Yog.Flow.NetworkSimplex → Yog.Flow.SuccessiveShortestPath.
  • Successive Shortest Path: Uses Dijkstra with potentials instead of Bellman-Ford per iteration. Improved from O(F · V · E) to O(F · (E + V log V)).
  • Contract: Major performance optimization via direct map surgery instead of per-edge add_edge_with_combine.
  • MinCut: Complete rewrite of Stoer-Wagner.
    • Eliminated O(V) total_nodes recomputation.
    • Replaced MapSet partition tracking with O(1) integer counts.
    • MinCutResult struct: source_side/sink_side MapSets → source_side_size/sink_side_size integers.

Breaking

[0.90.0] - 2026-03-30

Added

  • Yog.Flow.MaxFlow: Refactored residual storage to nested map (30-50% faster Edmonds-Karp).
  • Yog.Connectivity.shell_decomposition/1 — k-shell grouping.
  • Yog.Functional enhancements:
    • preorder/2, postorder/2, reachable/2.
    • transitive_closure/1, biconnected_components/1, dominators/2.
    • distances/2.
    • from_adjacency_graph/1, to_adjacency_graph/1.
  • Yog.Property: connected?/1, planar?/1, chordal?/1.

Changed

Breaking

  • Removed Yog.Model.add_edge_ensured/5.
  • Removed transitive_closure/1, transitive_reduction/1, count_reachability/2 from Yog.DAG.Algorithm.

[0.80.0] - 2026-03-27

Added

  • Pure Elixir Implementation: Complete migration from Gleam wrapper.
    • All 58 modules in pure Elixir; zero Gleam dependencies.
    • Installation: {:yog_ex, "~> 0.60"} only.

Changed

  • Graph Structure: Tuple {:graph, kind, nodes, out_edges, in_edges} → struct %Yog.Graph{kind, nodes, out_edges, in_edges}.
  • Priority Queue: Yog.PQ (pairing heap) replaces sorted lists.
    • lexicographical_topological_sort: O(V log V + E) vs O(V² + E).
    • implicit_dijkstra: O(E log V) vs O(E × V).
  • Module Reorganization:
  • API Updates:
    • Pathfinding returns %Yog.Pathfinding.Path{} with weight field.
    • edmonds_karp/8 compare function returns boolean.
    • floyd_warshall/4 uses positional args.

[0.70.0] - 2026-03-26

Various performance improvements and examples.

[0.52.3] - 2026-03-22

Fixed

  • Removed app: false from yog dependency; added explicit Gleam deps.

[0.52.2] - 2026-03-22

Fixed

  • Documentation builds correctly on HexDocs.

[0.52.1] - 2026-03-22

Changed

  • All I/O modules now pure Elixir (GraphML, GDF, Pajek, LEDA, TGF, JSON).
  • Removed yog_io dependency.

Fixed

  • Resolved dependency conflicts requiring manual yog_io configuration.

[0.51.0] - 2026-03-22

Added

  • Yog.Pathfinding facade module (unified keyword-based API for Dijkstra, AStar, BellmanFord, FloydWarshall).
  • Yog.Connectivity delegators: connected_components/1, weakly_connected_components/1.
  • I/O integration via yog_io: GDF, GraphML, JSON, LEDA, Pajek, TGF.

Changed

  • Renamed Yog.DAG.Models → Yog.DAG.Model, Yog.DAG.Algorithms → Yog.DAG.Algorithm.
  • Updated examples to use add_edge! for chaining.
  • Updated yog to ~> 5.1.
  • yog_io is now an optional dependency.