Module: AssociationItem

Defined in:
lib/scout/network/entity.rb

Class Method Summary collapse

Class Method Details

.components(associations, undirected: true) ⇒ Object

Connected components from a list of AssociationItems. Returns an Array of Arrays of node identifiers.



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
 
# File 'lib/scout/network/entity.rb', line 109

def self.components(associations, undirected: true)
  inc = associations.respond_to?(:incidence) ? associations.incidence : AssociationItem.incidence(associations)

  adjacency = Hash.new { |h,k| h[k] = [] }
  nodes     = Set.new
  targets   = inc.fields

  inc.each do |src, row|
    Array(row).each_with_index do |val, i|
      next if val.nil?
      t = targets[i]
      adjacency[src] << t
      nodes << src << t
      adjacency[t] << src if undirected
    end
  end

  components = []
  visited    = Set.new

  nodes.each do |n|
    next if visited.include?(n)
    comp  = []
    queue = [n]
    visited << n
    until queue.empty?
      u = queue.shift
      comp << u
      adjacency[u].each do |v|
        next if visited.include?(v)
        visited << v
        queue << v
      end
    end
    components << comp
  end

  components
end

.degrees(associations, direction: :both) ⇒ Object

Degree per node from an AssociationItem list. direction: :out, :in, :both



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
 
# File 'lib/scout/network/entity.rb', line 151

def self.degrees(associations, direction: :both)
  inc = associations.respond_to?(:incidence) ? associations.incidence : AssociationItem.incidence(associations)
  deg = Hash.new(0)
  targets = inc.fields

  inc.each do |src, row|
    Array(row).each_with_index do |val, i|
      next if val.nil?
      t = targets[i]
      case direction
      when :out
        deg[src] += 1
      when :in
        deg[t] += 1
      when :both
        deg[src] += 1
        deg[t]   += 1
      else
        raise ArgumentError, "Unknown direction: #{direction.inspect}"
      end
    end
  end

  deg
end

.dijkstra(associations, start_node, end_node = nil, threshold = nil, max_steps = nil, &block) ⇒ Object

Dijkstra over a list of AssociationItems, using an optional block to compute edge weights.



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
 
# File 'lib/scout/network/entity.rb', line 50

def self.dijkstra(associations, start_node, end_node = nil, threshold = nil, max_steps = nil, &block)
  adjacency = {}

  associations.each do |m|
    s, t, _sep = m.split "~"
    next if s.nil? || t.nil? || s.strip.empty? || t.strip.empty?
    adjacency[s] ||= Set.new
    adjacency[s] << t 
    next unless m.undirected
    adjacency[t] ||= Set.new
    adjacency[t] << s  
  end

  return nil unless adjacency.include? start_node

  active   = PriorityQueue.new         
  distances = Hash.new { 1.0 / 0.0 } 
  parents   = Hash.new                 

  active[start_node] << 0
  best   = 1.0 / 0.0
  found  = false
  node_dist_cache = {}

  until active.empty?
    u        = active.priorities.first
    distance = active.shift
    distances[u] = distance
    path = Paths.extract_path(parents, start_node, u) if parents.key?(u)
    next if max_steps && path && path.length > max_steps 
    next unless adjacency.include?(u) && adjacency[u] && !adjacency[u].empty?
    adjacency[u].each do |v|
      node_dist = node_dist_cache[[u,v]] ||= (block_given? ? block.call(u,v) : 1)
      next if node_dist.nil? || (threshold && node_dist > threshold)
      d = distance + node_dist
      next unless d < distances[v] && d < best # we can't relax this one
      active[v] << d
      distances[v] = d
      parents[v] = u
      if String === end_node ? (end_node == v) : (end_node && end_node.include?(v))
        best = d 
        found = true
      end
    end    
  end

  return nil unless found

  if end_node
    end_node = (end_node & parents.keys).first unless String === end_node
    return nil unless parents.include? end_node
    Paths.extract_path(parents, start_node, end_node)
  else
    parents
  end
end

.neighborhood(associations, seeds, k) ⇒ Object

Neighborhood within k steps inside a fixed subgraph, using unweighted BFS over adjacency built from associations.



190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
 
# File 'lib/scout/network/entity.rb', line 190

def self.neighborhood(associations, seeds, k)
  inc = associations.respond_to?(:incidence) ? associations.incidence : AssociationItem.incidence(associations)
  adjacency = Hash.new { |h,k| h[k] = [] }
  targets   = inc.fields

  inc.each do |src, row|
    Array(row).each_with_index do |val, i|
      next if val.nil?
      t = targets[i]
      adjacency[src] << t
      adjacency[t] << src
    end
  end

  Paths.neighborhood(adjacency, seeds, k)
end

.subset_by_nodes(associations, nodes) ⇒ Object

Induced subgraph: keep only edges whose endpoints are in the given node set.



178
179
180
181
182
183
184
185
186
 
# File 'lib/scout/network/entity.rb', line 178

def self.subset_by_nodes(associations, nodes)
  node_set = nodes.to_set
  associations.select do |m|
    s = m.source rescue nil
    t = m.target rescue nil
    next false if s.nil? || t.nil?
    node_set.include?(s) && node_set.include?(t)
  end
end