Class: KnowledgeBase

Inherits:
Object
  • Object
show all
Defined in:
lib/scout/network/knowledge_base.rb

Instance Method Summary collapse

Instance Method Details

#radial_expand(db, seeds, depth:, direction: :out, filter: nil) ⇒ Object

Outward k-hop expansion from seeds over a KB database db: database name (Symbol or String) seeds: Entity or Array of Entities/ids depth: Integer direction: :out, :in, :both filter: optional Proc taking an AssociationItem and returning true/false

Returns [visited_nodes, edges], where:

  • visited_nodes is an Array of identifiers (as returned by AssociationItem.source/target)

  • edges is an Array of AssociationItems traversed during the expansion



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
57
58
59
60
61
62
63
64
 
# File 'lib/scout/network/knowledge_base.rb', line 15

def radial_expand(db, seeds, depth:, direction: :out, filter: nil)
  current = Array(seeds).compact
  return [[], []] if current.empty?

  visited = Set.new(current)
  edges   = []

  1.upto(depth) do
    next_front = []

    current.each do |entity|
      step_edges = case direction
                   when :out
                     children(db, entity)
                   when :in
                     parents(db, entity)
                   when :both
                     children(db, entity) + parents(db, entity)
                   else
                     raise ArgumentError, "Unknown direction: #{direction.inspect}"
                   end

      step_edges.each do |item|
        next if filter && ! filter.call(item)

        s = item.source
        t = item.target

        edges << item

        targets = case direction
                  when :out then [t]
                  when :in  then [s]
                  when :both then [s, t]
                  end

        targets.each do |node|
          next if visited.include?(node)
          visited << node
          next_front << node
        end
      end
    end

    break if next_front.empty?
    current = next_front
  end

  [visited.to_a, edges.uniq]
end

#radial_expand_both(db, seeds, depth:, filter: nil) ⇒ Object 



133
134
135
 
# File 'lib/scout/network/knowledge_base.rb', line 133

def radial_expand_both(db, seeds, depth:, filter: nil)
  radial_expand(db, seeds, depth: depth, direction: :both, filter: filter)
end

#radial_expand_in(db, seeds, depth:, filter: nil) ⇒ Object 



129
130
131
 
# File 'lib/scout/network/knowledge_base.rb', line 129

def radial_expand_in(db, seeds, depth:, filter: nil)
  radial_expand(db, seeds, depth: depth, direction: :in, filter: filter)
end

#radial_expand_out(db, seeds, depth:, filter: nil) ⇒ Object

Directional convenience wrappers



125
126
127
 
# File 'lib/scout/network/knowledge_base.rb', line 125

def radial_expand_out(db, seeds, depth:, filter: nil)
  radial_expand(db, seeds, depth: depth, direction: :out, filter: filter)
end

#radial_layers(db, seeds, depth:, direction: :out, filter: nil) ⇒ Object

Return radial layers around seeds as an array of arrays of nodes, plus edges. layers are the seeds, layers nodes at distance 1, … up to depth or until no more nodes are reached.



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

def radial_layers(db, seeds, depth:, direction: :out, filter: nil)
  current = Array(seeds).compact
  return [[], []] if current.empty?

  layers  = []
  visited = Set.new(current)
  edges   = []

  layers << current.dup

  1.upto(depth) do
    next_front = []

    current.each do |entity|
      step_edges = case direction
                   when :out
                     children(db, entity)
                   when :in
                     parents(db, entity)
                   when :both
                     children(db, entity) + parents(db, entity)
                   else
                     raise ArgumentError, "Unknown direction: #{direction.inspect}"
                   end

      step_edges.each do |item|
        next if filter && ! filter.call(item)

        s = item.source
        t = item.target

        edges << item

        targets = case direction
                  when :out then [t]
                  when :in  then [s]
                  when :both then [s, t]
                  end

        targets.each do |node|
          next if visited.include?(node)
          visited << node
          next_front << node
        end
      end
    end

    break if next_front.empty?
    layers << next_front
    current = next_front
  end

  [layers, edges.uniq]
end

#subgraph_around(db, seeds, depth:, direction: :out, filter: nil) ⇒ Object

Convenience: only return the edges in a k-hop subgraph around seeds



138
139
140
141
 
# File 'lib/scout/network/knowledge_base.rb', line 138

def subgraph_around(db, seeds, depth:, direction: :out, filter: nil)
  _visited, edges = radial_expand(db, seeds, depth: depth, direction: direction, filter: filter)
  edges
end