The cl-union-find Reference Manual

This is the cl-union-find Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Sep 15 04:34:07 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

The main system appears first, followed by any subsystem dependency.


2.1 cl-union-find

An implementation of UNION-FIND datastructure

Author

Marco Antoniotti

License

LGPL

Source

cl-union-find.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


3.1 Lisp


3.1.1 cl-union-find/cl-union-find.asd

Source

cl-union-find.asd.

Parent Component

cl-union-find (system).

ASDF Systems

cl-union-find.


3.1.2 cl-union-find/union-find-pkg.lisp

Source

cl-union-find.asd.

Parent Component

cl-union-find (system).

Packages

cl.util.union-find.


3.1.3 cl-union-find/union-find.lisp

Dependency

union-find-pkg.lisp (file).

Source

cl-union-find.asd.

Parent Component

cl-union-find (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 cl.util.union-find

This package contains an implementation of the well known UNION-FIND data structure (with weighted path compression).
The data structure is very useful as a building block of many complex algorithms.

Source

union-find-pkg.lisp.

Nicknames
  • union-find
  • cl-uf
  • union-find
  • cl-uf
Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


5.1 Public Interface


5.1.1 Ordinary functions

Function: find-set (partition x)

A more ’high-level’ FIND operator which uses the actual set element X.

Package

cl.util.union-find.

Source

union-find.lisp.

Function: find-set-rep (partition x)

The traditional FIND operator of the UNION-FIND data structure.

Package

cl.util.union-find.

Source

union-find.lisp.

Function: make-partition (&key test)

The constructor for a Partition.
The constructor takes a sole keyword parameter :TEST (default to #’EQUAL), which is used to map elements to sets (i.e. forests) in the partition. The accepted values are #’EQ, #’EQL, #’EQUAL, and #’EQUALP. The result it a newly created partition.

Package

cl.util.union-find.

Source

union-find.lisp.

Function: make-set (partition x)

The public constructon for a Set Representative.

Package

cl.util.union-find.

Source

union-find.lisp.

Function: partition-p (object)
Package

cl.util.union-find.

Source

union-find.lisp.

Function: print-set (partition x &optional stream)

This is a utility function that PRINTS the result of COLLECT-SET on X.

Package

cl.util.union-find.

Source

union-find.lisp.

Function: set-representative-p (object)
Package

cl.util.union-find.

Source

union-find.lisp.

Function: union (partition x y)

The main UNION-FIND operator.
Note that this operator ’shadows’ CL:UNION.

Package

cl.util.union-find.

Source

union-find.lisp.


5.1.2 Generic functions

Generic Function: collect-set (partition x)

This function collects all the elements of the set which contains X. The result is a list. Use this function with care.

Package

cl.util.union-find.

Source

union-find.lisp.

Methods
Method: collect-set ((p partition) (x set-representative))
Method: collect-set ((p partition) x)

5.1.3 Standalone methods

Method: print-object ((object set-representative) stream)
Source

union-find.lisp.


5.1.4 Structures

Structure: partition

The Union-Find Partion Structure.
The Partition structure serves as a collector of various auxiliary data involved in the costruction and maintainance of disjoint sets (represented as a forest of trees).

Package

cl.util.union-find.

Source

union-find.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: element-sets-map
Type

(or null hash-table)

Readers

partition-element-sets-map.

Writers

(setf partition-element-sets-map).

Structure: set-representative

The Set Representative Structure.
This structure type is the main building block for the UNION-FIND internal representation of dijoint sets.

Package

cl.util.union-find.

Source

union-find.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: item
Readers

set-rep-item.

Writers

(setf set-rep-item).

Slot: parent
Readers

set-rep-parent.

Writers

(setf set-rep-parent).

Slot: rank
Type

fixnum

Initform

0

Readers

set-rep-rank.

Writers

(setf set-rep-rank).

Slot: partition
Type

(or null cl.util.union-find:partition)

Readers

set-rep-partition.

Writers

(setf set-rep-partition).


5.2 Internals


5.2.1 Special variables

Special Variable: *accepted-equality-tests*
Package

cl.util.union-find.

Source

union-find.lisp.


5.2.2 Ordinary functions

Function: %make-partition (&key element-sets-map)
Package

cl.util.union-find.

Source

union-find.lisp.

Function: %print-set-representative (set-rep stream depth)
Package

cl.util.union-find.

Source

union-find.lisp.

Function: copy-partition (instance)
Package

cl.util.union-find.

Source

union-find.lisp.

Function: copy-set-representative (instance)
Package

cl.util.union-find.

Source

union-find.lisp.

Package

cl.util.union-find.

Source

union-find.lisp.

Function: make-set-representative (&key item parent rank partition)
Package

cl.util.union-find.

Source

union-find.lisp.

Reader: partition-element-sets-map (instance)
Writer: (setf partition-element-sets-map) (instance)
Package

cl.util.union-find.

Source

union-find.lisp.

Target Slot

element-sets-map.

Reader: set-rep-item (instance)
Writer: (setf set-rep-item) (instance)
Package

cl.util.union-find.

Source

union-find.lisp.

Target Slot

item.

Reader: set-rep-parent (instance)
Writer: (setf set-rep-parent) (instance)
Package

cl.util.union-find.

Source

union-find.lisp.

Target Slot

parent.

Reader: set-rep-partition (instance)
Writer: (setf set-rep-partition) (instance)
Package

cl.util.union-find.

Source

union-find.lisp.

Target Slot

partition.

Reader: set-rep-rank (instance)
Writer: (setf set-rep-rank) (instance)
Package

cl.util.union-find.

Source

union-find.lisp.

Target Slot

rank.


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
C   F   G   L   M   P   S   U  
Index Entry  Section

%
%make-partition: Private ordinary functions
%print-set-representative: Private ordinary functions

(
(setf partition-element-sets-map): Private ordinary functions
(setf set-rep-item): Private ordinary functions
(setf set-rep-parent): Private ordinary functions
(setf set-rep-partition): Private ordinary functions
(setf set-rep-rank): Private ordinary functions

C
collect-set: Public generic functions
collect-set: Public generic functions
collect-set: Public generic functions
copy-partition: Private ordinary functions
copy-set-representative: Private ordinary functions

F
find-set: Public ordinary functions
find-set-rep: Public ordinary functions
Function, %make-partition: Private ordinary functions
Function, %print-set-representative: Private ordinary functions
Function, (setf partition-element-sets-map): Private ordinary functions
Function, (setf set-rep-item): Private ordinary functions
Function, (setf set-rep-parent): Private ordinary functions
Function, (setf set-rep-partition): Private ordinary functions
Function, (setf set-rep-rank): Private ordinary functions
Function, copy-partition: Private ordinary functions
Function, copy-set-representative: Private ordinary functions
Function, find-set: Public ordinary functions
Function, find-set-rep: Public ordinary functions
Function, link: Private ordinary functions
Function, make-partition: Public ordinary functions
Function, make-set: Public ordinary functions
Function, make-set-representative: Private ordinary functions
Function, partition-element-sets-map: Private ordinary functions
Function, partition-p: Public ordinary functions
Function, print-set: Public ordinary functions
Function, set-rep-item: Private ordinary functions
Function, set-rep-parent: Private ordinary functions
Function, set-rep-partition: Private ordinary functions
Function, set-rep-rank: Private ordinary functions
Function, set-representative-p: Public ordinary functions
Function, union: Public ordinary functions

G
Generic Function, collect-set: Public generic functions

L
link: Private ordinary functions

M
make-partition: Public ordinary functions
make-set: Public ordinary functions
make-set-representative: Private ordinary functions
Method, collect-set: Public generic functions
Method, collect-set: Public generic functions
Method, print-object: Public standalone methods

P
partition-element-sets-map: Private ordinary functions
partition-p: Public ordinary functions
print-object: Public standalone methods
print-set: Public ordinary functions

S
set-rep-item: Private ordinary functions
set-rep-parent: Private ordinary functions
set-rep-partition: Private ordinary functions
set-rep-rank: Private ordinary functions
set-representative-p: Public ordinary functions

U
union: Public ordinary functions