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.

Parameters:

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

    a list of vertices

Returns:

  • (Array<ActiveRecord::Base>) —

    a list of ancestor vertices



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.

Parameters:

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

    a list of vertices

Returns:

  • (Array<ActiveRecord::Base>) —

    a list of child vertices



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.

Parameters:

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

    a list of vertices

Returns:

  • (Array<ActiveRecord::Base>) —

    a list of descendant vertices



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.

Parameters:

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

    a list of vertices

Returns:

  • (Array<ActiveRecord::Base>) —

    a list of parent vertices



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.

Parameters:

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

    a list of vertices

Returns:

  • (Array<ActiveRecord::Base>) —

    a list of source vertices



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