Utilities

deepcopy_adjlist(adjlist::Vector{Vector{T}})

Internal utility function for copying adjacency lists. On adjacency lists this function is more efficient than deepcopy for two reasons:

• As of Julia v1.0.2, deepcopy is not typestable.
• deepcopy needs to track all references when traversing a recursive data structure in order to ensure that references to the same location do need get assigned to different locations in the copy. Because we can assume that all lists in our adjacency list are different, we don't need to keep track of them.

If T is not a bitstype (e.g. BigInt), we use the standard deepcopy.

findall!(A, B)

Set the B[1:|I|] to I where I is the set of indices A[I] returns true.

Assumes length(B) >= |I|.

greedy_contiguous_partition(weight, required_partitions, num_items=length(weight))

Partition 1:num_items into at most required_partitions number of contiguous partitions with the objective of minimising the largest partition. The size of a partition is equal to the num of the weight of its elements. weight[i] > 0.

Performance

Time: O(numitems+requiredpartitions) Requires only one iteration over weight but may not output the optimal partition.

Implementation Notes

Balance(wt, left, right, n_items, n_part) = max(sum(wt[left:right])*(n_part-1), sum(wt[right+1:n_items])). Find right that minimises Balance(weight, 1, right, num_items, required_partitions). Set the first partition as 1:right. Repeat on indices right+1:num_items and one less partition.

insorted(item, collection)

Return true if item is in sorted collection collection.

Implementation Notes

Does not verify that collection is sorted.

isbounded(n)

Returns true if typemax(n) of an integer n exists.

isbounded(T)

Returns true if typemax(T) of a type T <: Integer exists.

optimal_contiguous_partition(weight, required_partitions, num_items=length(weight))

Partition 1:num_items into at most required_partitions number of contiguous partitions such that the largest partition is minimised. The size of a partition is equal to the sum of the weight of its elements. weight[i] > 0.

Performance

Time: O(num_items*log(sum(weight)))

Implementation Notes

Binary Search for the partitioning over [fld(sum(weight)-1, required_partitions), sum(weight)].

rng_from_rng_or_seed(rng, seed)

Helper function for randomized functions that can take a random generator as well as a seed argument.

Currently most randomized functions in this package take a seed integer as an argument. As modern randomized Julia functions tend to take a random generator instead of a seed, this function helps with the transition by taking rng and seed as an argument and always returning a random number generator. At least one of these arguments must be nothing.

sample!([rng, ]a, k)

Sample k element from array a without repetition and eventually excluding elements in exclude.

Optional Arguments

• exclude=(): elements in a to exclude from sampling.

Implementation Notes

Changes the order of the elements in a. For a non-mutating version, see sample.

sample(a, k; exclude=(), rng=nothing, seed=nothing)

Sample k element from AbstractVector a without repetition and eventually excluding elements in exclude.

Optional Arguments

• exclude=(): elements in a to exclude from sampling.
• rng=nothing: set the Random Number Generator.
• seed=nothing: seed the Random Number Generator with this value.

Implementation Notes

Unlike sample!, does not produce side effects.

unweighted_contiguous_partition(num_items, required_partitions)

Partition 1:num_items into required_partitions number of partitions such that the difference in length of the largest and smallest partition is at most 1.

Performance

Time: O(required_partitions)