Class: Dagnabit::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/dagnabit/graph.rb

Overview

This class is a representation of a directed graph. It deviates from the definition of a directed graph in a few ways; here’s a couple:

  • It represents the vertex and edge sets using data structures more akin to bags than sets.

  • It imposes restrictions on the form of vertices and edges; namely, they must be ActiveRecord::Base subclasses that extend Vertex::Connectivity.

Despite these flaws, it is hoped that Graph is still useful for performing queries on graphs built with dagnabit.

Graph is not compatible with RGL’s Graph concept. This is because Graph defines #vertices and #edges as accessors, whereas RGL provides implementations of #vertices and #edges in terms of methods called ‘each_vertex` and `each_edge`, respectively. Nevertheless, RGL compatibility would be nice to have, so it is a to-do item.

Graphs may be constructed from a set of source nodes with Graph.from_vertices.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Graph

Returns a new instance of Graph.



77
78
79
80
 
# File 'lib/dagnabit/graph.rb', line 77

def initialize
  self.vertices = []
  self.edges = []
end

Instance Attribute Details

#edge_model ⇒ Class

The vertex model used by this graph.

This must be defined before calling #load_descendants!.

Returns:

  • (Class) 


50
51
52
 
# File 'lib/dagnabit/graph.rb', line 50

def edge_model
  @edge_model
end

#edges ⇒ Array<ActiveRecord::Base>

The edges of this graph.

Returns:

  • (Array<ActiveRecord::Base>) 


34
35
36
 
# File 'lib/dagnabit/graph.rb', line 34

def edges
  @edges
end

#vertex_model ⇒ Class

The vertex model used by this graph.

This must be defined before calling #load_descendants!.

Returns:

  • (Class) 


42
43
44
 
# File 'lib/dagnabit/graph.rb', line 42

def vertex_model
  @vertex_model
end

#vertices ⇒ Array<ActiveRecord::Base>

The vertices of this graph.

Returns:

  • (Array<ActiveRecord::Base>) 


28
29
30
 
# File 'lib/dagnabit/graph.rb', line 28

def vertices
  @vertices
end

Class Method Details

.from_vertices(vertices, vertex_model, edge_model) ⇒ Graph

Given a set of ‘vertices`, builds a subgraph from those vertices and their descendants.

This method is intended to be used in the case where ‘vertices` contains only source vertices (vertices having indegree zero), but can be used with non-source vertices as well.

If your vertices may be one of many subclasses (i.e. you’re using single table inheritance in your vertices table), then you should use the base class for #vertex_model.

Parameters:

  • vertices (Array<ActiveRecord::Base>) —

    the vertices to start from

  • vertex_model (Class) —

    the model class used for representing vertices

  • edge_model (Class) —

    the model class used for representing edges

Returns:



68
69
70
71
72
73
74
75
 
# File 'lib/dagnabit/graph.rb', line 68

def self.from_vertices(vertices, vertex_model, edge_model)
  new.tap do |g|
    g.vertex_model = vertex_model
    g.edge_model = edge_model
    g.vertices = vertices
    g.load_descendants!
  end
end

Instance Method Details

#load_descendants! ⇒ Object

Loads all descendants of the vertices in #vertices.

#vertex_model and #edge_model must be set before calling this method. If either are not set, this method raises ‘RuntimeError`.

Vertices and edges that were present before a ‘load_descendants!` call will remain in #vertices and #edges, respectively.

Edge load behavior

Once vertices have been loaded, ‘load_descendants!` loads all edges that connect vertices in the working vertex set. It also eagerly loads `parent` and `child` associations on edges.

Raises:



100
101
102
103
104
105
 
# File 'lib/dagnabit/graph.rb', line 100

def load_descendants!
  raise 'vertex_model and edge_model must be set' unless vertex_model && edge_model

  self.vertices += vertex_model.descendants_of(*vertices)
  self.edges += edge_model.connecting(*vertices).scoped(:include => [:parent, :child])
end

#sinks ⇒ Array<vertex_model>

Returns the sink vertices in the graph. Sinks are not returned in any particular order.

If this method is run on a subgraph of a larger graph, then the source determination is done relative to the subgraph.

This method expects all vertices and edges to have been persisted, and will return incorrect results if there exist unpersisted vertices of edges in the graph.

Returns:



160
161
162
163
164
165
 
# File 'lib/dagnabit/graph.rb', line 160

def sinks
  ids = vertices.inject({}) { |r, v| r.update(v.id => v) }
  edge_source_ids = edges.inject({}) { |r, e| r.update(e.parent_id => true) }

  ids.reject { |k, _| edge_source_ids[k] }.map { |_, v| v }
end

#sources ⇒ Array<vertex_model>

Returns the source vertices in the graph. Sources are not returned in any particular order.

This method is implemented using a hash anti-join on vertex ID and edge child ID. If a vertex is a child of some edge, then it is rejected, and thus only vertices that are not children of any edge (viz. have indegree zero and are therefore sources) remain.

If this method is run on a subgraph of a larger graph, then the source determination is done relative to the subgraph. Consider the following graph:

a   b
 \ /
  c
  |
  d

When considering the vertex set ‘{ a, b, c, d }` and corresponding edge set, `c` is clearly not a source. However, in the subgraph `S`

S = ({c, d}, {(c, d)})

‘c` is a source, and if S were reified as a Dagnabit::Graph instance (using, for example, from_vertices), `[c]` would be the output of calling `sources` on that instance.

This method expects all vertices and edges to have been persisted, and will return incorrect results if there exist unpersisted vertices or edges in the graph. For this reason, it is advised that you ensure that all vertices and edges in a graph are saved before calling #sources.

Returns:



141
142
143
144
145
146
 
# File 'lib/dagnabit/graph.rb', line 141

def sources
  ids = vertices.inject({}) { |r, v| r.update(v.id => v) }
  children = edges.inject({}) { |r, e| r.update(e.child_id => true) }

  ids.reject { |k, _| children[k] }.map { |_, v| v }
end