class Ogr::Graph
Graph
class
Public Class Methods
new(edges = nil, store = :list)
click to toggle source
Create new graph from array of edges. Second parameter determines graph internal implementation: :list (Adjency List), :tri_matrix (Triangular Matrix), :matrix (Matrix).
# File lib/ogr/graphs/graph.rb, line 7 def initialize(edges = nil, store = :list) @map = IndexedSet.new case store when :list @g = GraphAsList.new(directed: false) when :matrix @g = GraphAsMatrix.new when :tri_matrix @g = GraphAsTriMatrix.new end add_edges(edges) if edges end
new_dense(edges)
click to toggle source
Create new graph from array of edges. Internally graph will be represented by Triangular Matrix.
# File lib/ogr/graphs/graph.rb, line 23 def self.new_dense(edges) new(edges, :tri_matrix) end
Public Instance Methods
add(x, y, weight = 1)
click to toggle source
Creates new edge in graph.
# File lib/ogr/graphs/graph.rb, line 28 def add(x, y, weight = 1) weight ||= 1 @g.add(push(x), push(y), weight) end
add_edge(edge)
click to toggle source
Adds new edge to graph.
# File lib/ogr/graphs/graph.rb, line 43 def add_edge(edge) add_edges([edge]) end
add_edges(edges)
click to toggle source
Adds new edges to graph.
# File lib/ogr/graphs/graph.rb, line 34 def add_edges(edges) if edges[0].is_a? Array edges.each { |e| add(e[0], e[1], e[2]) } else edges.each { |e| add(e.from, e.to, e.weight) } end end
degree(x)
click to toggle source
Returns vertex degree.
# File lib/ogr/graphs/graph.rb, line 58 def degree(x) @g.degree index(x) end
each_edge(&block)
click to toggle source
Edge
iterator
# File lib/ogr/graphs/graph.rb, line 80 def each_edge(&block) @g.each_edge(vertexes, &block) end
each_vertex() { |vertexes| ... }
click to toggle source
Vertex iterator
# File lib/ogr/graphs/graph.rb, line 75 def each_vertex vc.each { |v| yield vertexes[v] } end
edge?(x, y)
click to toggle source
Checks if two elements are connected.
# File lib/ogr/graphs/graph.rb, line 63 def edge?(x, y) @g.edge?(index(x), index(y)) end
edges()
click to toggle source
Returns array of all graph edges
# File lib/ogr/graphs/graph.rb, line 100 def edges arr = [] each_edge { |e| arr << e } arr end
get_edge(x, y)
click to toggle source
Returns Edge(x,y) if exist.
# File lib/ogr/graphs/graph.rb, line 68 def get_edge(x, y) return nil unless edge?(x, y) w = @g.get_edge(index(x), index(y)) Edge.new(x, y, w) if w end
index(x)
click to toggle source
Internal numeric representation of vertex
# File lib/ogr/graphs/graph.rb, line 107 def index(x) @map.index(x) end
neighbors(x)
click to toggle source
Returns all neighbors for given vertex.
# File lib/ogr/graphs/graph.rb, line 53 def neighbors(x) @g.neighbors(index(x)).map { |i| vertexes[i] } end
remove(x, y)
click to toggle source
Removes connection between vertex x and y.
# File lib/ogr/graphs/graph.rb, line 48 def remove(x, y) @g.remove(index(x), index(y)) end
vc()
click to toggle source
Vertex numbers
# File lib/ogr/graphs/graph.rb, line 95 def vc (0...vertexes.size) end
vertex_size()
click to toggle source
Vertex size
# File lib/ogr/graphs/graph.rb, line 90 def vertex_size vertexes.size end
vertexes()
click to toggle source
Returns array of all graph vertexes
# File lib/ogr/graphs/graph.rb, line 85 def vertexes @map.to_a end
Private Instance Methods
push(x)
click to toggle source
# File lib/ogr/graphs/graph.rb, line 113 def push(x) @map.push(x) end