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

[](*a) click to toggle source

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

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

   # 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

Public Instance Methods

add_edge(u, v) click to toggle source

@see MutableGraph#add_edge.

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

If the vertex is already in the graph (using eql?), the method does nothing. @see MutableGraph#add_vertex

   # File lib/rgl/adjacency.rb
93 def add_vertex(v)
94   @vertices_dict[v] ||= @edgelist_class.new
95 end
directed?() click to toggle source

@return true.

   # File lib/rgl/adjacency.rb
71 def directed?
72   true
73 end
each_adjacent(v, &b) click to toggle source

@see Graph#each_adjacent

   # 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
each_vertex(&b) click to toggle source

Iterator for the keys of the vertices list hash. @see Graph#each_vertex

   # File lib/rgl/adjacency.rb
59 def each_vertex(&b)
60   @vertices_dict.each_key(&b)
61 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. @param [Class] klass

    # 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
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)). @see Graph#has_edge?

   # File lib/rgl/adjacency.rb
86 def has_edge?(u, v)
87   has_vertex?(u) && @vertices_dict[u].include?(v)
88 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.

@see Graph#has_vertex

   # File lib/rgl/adjacency.rb
79 def has_vertex?(v)
80   @vertices_dict.has_key?(v)
81 end
initialize_copy(orig) click to toggle source

Copy internal vertices_dict

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

@see MutableGraph::remove_edge.

    # File lib/rgl/adjacency.rb
113 def remove_edge(u, v)
114   @vertices_dict[u].delete(v) unless @vertices_dict[u].nil?
115 end
remove_vertex(v) click to toggle source

@see MutableGraph#remove_vertex.

    # 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

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