class FpGrowth::FpTree::FpTree

Attributes

heads[R]
root[R]
supports[R]
threshold[R]

Public Class Methods

build(transactions, threshold=1) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 19
def self.build(transactions, threshold=1)
  Builder.build(transactions, threshold)
end
new(supports={}, threshold=1, root=Node.new()) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 31
def initialize(supports={}, threshold=1, root=Node.new())
  @root = root
  @heads = Hash.new nil
  @supports = supports
  #initialiser les clés
  for k in @supports.keys
    @heads[k]=nil
  end
  @threshold=threshold
end

Public Instance Methods

append_node(cursor_tree, node) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 110
def append_node(cursor_tree, node)
  cursor_tree.children << node
  node.parent = cursor_tree
  sort_children_by_support(cursor_tree.children)
  left = find_lateral_leaf_for_item(node.item)
  if left == nil then
    @heads[node.item] = node
  else
    left.lateral = node
  end
end
clone() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 202
def clone
  clone = FpTree.new(@supports, @threshold, @root.clone_deep)
  clone.link_down()
  return clone
end
combinations() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 185
def combinations
  raise "Tree contains multiple paths" unless single_path?
  array = []
  item = @root.children.first
  while item != nil
    array << item
    item = item.children.first
  end
  yss = 1.upto(array.size).flat_map do |n|
    array.combination(n).to_a
  end
end
cut_branch(node) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 122
def cut_branch(node)
  node.children.each { |child| cut_branch(child) }
  remove(node)
end
empty?() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 198
def empty?
  return @heads.empty?
end
find_lateral_leaf_for_item(item) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 53
def find_lateral_leaf_for_item(item)
  cursor = heads[item]
  while cursor != nil and cursor.lateral != nil do
    cursor = cursor.lateral
  end
  return cursor
end
graphviz(fancy_name=nil) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 61
def graphviz(fancy_name=nil)
  g = GraphViz.new(:G, :type => :digraph)
  nodonode = {}
  nodonode[self.root]=g.add_nodes(self.root.to_s, :label => "nil")

  for row in self.heads.values
    node=row
    while node != nil
      nodonode[node]= g.add_nodes(node.to_s, :label => node.item.to_s + " : " + node.support.to_s)
      node = node.lateral
    end
  end

  for child in self.root.children
    g.add_edges(nodonode[self.root], nodonode[child])
  end

  for row in self.heads.values
    node=row
    while node != nil
      for child in node.children
        g.add_edges(nodonode[node], nodonode[child]) if nodonode[child]
      end
      node = node.lateral
    end
  end


  for row in self.heads.values
    node=row
    while node != nil
      g.add_edges(nodonode[node], nodonode[node.lateral], :style => :dashed, :color=> :green, :constraint => :false) if node.lateral
      g.add_edges(nodonode[node], nodonode[node.parent], :style => :dashed, :color=> :red, :constraint => :false) if node.parent
      node = node.lateral
    end
  end

  g.output(:png => "./graphs/#{fancy_name}-#{Etc.getlogin}-#{items_count}-items-#{Time.now.to_s.gsub(" ", "-")}.png")

end
has_lateral_cycle?() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 254
def has_lateral_cycle?
  i = 0
  while i < @heads.keys.size
    key = @heads.keys[i]
    cursor = @heads[key]
    stack = []
    flag = false
    j=0
    while cursor != nil and not flag
      flag = true if stack.include?(cursor.object_id)
      stack.push(cursor.object_id)
      cursor = cursor.lateral
      j += 1
      #puts "#{i}/#{@heads.keys.size} - #{j}"
    end
    return key if flag
    i += 1
  end
  return false
end
header_table() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 275
def header_table
  unless @header_table
    @header_table = HeaderTable.new()
    for row in @heads.keys
      node = @heads[row]
      while node != nil
        @header_table << [node.item, node.support, node]
        node = node.lateral
      end
    end
    return @header_table
  end
end
item_order_lookup() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 42
def item_order_lookup
  unless @lookup
    @lookup = {}
    @supports.keys.each_with_index do |item, index|
      @lookup[item] = index
    end
  end
  return @lookup

end
items_count() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 165
def items_count
  sum=0
  for val in supports.values
    sum+=val
  end
  return sum

end
lateral_sum() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 229
def lateral_sum
  sum=0
  for cursor in @heads.values
    while cursor != nil
      sum+=cursor.support
      cursor = cursor.lateral
    end

  end
  return sum
end
max_width() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 241
def max_width
  max_width=0
  for cursor in @heads.values
    width=0
    while cursor != nil
      width+=1
      cursor = cursor.lateral
    end
    max_width = width if max_width < width
  end
  return max_width
end
remove(node) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 148
def remove(node)
  # Remove from lateral linked list
  remove_from_lateral(node)

  # attach childrens
  node.parent.children += node.children
  node.children.each { |x| x.parent = node.parent }

  # Remove from parents
  node.parent.children.delete(node)

  # Remove from support
  @supports[node.item] -= node.support if @supports[node.item]


end
remove_from_lateral(node, verbose=false) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 127
def remove_from_lateral(node, verbose=false)
  if @heads[node.item].equal?(node)
    if node.lateral
      @heads[node.item] = node.lateral
    else
      @heads.delete(node.item)
    end
  else
    puts "node #{node.to_s}" if verbose
    puts "pas head" if verbose
    left = @heads[node.item]
    while left != nil and not left.equal? node and not left.lateral.equal? node
      left = left.lateral
    end
    puts "left found #{left.lateral}" if verbose
    left.lateral = node.lateral if left
    puts "left found #{left.lateral}" if verbose
  end
  node.lateral=nil
end
single_path?() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 174
def single_path?
  is = true
  cursor = @root
  while is and cursor != nil
    is = false if cursor.children.size > 1
    cursor = cursor.children.first
  end

  return is
end
size(subtree=@root) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 217
def size(subtree=@root)
  sum = 1
  subtree.children.each { |child| sum+= size(child) }
  return sum
end
sort_children_by_support(nodes) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 102
def sort_children_by_support(nodes)
  lookup = item_order_lookup

  nodes.sort_by! do |node|
    lookup.fetch(node.item, lookup.size + 1)
  end
end
sum() click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 223
def sum
  sum = 0
  @supports.each { |key, value| sum+=value}
  return sum
end
to_bonzai(hardness=20) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 23
def to_bonzai(hardness=20)
  return BonzaiSecateur.new(self, hardness).execute()
end
to_bonzai!(hardness=20) click to toggle source
# File lib/fpgrowth/fp_tree.rb, line 27
def to_bonzai!(hardness=20)
  return BonzaiSecateur.new(self, hardness).execute!()
end