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

Adds new edge to graph.



28
29
30
 
# File 'lib/ogr/graphs/graph.rb', line 28

def add(x, y, weight = 1)
  @g.add(push(x), push(y), weight)
end

#add_edge(edge) ⇒ Object

Adds new edge to graph.



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

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

#add_edges(edges) ⇒ Object

Adds new edges to graph.



33
34
35
36
37
38
39
 
# File 'lib/ogr/graphs/graph.rb', line 33

def add_edges(edges)
  if edges[0].is_a? Array
    edges.each { |e| add(e[0], e[1]) }
  else
    edges.each { |e| add(e.from, e.to, e.weight) }
  end
end

#degree(x) ⇒ Object

Returns vertex degree.



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

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

#each_edge(&block) ⇒ Object

Edge iterator



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

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

#each_vertex ⇒ Object

Vertex iterator



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

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

#edge?(x, y) ⇒ Boolean

Checks if two elements are connected.

Returns:

  • (Boolean) 


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

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

#get_edge(x, y) ⇒ Object

Returns Edge(x,y) if exist.



67
68
69
70
71
 
# File 'lib/ogr/graphs/graph.rb', line 67

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

#neighbors(x) ⇒ Object

Returns all neighbors for given vertex.



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

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

#remove(x, y) ⇒ Object

Removes connection between vertex x and y.



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

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

#vc ⇒ Object 



73
74
75
 
# File 'lib/ogr/graphs/graph.rb', line 73

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

#vertex_size ⇒ Object 



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

def vertex_size
  vertexes.size
end

#vertexes ⇒ Object 



77
78
79
 
# File 'lib/ogr/graphs/graph.rb', line 77

def vertexes
  @map.to_a
end