# Utilities

Here are a few useful functions that didn't fit in the other categories.

## Index

`Graphs.deepcopy_adjlist`

`Graphs.findall!`

`Graphs.greedy_contiguous_partition`

`Graphs.insorted`

`Graphs.isbounded`

`Graphs.isbounded`

`Graphs.optimal_contiguous_partition`

`Graphs.rng_from_rng_or_seed`

`Graphs.sample`

`Graphs.sample!`

`Graphs.unweighted_contiguous_partition`

## Full docs

`Graphs.deepcopy_adjlist`

— Method`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`

.

`Graphs.findall!`

— Method`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|`

.

`Graphs.greedy_contiguous_partition`

— Method`greedy_contiguous_partition(weight, required_partitions, num_items=length(weight))`

Partition `1:num_items`

into atmost `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(num*items+required*partitions) 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.

`Graphs.insorted`

— Method`insorted(item, collection)`

Return true if `item`

is in sorted collection `collection`

.

**Implementation Notes**

Does not verify that `collection`

is sorted.

`Graphs.isbounded`

— Method`isbounded(n)`

Returns true if `typemax(n)`

of an integer `n`

exists.

`Graphs.isbounded`

— Method`isbounded(T)`

Returns true if `typemax(T)`

of a type `T <: Integer`

exists.

`Graphs.optimal_contiguous_partition`

— Method`optimal_contiguous_partition(weight, required_partitions, num_items=length(weight))`

Partition `1:num_items`

into atmost `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)]`

.

`Graphs.rng_from_rng_or_seed`

— Method`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`

.

`Graphs.sample!`

— Method`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`

.

`Graphs.sample`

— Method`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.

`Graphs.unweighted_contiguous_partition`

— Method`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 atmost 1.

**Performance**

Time: O(required_partitions)