Class: Bundler::Molinillo::DependencyGraph

Inherits:
Object
  • Object
show all
Includes:
Enumerable, TSort
Defined in:
lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb

Overview

A directed acyclic graph that is tuned to hold named dependencies

Defined Under Namespace

Classes: Edge, Vertex

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DependencyGraph

Returns a new instance of DependencyGraph.



49
50
51
52
53
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 49

def initialize
  @vertices = {}
  @edges = Set.new
  @root_vertices = {}
end

Instance Attribute Details

#edges ⇒ Set<Edge> (readonly)

Returns the edges of the dependency graph.

Returns:

  • (Set<Edge>) —

    the edges of the dependency graph



47
48
49
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 47

def edges
  @edges
end

#root_vertices ⇒ {String => Vertex} (readonly)

Returns vertices that have no Bundler::Molinillo::DependencyGraph::Vertex#predecessors, keyed by by Bundler::Molinillo::DependencyGraph::Vertex#name.

Returns:



42
43
44
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 42

def root_vertices
  @root_vertices
end

#vertices ⇒ {String => Vertex} (readonly)

Returns the vertices of the dependency graph, keyed by Bundler::Molinillo::DependencyGraph::Vertex#name.

Returns:



45
46
47
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 45

def vertices
  @vertices
end

Class Method Details

.tsort(vertices) ⇒ Array<Vertex>

Topologically sorts the given vertices.

Parameters:

  • vertices (Enumerable<Vertex>) —

    the vertices to be sorted, which must all belong to the same graph.

Returns:

  • (Array<Vertex>) —

    The sorted vertices.



27
28
29
30
31
32
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 27

def self.tsort(vertices)
  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.

Returns:



82
83
84
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 82

def ==(other)
  root_vertices == other.root_vertices
end

#add_child_vertex(name, payload, parent_names, requirement) ⇒ void

This method returns an undefined value.

Parameters:

  • name (String)
  • payload (Object)
  • parent_names (Array<String>)
  • requirement (Object) —

    the requirement that is requiring the child



91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 91

def add_child_vertex(name, payload, parent_names, requirement)
  is_root = parent_names.include?(nil)
  parent_nodes = parent_names.compact.map { |n| vertex_named(n) }
  vertex = vertex_named(name) || if is_root
                                   add_root_vertex(name, payload)
                                 else
                                   add_vertex(name, payload)
                                 end
  vertex.payload ||= payload
  parent_nodes.each do |parent_node|
    add_edge(parent_node, vertex, requirement)
  end
  vertex
end

#add_edge(origin, destination, requirement) ⇒ Edge

Adds a new Edge to the dependency graph

Parameters:

  • origin (Vertex)
  • destination (Vertex)
  • requirement (Object) —

    the requirement that this edge represents

Returns:

  • (Edge) —

    the added edge



151
152
153
154
155
156
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 151

def add_edge(origin, destination, requirement)
  if origin == destination || destination.path_to?(origin)
    raise CircularDependencyError.new([origin, destination])
  end
  Edge.new(origin, destination, [requirement]).tap { |e| edges << e }
end

#add_root_vertex(name, payload) ⇒ Vertex

Returns the vertex that was added to ‘self`.

Parameters:

  • name (String)
  • payload (Object)

Returns:

  • (Vertex) —

    the vertex that was added to ‘self`



117
118
119
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 117

def add_root_vertex(name, payload)
  add_vertex(name, payload).tap { |v| root_vertices[name] = v }
end

#add_vertex(name, payload) ⇒ Vertex

Returns the vertex that was added to ‘self`.

Parameters:

  • name (String)
  • payload (Object)

Returns:

  • (Vertex) —

    the vertex that was added to ‘self`



109
110
111
112
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 109

def add_vertex(name, payload)
  vertex = vertices[name] ||= Vertex.new(self, name, payload)
  vertex.tap { |v| v.payload = payload }
end

#detach_vertex_named(name) ⇒ void

This method returns an undefined value.

Detaches the #vertex_named ‘name` Vertex from the graph, recursively removing any non-root vertices that were orphaned in the process

Parameters:

  • name (String) 


125
126
127
128
129
130
131
132
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 125

def detach_vertex_named(name)
  vertex = vertex_named(name)
  return unless vertex
  successors = vertex.successors
  vertices.delete(name)
  edges.reject! { |e| e.origin == vertex || e.destination == vertex }
  successors.each { |v| detach_vertex_named(v.name) unless root_vertices[v.name] || v.predecessors.any? }
end

#each ⇒ Array<Vertex> Also known as: tsort_each_node

Enumerates through the vertices of the graph.

Returns:

  • (Array<Vertex>) —

    The graph’s vertices.



11
12
13
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 11

def each
  vertices.values.each { |v| yield v }
end

#initialize_copy(other) ⇒ Object

Initializes a copy of a Bundler::Molinillo::DependencyGraph, ensuring that all #vertices have the correct Bundler::Molinillo::DependencyGraph::Vertex#graph set



57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 57

def initialize_copy(other)
  super
  @vertices = other.vertices.reduce({}) do |vertices, (name, vertex)|
    vertices.tap do |hash|
      hash[name] = vertex.dup.tap { |v| v.graph = self }
    end
  end
  @root_vertices = Hash[@vertices.select { |n, _v| other.root_vertices[n] }]
  @edges = other.edges.map do |edge|
    Edge.new(
      vertex_named(edge.origin.name),
      vertex_named(edge.destination.name),
      edge.requirements.dup
    )
  end
end

#inspect ⇒ String

Returns a string suitable for debugging.

Returns:

  • (String) —

    a string suitable for debugging



75
76
77
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 75

def inspect
  "#{self.class}:#{vertices.values.inspect}"
end

#root_vertex_named(name) ⇒ Vertex?

Returns the root vertex with the given name.

Parameters:

  • name (String)

Returns:

  • (Vertex, nil) —

    the root vertex with the given name



142
143
144
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 142

def root_vertex_named(name)
  root_vertices[name]
end

#tsort_each_child(vertex, &block) ⇒ Object 



19
20
21
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 19

def tsort_each_child(vertex, &block)
  vertex.successors.each(&block)
end

#vertex_named(name) ⇒ Vertex?

Returns the vertex with the given name.

Parameters:

  • name (String)

Returns:

  • (Vertex, nil) —

    the vertex with the given name



136
137
138
 
# File 'lib/bundler/vendor/molinillo/lib/molinillo/dependency_graph.rb', line 136

def vertex_named(name)
  vertices[name]
end