dideler
7/22/2016 - 2:36 PM

Example of building a Directed Acyclic Graph (DAG) for tasks that depend on each others

Example of building a Directed Acyclic Graph (DAG) for tasks that depend on each others

Gemfile
content_copyfile_download
source 'http://rubygems.org'

gem 'plexus'
gem 'gratr' # dependency of plexus to visualize graphs
README.md
content_copyfile_download
  • Rendered
  • Source

Requires a YAML file with mappings, e.g.

:task_a:
  :task_b:
    :task_c:
  :task_d:
  :task_e:

View interactive graph:

brew install xdot
xdot graph.dot

View static graph:

brew install graphviz
dot graph.dot -Tsvg -o graph.svg   # SVG
dot graph.dot -Tsvgz -o graph.svgz # Compressed SVG

Recommend using Gapplin to view the SVG files.

task_dag.rb
content_copyfile_download
require 'plexus'
require 'yaml'

class TaskDag
  include Plexus

  def initialize(filepath = File.join('config', 'task_mappings.yml'))
    @dag = DirectedGraph.new # alias of Digraph
    @filepath = filepath
  end

  def build
    add_vertices_and_edges
  end

  def ancestors(task)
    dag.ancestors(task)
  end

  def root(task)
    ancestors(task).last
  end

  def visualize
    filename = dag.write_to_graphic_file and puts "Created #{filename}"
  end

  private

  attr_reader :dag, :filepath

  def add_vertices_and_edges(tasks = yml_tasks)
    tasks.each_pair do |task, child_tasks|
      next if child_tasks.nil?
      child_tasks.keys.each do |child|
        dag.add_edge!(task, child)
      end
      add_vertices_and_edges(child_tasks)
    end
  end

  def yml_tasks
    @yml_tasks ||= YAML.load_file(filepath)
  end
end