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, line 29 def self.[](*a) result = new 0.step(a.size - 1, 2) { |i| result.add_edge(a[i], a[i + 1]) } result 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, line 42 def initialize(edgelist_class = Set, *other_graphs) @edgelist_class = edgelist_class @vertices_dict = Hash.new other_graphs.each do |g| g.each_vertex { |v| add_vertex v } g.each_edge { |v, w| add_edge v, w } end end
Public Instance Methods
See RGL::MutableGraph#add_edge.
# File lib/rgl/adjacency.rb, line 105 def add_edge(u, v) add_vertex(u) # ensure key add_vertex(v) # ensure key basic_add_edge(u, v) end
See RGL::MutableGraph#add_vertex.
If the vertex is already in the graph (using eql?), the method does nothing.
# File lib/rgl/adjacency.rb, line 99 def add_vertex(v) @vertices_dict[v] ||= @edgelist_class.new end
Returns true.
# File lib/rgl/adjacency.rb, line 73 def directed? true end
Iterator for the keys of the vertices list hash.
# File lib/rgl/adjacency.rb, line 62 def each_vertex(&b) @vertices_dict.each_key(&b) 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, line 130 def edgelist_class=(klass) @vertices_dict.keys.each do |v| @vertices_dict[v] = klass.new @vertices_dict[v].to_a end 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, line 90 def has_edge? (u, v) has_vertex?(u) && @vertices_dict[u].include?(v) 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, line 80 def has_vertex? (v) @vertices_dict.has_key?(v) end
Copy internal vertices_dict
# File lib/rgl/adjacency.rb, line 53 def initialize_copy(orig) @vertices_dict = orig.instance_eval { @vertices_dict }.dup @vertices_dict.keys.each do |v| @vertices_dict[v] = @vertices_dict[v].dup end end
See MutableGraph::remove_edge.
# File lib/rgl/adjacency.rb, line 122 def remove_edge(u, v) @vertices_dict[u].delete(v) unless @vertices_dict[u].nil? end
See RGL::MutableGraph#remove_vertex.
# File lib/rgl/adjacency.rb, line 113 def remove_vertex(v) @vertices_dict.delete(v) # remove v from all adjacency lists @vertices_dict.each_value { |adjList| adjList.delete(v) } end
Protected Instance Methods
# File lib/rgl/adjacency.rb, line 138 def basic_add_edge(u, v) @vertices_dict[u].add(v) end