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.



4
5
6
7
 
# File 'lib/mementus/structure/adjacency_list.rb', line 4

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

Instance Method Details

#adjacent(id) ⇒ Object 



51
52
53
 
# File 'lib/mementus/structure/adjacency_list.rb', line 51

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

#directed? ⇒ Boolean

Returns:

  • (Boolean) 


19
20
21
 
# File 'lib/mementus/structure/adjacency_list.rb', line 19

def directed?
  @is_directed
end

#each_adjacent(id, &blk) ⇒ Object 



59
60
61
 
# File 'lib/mementus/structure/adjacency_list.rb', line 59

def each_adjacent(id, &blk)
  @index[id].each(&blk)
end

#each_edge(&blk) ⇒ Object 



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

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

#each_node(&blk) ⇒ Object 



55
56
57
 
# File 'lib/mementus/structure/adjacency_list.rb', line 55

def each_node(&blk)
  nodes.each(&blk)
end

#edges_count ⇒ Object 



13
14
15
16
17
 
# File 'lib/mementus/structure/adjacency_list.rb', line 13

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

#has_edge?(edge) ⇒ Boolean

Returns:

  • (Boolean) 


39
40
41
 
# File 'lib/mementus/structure/adjacency_list.rb', line 39

def has_edge?(edge)
  has_node?(edge.from) && @index[edge.from.id].include?(edge.to.id)
end

#has_node?(node) ⇒ Boolean

Returns:

  • (Boolean) 


35
36
37
 
# File 'lib/mementus/structure/adjacency_list.rb', line 35

def has_node?(node)
  @index.key?(node.id)
end

#node(id) ⇒ Object 



43
44
45
 
# File 'lib/mementus/structure/adjacency_list.rb', line 43

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

#nodes ⇒ Object 



47
48
49
 
# File 'lib/mementus/structure/adjacency_list.rb', line 47

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

#nodes_count ⇒ Object 



9
10
11
 
# File 'lib/mementus/structure/adjacency_list.rb', line 9

def nodes_count
  @index.size
end

#set_edge(edge) ⇒ Object 



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

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

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

#set_node(node) ⇒ Object 



23
24
25
 
# File 'lib/mementus/structure/adjacency_list.rb', line 23

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