class RGL::DirectedAdjacencyGraph
Public Class Methods
Shortcut for creating a DirectedAdjacencyGraph:
RGL::DirectedAdjacencyGraph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s => "(1-2)(2-3)(2-4)(4-5)"
# File lib/rgl/adjacency.rb 29 def self.[](*a) 30 result = new 31 0.step(a.size - 1, 2) { |i| result.add_edge(a[i], a[i + 1]) } 32 result 33 end
Returns a new empty DirectedAdjacencyGraph
which has as its edgelist class the given class. The default edgelist class is Set, to ensure set semantics for edges and vertices.
If other graphs are passed as parameters their vertices and edges are added to the new graph.
# File lib/rgl/adjacency.rb 42 def initialize(edgelist_class = Set, *other_graphs) 43 @edgelist_class = edgelist_class 44 @vertices_dict = Hash.new 45 other_graphs.each do |g| 46 g.each_vertex { |v| add_vertex v } 47 g.each_edge { |v, w| add_edge v, w } 48 end 49 end
Public Instance Methods
# File lib/rgl/adjacency.rb 105 def add_edge(u, v) 106 add_vertex(u) # ensure key 107 add_vertex(v) # ensure key 108 basic_add_edge(u, v) 109 end
If the vertex is already in the graph (using eql?), the method does nothing.
# File lib/rgl/adjacency.rb 99 def add_vertex(v) 100 @vertices_dict[v] ||= @edgelist_class.new 101 end
Returns true.
# File lib/rgl/adjacency.rb 73 def directed? 74 true 75 end
Iterator for the keys of the vertices list hash.
# File lib/rgl/adjacency.rb 62 def each_vertex(&b) 63 @vertices_dict.each_key(&b) 64 end
Converts the adjacency list of each vertex to be of type klass. The class is expected to have a new constructor which accepts an enumerable as parameter.
# File lib/rgl/adjacency.rb 130 def edgelist_class=(klass) 131 @vertices_dict.keys.each do |v| 132 @vertices_dict[v] = klass.new @vertices_dict[v].to_a 133 end 134 end
Complexity is O(1), if a Set is used as adjacency list. Otherwise, complexity is O(out_degree(v)).
MutableGraph
interface.
# File lib/rgl/adjacency.rb 90 def has_edge?(u, v) 91 has_vertex?(u) && @vertices_dict[u].include?(v) 92 end
Complexity is O(1), because the vertices are kept in a Hash containing as values the lists of adjacent vertices of v.
# File lib/rgl/adjacency.rb 80 def has_vertex?(v) 81 @vertices_dict.has_key?(v) 82 end
Copy internal vertices_dict
# File lib/rgl/adjacency.rb 53 def initialize_copy(orig) 54 @vertices_dict = orig.instance_eval { @vertices_dict }.dup 55 @vertices_dict.keys.each do |v| 56 @vertices_dict[v] = @vertices_dict[v].dup 57 end 58 end
See MutableGraph::remove_edge.
# File lib/rgl/adjacency.rb 122 def remove_edge(u, v) 123 @vertices_dict[u].delete(v) unless @vertices_dict[u].nil? 124 end
See MutableGraph#remove_vertex
.
# File lib/rgl/adjacency.rb 113 def remove_vertex(v) 114 @vertices_dict.delete(v) 115 116 # remove v from all adjacency lists 117 @vertices_dict.each_value { |adjList| adjList.delete(v) } 118 end
Protected Instance Methods
# File lib/rgl/adjacency.rb 138 def basic_add_edge(u, v) 139 @vertices_dict[u].add(v) 140 end