Class: Nanoc::Int::DirectedGraph Private

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

Overview

This class is part of a private API. You should avoid using this class if possible, as it may be removed or be changed in the future.

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::Int::DirectedGraph.new(%w( a b c d ))

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

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

# Modify edges
graph.delete_edge('a', 'b')

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

Creating a graph collapse

Modifying the graph collapse

Querying the graph collapse

Constructor Details

#initialize(vertices) ⇒ DirectedGraph

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Creates a new directed graph with the given vertices.



35
36
37
38
39
40
41
42
43
44
45
46
47
 
# File 'lib/nanoc/base/directed_graph.rb', line 35

def initialize(vertices)
  @vertices = {}
  vertices.each_with_index do |v, i|
    @vertices[v] = i
  end

  @from_graph = {}
  @to_graph   = {}

  @roots = Set.new(@vertices.keys)

  invalidate_caches
end

Instance Method Details

#add_edge(from, to) ⇒ void

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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



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

def add_edge(from, to)
  add_vertex(from)
  add_vertex(to)

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

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

  @roots.delete(to)

  invalidate_caches
end

#add_vertex(v) ⇒ void

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

This method returns an undefined value.

Adds the given vertex to the graph.

Parameters:

  • v —

    The vertex to add to the graph

Since:

  • 3.2.0



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

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

  @vertices[v] = @vertices.size

  @roots << v
end

#delete_edge(from, to) ⇒ void

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

This method returns an undefined value.

Removes the edge from the first vertex to the second vertex. If the edge does not exist, nothing is done.

Parameters:

  • from —

    Start vertex of the edge

  • to —

    End vertex of the edge

Since:

  • 3.2.0



83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/nanoc/base/directed_graph.rb', line 83

def delete_edge(from, to)
  @from_graph[from] ||= Set.new
  @from_graph[from].delete(to)

  @to_graph[to] ||= Set.new
  @to_graph[to].delete(from)

  @roots.add(to) if @to_graph[to].empty?

  invalidate_caches
end

#delete_edges_from(from) ⇒ void

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

This method returns an undefined value.

Deletes all edges coming from the given vertex.

Parameters:

  • from —

    Vertex from which all edges should be removed

Since:

  • 3.2.0



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

def delete_edges_from(from)
  return if @from_graph[from].nil?

  @from_graph[from].each do |to|
    @to_graph[to].delete(from)
    @roots.add(to) if @to_graph[to].empty?
  end
  @from_graph.delete(from)
end

#delete_edges_to(to) ⇒ void

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

This method returns an undefined value.

Deletes all edges going to the given vertex.

Parameters:

  • to —

    Vertex to which all edges should be removed



132
133
134
135
136
137
138
139
140
 
# File 'lib/nanoc/base/directed_graph.rb', line 132

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

  @to_graph[to].each do |from|
    @from_graph[from].delete(to)
  end
  @to_graph.delete(to)
  @roots.add(to)
end

#delete_vertex(v) ⇒ void

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

This method returns an undefined value.

Removes the given vertex from the graph.

Parameters:

  • v —

    Vertex to remove from the graph

Since:

  • 3.2.0



149
150
151
152
153
154
155
 
# File 'lib/nanoc/base/directed_graph.rb', line 149

def delete_vertex(v)
  delete_edges_to(v)
  delete_edges_from(v)

  @vertices.delete(v)
  @roots.delete(v)
end

#direct_predecessors_of(to) ⇒ Array

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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



165
166
167
 
# File 'lib/nanoc/base/directed_graph.rb', line 165

def direct_predecessors_of(to)
  @to_graph[to].to_a
end

#direct_successors_of(from) ⇒ Array

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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

Parameters:

  • from —

    The vertex of which the successors should be calculated

Returns:

  • (Array) —

    Direct successors of the given vertex



175
176
177
 
# File 'lib/nanoc/base/directed_graph.rb', line 175

def direct_successors_of(from)
  @from_graph[from].to_a
end

#edges ⇒ Array

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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.



208
209
210
211
212
213
214
215
216
 
# File 'lib/nanoc/base/directed_graph.rb', line 208

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

#predecessors_of(to) ⇒ Array

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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



185
186
187
 
# File 'lib/nanoc/base/directed_graph.rb', line 185

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

#roots ⇒ Set

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns all root vertices, i.e. vertices where no edge points to.

Returns:

  • (Set) —

    The set of all root vertices in this graph.

Since:

  • 3.2.0



223
224
225
 
# File 'lib/nanoc/base/directed_graph.rb', line 223

def roots
  @roots
end

#successors_of(from) ⇒ Array

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

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

Parameters:

  • from —

    The vertex of which the successors should be calculated

Returns:

  • (Array) —

    Successors of the given vertex



195
196
197
 
# File 'lib/nanoc/base/directed_graph.rb', line 195

def successors_of(from)
  @successors[from] ||= recursively_find_vertices(from, :direct_successors_of)
end

#vertices ⇒ Array

This method is part of a private API. You should avoid using this method if possible, as it may be removed or be changed in the future.

Returns The list of all vertices in this graph.

Returns:

  • (Array) —

    The list of all vertices in this graph.



200
201
202
 
# File 'lib/nanoc/base/directed_graph.rb', line 200

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