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.
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
- (void) add_edge(from, to)
This method returns an undefined value.
Adds an edge from the first vertex to the second vertex.
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 |
- (void) add_vertex(v)
This method returns an undefined value.
Adds the given vertex to the graph.
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 |
- (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.
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 |
- (void) delete_edges_from(from)
This method returns an undefined value.
Deletes all edges coming from the given vertex.
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 |
- (void) delete_edges_to(to)
This method returns an undefined value.
Deletes all edges going to the given vertex.
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 |
- (void) delete_vertex(v)
This method returns an undefined value.
Removes the given vertex from the graph.
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 |
- (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.
165 166 167 |
# File 'lib/nanoc/base/directed_graph.rb', line 165 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.
175 176 177 |
# File 'lib/nanoc/base/directed_graph.rb', line 175 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.
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 |
- (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.
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 |
- (Object) remove_edge(from, to)
Use #delete_edge instead
230 231 232 |
# File 'lib/nanoc/base/directed_graph.rb', line 230 def remove_edge(from, to) delete_edge(from, to) end |
- (Set) roots
Returns all root vertices, i.e. vertices where no edge points to.
223 224 225 |
# File 'lib/nanoc/base/directed_graph.rb', line 223 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.
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 |
- (Array) vertices
Returns 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 |