class DAG
Constants
- Edge
Attributes
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/simple_dag.rb, line 16 def initialize(options = {}) @vertices = [] @mixin = options[:mixin] @n_of_edges = 0 end
Public Instance Methods
add_edge(attrs)
click to toggle source
# File lib/simple_dag.rb, line 29 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, 'Origin must be a vertex in this DAG' unless my_vertex?(origin) raise ArgumentError, 'Destination must be a vertex in this DAG' unless my_vertex?(destination) raise ArgumentError, 'Edge already exists' if origin.successors.include? destination raise ArgumentError, 'A DAG must not have cycles' if origin == destination raise ArgumentError, 'A DAG must not have cycles' if destination.path_to?(origin) @n_of_edges += 1 origin.send :add_edge, destination, properties end
add_vertex(payload = {})
click to toggle source
# File lib/simple_dag.rb, line 22 def add_vertex(payload = {}) Vertex.new(self, payload).tap do |v| v.extend(@mixin) if @mixin @vertices << v end end
edges()
click to toggle source
# File lib/simple_dag.rb, line 54 def edges enumerated_edges.to_a end
enumerated_edges()
click to toggle source
@return Enumerator over all edges in the dag
# File lib/simple_dag.rb, line 48 def enumerated_edges Enumerator.new(@n_of_edges) do |e| @vertices.each { |v| v.outgoing_edges.each { |out| e << out } } end end
subgraph(predecessors_of = [], successors_of = [])
click to toggle source
# File lib/simple_dag.rb, line 58 def subgraph(predecessors_of = [], successors_of = []) (predecessors_of + successors_of).each do |v| raise ArgumentError, 'You must supply a vertex in this DAG' unless my_vertex?(v) end 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) } # 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) } (predecessors_set + successors_set).each do |v| vertex_mapping[v] = result.add_vertex(v.payload) end predecessor_edges = predecessors_set.flat_map(&:outgoing_edges).select do |e| predecessors_set.include? e.destination end # Add the edges to the result via the vertex mapping n_of_result_edges = 0 (predecessor_edges | successors_set.flat_map(&:outgoing_edges)).each do |e| n_of_result_edges += 1 vertex_mapping[e.origin].send :add_edge, vertex_mapping[e.destination], e.properties end result.instance_variable_set :@n_of_edges, n_of_result_edges result end
topological_sort()
click to toggle source
Returns an array of the vertices in the graph in a topological order, i.e. for every path in the dag from a vertex v to a vertex u, v comes before u in the array.
Uses a depth first search.
Assuming that the method include? of class Set runs in linear time, which can be assumed in all practical cases, this method runs in O(n+m) where m is the number of edges and n is the number of vertices.
# File lib/simple_dag.rb, line 105 def topological_sort result_size = 0 result = Array.new(@vertices.length) visited = Set.new visit = lambda { |v| return if visited.include? v v.successors.each do |u| visit.call u end visited.add v result_size += 1 result[-result_size] = v } @vertices.each do |v| next if visited.include? v visit.call v end result end
Private Instance Methods
my_vertex?(v)
click to toggle source
# File lib/simple_dag.rb, line 130 def my_vertex?(v) v.is_a?(Vertex) && (v.dag == self) end