Module: RGL::BidirectionalGraph

Includes:
Graph
Included in:
BidirectionalAdjacencyGraph
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, #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, #directed?, #dotty, #each, #each_adjacent, #each_connected_component, #each_edge, #each_vertex, #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

Instance Method Details

#degree(v) ⇒ int

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

Returns:

  • (int) 


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

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) 


24
25
26
27
 
# File 'lib/rgl/bidirectional.rb', line 24

def each_in_neighbor(v)
  raise NotImplementedError
  yield u
end

#has_in_edge?(u, v) ⇒ Boolean

Returns:

  • (Boolean)

Raises:

  • (NotImplementedError) 


31
32
33
 
# File 'lib/rgl/bidirectional.rb', line 31

def has_in_edge?(u, v)
  raise NotImplementedError
end

#in_degree(v) ⇒ int

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

Returns:

  • (int) 


46
47
48
49
50
 
# File 'lib/rgl/bidirectional.rb', line 46

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

#in_neighbors(v) ⇒ Object

Raises:

  • (NotImplementedError) 


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

def in_neighbors(v)
  raise NotImplementedError
end