class Graphsrb::BaseGraph

This class is the base clase for undirected and directed graphs.

Attributes

adj_table[R]

Public Class Methods

new(args={}) click to toggle source
# File lib/graphsrb/base_graph.rb, line 5
def initialize(args={})
  @adj_table = {}
  args.fetch(:vertices,[]).each{|vertex_id| adj_table[vertex_id] = _create_adjacency_list }
  args.fetch(:edges,[]).each do |e|
    unless has_edge?(e[0], e[1])
      vertices_must_be_different!(e[0], e[1])
      add_edge(e[0], e[1], weight: e[2] || 1)
    end
  end
end

Public Instance Methods

add_edge(id1, id2, args={}) click to toggle source

Adds a new edge

# File lib/graphsrb/base_graph.rb, line 111
def add_edge(id1, id2, args={})
  vertices_must_be_different!(id1, id2)
  return nil if has_edge?(id1, id2)
  add_vertex(id1) unless has_vertex?(id1)
  add_vertex(id2) unless has_vertex?(id2)
  adj_table[id1] << _create_node(id2, args)
  true
end
add_vertex(id) click to toggle source

Adds a new vertex

# File lib/graphsrb/base_graph.rb, line 104
def add_vertex(id)
  return nil if has_vertex?(id)
  adj_table[id] = _create_adjacency_list
  true
end
clear() click to toggle source

Removes all vertices and edges.

# File lib/graphsrb/base_graph.rb, line 65
def clear
  adj_table.each_value{|list| list.clear}
  @adj_table = {}
  true
end
copy() click to toggle source

Creates a copy of the graph

# File lib/graphsrb/base_graph.rb, line 72
def copy
  Marshal::load(Marshal.dump(self))
end
edge(v, u) click to toggle source

Returns an edge

# File lib/graphsrb/base_graph.rb, line 26
def edge(v, u)
  id1, id2 = v.id, u.id
  if has_vertex?(id1)
    node = adj_table[id1].find(_create_node(id2))
    return _create_edge(id1, id2, weight:node.weight) if node
  end

  if has_vertex?(id2)
    node = adj_table[id2].find(_create_node(id1))
    return _create_edge(id1, id2, weight:node.weight) if node
  end
end
edge?(id1, id2)
Alias for: has_edge?
edge_count() click to toggle source

Returns the number of edges in the graph

# File lib/graphsrb/base_graph.rb, line 82
def edge_count
  sum = 0
  adj_table.each_value{|list| sum += list.size}
  sum
end
edges() click to toggle source

Returns edges of the graph

# File lib/graphsrb/base_graph.rb, line 54
def edges
  edges_array = []
  vertices.each do |vertex|
    adj_table[vertex.id].each do |node|
      edges_array << _create_edge(vertex.id, node.vertex.id, weight: node.weight)
    end
  end
  edges_array
end
has_edge?(id1, id2) click to toggle source

Checks whether the graph has an edge

# File lib/graphsrb/base_graph.rb, line 96
def has_edge?(id1, id2)
  has_vertex?(id1) && adj_table[id1].has_node?(_create_node(id2)) ||
  has_vertex?(id2) && adj_table[id2].has_node?(_create_node(id1))
end
Also aliased as: edge?
has_vertex?(id) click to toggle source

Checks whether the graph has a vertex

# File lib/graphsrb/base_graph.rb, line 89
def has_vertex?(id)
  not adj_table[id].nil?
end
Also aliased as: vertex?
increase_weight(v, u, dw) click to toggle source

Increases edge weight by dw

# File lib/graphsrb/base_graph.rb, line 47
def increase_weight(v, u, dw)
  id1, id2 = v.id, u.id
  adj_table[id1].increase_weight(_create_node(id2), dw) if has_vertex?(id1)
  adj_table[id2].increase_weight(_create_node(id1), dw) if has_vertex?(id2)
end
remove_edge(v1, v2) click to toggle source

Remove an edge from the graph

# File lib/graphsrb/base_graph.rb, line 121
def remove_edge(v1, v2)
  id1, id2 = v1.id, v2.id
  adj_table[id1].delete(_create_node(id2)) if has_vertex?(id1)
  adj_table[id2].delete(_create_node(id1)) if has_vertex?(id2)
  true
end
remove_vertex(v) click to toggle source

Remove a vertex from the graph

# File lib/graphsrb/base_graph.rb, line 129
def remove_vertex(v)
  id = v.id
  return nil unless has_vertex?(id)

  adj_table[id].clear
  adj_table.delete(id)

  node = _create_node(id)
  adj_table.each_value{|list| list.delete(node)}
  return v
end
update_weight(v, u, w) click to toggle source

Updates edge weight

# File lib/graphsrb/base_graph.rb, line 40
def update_weight(v, u, w)
  id1, id2 = v.id, u.id
  adj_table[id1].update_weight(_create_node(id2), w) if has_vertex?(id1)
  adj_table[id2].update_weight(_create_node(id1), w) if has_vertex?(id2)
end
vertex?(id)
Alias for: has_vertex?
vertex_count() click to toggle source

Returns the number of vertices

# File lib/graphsrb/base_graph.rb, line 77
def vertex_count
  vertices.size
end
vertices() click to toggle source

Returns vertices of the graph

# File lib/graphsrb/base_graph.rb, line 17
def vertices
  vertex_array = []
  adj_table.keys.each do |id|
    vertex_array << _create_vertex(id)
  end
  vertex_array
end

Protected Instance Methods

_create_adjacency_list() click to toggle source
# File lib/graphsrb/base_graph.rb, line 149
def _create_adjacency_list
  Graphsrb::AdjacencyList.new
end
_create_edge(id1, id2, args={}) click to toggle source
# File lib/graphsrb/base_graph.rb, line 153
def _create_edge(id1, id2, args={})
  Graphsrb::Edge.new(id1, id2, args)
end
_create_node(vertex_id, args={}) click to toggle source
# File lib/graphsrb/base_graph.rb, line 145
def _create_node(vertex_id, args={})
  Graphsrb::Node.new(vertex_id, args)
end
_create_vertex(id) click to toggle source
# File lib/graphsrb/base_graph.rb, line 157
def _create_vertex(id)
  Graphsrb::Vertex.new(id)
end
vertices_must_be_different!(id1, id2) click to toggle source
# File lib/graphsrb/base_graph.rb, line 161
def vertices_must_be_different!(id1, id2)
  if id1 == id2
    raise Graphsrb::EdgeInitializationError, "Vertex id's must be different from each other"
  end
end