u
and v
If no path exists between u
and v
, it returns null. It is not
symmetric, i.e. we may have dist(u, v) != dist(v, u)
.
var g = new HashDigraph[Int]
g.add_arc(1, 2)
g.add_arc(2, 3)
g.add_arc(3, 4)
assert g.distance(1, 4) == 3
g.add_arc(1, 3)
assert g.distance(1, 4) == 2
assert g.distance(4, 1) == null
# Returns the distance between `u` and `v`
#
# If no path exists between `u` and `v`, it returns null. It is not
# symmetric, i.e. we may have `dist(u, v) != dist(v, u)`.
#
# ~~~
# var g = new HashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
# g.add_arc(3, 4)
# assert g.distance(1, 4) == 3
# g.add_arc(1, 3)
# assert g.distance(1, 4) == 2
# assert g.distance(4, 1) == null
# ~~~
fun distance(u, v: V): nullable Int
do
var queue = new List[V].from([u]).as_fifo
var dist = new HashMap[V, Int]
var visited = new HashSet[V]
var w: nullable V
dist[u] = 0
while not queue.is_empty do
w = queue.take
if not visited.has(w) then
visited.add(w)
if w == v then break
for wp in successors(w) do
if not dist.keys.has(wp) then
queue.add(wp)
dist[wp] = dist[w] + 1
end
end
end
end
return dist.get_or_null(v)
end
lib/graph/digraph.nit:525,2--561,4
# Returns the distance between `u` and `v`
#
# If `u` is the same as `v` return `1`
#
# ~~~
# var g = new ReflexiveHashDigraph[Int]
# g.add_arc(1, 2)
# g.add_arc(2, 3)
# g.add_arc(3, 4)
# assert g.distance(1, 1) == 1
# assert g.distance(2, 2) == 1
# ~~~
redef fun distance(u, v)
do
if has_arc(u, v) and u == v then return 1
return super
end
lib/graph/digraph.nit:1098,2--1114,4