Class: Tangle::Directed::Graph

Inherits:
BaseGraph show all
Defined in:
lib/tangle/directed/graph.rb

Overview

A directed graph

Direct Known Subclasses

Acyclic::Graph

Instance Attribute Summary

Attributes included from Mixin::Initialize

#mixins

Instance Method Summary collapse

Methods inherited from BaseGraph

[], #[], #add_edge, #add_vertex, #clone, #edges, #fetch, #initialize, #remove_edge, #remove_vertex, #select, #subgraph, #to_s, #vertices

Methods included from Currify

included

Constructor Details

This class inherits a constructor from Tangle::BaseGraph

Instance Method Details

#balanced? ⇒ Boolean

Is the graph balanced?

Returns:

  • (Boolean) 


114
115
116
 
# File 'lib/tangle/directed/graph.rb', line 114

def balanced?
  vertices.all? { |vertex| in_degree(vertex) == out_degree(vertex) }
end

#direct_predecessor?(vertex, other) ⇒ Boolean

Is other a direct predecessor of vertex?

Returns:

  • (Boolean) 


24
25
26
 
# File 'lib/tangle/directed/graph.rb', line 24

def direct_predecessor?(vertex, other)
  direct_predecessors(vertex).include?(other)
end

#direct_predecessors(vertex) ⇒ Object

Return the direct predecessors of vertex



18
19
20
 
# File 'lib/tangle/directed/graph.rb', line 18

def direct_predecessors(vertex)
  in_edges(vertex).map(&:tail).to_set
end

#direct_successor?(vertex, other) ⇒ Boolean

Is other a direct successor of vertex?

Returns:

  • (Boolean) 


60
61
62
 
# File 'lib/tangle/directed/graph.rb', line 60

def direct_successor?(vertex, other)
  direct_successors(vertex).include?(other)
end

#direct_successors(vertex) ⇒ Object

Return the direct successors of vertex



54
55
56
 
# File 'lib/tangle/directed/graph.rb', line 54

def direct_successors(vertex)
  out_edges(vertex).map(&:head).to_set
end

#in_degree(vertex) ⇒ Object

Return the in degree for vertex



84
85
86
 
# File 'lib/tangle/directed/graph.rb', line 84

def in_degree(vertex)
  in_edges(vertex).count
end

#in_edges(vertex) ⇒ Object

Return the incoming edges for vertex



12
13
14
 
# File 'lib/tangle/directed/graph.rb', line 12

def in_edges(vertex)
  edges(vertex).select { |edge| edge.head?(vertex) }
end

#internal?(vertex) ⇒ Boolean

Is vertex internal in the graph?

Returns:

  • (Boolean) 


108
109
110
 
# File 'lib/tangle/directed/graph.rb', line 108

def internal?(vertex)
  !(sink?(vertex) || source?(vertex))
end

#out_degree(vertex) ⇒ Object

Return the out degree for vertex



90
91
92
 
# File 'lib/tangle/directed/graph.rb', line 90

def out_degree(vertex)
  out_edges(vertex).count
end

#out_edges(vertex) ⇒ Object

Return the outgoing edges for vertex



48
49
50
 
# File 'lib/tangle/directed/graph.rb', line 48

def out_edges(vertex)
  edges(vertex).select { |edge| edge.tail?(vertex) }
end

#predecessor?(vertex, other) ⇒ Boolean

Is other a predecessor of vertex?

Returns:

  • (Boolean) 


36
37
38
 
# File 'lib/tangle/directed/graph.rb', line 36

def predecessor?(vertex, other)
  predecessors(vertex).any? { |vtx| other.eql?(vtx) }
end

#predecessor_subgraph(vertex, &selector) ⇒ Object

Return a subgraph with all predecessors of a vertex



42
43
44
 
# File 'lib/tangle/directed/graph.rb', line 42

def predecessor_subgraph(vertex, &selector)
  subgraph(predecessors(vertex), &selector)
end

#predecessors(vertex) ⇒ Object

Return a breadth first enumerator for all predecessors



30
31
32
 
# File 'lib/tangle/directed/graph.rb', line 30

def predecessors(vertex)
  vertex_enumerator(vertex, :direct_predecessors)
end

#sink?(vertex) ⇒ Boolean

Is vertex a sink in the graph?

Returns:

  • (Boolean) 


96
97
98
 
# File 'lib/tangle/directed/graph.rb', line 96

def sink?(vertex)
  out_degree(vertex).zero?
end

#source?(vertex) ⇒ Boolean

Is vertex a source in the graph?

Returns:

  • (Boolean) 


102
103
104
 
# File 'lib/tangle/directed/graph.rb', line 102

def source?(vertex)
  in_degree(vertex).zero?
end

#successor?(vertex, other) ⇒ Boolean

Is other a successor of vertex?

Returns:

  • (Boolean) 


72
73
74
 
# File 'lib/tangle/directed/graph.rb', line 72

def successor?(vertex, other)
  successors(vertex).any? { |vtx| other.eql?(vtx) }
end

#successor_subgraph(vertex, &selector) ⇒ Object

Return a subgraph with all successors of a vertex



78
79
80
 
# File 'lib/tangle/directed/graph.rb', line 78

def successor_subgraph(vertex, &selector)
  subgraph(successors(vertex), &selector)
end

#successors(vertex) ⇒ Object

Return a breadth first enumerator for all successors



66
67
68
 
# File 'lib/tangle/directed/graph.rb', line 66

def successors(vertex)
  vertex_enumerator(vertex, :direct_successors)
end