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

Property definitions

graph $ Digraph :: distance
	# 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

graph $ ReflexiveHashDigraph :: distance
	# 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