Module: Tree::Utils::TreeMetricsHandler

Included in:
TreeNode
Defined in:
lib/tree/utils/metrics_methods.rb

Overview

Provides utility functions to measure various tree metrics.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Attribute Details

#breadth ⇒ Integer (readonly)

Breadth of the tree at this node's level. A single node without siblings has a breadth of 1.

Breadth is defined to be:

Breadth

Number of sibling nodes to this node + 1 (this node itself),

i.e., the number of children the parent of this node has.

Returns:

  • (Integer) —

    breadth of the node's level.



149
150
151
 
# File 'lib/tree/utils/metrics_methods.rb', line 149

def breadth
  is_root? ? 1 : parent.children.size
end

#depth ⇒ Integer (readonly)

Deprecated.

This method returns an incorrect value. Use the

Depth of the tree from this node. A single leaf node has a depth of 1.

This method is DEPRECATED and may be removed in the subsequent releases. Note that the value returned by this method is actually the:

height + 1 of the node, NOT the depth.

For correct and conventional behavior, please use #node_depth and #node_height methods instead.

#node_depth method instead.

Returns:

  • (Integer) —

    depth of the node.

See Also:



131
132
133
134
135
136
137
138
 
# File 'lib/tree/utils/metrics_methods.rb', line 131

def depth
  warn StructuredWarnings::DeprecatedMethodWarning,
       'This method is deprecated.  '\
       'Please use node_depth() or node_height() instead (bug # 22535)'

  return 1 if is_leaf?
  1 + @children.collect { |child| child.depth }.max
end

#in_degree ⇒ Integer (readonly)

The incoming edge-count of this node.

In-degree is defined as:

In-degree

Number of edges arriving at the node (0 for root, 1 for

all other nodes)

  • In-degree = 0 for a root or orphaned node

  • In-degree = 1 for a node which has a parent

Returns:

  • (Integer) —

    The in-degree of this node.



164
165
166
 
# File 'lib/tree/utils/metrics_methods.rb', line 164

def in_degree
  is_root? ? 0 : 1
end

#length ⇒ Integer (readonly)

Deprecated.

This method name is ambiguous and may be removed. Use

Convenience synonym for #size.

#size instead.

Returns:

  • (Integer) —

    The total number of nodes in this (sub)tree.

See Also:



70
71
72
 
# File 'lib/tree/utils/metrics_methods.rb', line 70

def length
  self.size
end

#level ⇒ Object (readonly)

Alias for #node_depth

See Also:



110
111
112
 
# File 'lib/tree/utils/metrics_methods.rb', line 110

def level
  node_depth
end

#node_depth ⇒ Integer (readonly)

Depth of this node in its tree. Depth of a node is defined as:

Depth

Length of the node's path to its root. Depth of a root node is

zero.

Note that the deprecated method #depth was incorrectly computing this value. Please replace all calls to the old method with #node_depth instead.

#level is an alias for this method.

Returns:

  • (Integer) —

    Depth of this node.



101
102
103
104
 
# File 'lib/tree/utils/metrics_methods.rb', line 101

def node_depth
  return 0 if is_root?
  1 + parent.node_depth
end

#node_height ⇒ Integer (readonly)

Height of the (sub)tree from this node. Height of a node is defined as:

Height

Length of the longest downward path to a leaf from the node.

  • Height from a root node is height of the entire tree.

  • The height of a leaf node is zero.

Returns:

  • (Integer) —

    Height of the node.



83
84
85
86
 
# File 'lib/tree/utils/metrics_methods.rb', line 83

def node_height
  return 0 if is_leaf?
  1 + @children.collect { |child| child.node_height }.max
end

#out_degree ⇒ Integer (readonly)

The outgoing edge-count of this node.

Out-degree is defined as:

Out-degree

Number of edges leaving the node (zero for leafs)

Returns:

  • (Integer) —

    The out-degree of this node.



175
176
177
 
# File 'lib/tree/utils/metrics_methods.rb', line 175

def out_degree
  is_leaf? ? 0 : children.size
end

#size ⇒ Integer (readonly)

Total number of nodes in this (sub)tree, including this node.

Size of the tree is defined as:

Size

Total number nodes in the subtree including this node.

Returns:

  • (Integer) —

    Total number of nodes in this (sub)tree.



58
59
60
 
# File 'lib/tree/utils/metrics_methods.rb', line 58

def size
  inject(0) {|sum, node| sum + 1 if node}
end

Class Method Details

.included(base) ⇒ Object

noinspection RubyUnusedLocalVariable



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/tree/utils/metrics_methods.rb', line 46

def self.included(base)

  # @!group Metrics and Measures

  # @!attribute [r] size
  # Total number of nodes in this (sub)tree, including this node.
  #
  # Size of the tree is defined as:
  #
  # Size:: Total number nodes in the subtree including this node.
  #
  # @return [Integer] Total number of nodes in this (sub)tree.
  def size
    inject(0) {|sum, node| sum + 1 if node}
  end

  # @!attribute [r] length
  # Convenience synonym for {#size}.
  #
  # @deprecated This method name is ambiguous and may be removed. Use
  # {#size} instead.
  #
  # @return [Integer] The total number of nodes in this (sub)tree.
  # @see #size
  def length
    self.size
  end

  # @!attribute [r] node_height
  # Height of the (sub)tree from this node.  Height of a node is defined as:
  #
  # Height:: Length of the longest downward path to a leaf from the node.
  #
  # - Height from a root node is height of the entire tree.
  # - The height of a leaf node is zero.
  #
  # @return [Integer] Height of the node.
  def node_height
    return 0 if is_leaf?
    1 + @children.collect { |child| child.node_height }.max
  end

  # @!attribute [r] node_depth
  # Depth of this node in its tree.  Depth of a node is defined as:
  #
  # Depth:: Length of the node's path to its root. Depth of a root node is
  # zero.
  #
  # *Note* that the deprecated method {#depth} was incorrectly computing
  # this value. Please replace all calls to the old method with
  # {#node_depth} instead.
  #
  # {#level} is an alias for this method.
  #
  # @return [Integer] Depth of this node.
  def node_depth
    return 0 if is_root?
    1 + parent.node_depth
  end

  # @!attribute [r] level
  # Alias for {#node_depth}
  #
  # @see #node_depth
  def level
    node_depth
  end

  # @!attribute [r] depth
  # Depth of the tree from this node. A single leaf node has a depth of 1.
  #
  # This method is *DEPRECATED* and may be removed in the subsequent
  # releases. Note that the value returned by this method is actually the:
  #
  # _height_ + 1 of the node, *NOT* the _depth_.
  #
  # For correct and conventional behavior, please use {#node_depth} and
  # {#node_height} methods instead.
  #
  # @return [Integer] depth of the node.
  #
  # @deprecated This method returns an incorrect value. Use the
  # {#node_depth} method instead.
  #
  # @see #node_depth
  def depth
    warn StructuredWarnings::DeprecatedMethodWarning,
         'This method is deprecated.  '\
         'Please use node_depth() or node_height() instead (bug # 22535)'

    return 1 if is_leaf?
    1 + @children.collect { |child| child.depth }.max
  end

  # @!attribute [r] breadth
  # Breadth of the tree at this node's level.
  # A single node without siblings has a breadth of 1.
  #
  # Breadth is defined to be:
  # Breadth:: Number of sibling nodes to this node + 1 (this node itself),
  # i.e., the number of children the parent of this node has.
  #
  # @return [Integer] breadth of the node's level.
  def breadth
    is_root? ? 1 : parent.children.size
  end

  # @!attribute [r] in_degree
  # The incoming edge-count of this node.
  #
  # In-degree is defined as:
  # In-degree:: Number of edges arriving at the node (0 for root, 1 for
  # all other nodes)
  #
  # - In-degree = 0 for a root or orphaned node
  # - In-degree = 1 for a node which has a parent
  #
  # @return [Integer] The in-degree of this node.
  def in_degree
    is_root? ? 0 : 1
  end

  # @!attribute [r] out_degree
  # The outgoing edge-count of this node.
  #
  # Out-degree is defined as:
  # Out-degree:: Number of edges leaving the node (zero for leafs)
  #
  # @return [Integer] The out-degree of this node.
  def out_degree
    is_leaf? ? 0 : children.size
  end

  # @!endgroup
end