module InventoryRefresh
  class Graph
    class TopologicalSort
      attr_reader :graph

      # @param graph [InventoryRefresh::Graph] graph object we want to sort
      def initialize(graph)
        @graph = graph
      end

        ################################################################################################################
        # 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.
        ################################################################################################################
      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
    end
  end
end