class RGL::DirectedAdjacencyGraph
The DirectedAdjacencyGraph
class implements a generalized adjacency list graph structure. An AdjacencyGraph
is basically a two-dimensional structure (ie, a list of lists). Each element of the first dimension represents a vertex. Each of the vertices contains a one-dimensional structure that is the list of all adjacent vertices.
The class for representing the adjacency list of a vertex is, by default, a Set
. This can be configured by the client, however, when an AdjacencyGraph
is created.
Public Class Methods
Source
# File lib/rgl/adjacency.rb 26 def self.[](*a) 27 result = new 28 0.step(a.size - 1, 2) { |i| result.add_edge(a[i], a[i + 1]) } 29 result 30 end
Shortcut for creating a DirectedAdjacencyGraph
@example
RGL::DirectedAdjacencyGraph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s => "(1-2)(2-3)(2-4)(4-5)"
Source
# File lib/rgl/adjacency.rb 39 def initialize(edgelist_class = Set, *other_graphs) 40 @edgelist_class = edgelist_class 41 @vertices_dict = Hash.new 42 other_graphs.each do |g| 43 g.each_vertex { |v| add_vertex v } 44 g.each_edge { |v, w| add_edge v, w } 45 end 46 end
The new empty graph 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. @param [Class] edgelist_class @param [Array] other_graphs
Public Instance Methods
Source
# File lib/rgl/adjacency.rb 98 def add_edge(u, v) 99 add_vertex(u) # ensure key 100 add_vertex(v) # ensure key 101 basic_add_edge(u, v) 102 end
@see MutableGraph#add_edge
.
Source
# File lib/rgl/adjacency.rb 93 def add_vertex(v) 94 @vertices_dict[v] ||= @edgelist_class.new 95 end
If the vertex is already in the graph (using eql?
), the method does nothing. @see MutableGraph#add_vertex
Source
# File lib/rgl/adjacency.rb 64 def each_adjacent(v, &b) 65 adjacency_list = (@vertices_dict[v] or raise NoVertexError, "No vertex #{v}.") 66 adjacency_list.each(&b) 67 end
@see Graph#each_adjacent
Source
# File lib/rgl/adjacency.rb 59 def each_vertex(&b) 60 @vertices_dict.each_key(&b) 61 end
Iterator for the keys of the vertices list hash. @see Graph#each_vertex
Source
# File lib/rgl/adjacency.rb 121 def edgelist_class=(klass) 122 @vertices_dict.keys.each do |v| 123 @vertices_dict[v] = klass.new @vertices_dict[v].to_a 124 end 125 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. @param [Class] klass
Source
# File lib/rgl/adjacency.rb 86 def has_edge?(u, v) 87 has_vertex?(u) && @vertices_dict[u].include?(v) 88 end
Complexity is O(1), if a Set is used as adjacency list. Otherwise, complexity is O(out_degree(v)). @see Graph#has_edge?
Source
# File lib/rgl/adjacency.rb 79 def has_vertex?(v) 80 @vertices_dict.has_key?(v) 81 end
Complexity is O(1), because the vertices are kept in a Hash
containing as values the lists of adjacent vertices of v.
@see Graph#has_vertex
Source
# File lib/rgl/adjacency.rb 50 def initialize_copy(orig) 51 @vertices_dict = orig.instance_eval { @vertices_dict }.dup 52 @vertices_dict.keys.each do |v| 53 @vertices_dict[v] = @vertices_dict[v].dup 54 end 55 end
Copy internal vertices_dict
Source
# File lib/rgl/adjacency.rb 113 def remove_edge(u, v) 114 @vertices_dict[u].delete(v) unless @vertices_dict[u].nil? 115 end
@see MutableGraph::remove_edge.
Source
# File lib/rgl/adjacency.rb 105 def remove_vertex(v) 106 @vertices_dict.delete(v) 107 108 # remove v from all adjacency lists 109 @vertices_dict.each_value { |adjList| adjList.delete(v) } 110 end
Protected Instance Methods
Source
# File lib/rgl/adjacency.rb 129 def basic_add_edge(u, v) 130 @vertices_dict[u].add(v) 131 end