Class: Gem::Resolver::Molinillo::DependencyGraph
Relationships & Source Files | |
Namespace Children | |
Classes:
| |
Super Chains via Extension / Inclusion / Inheritance | |
Instance Chain:
self,
TSort,
Enumerable
|
|
Inherits: | Object |
Defined in: | lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb |
Overview
A directed acyclic graph that is tuned to hold named dependencies
Class Method Summary
-
.new ⇒ DependencyGraph
constructor
Initializes an empty dependency graph.
-
.tsort(vertices) ⇒ Array<Vertex>
Topologically sorts the given vertices.
Instance Attribute Summary
- #vertices ⇒ {String => Vertex} readonly
Instance Method Summary
- #==(other) ⇒ Boolean
- #add_child_vertex(name, payload, parent_names, requirement) ⇒ void
-
#add_edge(origin, destination, requirement) ⇒ Edge
Adds a new Edge to the dependency graph.
-
#add_vertex(name, payload, root = false) ⇒ Vertex
Adds a vertex with the given name, or updates the existing one.
-
#detach_vertex_named(name) ⇒ void
Detaches the #vertex_named
name
Vertex from the graph, recursively removing any non-root vertices that were orphaned in the process. -
#each ⇒ Array<Vertex>
(also: #tsort_each_node)
Enumerates through the vertices of the graph.
-
#initialize_copy(other)
Initializes a copy of a
DependencyGraph
, ensuring that all #vertices are properly copied. - #inspect ⇒ String
- #root_vertex_named(name) ⇒ Vertex?
- #vertex_named(name) ⇒ Vertex?
-
#add_edge_no_circular(origin, destination, requirement)
private
Adds a new Edge to the dependency graph without checking for circularity.
- #tsort_each_child(vertex, &block) private
-
#tsort_each_node
private
Alias for #each.
Constructor Details
.new ⇒ DependencyGraph
Initializes an empty dependency graph
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 48
def initialize @vertices = {} end
Class Method Details
.tsort(vertices) ⇒ Array
<Vertex>
Topologically sorts the given vertices.
Instance Attribute Details
#vertices ⇒ {String
=> Vertex} (readonly)
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 45
attr_reader :vertices
Instance Method Details
#==(other) ⇒ Boolean
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 81
def ==(other) return false unless other vertices.each do |name, vertex| other_vertex = other.vertex_named(name) return false unless other_vertex return false unless other_vertex.successors.map(&:name).to_set == vertex.successors.map(&:name).to_set end end
#add_child_vertex(name, payload, parent_names, requirement) ⇒ void
This method returns an undefined value.
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 95
def add_child_vertex(name, payload, parent_names, requirement) vertex = add_vertex(name, payload) parent_names.each do |parent_name| unless parent_name vertex.root = true next end parent_node = vertex_named(parent_name) add_edge(parent_node, vertex, requirement) end vertex end
#add_edge(origin, destination, requirement) ⇒ Edge
Adds a new DependencyGraph::Edge to the dependency graph
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 150
def add_edge(origin, destination, requirement) if destination.path_to?(origin) raise CircularDependencyError.new([origin, destination]) end add_edge_no_circular(origin, destination, requirement) end
#add_edge_no_circular(origin, destination, requirement) (private)
Adds a new DependencyGraph::Edge to the dependency graph without checking for circularity.
#add_vertex(name, payload, root = false) ⇒ Vertex
Adds a vertex with the given name, or updates the existing one.
#detach_vertex_named(name) ⇒ void
This method returns an undefined value.
Detaches the #vertex_named name
DependencyGraph::Vertex from the graph, recursively removing any non-root vertices that were orphaned in the process
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 123
def detach_vertex_named(name) return unless vertex = vertices.delete(name) vertex.outgoing_edges.each do |e| v = e.destination v.incoming_edges.delete(e) detach_vertex_named(v.name) unless v.root? || v.predecessors.any? end end
#each ⇒ Array
<Vertex>
Also known as: #tsort_each_node
Enumerates through the vertices of the graph.
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 12
def each vertices.values.each { |v| yield v } end
#initialize_copy(other)
Initializes a copy of a DependencyGraph
, ensuring that all #vertices are properly copied.
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 55
def initialize_copy(other) super @vertices = {} traverse = lambda do |new_v, old_v| return if new_v.outgoing_edges.size == old_v.outgoing_edges.size old_v.outgoing_edges.each do |edge| destination = add_vertex(edge.destination.name, edge.destination.payload) add_edge_no_circular(new_v, destination, edge.requirement) traverse.call(destination, edge.destination) end end other.vertices.each do |name, vertex| new_vertex = add_vertex(name, vertex.payload, vertex.root?) new_vertex.explicit_requirements.replace(vertex.explicit_requirements) traverse.call(new_vertex, vertex) end end
#inspect ⇒ String
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 74
def inspect "#{self.class}:#{vertices.values.inspect}" end
#root_vertex_named(name) ⇒ Vertex?
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 140
def root_vertex_named(name) vertex = vertex_named(name) vertex if vertex && vertex.root? end
#tsort_each_child(vertex, &block) (private)
[ GitHub ]# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 22
def tsort_each_child(vertex, &block) vertex.successors.each(&block) end
#tsort_each_node (private)
Alias for #each.
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 19
alias_method :tsort_each_node, :each
#vertex_named(name) ⇒ Vertex?
# File 'lib/rubygems/resolver/molinillo/lib/molinillo/dependency_graph.rb', line 134
def vertex_named(name) vertices[name] end