Class: Mementus::Structure::AdjacencyList

Inherits:
Object
  • Object
show all
Defined in:
lib/mementus/structure/adjacency_list.rb

Instance Method Summary collapse

Constructor Details

#initialize(is_directed = true) ⇒ AdjacencyList

Returns a new instance of AdjacencyList.



6
7
8
9
 
# File 'lib/mementus/structure/adjacency_list.rb', line 6

def initialize(is_directed=true)
  @index = {}
  @is_directed = is_directed
end

Instance Method Details

#adjacent(id) ⇒ Object 



61
62
63
 
# File 'lib/mementus/structure/adjacency_list.rb', line 61

def adjacent(id)
  @index[id].to_a
end

#directed? ⇒ Boolean

Returns:

  • (Boolean) 


21
22
23
 
# File 'lib/mementus/structure/adjacency_list.rb', line 21

def directed?
  @is_directed
end

#each_edge(&blk) ⇒ Object 



65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/mementus/structure/adjacency_list.rb', line 65

def each_edge(&blk)
  if directed?
    nodes.each do |from|
      adjacent(from.id).each do |to|
        yield EdgeProxy.new(Edge.new(from: from, to: to), self)
      end
    end
  else
    raise 'Edge traversal unsupported for undirected graphs'
  end
end

#edges_count ⇒ Object 



15
16
17
18
19
 
# File 'lib/mementus/structure/adjacency_list.rb', line 15

def edges_count
  c = 0
  each_edge { c += 1 }
  c
end

#has_edge?(edge) ⇒ Boolean

Returns:

  • (Boolean) 


45
46
47
48
49
50
51
 
# File 'lib/mementus/structure/adjacency_list.rb', line 45

def has_edge?(edge)
  if edge.is_a?(Mementus::Edge) || edge.is_a?(Mementus::EdgeProxy)
    has_node?(edge.from.id) && @index[edge.from.id].include?(edge.to.id)
  else
    raise 'Edge IDs are not supported by this data structure'
  end
end

#has_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


37
38
39
40
41
42
43
 
# File 'lib/mementus/structure/adjacency_list.rb', line 37

def has_node?(node)
  if node.is_a?(Mementus::Node) || node.is_a?(Mementus::NodeProxy)
    @index.key?(node.id)
  else
    @index.key?(node)
  end
end

#node(id) ⇒ Object 



53
54
55
 
# File 'lib/mementus/structure/adjacency_list.rb', line 53

def node(id)
  NodeProxy.new(Node.new(id: id), self)
end

#nodes ⇒ Object 



57
58
59
 
# File 'lib/mementus/structure/adjacency_list.rb', line 57

def nodes
  @index.keys.map { |id| NodeProxy.new(Node.new(id: id), self) }
end

#nodes_count ⇒ Object 



11
12
13
 
# File 'lib/mementus/structure/adjacency_list.rb', line 11

def nodes_count
  @index.size
end

#set_edge(edge) ⇒ Object 



29
30
31
32
33
34
35
 
# File 'lib/mementus/structure/adjacency_list.rb', line 29

def set_edge(edge)
  set_node(edge.from) unless has_node?(edge.from.id)
  set_node(edge.to) unless has_node?(edge.to.id)

  @index[edge.from.id].add(edge.to.id)
  @index[edge.to.id].add(edge.from.id) unless directed?
end

#set_node(node) ⇒ Object 



25
26
27
 
# File 'lib/mementus/structure/adjacency_list.rb', line 25

def set_node(node)
  @index[node.id] ||= Set.new
end