class RGL::DirectedAdjacencyGraph

Public Class Methods

[](*a) click to toggle source

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
new(edgelist_class = Set, *other_graphs) click to toggle source

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

add_edge(u, v) click to toggle source

See MutableGraph#add_edge.

    # 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
add_vertex(v) click to toggle source

See MutableGraph#add_vertex.

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
directed?() click to toggle source

Returns true.

   # File lib/rgl/adjacency.rb
73 def directed?
74   true
75 end
each_vertex(&b) click to toggle source

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
edgelist_class=(klass) click to toggle source

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
has_edge?(u, v) click to toggle source

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
has_vertex?(v) click to toggle source

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
initialize_copy(orig) click to toggle source

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
remove_edge(u, v) click to toggle source

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
remove_vertex(v) click to toggle source

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

basic_add_edge(u, v) click to toggle source
    # File lib/rgl/adjacency.rb
138 def basic_add_edge(u, v)
139   @vertices_dict[u].add(v)
140 end