Class: Bundler::Molinillo::DependencyGraph
- Inherits:
-
Object
- Object
- Bundler::Molinillo::DependencyGraph
- Includes:
- TSort, Enumerable
- Defined in:
- lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/log.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/tag.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/action.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/vertex.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_vertex.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/delete_edge.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/set_payload.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/detach_vertex_named.rb,
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph/add_edge_no_circular.rb
Overview
A directed acyclic graph that is tuned to hold named dependencies
Defined Under Namespace
Classes: Action, Edge, Log, Vertex
Instance Attribute Summary collapse
-
#log ⇒ Log
readonly
The op log for this graph.
-
#vertices ⇒ {String => Vertex}
readonly
The vertices of the dependency graph, keyed by Vertex#name.
Class Method Summary collapse
-
.tsort(vertices) ⇒ Array<Vertex>
Topologically sorts the given vertices.
Instance Method Summary collapse
-
#==(other) ⇒ Boolean
Whether the two dependency graphs are equal, determined by a recursive traversal of each #root_vertices and its Vertex#successors.
- #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.
-
#delete_edge(edge) ⇒ Void
Deletes an Edge from the dependency graph.
-
#detach_vertex_named(name) ⇒ Array<Vertex>
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 ⇒ DependencyGraph
constructor
Initializes an empty dependency graph.
-
#initialize_copy(other) ⇒ Object
Initializes a copy of a DependencyGraph, ensuring that all #vertices are properly copied.
-
#inspect ⇒ String
A string suitable for debugging.
-
#rewind_to(tag) ⇒ Void
Rewinds the graph to the state tagged as ‘tag`.
-
#root_vertex_named(name) ⇒ Vertex?
The root vertex with the given name.
-
#set_payload(name, payload) ⇒ Void
Sets the payload of the vertex with the given name.
-
#tag(tag) ⇒ Void
Tags the current state of the dependency as the given tag.
-
#to_dot(options = {}) ⇒ String
Returns a dot format representation of the graph.
-
#vertex_named(name) ⇒ Vertex?
The vertex with the given name.
Methods included from TSort
#each_strongly_connected_component, each_strongly_connected_component, #each_strongly_connected_component_from, each_strongly_connected_component_from, #strongly_connected_components, strongly_connected_components, #tsort, #tsort_each, tsort_each
Constructor Details
#initialize ⇒ DependencyGraph
Initializes an empty dependency graph
55 56 57 58 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 55 def initialize @vertices = {} @log = Log.new end |
Instance Attribute Details
#log ⇒ Log (readonly)
Returns the op log for this graph.
52 53 54 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 52 def log @log end |
#vertices ⇒ {String => Vertex} (readonly)
Returns the vertices of the dependency graph, keyed by Bundler::Molinillo::DependencyGraph::Vertex#name.
49 50 51 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 49 def vertices @vertices end |
Class Method Details
.tsort(vertices) ⇒ Array<Vertex>
Topologically sorts the given vertices.
34 35 36 37 38 39 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 34 def self.tsort(vertices) Bundler::TSort.tsort( lambda { |b| vertices.each(&b) }, lambda { |v, &b| (v.successors & vertices).each(&b) } ) end |
Instance Method Details
#==(other) ⇒ Boolean
Returns whether the two dependency graphs are equal, determined by a recursive traversal of each #root_vertices and its Bundler::Molinillo::DependencyGraph::Vertex#successors.
130 131 132 133 134 135 136 137 138 139 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 130 def ==(other) return false unless other return true if equal?(other) vertices.each do |name, vertex| other_vertex = other.vertex_named(name) return false unless other_vertex return false unless vertex.payload == other_vertex.payload return false unless other_vertex.successors.to_set == vertex.successors.to_set end end |
#add_child_vertex(name, payload, parent_names, requirement) ⇒ void
This method returns an undefined value.
146 147 148 149 150 151 152 153 154 155 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 146 def add_child_vertex(name, payload, parent_names, requirement) root = !parent_names.delete(nil) { true } vertex = add_vertex(name, payload, root) vertex.explicit_requirements << requirement if root parent_names.each do |parent_name| parent_vertex = vertex_named(parent_name) add_edge(parent_vertex, vertex, requirement) end vertex end |
#add_edge(origin, destination, requirement) ⇒ Edge
Adds a new Edge to the dependency graph
191 192 193 194 195 196 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 191 def add_edge(origin, destination, requirement) if destination.path_to?(origin) raise CircularDependencyError.new(path(destination, origin)) end add_edge_no_circular(origin, destination, requirement) end |
#add_vertex(name, payload, root = false) ⇒ Vertex
Adds a vertex with the given name, or updates the existing one.
161 162 163 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 161 def add_vertex(name, payload, root = false) log.add_vertex(self, name, payload, root) end |
#delete_edge(edge) ⇒ Void
Deletes an Edge from the dependency graph
201 202 203 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 201 def delete_edge(edge) log.delete_edge(self, edge.origin.name, edge.destination.name, edge.requirement) end |
#detach_vertex_named(name) ⇒ Array<Vertex>
Detaches the #vertex_named ‘name` Vertex from the graph, recursively removing any non-root vertices that were orphaned in the process
169 170 171 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 169 def detach_vertex_named(name) log.detach_vertex_named(self, name) end |
#each ⇒ Array<Vertex> Also known as: tsort_each_node
Enumerates through the vertices of the graph.
15 16 17 18 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 15 def each return vertices.values.each unless block_given? vertices.values.each { |v| yield v } end |
#initialize_copy(other) ⇒ Object
Initializes a copy of a Bundler::Molinillo::DependencyGraph, ensuring that all #vertices are properly copied.
77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 77 def initialize_copy(other) super @vertices = {} @log = other.log.dup 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
Returns a string suitable for debugging.
97 98 99 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 97 def inspect "#{self.class}:#{vertices.values.inspect}" end |
#rewind_to(tag) ⇒ Void
Rewinds the graph to the state tagged as ‘tag`
70 71 72 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 70 def rewind_to(tag) log.rewind_to(self, tag) end |
#root_vertex_named(name) ⇒ Vertex?
Returns the root vertex with the given name.
181 182 183 184 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 181 def root_vertex_named(name) vertex = vertex_named(name) vertex if vertex && vertex.root? end |
#set_payload(name, payload) ⇒ Void
Sets the payload of the vertex with the given name
209 210 211 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 209 def set_payload(name, payload) log.set_payload(self, name, payload) end |
#tag(tag) ⇒ Void
Tags the current state of the dependency as the given tag
63 64 65 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 63 def tag(tag) log.tag(self, tag) end |
#to_dot(options = {}) ⇒ String
Returns a dot format representation of the graph
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 103 def to_dot( = {}) edge_label = .delete(:edge_label) raise ArgumentError, "Unknown options: #{.keys}" unless .empty? dot_vertices = [] dot_edges = [] vertices.each do |n, v| dot_vertices << " #{n} [label=\"{#{n}|#{v.payload}}\"]" v.outgoing_edges.each do |e| label = edge_label ? edge_label.call(e) : e.requirement dot_edges << " #{e.origin.name} -> #{e.destination.name} [label=#{label.to_s.dump}]" end end dot_vertices.uniq! dot_vertices.sort! dot_edges.uniq! dot_edges.sort! dot = dot_vertices.unshift('digraph G {').push('') + dot_edges.push('}') dot.join("\n") end |
#vertex_named(name) ⇒ Vertex?
Returns the vertex with the given name.
175 176 177 |
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 175 def vertex_named(name) vertices[name] end |