class InventoryRefresh::Graph::TopologicalSort

Attributes

graph[R]

Public Class Methods

new(graph) click to toggle source

@param graph [InventoryRefresh::Graph] graph object we want to sort

# File lib/inventory_refresh/graph/topological_sort.rb, line 7
def initialize(graph)
  @graph = graph
end

Public Instance Methods

topological_sort() click to toggle source

Topological sort of the graph of the DTO collections to find the right order of saving DTO collections and identify what DTO collections can be saved in parallel. Does not mutate graph.

@return [Array<Array>] Array of arrays(layers) of InventoryCollection objects

The expected input here is the directed acyclic Graph G (inventory_collections), consisting of Vertices(Nodes) V and Edges E: G = (V, E)

The directed edge is defined as (u, v), where u is the dependency of v, i.e. arrow comes from u to v: (u, v) ∈ E and u,v ∈ V

S0 is a layer that has no dependencies: S0 = { v ∈ V ∣ ∀u ∈ V.(u,v) ∉ E}

Si+1 is a layer whose dependencies are in the sum of the previous layers from i to 0, cannot write mathematical sum using U in text editor, so there is an alternative format using _(sum) Si+1 = { v ∈ V ∣ ∀u ∈ V.(u,v) ∈ E → u ∈ _(sum(S0..Si))_ }

Then each Si can have their Vertices(DTO collections) processed in parallel. This algorithm cannot identify independent sub-graphs inside of the layers Si, so we can make the processing even more effective.

# File lib/inventory_refresh/graph/topological_sort.rb, line 35
def topological_sort
  nodes          = graph.nodes.dup
  edges          = graph.edges
  sets           = []
  i              = 0
  sets[0], nodes = nodes.partition { |v| !edges.detect { |e| e.second == v } }

  max_depth = 1000
  while nodes.present?
    i         += 1
    max_depth -= 1
    if max_depth <= 0
      message = "Max depth reached while doing topological sort, your graph probably contains a cycle"
      #logger.error("#{message}:\n#{graph.to_graphviz}")
      raise "#{message} (see log)"
    end

    set, nodes = nodes.partition { |v| edges.select { |e| e.second == v }.all? { |e| sets.flatten.include?(e.first) } }
    if set.blank?
      message = "Blank dependency set while doing topological sort, your graph probably contains a cycle"
      #logger.error("#{message}:\n#{graph.to_graphviz}")
      raise "#{message} (see log)"
    end

    sets[i] = set
  end

  sets
end