Represents a directed graph. It is used by the dependency tracker for storing and querying dependencies between items.
@example Creating and using a directed graph
# Create a graph with three vertices graph = Nanoc::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 )
Creates a new directed graph with the given vertices.
# File lib/nanoc/base/directed_graph.rb, line 36 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
Adds an edge from the first vertex to the second vertex.
@param from Vertex where the edge should start
@param to Vertex where the edge should end
@return [void]
# File lib/nanoc/base/directed_graph.rb, line 59 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
Adds the given vertex to the graph.
@param v The vertex to add to the graph
@return [void]
@since 3.2.0
# File lib/nanoc/base/directed_graph.rb, line 103 def add_vertex(v) return if @vertices.has_key?(v) @vertices[v] = @vertices.size @roots << v end
Removes the edge from the first vertex to the second vertex. If the edge does not exist, nothing is done.
@param from Start vertex of the edge
@param to End vertex of the edge
@return [void]
@since 3.2.0
# File lib/nanoc/base/directed_graph.rb, line 84 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
Deletes all edges coming from the given vertex.
@param from Vertex from which all edges should be removed
@return [void]
@since 3.2.0
# File lib/nanoc/base/directed_graph.rb, line 118 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
Deletes all edges going to the given vertex.
@param to Vertex to which all edges should be removed
@return [void]
# File lib/nanoc/base/directed_graph.rb, line 133 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
Removes the given vertex from the graph.
@param v Vertex to remove from the graph
@return [void]
@since 3.2.0
# File lib/nanoc/base/directed_graph.rb, line 150 def delete_vertex(v) delete_edges_to(v) delete_edges_from(v) @vertices.delete(v) @roots.delete(v) end
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.
@param to The vertex of which the predecessors should be calculated
@return [Array] Direct predecessors of the given vertex
# File lib/nanoc/base/directed_graph.rb, line 166 def direct_predecessors_of(to) @to_graph[to].to_a end
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.
@param from The vertex of which the successors should be calculated
@return [Array] Direct successors of the given vertex
# File lib/nanoc/base/directed_graph.rb, line 176 def direct_successors_of(from) @from_graph[from].to_a end
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.
@return [Array] The list of all edges in this graph.
# File lib/nanoc/base/directed_graph.rb, line 209 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
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.
@param to The vertex of which the predecessors should be calculated
@return [Array] Predecessors of the given vertex
# File lib/nanoc/base/directed_graph.rb, line 186 def predecessors_of(to) @predecessors[to] ||= recursively_find_vertices(to, :direct_predecessors_of) end
@deprecated Use {delete_edge} instead
# File lib/nanoc/base/directed_graph.rb, line 231 def remove_edge(from, to) delete_edge(from, to) end
Returns all root vertices, i.e. vertices where no edge points to.
@return [Set] The set of all root vertices in this graph.
@since 3.2.0
# File lib/nanoc/base/directed_graph.rb, line 224 def roots @roots end
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.
@param from The vertex of which the successors should be calculated
@return [Array] Successors of the given vertex
# File lib/nanoc/base/directed_graph.rb, line 196 def successors_of(from) @successors[from] ||= recursively_find_vertices(from, :direct_successors_of) end
Generated with the Darkfish Rdoc Generator 2.