Utilities

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

Index

Full docs

Graphs.deepcopy_adjlistMethod
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.

source
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|.

source
Graphs.greedy_contiguous_partitionMethod
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(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.

source
Graphs.insortedMethod
insorted(item, collection)

Return true if item is in sorted collection collection.

Implementation Notes

Does not verify that collection is sorted.

source
Graphs.optimal_contiguous_partitionMethod
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)].

source
Graphs.rng_from_rng_or_seedMethod
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.

source
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.

source
Graphs.sampleMethod
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.

source
Graphs.unweighted_contiguous_partitionMethod
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)

source