Class: Yargraph::UndirectedGraph::EdgeSet

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/yargraph.rb

Overview

Contained within is a Hash of vertex1 => Set: vertex2, vertex3, .. If vertex1 => Set: vertex2, then vertex2 => Set: vertex1, ..

Instance Method Summary collapse

Constructor Details

#initialize ⇒ EdgeSet

Returns a new instance of EdgeSet.



18
19
20
 
# File 'lib/yargraph.rb', line 18

def initialize
  @edges = {}
end

Instance Method Details

#[](vertex) ⇒ Object

Return a Set of vertices that are neighbours of the given vertex, or an empty Set if there are none



38
39
40
41
42
43
44
45
 
# File 'lib/yargraph.rb', line 38

def [](vertex)
  e = @edges[vertex]
  if e
    return e
  else
    return Set.new
  end
end

#add_edge(v1, v2) ⇒ Object 



22
23
24
25
26
27
 
# File 'lib/yargraph.rb', line 22

def add_edge(v1, v2)
  @edges[v1] ||= Set.new
  @edges[v2] ||= Set.new
  @edges[v1] << v2
  @edges[v2] << v1
end

#delete(v1, v2) ⇒ Object 



79
80
81
82
83
84
85
 
# File 'lib/yargraph.rb', line 79

def delete(v1,v2)
  @edges[v1].delete v2
  @edges[v2].delete v1

  @edges.delete v1 if @edges[v1].empty?
  @edges.delete v2 if @edges[v2].empty?
end

#each ⇒ Object 



47
48
49
50
51
52
53
54
55
 
# File 'lib/yargraph.rb', line 47

def each
  already_seen_vertices = Set.new
  @edges.each do |v1, neighbours|
    neighbours.each do |v2|
      yield v1, v2 unless already_seen_vertices.include?(v2)
    end
    already_seen_vertices << v1
  end
end

#edge?(v1, v2) ⇒ Boolean

Is there an edge between v1 and v2?

Returns:

  • (Boolean) 


66
67
68
69
70
 
# File 'lib/yargraph.rb', line 66

def edge?(v1,v2)
  e = @edges[v1]
  return false if e.nil?
  return e.include?(v2)
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


72
73
74
75
76
77
 
# File 'lib/yargraph.rb', line 72

def empty?
  @edges.each do |v, neighbours|
    return false unless neighbours.empty?
  end
  return true
end

#length ⇒ Object 



57
58
59
60
61
62
63
 
# File 'lib/yargraph.rb', line 57

def length
  count = 0
  each do
    count += 1
  end
  return count
end

#neighbours(v) ⇒ Object

Return an array of neighbours



30
31
32
33
34
 
# File 'lib/yargraph.rb', line 30

def neighbours(v)
  e = @edges[v]
  return [] if e.nil?
  return e.to_a
end

#pop ⇒ Object

Remove and return an arbitrary edge from the Set, or nil if there are no edges remaining. Returned is a 2 element Array of vertex1, vertex2



91
92
93
94
95
96
97
98
 
# File 'lib/yargraph.rb', line 91

def pop
  pp self
  each do |v1, v2|
    delete v1, v2
    return [v1, v2]
  end
  return nil
end

#to_s ⇒ Object 



100
101
102
 
# File 'lib/yargraph.rb', line 100

def to_s
  "EdgeSet: #{collect{|v1,v2| [v1,v2] }.join(',') }"
end