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


39
40
41
42
43
44
45
46
 
# File 'lib/rgl/adjacency.rb', line 39

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


26
27
28
29
30
 
# File 'lib/rgl/adjacency.rb', line 26

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:



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

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:



93
94
95
 
# File 'lib/rgl/adjacency.rb', line 93

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

#directed? ⇒ Boolean

Returns true.

Returns:

  • (Boolean) —

    true.



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

def directed?
  true
end

#each_adjacent(v, &b) ⇒ Object

See Also:



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

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:



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

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) 


121
122
123
124
125
 
# File 'lib/rgl/adjacency.rb', line 121

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:



86
87
88
 
# File 'lib/rgl/adjacency.rb', line 86

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


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

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

#initialize_copy(orig) ⇒ Object

Copy internal vertices_dict



50
51
52
53
54
55
 
# File 'lib/rgl/adjacency.rb', line 50

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.


113
114
115
 
# File 'lib/rgl/adjacency.rb', line 113

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

#remove_vertex(v) ⇒ Object

See Also:



105
106
107
108
109
110
 
# File 'lib/rgl/adjacency.rb', line 105

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

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