EquivalenceClassesConstructor
This code aims to provide a collection of methods that are able to exploit symmetries in arbitrary indexable objects over a given index set vl. For any indices x, y these symmetries must be known in the form of predicates, i.e. p(x,y) ∈ {true, false} or in form of mappings m(x) = y. The latter greatly increases performance but may lead to unexpected behavior with non monotonic mappings. The reason being that m(m(x)) may lie in vl but m(x)) may not, forcing the algorithm to terminate.
Index
EquivalenceClassesConstructor.ExpandMapEquivalenceClassesConstructor.ReduceMapEquivalenceClassesConstructor.EquivalenceClassesEquivalenceClassesConstructor.EquivalenceClassesEquivalenceClassesConstructor.build_adj_matrixEquivalenceClassesConstructor.check_for_equivalence_relationEquivalenceClassesConstructor.find_classesEquivalenceClassesConstructor.find_classesEquivalenceClassesConstructor.find_classesEquivalenceClassesConstructor.invertDictEquivalenceClassesConstructor.labelsMap
EquivalenceClassesConstructor.ExpandMap — TypeExpandMap(rm::ReduceMap [,sorted])Constructs mapping from a set of representatives of classes to full set using a ReduceMap rm. Each lit of mappings to the full can be ordered by setting sorted.
EquivalenceClassesConstructor.ReduceMap — TypeReduceMapEquivalenceClassesConstructor.EquivalenceClasses — MethodEquivalenceClasses(m::Mapping, vl::AbstractArray)Constructs an EquivalenceClasses struct from a mapping m over the indices in the list vl.
Examples
julia> EquivalenceClasses(Mapping((x)->[-x]),
[(i,j) for i in -2:2 for j in 4:7])EquivalenceClassesConstructor.EquivalenceClasses — MethodEquivalenceClasses(pred::Predicate, vl::AbstractArray)Constructs an EquivalenceClasses struct from a predicate pred over n indices in the list vl. This inputs requires n^2 operations in order to create the adjecency matrix. For large inputs a mapping is therefore preferabel.
Examples
julia> EquivalenceClasses(Predicate((x,y)->all(x .== -y)),
[(i,j) for i in -2:2 for j in 4:7])EquivalenceClassesConstructor.build_adj_matrix — Methodbuild_adj_matrix(pred, vl)Constructs adjacency matrix with vertices from vl and edges from pred(i,j) where i,j ∈ vl
EquivalenceClassesConstructor.check_for_equivalence_relation — Methodcheck_for_equivalence_relation(f::Predicate, dom)Given a Predicate f over a domain dom, return true if f is a equivalence relation, false otherwise. TODO: check transitivity.
Examples
julia> check_for_equivalence_relation(Predicate((x,y) -> x == -y), -5:10)
true
julia> check_for_equivalence_relation(Predicate((x,y) -> x == y+2), -1:10)
falseEquivalenceClassesConstructor.find_classes — Methodfind_classes(adj::BitArray{2})returns an array of length size(adj,1) with each entry with index i being a unique identifier for the equivalency class of the node i. Uses adjacency matrix as input. I.e. graph needs to be constructed before.
Examples
julia> find_classes(convert(BitArray, [0 1 0; 1 0 0; 0 0 0]))
[1, 1, 2]EquivalenceClassesConstructor.find_classes — Methodfind_classes(pred::Predicate, vl; isSymmetric=false)returns an array of length length(vl) with each entry with index i being a unique identifier for the equivalency class of the node i. See find_classes(m::Mapping, vl) for more information.
EquivalenceClassesConstructor.find_classes — Methodfind_classes(m::Mapping, vl; vl_len=length(vl), sorted=false)returns an array of length size(adj,1) with each entry with index i being a unique identifier for the equivalency class of the node i. Uses a mapping function m(x) = y and an vertex list vl to construct graph i n place. m has to be symmetric (i.e. m(x) = y => m(y) = x)! In case the vertex list is closed under the mapping (i.e. there exist no x in vl such that m(x) is not in vl), closed can be set to false in order to improve performace. for that class. By specifying continuous = true, vl_len can be specified explicitly in cases where length(vl) does not work (e.g. nested generator objects). For performace reasons this function can also be called with a plain function instead of a Mapping.
Examples
EquivalenceClassesConstructor.invertDict — Method invertDict(D::OrderedDict; sorted=false)For a given injective dictionary D with key set K and value set V, this function returns a dict with key set V and values Array{K}.
EquivalenceClassesConstructor.labelsMap — MethodlabelsMap(m::ReduceMap)Transforms values to set of continuous numbers.
Examples
label(ReduceMap(1=>1, 2=>3, 3=>5)) julia> ReduceMap{Int64,Int64} with 3 entries: 2 => 3 3 => 5 1 => 1