Sha256: 45914daf095b30c026e75e22f59570958fb91023c186f54d472aa9509c693451
Contents?: true
Size: 1.77 KB
Versions: 7
Compression:
Stored size: 1.77 KB
Contents
require 'rgl/base'
module RGL
# 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.
#
module BidirectionalGraph
include Graph
# 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_.
#
def each_in_neighbor(v)
raise NotImplementedError
yield u
end
alias :each_out_neighbor :each_adjacent
def has_in_edge?(u, v)
raise NotImplementedError
end
alias :has_out_edge? :has_edge?
def in_neighbors(v)
raise NotImplementedError
end
alias :out_neighbors :adjacent_vertices
# Returns the number of in-edges (for directed graphs) or the number of
# incident edges (for undirected graphs) of vertex _v_.
# @return [int]
def in_degree(v)
r = 0
each_in_neighbor(v) { |u| r += 1 }
r
end
# 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]
def degree(v)
in_degree(v) + out_degree(v)
end
end
end
Version data entries
7 entries across 7 versions & 1 rubygems