Exploring Graphs with Ruby
summary
Ruby code builds graph objects from JSON adjacency matrices and adjacency lists and runs traversal and shortest-path algorithms on up to 230 nodes. Implements Dijkstra and A implemented with edge weights stored on edges and a priority queue frontier (uses a priority_queue gem* or simple binary heap). Also adapts a 2018 cache-shortest-path variant for multiple alternatives. Example: site for International Union for Crystallography uses these Ruby routines to compute shortest routes and diagnostics; suitable for experimentation, not big-data graph databases.
AI-written summary · about
chapters (12)
- 0:00Introduction and speaker background
- 4:29What is a graph
- 8:32Graph representation in Ruby
- 13:31Building a Graph class
- 14:56Graph traversal algorithms overview
- 15:58Depth-first search explained
- 20:43Breadth-first search explained
- 24:12Weighted graphs and Dijkstra's
- 29:52A-star search algorithm
- 32:02k-shortest paths problem
- 33:51Limitations of graph algorithms
- 35:19Conclusion and key takeaways
related talks
31mExtending CRuby with native Graph data type
38mGraphs Are Everywhere!
24mOur daily graphs written in Ruby and Neo4j
43mGraphs are Everywhere
23mPowerful (but Easy) Data Visualization with the Graph Gem
25mPowerful (but Easy) Data Visualization with the Graph Gem
31mGraph Analytics - From the Whiteboard to Your Toolbox
51mDungeons, Dragons, and Graph Databases.