Class: RGL::ImplicitGraph

Inherits:
Object
  • Object
show all
Includes:
Graph
Defined in:
lib/rgl/implicit.rb

Overview

An ImplicitGraph provides a handy way to define graphs on the fly, using two blocks for the two iterators defining a graph. Other examples are given by the methods Graph#vertices_filtered_by and Graph#edges_filtered_by, which can be applied to any graph.

Examples:

# A directed cyclic graph, with five vertices can be created as follows:
g = RGL::ImplicitGraph.new do |g|
  g.vertex_iterator { |b| 0.upto(4,&b) }
  g.adjacent_iterator { |x, b| b.call((x+1)%5) }
  g.directed = true
end

g.to_s # => "(0-1)(1-2)(2-3)(3-4)(4-0)"

Constant Summary collapse

EMPTY_VERTEX_ITERATOR = 
proc { |b| }
EMPTY_NEIGHBOR_ITERATOR = 
proc { |x, b| }

Instance Attribute Summary collapse

Instance Method Summary collapse

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, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #has_edge?, #has_vertex?, #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 {|_self| ... } ⇒ ImplicitGraph

Create a new RGL::ImplicitGraph, which is empty by default. The caller should configure the graph using vertex and neighbor iterators. If the graph is directed, the client should set @directed to true. The default value for @directed is false.

Yields:

  • (_self)

Yield Parameters:



42
43
44
45
46
47
 
# File 'lib/rgl/implicit.rb', line 42

def initialize
  @directed          = false
  @vertex_iterator   = EMPTY_VERTEX_ITERATOR
  @adjacent_iterator = EMPTY_NEIGHBOR_ITERATOR
  yield self if block_given? # Let client overwrite defaults.
end

Instance Attribute Details

#directed=(value) ⇒ Object (writeonly)

Sets the attribute directed

Parameters:

  • value —

    the value to set the attribute directed to.



32
33
34
 
# File 'lib/rgl/implicit.rb', line 32

def directed=(value)
  @directed = value
end

Instance Method Details

#adjacent_iterator(&block) ⇒ Object

Sets the adjacent_iterator to block, which must be a block of two parameters:

The first parameter is the vertex the neighbors of which are to be
traversed.

The second is the block which will be called for each neighbor
of this vertex.



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

def adjacent_iterator(&block)
  @adjacent_iterator = block
end

#directed? ⇒ Boolean

Returns the value of @directed.

Returns:

  • (Boolean) 


51
52
53
 
# File 'lib/rgl/implicit.rb', line 51

def directed?
  @directed
end

#each_adjacent(v, &block) ⇒ Object 



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

def each_adjacent(v, &block)
  @adjacent_iterator.call(v, block)
end

#each_edge(&block) ⇒ Object 



63
64
65
66
67
68
69
 
# File 'lib/rgl/implicit.rb', line 63

def each_edge(&block)
  if defined? @edge_iterator
    @edge_iterator.call(block)
  else
    super # use default implementation
  end
end

#each_vertex(&block) ⇒ Object 



55
56
57
 
# File 'lib/rgl/implicit.rb', line 55

def each_vertex(&block)
  @vertex_iterator.call(block)
end

#edge_iterator(&block) ⇒ Object

Sets the edge_iterator to block, which must be a block of two parameters: The first parameter is the source of the edges; the second is the target of the edge.



96
97
98
 
# File 'lib/rgl/implicit.rb', line 96

def edge_iterator(&block)
  @edge_iterator = block
end

#vertex_iterator(&block) ⇒ Object

Sets the vertex_iterator to block, which must be a block of one parameter which again is the block called by #each_vertex.



75
76
77
 
# File 'lib/rgl/implicit.rb', line 75

def vertex_iterator(&block)
  @vertex_iterator = block
end