Module: RGL::BidirectionalGraph

Includes:
Graph
Defined in:
lib/laser/third_party/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, #build_dfst, #condensation_graph, #depth_first_search, #depth_first_spanning_tree, #depth_first_visit, #dfs_iterator, #directed?, #dominance_frontier, #dominator_tree, #dotty, #each, #each_adjacent, #each_connected_component, #each_edge, #each_vertex, #edge_class, #edges, #edges_filtered_by, #empty?, #eql?, #has_vertex?, #implicit_graph, #iterated_dominance_frontier, #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

#all?, #any?, #chunk, #collect, #collect_concat, #count, #cycle, #detect, #drop, #drop_while, #each_cons, #each_entry, #each_slice, #each_with_index, #each_with_object, #entries, #find_index, #first, #flat_map, #grep, #group_by, #include?, #inject, #map, #max, #max_by, #min, #min_by, #minmax, #minmax_by, #none?, #one?, #partition, #reject, #reverse_each, #select, #slice_before, #sort, #sort_by, #take, #take_while, #to_a, #to_set, #zip

Instance Method Details

- (Object) degree(v)

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



35
36
37
 
# File 'lib/laser/third_party/rgl/bidirectional.rb', line 35

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

- (Object) each_in_neighbor(v, &blk)

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.



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

def each_in_neighbor(v, &blk)
  each_predecessor(v, &blk)
end

- (Object) in_degree(v)

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



27
28
29
30
31
 
# File 'lib/laser/third_party/rgl/bidirectional.rb', line 27

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