Class: NoSE::QueryGraph::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/nose/query_graph.rb

Overview

A graph identifying entities and relationships involved in a query

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(nodes = [], *edges) ⇒ Graph

Returns a new instance of Graph.



77
78
79
80
81
82
83
84
 
# File 'lib/nose/query_graph.rb', line 77

def initialize(nodes = [], *edges)
  @nodes = Set.new
  @entities = Set.new
  nodes.each { |n| add_node n }
  @edges = {}

  edges.each { |edge| add_edge(*edge) }
end

Instance Attribute Details

#entities ⇒ Object (readonly)

Returns the value of attribute entities.



75
76
77
 
# File 'lib/nose/query_graph.rb', line 75

def entities
  @entities
end

#nodes ⇒ Object (readonly)

Returns the value of attribute nodes.



75
76
77
 
# File 'lib/nose/query_graph.rb', line 75

def nodes
  @nodes
end

Class Method Details

.from_path(path) ⇒ Graph

Construct a graph from a KeyPath

Returns:



323
324
325
326
327
328
329
330
331
332
333
334
335
336
 
# File 'lib/nose/query_graph.rb', line 323

def self.from_path(path)
  return Graph.new if path.empty?

  path = path.entries if path.is_a?(KeyPath)
  graph = Graph.new
  prev_node = graph.add_node path.first.parent
  path[1..-1].each do |key|
    next_node = graph.add_node key.entity
    graph.add_edge prev_node, next_node, key
    prev_node = next_node
  end

  graph
end

Instance Method Details

#==(other) ⇒ Object Also known as: eql?

Graphs are equal if they have the same nodes and edges



94
95
96
97
 
# File 'lib/nose/query_graph.rb', line 94

def ==(other)
  return false unless other.is_a? Graph
  @nodes == other.nodes && unique_edges == other.unique_edges
end

#add_edge(node1, node2, key) ⇒ void

This method returns an undefined value.

Add a new edge betwene two nodes in the graph



226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/nose/query_graph.rb', line 226

def add_edge(node1, node2, key)
  node1 = add_node node1
  node2 = add_node node2

  @edges[node1] = Set.new unless @edges.key? node1
  @edges[node1].add Edge.new(node1, node2, key)
  @edges[node2] = Set.new unless @edges.key? node2
  @edges[node2].add Edge.new(node2, node1, key.reverse)

  @unique_edges = nil
end

#add_node(node) ⇒ Node

Add a new node to the graph

Returns:

  • (Node) —

    the new node which was added



206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/nose/query_graph.rb', line 206

def add_node(node)
  if node.is_a? Entity
    existing = find_entity_node node
    if existing.nil?
      node = Node.new(node)
      @nodes.add node
      @entities.add node.entity
    else
      node = existing
    end
  elsif !@nodes.include? node
    @nodes.add node
    @entities.add node.entity
  end

  node
end

#dup ⇒ Graph

Duplicate graphs ensuring that edges are correctly copied

Returns:



118
119
120
121
122
123
124
125
126
127
128
129
 
# File 'lib/nose/query_graph.rb', line 118

def dup
  new_graph = super

  new_graph.instance_variable_set :@nodes, @nodes.dup
  new_edges = Hash[@edges.map do |k, v|
    [k, v.dup]
  end]
  new_graph.instance_variable_set :@edges, new_edges
  new_graph.instance_variable_set :@unique_edges, nil

  new_graph
end

#empty? ⇒ Boolean

Check if the graph is empty

Returns:

  • (Boolean) 


112
113
114
 
# File 'lib/nose/query_graph.rb', line 112

def empty?
  @nodes.empty?
end

#entity_node(entity) ⇒ Node

Find the node corresponding to a given entity in the graph

Returns:



171
172
173
 
# File 'lib/nose/query_graph.rb', line 171

def entity_node(entity)
  @nodes.find { |n| n.entity == entity }
end

#find_entity_node(entity) ⇒ Object

Find the node which corresponds to a given entity



200
201
202
 
# File 'lib/nose/query_graph.rb', line 200

def find_entity_node(entity)
  @nodes.find { |n| n.entity == entity }
end

#hash ⇒ Object 



100
101
102
 
# File 'lib/nose/query_graph.rb', line 100

def hash
  [@nodes, unique_edges.map(&:canonical_params).sort!].hash
end

#include_entity?(entity) ⇒ Boolean

Check if the graph includes the given entity

Returns:

  • (Boolean) 


177
178
179
 
# File 'lib/nose/query_graph.rb', line 177

def include_entity?(entity)
  !entity_node(entity).nil?
end

#inspect ⇒ Object

:nocov:



87
88
89
90
 
# File 'lib/nose/query_graph.rb', line 87

def inspect
  "Graph(nodes: #{@nodes.map(&:inspect).join(', ')}, " \
        "edges: #{@edges.inspect})"
end

#join_order(eq_fields) ⇒ Array<Entity>

Produce an array of entities in the desired join order

Returns:



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
 
# File 'lib/nose/query_graph.rb', line 133

def join_order(eq_fields)
  return [@nodes.first.entity] if @nodes.size == 1

  # Start with a leaf entity which has an equality predicate
  # and the lowest overall count of all such entities
  entities = @entities.dup
  leaf_entities = entities.select { |e| leaf_entity?(e) }
  join_order = [leaf_entities.select do |entity|
    eq_fields.map(&:parent).include?(entity)
  end.min_by(&:count)].compact
  join_order = [leaf_entities.min_by(&:count)] if join_order.empty?
  entities.delete join_order.first

  # Keep going until we have joined all entities
  until entities.empty?
    # Try to continue from the last entity
    next_entities = edges_for_entity(join_order.last).map do |edge|
      edge.to.entity
    end.to_set

    # Otherwise look for a new branch from the existing entities
    if (next_entities & entities).empty?
      next_entities = join_order.reduce(Set.new) do |edges, entity|
        edges.union(edges_for_entity(entity))
      end.map { |edge| edge.to.entity }.to_set
    end

    # Pick the entity with the smallest count, remove it, and keep going
    next_entity = (next_entities & entities).min_by(&:count)
    join_order << next_entity
    entities.delete next_entity
  end

  join_order
end

#keys_from_entity(entity) ⇒ Array<Fields::ForeignKeyField>

Produce the keys for all edges leaving the given entity

Returns:



428
429
430
 
# File 'lib/nose/query_graph.rb', line 428

def keys_from_entity(entity)
  edges_for_entity(entity).map(&:key)
end

#leaf_entity?(entity) ⇒ Boolean

Check if this entity is a leaf in the graph (at most one edge)

Returns:

  • (Boolean) 


183
184
185
186
187
 
# File 'lib/nose/query_graph.rb', line 183

def leaf_entity?(entity)
  node = entity_node(entity)
  return false if node.nil?
  !@edges.key?(node) || @edges[node].size <= 1
end

#longest_path ⇒ KeyPath

Produce a path through the graph of maximum length

Returns:



370
371
372
373
374
375
376
377
378
379
380
381
382
383
 
# File 'lib/nose/query_graph.rb', line 370

def longest_path
  return KeyPath.new [@nodes.first.entity.id_field] if @nodes.size == 1

  longest_path = []
  @nodes.each do |node|
    next unless leaf_entity?(node.entity)

    longest_path = longest_path_visit node, Set.new([node]), [],
                                      longest_path
  end

  KeyPath.new [longest_path.first.from.entity.id_field] +
              longest_path.map(&:key)
end

#output(format, filename) ⇒ void

This method returns an undefined value.

Output an image of the query graph



387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
 
# File 'lib/nose/query_graph.rb', line 387

def output(format, filename)
  graph = GraphViz.new :G, type: :graph
  nodes = Hash[@nodes.map do |node|
    [node, graph.add_nodes(node.entity.name)]
  end]

  @edges.each do |_, edges|
    edges.each do |edge|
      graph.add_edges nodes[edge.from], nodes[edge.to],
                      label: edge.key.name
    end
  end

  graph.output(**{ format => filename })
end

#path_between(node1, node2) ⇒ KeyPath

Produce a path in the graph between two nodes

Returns:



191
192
193
194
195
196
197
 
# File 'lib/nose/query_graph.rb', line 191

def path_between(node1, node2)
  node1 = find_entity_node node1
  node2 = find_entity_node node2
  keys = path_between_visit [node1.entity.id_field], [node1], node2

  KeyPath.new keys
end

#prune(start) ⇒ void

This method returns an undefined value.

Prune nodes not reachable from a given starting node



240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
 
# File 'lib/nose/query_graph.rb', line 240

def prune(start)
  to_visit = [start]
  reachable = Set.new([start])

  # Determine which nodes are reachable
  until to_visit.empty?
    discovered = Set.new
    to_visit.each do |node|
      next unless @edges.key? node
      discovered += @edges[node].map(&:to).to_set
    end
    to_visit = discovered - reachable
    reachable += discovered
  end

  remove_nodes @nodes - reachable
end

#remove_nodes(nodes) ⇒ Object

Remove nodes (or entities) from the graph



259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
 
# File 'lib/nose/query_graph.rb', line 259

def remove_nodes(nodes)
  # Find all the nodes to be removed if needed
  nodes.map! { |n| n.is_a?(Node) ? n : find_entity_node(n) }

  # Remove any nodes and edges which are not reachable
  @edges.reject! { |node| nodes.include? node }
  @edges.each do |_, edges|
    edges.reject! do |edge|
      nodes.include?(edge.to) || nodes.include?(edge.from)
    end
  end
  @edges.reject! { |_, edges| edges.empty? }
  @nodes -= nodes.to_set
  @entities -= nodes.map(&:entity)

  @unique_edges = nil
end

#size ⇒ Integer

The total number of nodes in the graph

Returns:



106
107
108
 
# File 'lib/nose/query_graph.rb', line 106

def size
  @nodes.size
end

#split(entity, keep = false) ⇒ Object

Split this graph into multiple graphs at the given entity, optionally removing the corresponding node return [Array<Graph>]



406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
 
# File 'lib/nose/query_graph.rb', line 406

def split(entity, keep = false)
  # Simple case with one node
  return keep ? [dup] : [] if size == 1

  # Find the node corresponding to the entity to remove
  remove_node = @nodes.find { |n| n.entity == entity }

  # For each edge from this entity, build a new graph with
  # the entity removed and explore the different paths
  @edges[remove_node].map do |edge|
    new_graph = dup
    remove_nodes = (@edges[remove_node] - [edge]).map(&:to)
    remove_nodes << remove_node unless keep
    new_graph.remove_nodes remove_nodes
    new_graph.prune edge.to

    new_graph
  end
end

#subgraphs(recursive = true) ⇒ Set<Graph>

Produce an enumerator which yields all subgraphs of this graph

Returns:



291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
 
# File 'lib/nose/query_graph.rb', line 291

def subgraphs(recursive = true)
  # We have no subgraphs if there is only one node
  return [self] if @nodes.size == 1

  all_edges = unique_edges
  all_subgraphs = Set.new([self])
  all_edges.each do |remove_edge|
    # Construct new graphs from either side of the cut edge
    graph1 = Graph.new [remove_edge.from]
    graph2 = Graph.new [remove_edge.to]
    all_edges.each do |edge|
      next if edge == remove_edge

      graph1.add_edge edge.from, edge.to, edge.key
      graph2.add_edge edge.from, edge.to, edge.key
    end

    # Prune the graphs before yielding them and their subgraphs
    graph1.prune remove_edge.from
    all_subgraphs.add graph1
    all_subgraphs += graph1.subgraphs if recursive

    graph2.prune remove_edge.to
    all_subgraphs.add graph2
    all_subgraphs += graph2.subgraphs if recursive
  end

  all_subgraphs.to_set
end

#to_path(start_entity) ⇒ KeyPath

Convert this graph into a path if possible

Returns:

Raises:



341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
 
# File 'lib/nose/query_graph.rb', line 341

def to_path(start_entity)
  return KeyPath.new if @nodes.empty?

  start = @nodes.find { |n| n.entity == start_entity }

  fail InvalidPathException, 'Need start for path conversion' \
    if start.nil?
  keys = [start.entity.id_field]
  entities = Set.new [start.entity]

  edges = edges_for_entity start.entity
  until edges.empty?
    new_entities = edges.map { |e| e.to.entity }.to_set.delete_if do |n|
      entities.include?(n)
    end
    break if new_entities.empty?
    fail InvalidPathException, 'Graph cannot be converted to path' \
      if new_entities.size > 1
    edge = edges.find { |e| !entities.include? e.to.entity }
    keys << edge.key
    entities.add edge.to.entity
    edges = edges_for_entity edge.to.entity
  end

  KeyPath.new keys
end

#unique_edges ⇒ Object

Construct a list of all unique edges in the graph



279
280
281
282
283
284
285
286
287
 
# File 'lib/nose/query_graph.rb', line 279

def unique_edges
  # We memoize this calculation so check if it has already been computed
  return @unique_edges unless @unique_edges.nil?

  all_edges = @edges.values.reduce(&:union).to_a
  all_edges.uniq!(&:canonical_params)

  @unique_edges = all_edges.to_set
end