Class: Rukawa::Dag

Inherits:
Object
  • Object
show all
Includes:
Enumerable, TSort
Defined in:
lib/rukawa/dag.rb

Defined Under Namespace

Classes: Edge

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Dag

Returns a new instance of Dag.



11
12
13
14
15
 
# File 'lib/rukawa/dag.rb', line 11

def initialize
  @nodes = Set.new
  @jobs = Set.new
  @edges = Set.new
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



9
10
11
 
# File 'lib/rukawa/dag.rb', line 9

def edges
  @edges
end

#jobs ⇒ Object (readonly)

Returns the value of attribute jobs.



9
10
11
 
# File 'lib/rukawa/dag.rb', line 9

def jobs
  @jobs
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



9
10
11
 
# File 'lib/rukawa/dag.rb', line 9

def nodes
  @nodes
end

Instance Method Details

#build(job_net, variables, dependencies) ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/rukawa/dag.rb', line 17

def build(job_net, variables, dependencies)
  deps = tsortable_hash(dependencies).tsort

  deps.each do |job_class|
    job = job_class.new(job_net, variables)
    @nodes << job
    @jobs << job if job.is_a?(Job)

    dependencies[job_class].each do |depend_job_class|
      depend_job = @nodes.find { |j| j.instance_of?(depend_job_class) }

      depend_job.jobs_as_from.product(job.jobs_as_to).each do |from, to|
        @jobs << from
        @jobs << to
        edge = Edge.new(from, to, job_net)
        @edges << edge
        from.out_goings << edge
        to.in_comings << edge
      end
    end
  end

  if job_net.parent_job_net
    job_net.parent_job_net.dag.jobs.merge(@jobs)
  end
end

#each ⇒ Object 



44
45
46
47
48
49
50
 
# File 'lib/rukawa/dag.rb', line 44

def each
  if block_given?
    @nodes.each { |j| yield j }
  else
    @nodes.each
  end
end

#leveled_each ⇒ Object 



70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
# File 'lib/rukawa/dag.rb', line 70

def leveled_each
  visited = Set.new
  queue = []
  queue.push(*@jobs.select { |j| j.in_comings.empty? })

  if block_given?
    until queue.empty?
      next_job = queue.shift
      yield next_job unless visited.include?(next_job)
      queue.push(*next_job.out_goings.map(&:to)) if visited.add?(next_job)
    end
  else
    Enumerator.new do |y|
      until queue.empty?
        next_job = queue.shift
        y << next_job unless visited.include?(next_job)
        queue.push(*next_job.out_goings.map(&:to)) if visited.add?(next_job)
      end
    end
  end
end

#tsort_each_child(node) ⇒ Object 



56
57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/rukawa/dag.rb', line 56

def tsort_each_child(node)
  if block_given?
    node.out_goings.each do |edge|
      yield edge.to
    end
  else
    Enumerator.new do |y|
      node.out_goings.each do |edge|
        y << edge.to
      end
    end
  end
end

#tsort_each_node(&block) ⇒ Object 



52
53
54
 
# File 'lib/rukawa/dag.rb', line 52

def tsort_each_node(&block)
  @jobs.each(&block)
end