Class: DAG

Inherits:
Object
  • Object
show all
Defined in:
lib/dag.rb,
lib/dag/vertex.rb

Defined Under Namespace

Classes: Edge, Vertex

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(options = {}) ⇒ DAG

Create a new Directed Acyclic Graph

Parameters:

  • options (Hash) (defaults to: {}) —

    configuration options

Options Hash (options):

  • mix (Module) —

    this module into any created Vertex



17
18
19
20
21
 
# File 'lib/dag.rb', line 17

def initialize(options = {})
  @vertices = []
  @edges = []
  @mixin = options[:mixin]
end

Instance Attribute Details

#edges ⇒ Object (readonly)

Returns the value of attribute edges.



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

def edges
  @edges
end

#vertices ⇒ Object (readonly)

Returns the value of attribute vertices.



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

def vertices
  @vertices
end

Instance Method Details

#add_edge(attrs) ⇒ Object

Raises:

  • (ArgumentError) 


30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/dag.rb', line 30

def add_edge(attrs)
  origin = attrs[:origin] || attrs[:source] || attrs[:from] || attrs[:start]
  destination = attrs[:destination] || attrs[:sink] || attrs[:to] || attrs[:end]
  properties = attrs[:properties] || {}
  raise ArgumentError.new('Origin must be a vertex in this DAG') unless
    is_my_vertex?(origin)
  raise ArgumentError.new('Destination must be a vertex in this DAG') unless
    is_my_vertex?(destination)
  raise ArgumentError.new('A DAG must not have cycles') if origin == destination
  raise ArgumentError.new('A DAG must not have cycles') if destination.has_path_to?(origin)
  Edge.new(origin, destination, properties).tap {|e| @edges << e }
end

#add_vertex(payload = {}) ⇒ Object 



23
24
25
26
27
28
 
# File 'lib/dag.rb', line 23

def add_vertex(payload = {})
  Vertex.new(self, payload).tap {|v|
    v.extend(@mixin) if @mixin
    @vertices << v
  }
end

#subgraph(predecessors_of = [], successors_of = []) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/dag.rb', line 43

def subgraph(predecessors_of = [], successors_of = [])


  (predecessors_of + successors_of).each { |v|
    raise ArgumentError.new('You must supply a vertex in this DAG') unless
      is_my_vertex?(v)
    }

  result = self.class.new({mixin: @mixin})
  vertex_mapping = {}

  # Get the set of predecessors verticies and add a copy to the result
  predecessors_set = Set.new(predecessors_of)
  predecessors_of.each { |v| v.ancestors(predecessors_set) }

  predecessors_set.each do |v|
    vertex_mapping[v] = result.add_vertex(payload=v.payload)
  end

  # Get the set of successor vertices and add a copy to the result
  successors_set = Set.new(successors_of)
  successors_of.each { |v| v.descendants(successors_set) }

  successors_set.each do |v|
    vertex_mapping[v] = result.add_vertex(payload=v.payload) unless vertex_mapping.include? v
  end

  # get the unique edges
  edge_set = (
    predecessors_set.flat_map(&:incoming_edges) +
    successors_set.flat_map(&:outgoing_edges)
  ).uniq

  # Add them to the result via the vertex mapping
  edge_set.each do |e|
    result.add_edge(
      from: vertex_mapping[e.origin],
      to: vertex_mapping[e.destination],
      properties: e.properties)
  end

  return result
end