Class: Nanoc3::DirectedGraph

Inherits:
Object
  • Object
show all
Defined in:
lib/nanoc3/base/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 = 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.remove_edge('a', 'b')

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

Instance Attribute Summary collapse

Creating a graph collapse

Modifying the graph collapse

Querying the graph collapse

Deprecated methods collapse

Constructor Details

#initialize(vertices) ⇒ DirectedGraph

Creates a new directed graph with the given vertices.



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

def initialize(vertices)
  @vertices = Set.new(vertices)

  @from_graph = {}
  @to_graph   = {}

  @vertice_indexes = {}
  @vertices.each_with_index do |v, i|
    @vertice_indexes[v] = i
  end

  @roots = Set.new(@vertices)

  invalidate_caches
end

Instance Attribute Details

#vertices ⇒ Set (readonly)

The set of vertices in this graph.

Returns:

  • (Set) 


37
38
39
 
# File 'lib/nanoc3/base/directed_graph.rb', line 37

def vertices
  @vertices
end

Instance Method Details

#add_edge(from, to) ⇒ 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



67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
# File 'lib/nanoc3/base/directed_graph.rb', line 67

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 returns an undefined value.

Adds the given vertex to the graph.

Parameters:

  • v —

    The vertex to add to the graph

Since:

  • 3.2.0



111
112
113
114
115
116
117
118
 
# File 'lib/nanoc3/base/directed_graph.rb', line 111

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

  @vertices << v
  @vertice_indexes[v] = @vertices.size-1

  @roots    << v
end

#delete_edge(from, to) ⇒ void

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



92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/nanoc3/base/directed_graph.rb', line 92

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 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



127
128
129
130
131
132
133
134
135
 
# File 'lib/nanoc3/base/directed_graph.rb', line 127

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 returns an undefined value.

Deletes all edges going to the given vertex.

Parameters:

  • to —

    Vertex to which all edges should be removed



142
143
144
145
146
147
148
149
150
 
# File 'lib/nanoc3/base/directed_graph.rb', line 142

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 returns an undefined value.

Removes the given vertex from the graph.

Parameters:

  • v —

    Vertex to remove from the graph

Since:

  • 3.2.0



159
160
161
162
163
164
165
 
# File 'lib/nanoc3/base/directed_graph.rb', line 159

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

  @vertices.delete(v)
  @roots.delete(v)
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



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

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

#direct_successors_of(from) ⇒ Array

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



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

def direct_successors_of(from)
  @from_graph[from].to_a
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.



213
214
215
216
217
218
219
220
221
 
# File 'lib/nanoc3/base/directed_graph.rb', line 213

def edges
  result = []
  @vertices.each_with_index do |v, i|
    direct_successors_of(v).map { |v2| @vertice_indexes[v2] }.each do |i2|
      result << [ i, i2 ]
    end
  end
  result
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



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

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

#remove_edge(from, to) ⇒ Object

Deprecated.

Use #delete_edge instead



235
236
237
 
# File 'lib/nanoc3/base/directed_graph.rb', line 235

def remove_edge(from, to)
  delete_edge(from, to)
end

#roots ⇒ Set

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



228
229
230
 
# File 'lib/nanoc3/base/directed_graph.rb', line 228

def roots
  @roots
end

#successors_of(from) ⇒ Array

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



205
206
207
 
# File 'lib/nanoc3/base/directed_graph.rb', line 205

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