Class: DS::GraphAsList

Inherits:
Object
  • Object
show all
Defined in:
lib/ds/graphs/graph_as_list.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ GraphAsList

Returns a new instance of GraphAsList.



4
5
6
7
8
 
# File 'lib/ds/graphs/graph_as_list.rb', line 4

def initialize
  @store = {}	 # the graph // {node => { edge1 => weight, edge2 => weight}, node2 => ...
  @nodes = Array.new		 
  @INFINITY = 1 << 64 	 
end

Instance Method Details

#add_edge(x, y, w = nil) ⇒ Object

s= source, t= target, w= weight



10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
# File 'lib/ds/graphs/graph_as_list.rb', line 10

def add_edge(x,y,w=nil) 		# s= source, t= target, w= weight
  if (not @store.has_key?(x))	 
    @store[x] = {y=>w}		 
  else
    @store[x][y] = w         
  end

  # Begin code for non directed graph (inserts the other edge too)

  if (not @store.has_key?(y))
    @store[y] = {x=>w}
  else
    @store[y][x] = w
  end

  # End code for non directed graph (ie. deleteme if you want it directed)

  if (not @nodes.include?(x))	
    @nodes << x
  end
  if (not @nodes.include?(y))
    @nodes << y
  end	
end

#add_edges(edges) ⇒ Object 



35
36
37
38
39
 
# File 'lib/ds/graphs/graph_as_list.rb', line 35

def add_edges(edges)
  for e in edges
    add(e.from,e.to)   
  end    
end

#each_vertex ⇒ Object 



41
42
43
44
45
 
# File 'lib/ds/graphs/graph_as_list.rb', line 41

def each_vertex
  @adj_matrix.keys.each do |vertex|
    yield vertex
  end
end