Class: DAG::Vertex

Inherits:
Object
  • Object
show all
Defined in:
lib/simple_dag/vertex.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#dag ⇒ Object (readonly)

Returns the value of attribute dag.



5
6
7
 
# File 'lib/simple_dag/vertex.rb', line 5

def dag
  @dag
end

#outgoing_edges ⇒ Object (readonly)

Returns the value of attribute outgoing_edges.



5
6
7
 
# File 'lib/simple_dag/vertex.rb', line 5

def outgoing_edges
  @outgoing_edges
end

#payload ⇒ Object (readonly)

Returns the value of attribute payload.



5
6
7
 
# File 'lib/simple_dag/vertex.rb', line 5

def payload
  @payload
end

Instance Method Details

#[](key) ⇒ Object

Retrieve a value from the vertex’s payload. This is a shortcut for vertex.payload.

Parameters:

  • key (Object) —

    the payload key

Returns:

  • the corresponding value from the payload Hash, or nil if not found



72
73
74
 
# File 'lib/simple_dag/vertex.rb', line 72

def [](key)
  @payload[key]
end

#ancestors(result_set = Set.new) ⇒ Object 



76
77
78
79
80
81
 
# File 'lib/simple_dag/vertex.rb', line 76

def ancestors(result_set = Set.new)
  predecessors.each do |v|
    v.ancestors(result_set) unless result_set.add?(v).nil?
  end
  result_set
end

#descendants(result_set = Set.new) ⇒ Object 



83
84
85
86
87
88
 
# File 'lib/simple_dag/vertex.rb', line 83

def descendants(result_set = Set.new)
  successors.each do |v|
    v.descendants(result_set) unless result_set.add?(v).nil?
  end
  result_set
end

#incoming_edges ⇒ Object 



15
16
17
 
# File 'lib/simple_dag/vertex.rb', line 15

def incoming_edges
  @dag.enumerated_edges.select { |e| e.destination == self }
end

#inspect ⇒ Object 



27
28
29
 
# File 'lib/simple_dag/vertex.rb', line 27

def inspect
  "DAG::Vertex:#{@payload.inspect}"
end

#path_to?(other) ⇒ Boolean

Is there a path from here to other following edges in the DAG?

Parameters:

Returns:

  • (Boolean) —

    true iff there is a path following edges within this DAG

Raises:

  • (ArgumentError) —

    if other is not a Vertex



38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/simple_dag/vertex.rb', line 38

def path_to?(other)
  raise ArgumentError, 'You must supply a vertex' unless other.is_a? Vertex
  visited = Set.new

  visit = lambda { |v|
    return false if visited.include? v
    return true if v.successors.lazy.include? other
    return true if v.successors.lazy.any? { |succ| visit.call succ }
    visited.add v
    false
  }

  visit.call self
end

#predecessors ⇒ Object 



19
20
21
 
# File 'lib/simple_dag/vertex.rb', line 19

def predecessors
  incoming_edges.map(&:origin)
end

#reachable_from?(other) ⇒ Boolean

Is there a path from other to here following edges in the DAG?

Parameters:

Returns:

  • (Boolean) —

    true iff there is a path following edges within this DAG

Raises:

  • (ArgumentError) —

    if other is not a Vertex



60
61
62
63
 
# File 'lib/simple_dag/vertex.rb', line 60

def reachable_from?(other)
  raise ArgumentError, 'You must supply a vertex' unless other.is_a? Vertex
  other.path_to? self
end

#successors ⇒ Object 



23
24
25
 
# File 'lib/simple_dag/vertex.rb', line 23

def successors
  @outgoing_edges.map(&:destination)
end