Module: Dagnabit::Vertex::Connectivity

Includes:
Settings
Defined in:
lib/dagnabit/vertex/connectivity.rb

Overview

Methods for checking connectivity between vertices.

This module is meant to be used by ActiveRecord::Base subclasses.

Instance Attribute Summary

Attributes included from Settings

#edge_model_name

Instance Method Summary collapse

Methods included from Settings

#connected_by, #edge_model, #edge_table, #inherited

Instance Method Details

#ancestors_of(*vertices) ⇒ Array<ActiveRecord::Base>

Find all ancestors of the given vertices.

The result is the set union of all ancestors of the vertices in vertices. The ordering of the result is unspecified.



52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/dagnabit/vertex/connectivity.rb', line 52

def ancestors_of(*vertices)
  ids = vertices.map(&:id)

  find_by_sql([%Q{
    WITH RECURSIVE ancestors(id) AS (
      SELECT #{edge_table}.parent_id FROM #{table_name} INNER JOIN #{edge_table} ON #{edge_table}.child_id = #{table_name}.id WHERE #{table_name}.id IN (?)
      UNION
      SELECT #{edge_table}.parent_id FROM ancestors INNER JOIN #{edge_table} ON #{edge_table}.child_id = ancestors.id
    )
    SELECT * FROM #{table_name} WHERE #{table_name}.id IN (SELECT id FROM ancestors)
  }, ids])
end

#children_of(*vertices) ⇒ Array<ActiveRecord::Base>

Finds all immediate children of vertices.

The result is the set union of all immediate children of the vertices in vertices. The ordering of the result is unspecified.



95
96
97
98
99
100
101
102
103
104
105
106
107
 
# File 'lib/dagnabit/vertex/connectivity.rb', line 95

def children_of(*vertices)
  ids = vertices.map(&:id)

  find_by_sql([%Q{
    SELECT
      *
    FROM
      #{table_name}
    WHERE
      #{table_name}.id IN
        (SELECT child_id FROM #{edge_table} WHERE parent_id IN (?))
  }, ids])
end

#descendants_of(*vertices) ⇒ Array<ActiveRecord::Base>

Find all descendants of the given vertices.

The result is the set union of all descendants of the vertices in vertices. The ordering of the result is unspecified.



117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/dagnabit/vertex/connectivity.rb', line 117

def descendants_of(*vertices)
  ids = vertices.map(&:id)

  find_by_sql([%Q{
    WITH RECURSIVE descendants(id) AS (
      SELECT #{edge_table}.child_id FROM #{table_name} INNER JOIN #{edge_table} ON #{edge_table}.parent_id = #{table_name}.id WHERE #{table_name}.id IN (?)
      UNION
      SELECT #{edge_table}.child_id FROM descendants INNER JOIN #{edge_table} ON #{edge_table}.parent_id = descendants.id
    )
    SELECT * FROM #{table_name} WHERE #{table_name}.id IN (SELECT id FROM descendants)
  }, ids])
end

#parents_of(*vertices) ⇒ Array<ActiveRecord::Base>

Finds all immediate parents of vertices.

The result is the set union of all immediate parents of the vertices in vertices. The ordering of the result is unspecified.



73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/dagnabit/vertex/connectivity.rb', line 73

def parents_of(*vertices)
  ids = vertices.map(&:id)

  find_by_sql([%Q{
    SELECT
      *
    FROM
      #{table_name}
    WHERE
      #{table_name}.id IN
        (SELECT parent_id FROM #{edge_table} WHERE child_id IN (?))
  }, ids])
end

#roots_of(*vertices) ⇒ Array<ActiveRecord::Base>

Finds all source vertices of the given vertices. A source vertex is a vertex that has an indegree of zero.

The result is the set union of all source vertices of the vertices in vertices. The ordering of the result is unspecified.



20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/dagnabit/vertex/connectivity.rb', line 20

def roots_of(*vertices)
  ids = vertices.map(&:id)

  find_by_sql([%Q{
    WITH RECURSIVE roots(id) AS (
      SELECT #{edge_table}.parent_id FROM #{table_name} INNER JOIN #{edge_table} ON #{edge_table}.child_id = #{table_name}.id WHERE #{table_name}.id IN (?)
      UNION
      SELECT #{edge_table}.parent_id FROM roots INNER JOIN #{edge_table} ON #{edge_table}.child_id = roots.id
    )
    SELECT
      *
    FROM
      #{table_name}
    WHERE
      #{table_name}.id IN (SELECT
                            roots.id
                           FROM
                            roots
                            LEFT JOIN
                            #{edge_table} ON roots.id = #{edge_table}.child_id
                           WHERE #{edge_table}.child_id IS NULL)
  }, ids])
end