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_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_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