Class: RGL::DirectedAdjacencyGraph

Inherits:
Object
  • Object
show all
Includes:
MutableGraph
Defined in:
lib/rgl/adjacency.rb

Direct Known Subclasses

AdjacencyGraph

Class Method Summary collapse

Instance Method Summary collapse

Methods included from MutableGraph

#add_edges, #add_vertices, #cycles, #cycles_with_vertex, #from_graphxml, #remove_vertices

Methods included from Graph

#acyclic?, #adjacent_vertices, #bfs_iterator, #bfs_search_tree_from, #condensation_graph, #depth_first_search, #depth_first_visit, #dfs_iterator, #dotty, #each, #each_connected_component, #each_edge, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #implicit_graph, #num_edges, #out_degree, #print_dotted_on, #reverse, #size, #strongly_connected_components, #to_adjacency, #to_dot_graph, #to_s, #to_undirected, #topsort_iterator, #transitive_closure, #transitive_reduction, #vertices, #vertices_filtered_by, #write_to_graphic_file

Methods included from Enumerable

#length

Constructor Details

#initialize(edgelist_class = Set, *other_graphs) ⇒ DirectedAdjacencyGraph

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.



41
42
43
44
45
46
47
48
 
# 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

Class Method Details

.[](*a) ⇒ Object

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)"



29
30
31
32
33
 
# 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

Instance Method Details

#add_edge(u, v) ⇒ Object

See MutableGraph#add_edge.



104
105
106
107
108
 
# 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) ⇒ Object

See MutableGraph#add_vertex.

If the vertex is already in the graph (using eql?), the method does nothing.



98
99
100
 
# File 'lib/rgl/adjacency.rb', line 98

def add_vertex (v)
  @vertice_dict[v] ||= @edgelist_class.new
end

#directed? ⇒ Boolean

Returns true.

Returns:

  • (Boolean) 


72
73
74
 
# File 'lib/rgl/adjacency.rb', line 72

def directed?
  true
end

#each_adjacent(v, &b) ⇒ Object

:nodoc:



64
65
66
67
68
 
# File 'lib/rgl/adjacency.rb', line 64

def each_adjacent (v, &b)			# :nodoc:
  adjacency_list = (@vertice_dict[v] or
    raise NoVertexError, "No vertex #{v}.")
  adjacency_list.each(&b)
end

#each_vertex(&b) ⇒ Object

Iterator for the keys of the vertice list hash.



60
61
62
 
# File 'lib/rgl/adjacency.rb', line 60

def each_vertex (&b)
  @vertice_dict.each_key(&b)
end

#edgelist_class=(klass) ⇒ Object

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.



129
130
131
132
133
 
# 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) ⇒ Boolean

Complexity is O(1), if a Set is used as adjacency list. Otherwise, complexity is O(out_degree(v)).

MutableGraph interface.

Returns:

  • (Boolean) 


89
90
91
 
# 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) ⇒ Boolean

Complexity is O(1), because the vertices are kept in a Hash containing as values the lists of adjacent vertices of v.

Returns:

  • (Boolean) 


79
80
81
 
# File 'lib/rgl/adjacency.rb', line 79

def has_vertex? (v)
  @vertice_dict.has_key?(v)
end

#initialize_copy(orig) ⇒ Object

Copy internal vertice_dict



51
52
53
54
55
56
 
# 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) ⇒ Object

See MutableGraph::remove_edge.



122
123
124
 
# 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) ⇒ Object

See MutableGraph#remove_vertex.



112
113
114
115
116
117
118
 
# 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