uneven_block distribution does not handle empty processes correctly

[alexrobomind]

When creating an instance of uneven_block with the distribution [1, 0, 1] then the implementation incorrectly returns process id 1 (counting from 0) to be the owner of element id 1 (counting from zero), because the local starts of processes 1 and 2 are identical (local starts would be [0, 1, 1, 2] in this case).

In general, the implementation incorrectly assigns elements belonging to the first owner after one or more adjacent empty owners to the first of those empty ones.

I would suggest to change the implementation from

graph_parallel/include/boost/graph/parallel/distribution.hpp

Lines 225 to 226 in 22385cc

	size_vector::const_iterator lb = std::lower_bound(local_starts.begin(), local_starts.end(), (std::size_t) i);
	return ((SizeType)(*lb) == i ? lb : --lb) - local_starts.begin();

to

size_vector::const_iterator ub = std::upper_bound(local_starts.begin(), local_starts.end(), (std::size_t) i);
return (--ub) - local_starts.begin();

Edit: Corrected mistake as pointed out below.

[fearsomepirate]

I just ran into this bug, can confirm. I have a graph on 3 processes with 4/0/4 distribution, and it crashes due to incorrectly converting index value of 4 to {local, owner} = {0,1}.

By the way, that fix should say (--ub).

[alexrobomind]

Oops. Edited.