Class: Molinillo::DependencyGraph

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
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

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DependencyGraph

Returns a new instance of DependencyGraph.



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

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



25
26
27
 
# File 'lib/molinillo/dependency_graph.rb', line 25

def edges
  @edges
end

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

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

Returns:



20
21
22
 
# File 'lib/molinillo/dependency_graph.rb', line 20

def root_vertices
  @root_vertices
end

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

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

Returns:



23
24
25
 
# File 'lib/molinillo/dependency_graph.rb', line 23

def vertices
  @vertices
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 Molinillo::DependencyGraph::Vertex#successors.

Returns:



60
61
62
 
# File 'lib/molinillo/dependency_graph.rb', line 60

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



69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/molinillo/dependency_graph.rb', line 69

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



128
129
130
131
132
133
 
# File 'lib/molinillo/dependency_graph.rb', line 128

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



95
96
97
 
# File 'lib/molinillo/dependency_graph.rb', line 95

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



87
88
89
90
 
# File 'lib/molinillo/dependency_graph.rb', line 87

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) 


103
104
105
106
107
108
109
 
# File 'lib/molinillo/dependency_graph.rb', line 103

def detach_vertex_named(name)
  vertex = vertex_named(name)
  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 ⇒ Object 



8
9
10
 
# File 'lib/molinillo/dependency_graph.rb', line 8

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

#initialize_copy(other) ⇒ Object

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



35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/molinillo/dependency_graph.rb', line 35

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



53
54
55
 
# File 'lib/molinillo/dependency_graph.rb', line 53

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



119
120
121
 
# File 'lib/molinillo/dependency_graph.rb', line 119

def root_vertex_named(name)
  root_vertices[name]
end

#vertex_named(name) ⇒ Vertex?

Returns the vertex with the given name.

Parameters:

  • name (String)

Returns:

  • (Vertex, nil) —

    the vertex with the given name



113
114
115
 
# File 'lib/molinillo/dependency_graph.rb', line 113

def vertex_named(name)
  vertices[name]
end