module RGL::BidirectionalGraph
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.
Public Instance Methods
Returns the number of in-edges plus out-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v. @return [int]
# File lib/rgl/bidirectional.rb 55 def degree(v) 56 in_degree(v) + out_degree(v) 57 end
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.
# File lib/rgl/bidirectional.rb 24 def each_in_neighbor(v) 25 raise NotImplementedError 26 yield u 27 end
# File lib/rgl/bidirectional.rb 31 def has_in_edge?(u, v) 32 raise NotImplementedError 33 end
Returns the number of in-edges (for directed graphs) or the number of incident edges (for undirected graphs) of vertex v. @return [int]
# File lib/rgl/bidirectional.rb 46 def in_degree(v) 47 r = 0 48 each_in_neighbor(v) { |u| r += 1 } 49 r 50 end
# File lib/rgl/bidirectional.rb 37 def in_neighbors(v) 38 raise NotImplementedError 39 end