Module: RGL::BidirectionalGraph

Includes:
Graph
Defined in:
lib/rgl/bidirectional.rb

Overview

BGL defines the concept BidirectionalGraph as follows:

The BidirectionalGraph concept refines IncidenceGraph and adds the requirement for efficient access to the in-edges of each vertex. This concept is separated from IncidenceGraph because, for directed graphs, efficient access to in-edges typically requires more storage space, and many algorithms do not require access to in-edges. For undirected graphs, this is not an issue; because the in_edges() and out_edges() functions are the same, they both return the edges incident to the vertex.

Instance Method Summary collapse

Methods included from Graph

#acyclic?, #adjacent_vertices, #bfs_iterator, #bfs_search_tree_from, #condensation_graph, #depth_first_search, #depth_first_visit, #dfs_iterator, #directed?, #dotty, #each, #each_adjacent, #each_connected_component, #each_edge, #each_vertex, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #has_vertex?, #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

Instance Method Details

#degree(v) ⇒ Object

Returns the number of in-edges plus out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v.



36
37
38
 
# File 'lib/rgl/bidirectional.rb', line 36

def degree (v)
  in_degree(v) + out_degree(v)
end

#each_in_neighbor(v) {|u| ... } ⇒ Object

Iterator providing access to the in-edges (for directed graphs) or incident edges (for undirected graphs) of vertex v. For both directed and undirected graphs, the target of an out-edge is required to be vertex v and the source is required to be a vertex that is adjacent to v.

Yields:

  • (u)

Raises:

  • (NotImplementedError) 


21
22
23
24
 
# File 'lib/rgl/bidirectional.rb', line 21

def each_in_neighbor (v)
  raise NotImplementedError
  yield u
end

#in_degree(v) ⇒ Object

Returns the number of in-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v.



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

def in_degree (v)
  r = 0;
  each_in_neighbor(v) { |u| r += 1}
  r
end