Class: InventoryRefresh::InventoryCollection::Graph

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

Instance Attribute Summary

Attributes inherited from Graph

#edges, #fixed_edges, #nodes

Instance Method Summary collapse

Methods inherited from Graph

#to_graphviz

Constructor Details

#initialize(nodes) ⇒ Graph 



5
6
7
8
9
 
# File 'lib/inventory_refresh/inventory_collection/graph.rb', line 5

def initialize(nodes)
  super(nodes)

  assert_inventory_collections(nodes)
end

Instance Method Details

#build_directed_acyclic_graph! ⇒ InventoryRefresh::InventoryCollection::Graph

Turns the graph into DAG (Directed Acyclic Graph)



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/inventory_refresh/inventory_collection/graph.rb', line 14

def build_directed_acyclic_graph!
  ################################################################################################################
  ## Description of an algorithm for building DAG
  ################################################################################################################
  # Terms:
  ##############
  # Fixed Edges - Are edges that cannot be removed from Graph, in our case these are edges caused by attributes
  #               that has to be present before saving the record. These are attributes that are part of the
  #               record identity (unique index of the DB record) and attributes validated for presence.
  # Feedback Edge Set - Is a set of edges that are causing a cycle in the graph
  # DAG - Directed Acyclic Graph
  #
  # Alghoritm:
  ##############
  # Building a Feedback Edge Set:
  # We will be building DAG from a Graph containing cycles, the algorithm is building a Feedback Edge Set by
  # adding edges to a DAG made from Fixed Edges, while checking if by adding a new edge we haven't created
  # a cycle in the graph.
  # Converting original graph to DAG:
  # Using the Feedback Edge Set, we remove the attributes causing cycles from the original graph. This way, we
  # get a DAG, but the DAG is missing attributes.
  # Using the Feedback Edge Set we create new Nodes, containing only removed attributes in a step before. These
  # nodes will be attached to Graph according to their dependencies. By saving these nodes, we will add the
  # missing relations.
  ################################################################################################################

  # Assert that Fixed edges do not have a cycle, we cannot move with fixed edges, so exception is thrown here
  assert_graph!(fixed_edges)

  # Collect Feedback Edge (Arc) Set
  feedback_edge_set = build_feedback_edge_set(edges, fixed_edges)

  # We will build a DAG using the Feedback Edge (Arc) Set. All edges from this set has to be removed, and the
  # edges are transferred to newly created nodes.
  convert_to_dag!(nodes, feedback_edge_set)

  # And assert again we've really built a DAG
  # TODO(lsmola) And if the result causes a cycle, we should repeat the build_dag method, with a max
  # depth 10. We should throw a warning maybe asking for simplifying the interconnections in the models.
  assert_graph!(edges)

  self
end