Class: Ogr::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/ogr/graphs/graph.rb

Overview

Graph class

Direct Known Subclasses

Digraph

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(edges = nil, store = :list) ⇒ Graph

Create new graph from array of edges. Second parameter determines graph internal implementation: :list (Adjency List), :tri_matrix (Triangular Matrix), :matrix (Matrix).



7
8
9
10
11
12
13
14
15
16
17
18
19
 
# 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

Class Method Details

.new_dense(edges) ⇒ Object

Create new graph from array of edges. Internally graph will be represented by Triangular Matrix.



23
24
25
 
# File 'lib/ogr/graphs/graph.rb', line 23

def self.new_dense(edges)
  new(edges, :tri_matrix)
end

Instance Method Details

#add(x, y, weight = 1) ⇒ Object

Creates new edge in graph.



28
29
30
31
 
# 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) ⇒ Object

Adds new edge to graph.



43
44
45
 
# File 'lib/ogr/graphs/graph.rb', line 43

def add_edge(edge)
  add_edges([edge])
end

#add_edges(edges) ⇒ Object

Adds new edges to graph.



34
35
36
37
38
39
40
 
# 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) ⇒ Object

Returns vertex degree.



58
59
60
 
# File 'lib/ogr/graphs/graph.rb', line 58

def degree(x)
  @g.degree index(x)
end

#each_edge(&block) ⇒ Object

Edge iterator



80
81
82
 
# File 'lib/ogr/graphs/graph.rb', line 80

def each_edge(&block)
  @g.each_edge(vertexes, &block)
end

#each_vertex ⇒ Object

Vertex iterator



75
76
77
 
# File 'lib/ogr/graphs/graph.rb', line 75

def each_vertex
  vc.each { |v| yield vertexes[v] }
end

#edge?(x, y) ⇒ Boolean

Checks if two elements are connected.

Returns:

  • (Boolean) 


63
64
65
 
# File 'lib/ogr/graphs/graph.rb', line 63

def edge?(x, y)
  @g.edge?(index(x), index(y))
end

#edges ⇒ Object

Returns array of all graph edges



100
101
102
103
104
 
# File 'lib/ogr/graphs/graph.rb', line 100

def edges
  arr = []
  each_edge { |e| arr << e }
  arr
end

#get_edge(x, y) ⇒ Object

Returns Edge(x,y) if exist.



68
69
70
71
72
 
# 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) ⇒ Object

Internal numeric representation of vertex



107
108
109
 
# File 'lib/ogr/graphs/graph.rb', line 107

def index(x)
  @map.index(x)
end

#neighbors(x) ⇒ Object

Returns all neighbors for given vertex.



53
54
55
 
# File 'lib/ogr/graphs/graph.rb', line 53

def neighbors(x)
  @g.neighbors(index(x)).map { |i| vertexes[i] }
end

#remove(x, y) ⇒ Object

Removes connection between vertex x and y.



48
49
50
 
# File 'lib/ogr/graphs/graph.rb', line 48

def remove(x, y)
  @g.remove(index(x), index(y))
end

#vc ⇒ Object

Vertex numbers



95
96
97
 
# File 'lib/ogr/graphs/graph.rb', line 95

def vc
  (0...vertexes.size)
end

#vertex_size ⇒ Object

Vertex size



90
91
92
 
# File 'lib/ogr/graphs/graph.rb', line 90

def vertex_size
  vertexes.size
end

#vertexes ⇒ Object

Returns array of all graph vertexes



85
86
87
 
# File 'lib/ogr/graphs/graph.rb', line 85

def vertexes
  @map.to_a
end