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:



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

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.



30
31
32
 
# File 'lib/rgl/implicit.rb', line 30

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.



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

def adjacent_iterator(&block)
  @adjacent_iterator = block
end

#directed? ⇒ Boolean

Returns the value of @directed.

Returns:

  • (Boolean) 


49
50
51
 
# File 'lib/rgl/implicit.rb', line 49

def directed?
  @directed
end

#each_adjacent(v, &block) ⇒ Object 



57
58
59
 
# File 'lib/rgl/implicit.rb', line 57

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

#each_edge(&block) ⇒ Object 



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

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

#each_vertex(&block) ⇒ Object 



53
54
55
 
# File 'lib/rgl/implicit.rb', line 53

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.



94
95
96
 
# File 'lib/rgl/implicit.rb', line 94

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.



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

def vertex_iterator(&block)
  @vertex_iterator = block
end