Class: Nanoc::Core::DirectedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/nanoc/core/directed_graph.rb

Overview

Represents a directed graph. It is used by the dependency tracker for storing and querying dependencies between items.

Examples:

Creating and using a directed graph


# Create a graph with three vertices
graph = Nanoc::Core::DirectedGraph.new(%w( a b c d e f g ))

# Add edges
graph.add_edge('a', 'b')
graph.add_edge('b', 'c')
graph.add_edge('b', 'f')
graph.add_edge('b', 'g')
graph.add_edge('c', 'd')
graph.add_edge('d', 'e')

# Get (direct) predecessors
graph.direct_predecessors_of('b').sort
  # => %w( a )
graph.predecessors_of('e').sort
  # => %w( a b c d )

# Modify edges
graph.delete_edges_to('c')

# Get (direct) predecessors again
graph.direct_predecessors_of('e').sort
  # => %w( d )
graph.predecessors_of('e').sort
  # => %w( c d )

Constant Summary collapse

EMPTY_SET = 
Set.new.freeze

Creating a graph collapse

Modifying the graph collapse

Querying the graph collapse

Constructor Details

#initialize(vertices) ⇒ DirectedGraph

Creates a new directed graph with the given vertices.



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/nanoc/core/directed_graph.rb', line 41

def initialize(vertices)
  @vertices = {}
  @next_vertex_idx = 0
  vertices.each do |v|
    @vertices[v] = @next_vertex_idx
    @next_vertex_idx += 1
  end

  @to_graph = {}
  @from_graph = {}

  @edge_props = {}

  invalidate_caches
end

Instance Method Details

#add_edge(from, to, props: nil) ⇒ void

This method returns an undefined value.

Adds an edge from the first vertex to the second vertex.

Parameters:

  • from —

    Vertex where the edge should start

  • to —

    Vertex where the edge should end



81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/nanoc/core/directed_graph.rb', line 81

def add_edge(from, to, props: nil)
  add_vertex(from)
  add_vertex(to)

  @to_graph[to] ||= Set.new
  @to_graph[to] << from

  @from_graph[from] ||= Set.new
  @from_graph[from] << to

  if props
    @edge_props[[from, to]] = props
  end

  invalidate_caches
end

#add_vertex(vertex) ⇒ void

This method returns an undefined value.

Adds the given vertex to the graph.

Parameters:

  • vertex —

    The vertex to add to the graph



103
104
105
106
107
108
 
# File 'lib/nanoc/core/directed_graph.rb', line 103

def add_vertex(vertex)
  return if @vertices.key?(vertex)

  @vertices[vertex] = @next_vertex_idx
  @next_vertex_idx += 1
end

#delete_edges_to(to) ⇒ void

This method returns an undefined value.

Deletes all edges going to the given vertex.

Parameters:

  • to —

    Vertex to which all edges should be removed



115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/nanoc/core/directed_graph.rb', line 115

def delete_edges_to(to)
  return if @to_graph[to].nil?

  @to_graph[to].each do |from|
    @edge_props.delete([from, to])
    @from_graph.delete(from)
  end
  @to_graph.delete(to)

  invalidate_caches
end

#direct_predecessors_of(to) ⇒ Array

Returns the direct predecessors of the given vertex, i.e. the vertices x where there is an edge from x to the given vertex y.

Parameters:

  • to —

    The vertex of which the predecessors should be calculated

Returns:

  • (Array) —

    Direct predecessors of the given vertex



135
136
137
 
# File 'lib/nanoc/core/directed_graph.rb', line 135

def direct_predecessors_of(to)
  @to_graph.fetch(to, EMPTY_SET)
end

#direct_successors_of(from) ⇒ Object 



139
140
141
 
# File 'lib/nanoc/core/directed_graph.rb', line 139

def direct_successors_of(from)
  @from_graph.fetch(from, EMPTY_SET)
end

#edges ⇒ Array

Returns an array of tuples representing the edges. The result of this method may take a while to compute and should be cached if possible.

Returns:

  • (Array) —

    The list of all edges in this graph.



167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/nanoc/core/directed_graph.rb', line 167

def edges
  result = []
  @vertices.each_pair do |v2, i2|
    direct_predecessors_of(v2)
      .map { |v1| [@vertices[v1], v1] }
      .each do |i1, v1|
        result << [i1, i2, @edge_props[[v1, v2]]]
      end
  end
  result
end

#inspect ⇒ Object 



57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/nanoc/core/directed_graph.rb', line 57

def inspect
  s = []

  @vertices.each_pair do |v2, _|
    direct_predecessors_of(v2).each do |v1|
      s << [
        "#{v1.inspect} -> #{v2.inspect} " \
        "props=#{@edge_props[[v1, v2]].inspect}",
      ]
    end
  end

  "#{self.class}(#{s.join(', ')})"
end

#predecessors_of(to) ⇒ Array

Returns the predecessors of the given vertex, i.e. the vertices x for which there is a path from x to the given vertex y.

Parameters:

  • to —

    The vertex of which the predecessors should be calculated

Returns:

  • (Array) —

    Predecessors of the given vertex



149
150
151
152
 
# File 'lib/nanoc/core/directed_graph.rb', line 149

def predecessors_of(to)
  @predecessors[to] ||=
    recursively_find_vertices(to, :direct_predecessors_of)
end

#props_for(from, to) ⇒ Object 



154
155
156
 
# File 'lib/nanoc/core/directed_graph.rb', line 154

def props_for(from, to)
  @edge_props[[from, to]]
end

#vertices ⇒ Array

Returns The list of all vertices in this graph.

Returns:

  • (Array) —

    The list of all vertices in this graph.



159
160
161
 
# File 'lib/nanoc/core/directed_graph.rb', line 159

def vertices
  @vertices.keys.sort_by { |v| @vertices[v] }
end