Parent

Class/Module Index [+]

Quicksearch

Nanoc::DirectedGraph

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 )

Public Class Methods

new(vertices) click to toggle source

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

Public Instance Methods

add_edge(from, to) click to toggle source

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
add_vertex(v) click to toggle source

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
delete_edge(from, to) click to toggle source

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
delete_edges_from(from) click to toggle source

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
delete_edges_to(to) click to toggle source

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
delete_vertex(v) click to toggle source

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
direct_predecessors_of(to) click to toggle source

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
direct_successors_of(from) click to toggle source

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
edges() click to toggle source

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
predecessors_of(to) click to toggle source

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
remove_edge(from, to) click to toggle source

@deprecated Use {delete_edge} instead

# File lib/nanoc/base/directed_graph.rb, line 231
def remove_edge(from, to)
  delete_edge(from, to)
end
roots() click to toggle source

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
successors_of(from) click to toggle source

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
vertices() click to toggle source

@return [Array] The list of all vertices in this graph.

# File lib/nanoc/base/directed_graph.rb, line 201
def vertices
  @vertices.keys.sort_by { |v| @vertices[v] }
end

[Validate]

Generated with the Darkfish Rdoc Generator 2.