class MiniGraph::Core::Graph

Attributes

vertices[R]

Public Class Methods

new(vertices, directed: false) click to toggle source

Initialize a directed or undirected graph with a list of vertices

# File lib/mini_graph/core/graph.rb, line 17
def initialize(vertices, directed: false)
  @directed = !!directed
  @vertices = [vertices].flatten.freeze
  @edges    = []
end

Public Instance Methods

add_edge(*args) click to toggle source

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

# 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) click to toggle source

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

# 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?() click to toggle source
# File lib/mini_graph/core/graph.rb, line 51
def directed?
  @directed
end
edge_class() click to toggle source
# 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() click to toggle source

Returns a reversed copy of the digraph.

# 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() click to toggle source
# File lib/mini_graph/core/graph.rb, line 77
def to_s
  edges.join
end
undirected?() click to toggle source
# File lib/mini_graph/core/graph.rb, line 55
def undirected?
  !directed?
end

Protected Instance Methods

edges() click to toggle source

Protected


# File lib/mini_graph/core/graph.rb, line 87
def edges
  @edges
end
edges=(edges) click to toggle source
# File lib/mini_graph/core/graph.rb, line 91
def edges=(edges)
  @edges = edges
end

Private Instance Methods

args_to_edge(args) click to toggle source

Private


# File lib/mini_graph/core/graph.rb, line 101
def args_to_edge(args)
  case args.length
  when 1
    args.first.tap do |edge|
      if edge.class != edge_class
        raise MiniGraph::Core::Error::InvalidEdgeTypeError,
              "edge must be instance of #{edge_class.name}"
      end
    end
  when 2
    edge_class.new(*args)
  else
    raise ArgumentError,
          "wrong number of arguments.  #{args.length} args were provided. 1 or 2 arguments were expected."
  end
end