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

Returns a new instance of Graph.

Parameters:



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)

Returns:



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