Class: InventoryRefresh::Graph::TopologicalSort

Inherits:
Object
  • Object
show all
Defined in:
lib/inventory_refresh/graph/topological_sort.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(graph) ⇒ TopologicalSort

Returns a new instance of TopologicalSort.

Parameters:



7
8
9
 
# File 'lib/inventory_refresh/graph/topological_sort.rb', line 7

def initialize(graph)
  @graph = graph
end

Instance Attribute Details

#graph ⇒ Object (readonly)

Returns the value of attribute graph.



4
5
6
 
# File 'lib/inventory_refresh/graph/topological_sort.rb', line 4

def graph
  @graph
end

Instance Method Details

#topological_sort ⇒ Array<Array>

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.

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.

Returns:

  • (Array<Array>) —

    Array of arrays(layers) of InventoryCollection objects



35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# 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