Class: Nanoc::DirectedGraph
- Inherits:
-
Object
- Object
- Nanoc::DirectedGraph
- Defined in:
- lib/nanoc/base/directed_graph.rb
Overview
Represents a directed graph. It is used by the dependency tracker for storing and querying dependencies between items.
Creating a graph (collapse)
-
- (DirectedGraph) initialize(vertices)
constructor
Creates a new directed graph with the given vertices.
Modifying the graph (collapse)
-
- (void) add_edge(from, to)
Adds an edge from the first vertex to the second vertex.
-
- (void) add_vertex(v)
Adds the given vertex to the graph.
-
- (void) delete_edge(from, to)
Removes the edge from the first vertex to the second vertex.
-
- (void) delete_edges_from(from)
Deletes all edges coming from the given vertex.
-
- (void) delete_edges_to(to)
Deletes all edges going to the given vertex.
-
- (void) delete_vertex(v)
Removes the given vertex from the graph.
Querying the graph (collapse)
-
- (Array) direct_predecessors_of(to)
Returns the direct predecessors of the given vertex, i.e.
-
- (Array) direct_successors_of(from)
Returns the direct successors of the given vertex, i.e.
-
- (Array) edges
Returns an array of tuples representing the edges.
-
- (Array) predecessors_of(to)
Returns the predecessors of the given vertex, i.e.
-
- (Set) roots
Returns all root vertices, i.e.
-
- (Array) successors_of(from)
Returns the successors of the given vertex, i.e.
-
- (Array) vertices
The list of all vertices in this graph.
Deprecated methods (collapse)
-
- (Object) remove_edge(from, to)
deprecated
Deprecated.
Use #delete_edge instead
Constructor Details
- (DirectedGraph) initialize(vertices)
Creates a new directed graph with the given vertices.
37 38 39 40 41 42 43 44 45 46 47 48 49 |
# File 'lib/nanoc/base/directed_graph.rb', line 37 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
- (void) add_edge(from, to)
This method returns an undefined value.
Adds an edge from the first vertex to the second vertex.
60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
# File 'lib/nanoc/base/directed_graph.rb', line 60 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 |
- (void) add_vertex(v)
This method returns an undefined value.
Adds the given vertex to the graph.
104 105 106 107 108 109 110 |
# File 'lib/nanoc/base/directed_graph.rb', line 104 def add_vertex(v) return if @vertices.key?(v) @vertices[v] = @vertices.size @roots << v end |
- (void) delete_edge(from, to)
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.
85 86 87 88 89 90 91 92 93 94 95 |
# File 'lib/nanoc/base/directed_graph.rb', line 85 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 |
- (void) delete_edges_from(from)
This method returns an undefined value.
Deletes all edges coming from the given vertex.
119 120 121 122 123 124 125 126 127 |
# File 'lib/nanoc/base/directed_graph.rb', line 119 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 |
- (void) delete_edges_to(to)
This method returns an undefined value.
Deletes all edges going to the given vertex.
134 135 136 137 138 139 140 141 142 |
# File 'lib/nanoc/base/directed_graph.rb', line 134 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 |
- (void) delete_vertex(v)
This method returns an undefined value.
Removes the given vertex from the graph.
151 152 153 154 155 156 157 |
# File 'lib/nanoc/base/directed_graph.rb', line 151 def delete_vertex(v) delete_edges_to(v) delete_edges_from(v) @vertices.delete(v) @roots.delete(v) end |
- (Array) direct_predecessors_of(to)
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.
167 168 169 |
# File 'lib/nanoc/base/directed_graph.rb', line 167 def direct_predecessors_of(to) @to_graph[to].to_a end |
- (Array) direct_successors_of(from)
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.
177 178 179 |
# File 'lib/nanoc/base/directed_graph.rb', line 177 def direct_successors_of(from) @from_graph[from].to_a end |
- (Array) edges
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.
210 211 212 213 214 215 216 217 218 |
# File 'lib/nanoc/base/directed_graph.rb', line 210 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 |
- (Array) predecessors_of(to)
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.
187 188 189 |
# File 'lib/nanoc/base/directed_graph.rb', line 187 def predecessors_of(to) @predecessors[to] ||= recursively_find_vertices(to, :direct_predecessors_of) end |
- (Object) remove_edge(from, to)
Use #delete_edge instead
232 233 234 |
# File 'lib/nanoc/base/directed_graph.rb', line 232 def remove_edge(from, to) delete_edge(from, to) end |
- (Set) roots
Returns all root vertices, i.e. vertices where no edge points to.
225 226 227 |
# File 'lib/nanoc/base/directed_graph.rb', line 225 def roots @roots end |
- (Array) successors_of(from)
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.
197 198 199 |
# File 'lib/nanoc/base/directed_graph.rb', line 197 def successors_of(from) @successors[from] ||= recursively_find_vertices(from, :direct_successors_of) end |
- (Array) vertices
Returns The list of all vertices in this graph.
202 203 204 |
# File 'lib/nanoc/base/directed_graph.rb', line 202 def vertices @vertices.keys.sort_by { |v| @vertices[v] } end |