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
— Methoddeepcopy_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!
— Methodfindall!(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
— Methodgreedy_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.
Graphs.insorted
— Methodinsorted(item, collection)
Return true if item
is in sorted collection collection
.
Implementation Notes
Does not verify that collection
is sorted.
Graphs.isbounded
— Methodisbounded(n)
Returns true if typemax(n)
of an integer n
exists.
Graphs.isbounded
— Methodisbounded(T)
Returns true if typemax(T)
of a type T <: Integer
exists.
Graphs.optimal_contiguous_partition
— Methodoptimal_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)]
.
Graphs.rng_from_rng_or_seed
— Methodrng_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!
— Methodsample!([rng, ]a, k)
Sample k
element from array a
without repetition and eventually excluding elements in exclude
.
Optional Arguments
exclude=()
: elements ina
to exclude from sampling.
Implementation Notes
Changes the order of the elements in a
. For a non-mutating version, see sample
.
Graphs.sample
— Methodsample(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 ina
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
— Methodunweighted_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)