Parent

Included Modules

Files

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, line 29
def self.[] (*a)
  result = new
  0.step(a.size-1, 2) { |i| result.add_edge(a[i], a[i+1]) }
  result
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, line 41
def initialize (edgelist_class = Set, *other_graphs)
  @edgelist_class = edgelist_class
  @vertice_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

add_edge(u, v) click to toggle source

See MutableGraph#add_edge.

# File lib/rgl/adjacency.rb, line 104
def add_edge (u, v)
  add_vertex(u)                         # ensure key
  add_vertex(v)                         # ensure key
  basic_add_edge(u, v)
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, line 98
def add_vertex (v)
  @vertice_dict[v] ||= @edgelist_class.new
end
directed?() click to toggle source

Returns true.

# File lib/rgl/adjacency.rb, line 72
def directed?
  true
end
each_vertex(&b) click to toggle source

Iterator for the keys of the vertice list hash.

# File lib/rgl/adjacency.rb, line 60
def each_vertex (&b)
  @vertice_dict.each_key(&b)
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 contructor which accepts an enumerable as parameter.

# File lib/rgl/adjacency.rb, line 129
def edgelist_class=(klass)
  @vertice_dict.keys.each do |v|
     @vertice_dict[v] = klass.new @vertice_dict[v].to_a
  end
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, line 89
def has_edge? (u, v)
  has_vertex?(u) and @vertice_dict[u].include?(v)
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, line 79
def has_vertex? (v)
  @vertice_dict.has_key?(v)
end
initialize_copy(orig) click to toggle source

Copy internal vertice_dict

# File lib/rgl/adjacency.rb, line 51
def initialize_copy(orig)
  @vertice_dict = orig.instance_eval{@vertice_dict}.dup
  @vertice_dict.keys.each do |v|
    @vertice_dict[v] = @vertice_dict[v].dup
  end
end
remove_edge(u, v) click to toggle source

See MutableGraph::remove_edge.

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

See MutableGraph#remove_vertex.

# File lib/rgl/adjacency.rb, line 112
def remove_vertex (v)
  @vertice_dict.delete(v)
      
  # remove v from all adjacency lists

  @vertice_dict.each_value { |adjList| adjList.delete(v) }
end

Protected Instance Methods

basic_add_edge(u, v) click to toggle source
# File lib/rgl/adjacency.rb, line 137
def basic_add_edge (u, v)
  @vertice_dict[u].add(v)
end

[Validate]

Generated with the Darkfish Rdoc Generator 2.