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