Class: MiniGraph::Core::Graph

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Includes:
Enumerable
Defined in:
lib/mini_graph/core/graph.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(vertices, directed: false) ⇒ Graph

Initialize a directed or undirected graph with a list of vertices



17
18
19
20
21
 
# File 'lib/mini_graph/core/graph.rb', line 17

def initialize(vertices, directed: false)
  @directed = !!directed
  @vertices = [vertices].flatten.freeze
  @edges    = []
end

Instance Attribute Details

#vertices ⇒ Object (readonly)

Returns the value of attribute vertices.



14
15
16
 
# File 'lib/mini_graph/core/graph.rb', line 14

def vertices
  @vertices
end

Instance Method Details

#add_edge(*args) ⇒ Object

Adds an edge from the vertex at origin_index to the vertex at destination_index



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/mini_graph/core/graph.rb', line 33

def add_edge(*args)
  edge = args_to_edge(args)

  # origin must reference a valid index within the graph
  if edge.origin >= size
    raise ::MiniGraph::Core::Error::InvalidIndexError,
          'origin_index invalid'
  end

  # destination must reference a valid index within the graph
  if edge.destination >= size
    raise ::MiniGraph::Core::Error::InvalidIndexError,
          'destination_index invalid'
  end

  edges << edge
end

#adjacent_vertices(index) ⇒ Object

Returns an array of vertex indices that have an inbound edge from the vertex at the supplied index



61
62
63
64
65
66
67
68
 
# File 'lib/mini_graph/core/graph.rb', line 61

def adjacent_vertices(index)
  edges.reduce([]) do |adj, edge|
    adj << edge.destination if edge.origin == index
    adj << edge.origin      if undirected? && edge.destination == index
    adj
  end
  .uniq
end

#directed? ⇒ Boolean

Returns:

  • (Boolean) 


51
52
53
 
# File 'lib/mini_graph/core/graph.rb', line 51

def directed?
  @directed
end

#edge_class ⇒ Object 



23
24
25
26
27
28
29
 
# File 'lib/mini_graph/core/graph.rb', line 23

def edge_class
  if directed?
    MiniGraph::Core::Edge::Directed
  else
    MiniGraph::Core::Edge::Undirected
  end
end

#reverse ⇒ Object

Returns a reversed copy of the digraph.



71
72
73
74
75
 
# File 'lib/mini_graph/core/graph.rb', line 71

def reverse
  self.class.new(vertices, directed: @directed).tap do |dg|
    dg.edges = edges.map(&:reverse)
  end
end

#to_s ⇒ Object 



77
78
79
 
# File 'lib/mini_graph/core/graph.rb', line 77

def to_s
  edges.join
end

#undirected? ⇒ Boolean

Returns:

  • (Boolean) 


55
56
57
 
# File 'lib/mini_graph/core/graph.rb', line 55

def undirected?
  !directed?
end