class InventoryRefresh::Graph

Attributes

edges[RW]
fixed_edges[RW]
nodes[RW]

Public Class Methods

new(nodes) click to toggle source

@param nodes [Array<InventoryRefresh::InventoryCollection>] List of Inventory collection nodes

# File lib/inventory_refresh/graph.rb, line 8
def initialize(nodes)
  @nodes       = nodes
  @edges       = []
  @fixed_edges = []

  construct_graph!(@nodes)
end

Public Instance Methods

to_graphviz(layers: nil) click to toggle source

Returns graph in GraphViz format, as a string. So it can be displayed.

@param layers [Array<Array>] Array of arrays(layers) of InventoryCollection objects @return [String] Graph in GraphViz format

# File lib/inventory_refresh/graph.rb, line 20
def to_graphviz(layers: nil)
  node_names = friendly_unique_node_names
  s = []

  s << "digraph {"
  (layers || [nodes]).each_with_index do |layer_nodes, i|
    s << "  subgraph cluster_#{i} {  label = \"Layer #{i}\";" unless layers.nil?

    layer_nodes.each do |n|
      s << "    #{node_names[n]}; \t// #{n.inspect}"
    end

    s << "  }" unless layers.nil?
  end

  s << "  // edges:"
  edges.each do |from, to|
    s << "  #{node_names[from]} -> #{node_names[to]};"
  end
  s << "}"
  s.join("\n") + "\n"
end

Protected Instance Methods

assert_graph!(fixed_edges) click to toggle source

Checks that there are no cycles in the graph

@param fixed_edges [Array<Array>] List of edges, where edge is defined as [InventoryCollection, InventoryCollection],

fixed edges are those that can't be moved
# File lib/inventory_refresh/graph.rb, line 61
def assert_graph!(fixed_edges)
  fixed_edges.each do |edge|
    detect_cycle(edge, fixed_edges - [edge], :exception)
  end
end
build_feedback_edge_set(edges, fixed_edges) click to toggle source

Builds a feedback edge set, which is a set of edges creating a cycle

@param edges [Array<Array>] List of edges, where edge is defined as [InventoryCollection, InventoryCollection],

these are all edges except fixed_edges

@param fixed_edges [Array<Array>] List of edges, where edge is defined as [InventoryCollection, InventoryCollection],

fixed edges are those that can't be moved
# File lib/inventory_refresh/graph.rb, line 73
def build_feedback_edge_set(edges, fixed_edges)
  edges             = edges.dup
  acyclic_edges     = fixed_edges.dup
  feedback_edge_set = []

  while edges.present?
    edge = edges.shift
    if detect_cycle(edge, acyclic_edges)
      feedback_edge_set << edge
    else
      acyclic_edges << edge
    end
  end

  feedback_edge_set
end
construct_graph!(nodes) click to toggle source

Given array of InventoryCollection objects as nodes, we construct a graph with nodes and edges

@param nodes [Array<InventoryRefresh::InventoryCollection>] List of Inventory collection nodes @return [InventoryRefresh::Graph] Constructed graph

# File lib/inventory_refresh/graph.rb, line 51
def construct_graph!(nodes)
  self.nodes = nodes
  self.edges, self.fixed_edges = build_edges(nodes)
  self
end
detect_cycle(edge, acyclic_edges, escalation = nil) click to toggle source

Detects a cycle. Based on escalation returns true or raises exception if there is a cycle

@param edge [Array(InventoryRefresh::InventoryCollection, InventoryRefresh::InventoryCollection)] Edge we are

inspecting for cycle

@param acyclic_edges [Array<Array>] Starting with fixed edges that can't have cycle, these are edges without cycle @param escalation [Symbol] If :exception, this method throws exception when it finds a cycle @return [Boolean, Exception] Based on escalation returns true or raises exception if there is a cycle

# File lib/inventory_refresh/graph.rb, line 97
def detect_cycle(edge, acyclic_edges, escalation = nil)
  # Test if adding edge creates a cycle, ew will traverse the graph from edge Node, through all it's
  # dependencies
  starting_node = edge.second
  edges         = [edge] + acyclic_edges
  traverse_dependecies([], starting_node, starting_node, edges, node_edges(edges, starting_node), escalation)
end
friendly_unique_node_names() click to toggle source

Returns Hash of {node => name}, appending numbers if needed to make unique, quoted if needed. Used for the GraphViz format

@return [Hash] Hash of {node => name}

# File lib/inventory_refresh/graph.rb, line 144
def friendly_unique_node_names
  node_names = {}
  # Try to use shorter .name method that InventoryCollection has.
  nodes.group_by { |n| n.respond_to?(:name) ? n.name.to_s : n.to_s }.each do |base_name, ns|
    ns.each_with_index do |n, i|
      name = ns.size == 1 ? base_name : "#{base_name}_#{i}"
      name = '"' + name.gsub(/["\\]/) { |c| "\\" + c } + '"' unless name =~ /^[A-Za-z0-9_]+$/
      node_names[n] = name
    end
  end
  node_names
end
node_edges(edges, node) click to toggle source

Returns dependencies of the node, i.e. nodes that are connected by edge

@param edges [Array<Array>] All graph edges @param node [InventoryRefresh::InventoryCollection] Node we are inspecting @return [Array<InventoryRefresh::InventoryCollection>] Nodes that are connected to the inspected node

# File lib/inventory_refresh/graph.rb, line 136
def node_edges(edges, node)
  edges.select { |e| e.second == node }
end
traverse_dependecies(traversed_nodes, starting_node, current_node, edges, dependencies, escalation) click to toggle source

Recursive method for traversing dependencies and finding a cycle

@param traversed_nodes [Array<InventoryRefresh::InventoryCollection> Already traversed nodes @param starting_node [InventoryRefresh::InventoryCollection] Node we've started the traversal on @param current_node [InventoryRefresh::InventoryCollection] Node we are currently on @param edges [Array<Array>] All graph edges @param dependencies [Array<InventoryRefresh::InventoryCollection> Dependencies of the current node @param escalation [Symbol] If :exception, this method throws exception when it finds a cycle @return [Boolean, Exception] Based on escalation returns true or raises exception if there is a cycle

# File lib/inventory_refresh/graph.rb, line 114
def traverse_dependecies(traversed_nodes, starting_node, current_node, edges, dependencies, escalation)
  dependencies.each do |node_edge|
    node = node_edge.first
    traversed_nodes << node
    if traversed_nodes.include?(starting_node)
      if escalation == :exception
        raise "Cycle from #{current_node} to #{node}, starting from #{starting_node} passing #{traversed_nodes}"
      else
        return true
      end
    end
    return true if traverse_dependecies(traversed_nodes, starting_node, node, edges, node_edges(edges, node), escalation)
  end

  false
end