Method: NoSE::QueryGraph::Graph#subgraphs

Defined in:
lib/nose/query_graph.rb

#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