|
##
## Datastructures: GAP package providing common datastructures.
##
## Copyright (C) 2015-2018 The datastructures team.
## For list of the team members, please refer to the COPYRIGHT file.
##
## This package is licensed under the GPL 2 or later, please refer
## to the COPYRIGHT.md and LICENSE files for details.
##
#! @Chapter Union-Find
#!
#! @Section Introduction
#! <Package>datastructures</Package> defines the interface for mutable data structures
#! representing partitions of <C>[1..n]</C>, commonly known as union-find data structures.
#! Key operations are
#! <Ref Oper="Unite" Label="for IsPartitionDS and IsMutable, IsPosInt, IsPosInt"/>
#! which fuses two parts of a partition and
#! <Ref Oper="Representative" Label="for IsPartitionDS, IsPosInt"/> which
#! returns a canonical representative of the part containing a given point.
#!
#! @Section API
#! @Description
#! Category of datastructures representing partitions.
#! Equality is identity and family is ignored.
DeclareCategory("IsPartitionDS", IsObject);
#! @Description
#! Family containing all partition data structures
BindGlobal("PartitionDSFamily", NewFamily("PartitionDSFamily", IsPartitionDS));
#
# Constructors. Given an integer return the trivial partition (n parts of size 1)
# Given a list of disjoint sets, return that partition. Any points up to the maximum
# of any of the sets not included in a set are in singleton parts.
#
#! @Description
#! Returns the trivial partition of the set <C>[1..n]</C>.
#! @Arguments filter, n
DeclareConstructor("PartitionDSCons",[IsPartitionDS, IsPosInt]);
#! @Description
#! Returns the union find structure of <A>partition</A>.
#! @Arguments filter, partition
DeclareConstructor("PartitionDSCons",[IsPartitionDS, IsCyclotomicCollColl]);
#
# Operations. Given an integer return the trivial partition (n parts of size 1)
# Given a list of disjoint sets, return that partition. Any points up to the maximum
# of any of the sets not included in a set are in singleton parts.
#
#! @Description
#! Returns the trivial partition of the set <C>[1..n]</C>.
#! @Arguments filter, n
DeclareOperation("PartitionDS",[IsFunction, IsPosInt]);
#! @Description
#! Returns the trivial partition of the set <C>[1..n]</C>.
#! @Arguments n
DeclareOperation("PartitionDS",[IsPosInt]);
#! @Description
#! Returns the union find structure of <A>partition</A>.
#! @Arguments filter, partition
DeclareOperation("PartitionDS",[IsFunction, IsCyclotomicCollColl]);
#! @Description
#! Returns the union find structure of <A>partition</A>.
#! @Arguments partition
DeclareOperation("PartitionDS",[IsCyclotomicCollColl]);
#
# Key operations
#
#! @Description
#! Returns a canonical representative of the part of the partition that
#! <A>k</A> is contained in.
#! @Arguments unionfind, k
#! @Returns a positive integer
DeclareOperation("Representative",[IsPartitionDS, IsPosInt]);
#! @Description
#! Fuses the parts of the partition <A>unionfind</A> containing <A>k1</A>
#! and <A>k2</A>.
#! @Arguments unionfind, k1, k2
#! @Returns
DeclareOperation("Unite",[IsPartitionDS and IsMutable, IsPosInt, IsPosInt]);
#! @Description
#! Returns an iterator that runs through canonical representatives of parts
#! of the partition <A>unionfind</A>.
#! @Arguments unionfind
#! @Returns an iterator
DeclareOperation("RootsIteratorOfPartitionDS", [IsPartitionDS]);
#! @Description
#! Returns a list of the canonical representatives of the parts
#! of the partition <A>unionfind</A>.
#! @Arguments unionfind
#! @Returns A list.
DeclareOperation("RootsOfPartitionDS", [IsPartitionDS]);
#! @Description
#! Returns the number of parts of the partition <A>unionfind</A>.
#! @Arguments unionfind
#! @Returns a positive integer
DeclareAttribute("NumberParts", IsPartitionDS);
#! @Description
#! Returns the size of the underlying set of the partition <A>unionfind</A>.
#! @Arguments unionfind
#! @Returns a positive integer
DeclareAttribute("SizeUnderlyingSetDS", IsPartitionDS);
#! @Description
#! Returns the partition <A>unionfind</A> as a list of lists.
#! @Arguments unionfind
#! @Returns a list of lists
DeclareAttribute("PartsOfPartitionDS", IsPartitionDS);
[ Dauer der Verarbeitung: 0.27 Sekunden
(vorverarbeitet)
]
|
