Class: RGL::DirectedAdjacencyGraph

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

Overview

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.

Direct Known Subclasses

AdjacencyGraph, BidirectionalAdjacencyGraph

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, #bellman_ford_shortest_paths, #bfs_iterator, #bfs_search_tree_from, #bipartite?, #bipartite_sets, #condensation_graph, #depth_first_search, #depth_first_visit, #dfs_iterator, #dijkstra_shortest_path, #dijkstra_shortest_paths, #dotty, #each, #each_connected_component, #each_edge, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #implicit_graph, #maximum_flow, #num_edges, #out_degree, #path?, #prim_minimum_spanning_tree, #print_dotted_on, #reverse, #set_edge_options, #set_vertex_options, #size, #strongly_connected_components, #to_adjacency, #to_dot_graph, #to_s, #to_undirected, #topsort_iterator, #transitive_closure, #transitive_reduction, #vertex_id, #vertex_label, #vertices, #vertices_filtered_by, #write_to_graphic_file

Constructor Details

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

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.

Parameters:

  • edgelist_class (Class) (defaults to: Set)
  • other_graphs (Array[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
  @vertices_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

Examples:

RGL::DirectedAdjacencyGraph[1,2, 2,3, 2,4, 4,5].edges.to_a.to_s =>
  "(1-2)(2-3)(2-4)(4-5)"


28
29
30
31
32
 
# File 'lib/rgl/adjacency.rb', line 28

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 Also:



100
101
102
103
104
 
# File 'lib/rgl/adjacency.rb', line 100

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

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

See Also:



95
96
97
 
# File 'lib/rgl/adjacency.rb', line 95

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

#directed? ⇒ Boolean

Returns true.

Returns:

  • (Boolean) —

    true.



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

def directed?
  true
end

#each_adjacent(v, &b) ⇒ Object

See Also:



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

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

#each_vertex(&b) ⇒ Object

Iterator for the keys of the vertices list hash.

See Also:



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

def each_vertex(&b)
  @vertices_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 constructor which accepts an enumerable as parameter.

Parameters:

  • klass (Class) 


123
124
125
126
127
 
# File 'lib/rgl/adjacency.rb', line 123

def edgelist_class=(klass)
  @vertices_dict.keys.each do |v|
    @vertices_dict[v] = klass.new @vertices_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)).

Returns:

  • (Boolean)

See Also:



88
89
90
 
# File 'lib/rgl/adjacency.rb', line 88

def has_edge?(u, v)
  has_vertex?(u) && @vertices_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)

See Also:

  • Graph#has_vertex


81
82
83
 
# File 'lib/rgl/adjacency.rb', line 81

def has_vertex?(v)
  @vertices_dict.key?(v)
end

#initialize_copy(orig) ⇒ Object

Copy internal vertices_dict



52
53
54
55
56
57
 
# File 'lib/rgl/adjacency.rb', line 52

def initialize_copy(orig)
  @vertices_dict = orig.instance_eval { @vertices_dict }.dup
  @vertices_dict.keys.each do |v|
    @vertices_dict[v] = @vertices_dict[v].dup
  end
end

#remove_edge(u, v) ⇒ Object

See Also:

  • MutableGraph::remove_edge.


115
116
117
 
# File 'lib/rgl/adjacency.rb', line 115

def remove_edge(u, v)
  @vertices_dict[u].delete(v) unless @vertices_dict[u].nil?
end

#remove_vertex(v) ⇒ Object

See Also:



107
108
109
110
111
112
 
# File 'lib/rgl/adjacency.rb', line 107

def remove_vertex(v)
  @vertices_dict.delete(v)

  # remove v from all adjacency lists
  @vertices_dict.each_value { |adjList| adjList.delete(v) }
end