class DAG
Constants
- Edge
Attributes
edges[R]
vertices[R]
Public Class Methods
new(options = {})
click to toggle source
Create a new Directed Acyclic Graph
@param [Hash] options configuration options @option options [Module] mix this module into any created Vertex
# File lib/dag.rb, line 17 def initialize(options = {}) @vertices = [] @edges = [] @mixin = options[:mixin] end
Public Instance Methods
add_edge(attrs)
click to toggle source
# 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 = {})
click to toggle source
# 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 = [])
click to toggle source
# 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
Private Instance Methods
is_my_vertex?(v)
click to toggle source
# File lib/dag.rb, line 89 def is_my_vertex?(v) v.kind_of?(Vertex) and v.dag == self end