Tcl Library Source Code

[vset VERSION 1.1]
[manpage_begin struct::disjointset n [vset VERSION]]
[keywords {disjoint set}]
[keywords {equivalence class}]
[keywords find]
[keywords {merge find}]
[keywords partition]
[keywords {partitioned set}]
[keywords union]
[moddesc   {Tcl Data Structures}]
[titledesc {Disjoint set data structure}]
[category  {Data structures}]
[require Tcl 8.6]
[require struct::disjointset [opt [vset VERSION]]]
[description]
[para]

This package provides [term {disjoint sets}]. An alternative name for
this kind of structure is [term {merge-find}].

[para]

[call [arg disjointsetName] [arg option] [opt [arg {arg arg ...}]]]

The [cmd option] and the [arg arg]s determine the exact behavior of
the command. The following commands are possible for disjointset
objects:

[list_end]

[call [arg disjointsetName] [method add-element] [arg item]]

Creates a new partition in the specified disjoint set, and fills it
with the single item [arg item].  The command maintains
the integrity of the disjoint set, i.e. it verifies that none of the
[arg elements] are already part of the disjoint set and throws an
error otherwise.

[para]

The result of this method is the empty string.

[para]

This method runs in constant time.

[call [arg disjointsetName] [method add-partition] [arg elements]]

Creates a new partition in specified disjoint set, and fills it with
the values found in the set of [arg elements]. The command maintains
the integrity of the disjoint set, i.e. it verifies that none of the
[arg elements] are already part of the disjoint set and throws an
error otherwise.

[para]

The result of the command is the empty string.

[para]

This method runs in time proportional to the size of [arg elements]].


[call [arg disjointsetName] [method partitions]]

Returns the set of partitions the named disjoint set currently
consists of. The form of the result is a list of lists; the inner
lists contain the elements of the partitions.

[para]

This method runs in time O(N*alpha(N)),
where N is the number of elements in the disjoint set and alpha
is the inverse Ackermann function.

[call [arg disjointsetName] [method num-partitions]]

Returns the number of partitions the named disjoint set currently
consists of.

[para]

This method runs in constant time.

[call [arg disjointsetName] [method equal] [arg a] [arg b]]

Determines if the two elements [arg a] and [arg b] of the disjoint set
belong to the same partition. The result of the method is a boolean
value, [const True] if the two elements are contained in the same
partition, and [const False] otherwise.

[para]

An error will be thrown if either [arg a] or [arg b] are not elements
of the disjoint set.

[para]

This method runs in amortized time O(alpha(N)), where N is the number of
elements in the larger partition and alpha is the inverse Ackermann function.

[call [arg disjointsetName] [method merge] [arg a] [arg b]]

Determines the partitions the elements [arg a] and [arg b] are
contained in and merges them into a single partition.  If the two
elements were already contained in the same partition nothing will
change.

[para]

The result of the method is the empty string.

[para]

This method runs in amortized time O(alpha(N)), where N is the number of
items in the larger of the partitions being merged. The worst case time
is O(N).

[call [arg disjointsetName] [method find] [arg e]]

Returns a list of the members of the partition of the disjoint set
which contains the element
[arg e].

[para]

This method runs in O(N*alpha(N)) time, where N is the total number of
items in the disjoint set and alpha is the inverse Ackermann function,
See [method find-exemplar] for a faster method, if all that is needed
is a unique identifier for the partition, rather than an enumeration
of all its elements.

[call [arg disjointsetName] [method exemplars]]

Returns a list containing an exemplar of each partition in the disjoint
set. The exemplar is a member of the partition, chosen arbitrarily.

[para]

This method runs in O(N*alpha(N)) time, where N is the total number of items
in the disjoint set and alpha is the inverse Ackermann function.

[call [arg disjointsetName] [method find-exemplar] [arg e]]

Returns the exemplar of the partition of the disjoint set containing
the element [arg e].  Throws an error if [arg e] is not found in the
disjoint set.  The exemplar is an arbitrarily chosen member of the partition.
The only operation that will change the exemplar of any partition is
[method merge].

[para]

This method runs in O(alpha(N)) time, where N is the number of items in
the partition containing E, and alpha is the inverse Ackermann function.

[call [arg disjointsetName] [method destroy]]

Destroys the disjoint set object and all associated memory.

[list_end]

[vset CATEGORY {struct :: disjointset}]
[include ../doctools2base/include/feedback.inc]
[manpage_end]

# disjointset.tcl --
#
#  Implementation of a Disjoint Set for Tcl.
#
# Copyright (c) Google Summer of Code 2008 Alejandro Eduardo Cruz Paz
# Copyright (c) 2008 Andreas Kupries (API redesign and simplification)
# Copyright (c) 2018 by Kevin B. Kenny - reworked to a proper disjoint-sets
# data structure, added 'add-element', 'exemplars' and 'find-exemplar'.

# References
#
# - General overview
#   - https://en.wikipedia.org/wiki/Disjoint-set_data_structure
#
# - Time/Complexity proofs
#   - https://dl.acm.org/citation.cfm?doid=62.2160
#   - https://dl.acm.org/citation.cfm?doid=364099.364331
#

package require Tcl 8.6

# Initialize the disjointset structure namespace. Note that any
# missing parent namespace (::struct) will be automatically created as
# well.
namespace eval ::struct::disjointset {



    # Only export one command, the one used to instantiate a new
    # disjoint set
    namespace export disjointset
}

# class struct::disjointset::_disjointset --
#
#	Implementation of a disjoint-sets data structure

oo::class create struct::disjointset::_disjointset {

    # elements - Dictionary whose keys are all the elements in the structure,
    #            and whose values are element numbers. 
    # tree     - List indexed by element number whose members are
    #            ordered triples consisting of the element's name,
    #            the element number of the element's parent (or the element's
    #            own index if the element is a root), and the rank of
    #		 the element.
    # nParts   - Number of partitions in the structure. Maintained only
    #            so that num_partitions will work.

    variable elements tree nParts

    constructor {} {
	set elements {}
	set tree {}
	set nParts 0
    }

    # add-element --
    #
    #	Adds an element to the structure
    #
    # Parameters:
    #	item - Name of the element to add
    #
    # Results:
    #	None.
    #
    # Side effects:
    #	Element is added

    method add-element {item} {
	if {[dict exists $elements $item]} {
	    return -code error \
		-errorcode [list STRUCT DISJOINTSET DUPLICATE $item [self]] \
		"The element \"$item\" is already known to the disjoint\
            	 set [self]"
	}
	set n [llength $tree]
	dict set elements $item $n
	lappend tree [list $item $n 0]
	incr nParts
	return
    }

    # add-partition --
    #
    #	Adds a collection of new elements to a disjoint-sets structure and
    #	makes them all one partition.
    #
    # Parameters:
    #	items - List of elements to add.
    #
    # Results:
    #	None.
    #
    # Side effects:
    #	Adds all the elements, and groups them into a single partition.

    method add-partition {items} {

	# Integrity check - make sure that none of the elements have yet
	# been added

	foreach name $items {
	    if {[dict exists $elements $name]} {
		return -code error \
		    -errorcode [list STRUCT DISJOINTSET DUPLICATE \
				    $name [self]] \
		    "The element \"$name\" is already known to the disjoint\
            	     set [self]"	      	 
	    }
	}

	# Add all the elements in one go, and establish parent links for all
	# but the first
	
	set first -1
	foreach n $items {
	    set idx [llength $tree]
	    dict set elements $n $idx
	    if {$first < 0} {
		set first $idx
		set rank 1
	    } else {
		set rank 0
	    }
	    lappend tree [list $n $first $rank]
	}
	incr nParts
	return
    }

    # equal --
    #
    #	Test if two elements belong to the same partition in a disjoint-sets
    #	data structure.
    #
    # Parameters:
    #	a - Name of the first element
    #	b - Name of the second element
    #
    # Results:
    #	Returns 1 if the elements are in the same partition, and 0 otherwise.

    method equal {a b} {
	expr {[my FindNum $a] == [my FindNum $b]}
    }

    # exemplars --
    #
    #	Find one representative element for each partition in a disjoint-sets
    #	data structure.
    #
    # Results:
    #	Returns a list of element names

    method exemplars {} {
	set result {}
	set n -1
	foreach row $tree {
	    if {[lindex $row 1] == [incr n]} {
		lappend result [lindex $row 0]
	    }
	}
	return $result
    }

    # find --
    #
    #	Find the partition to which a given element belongs.
    #
    # Parameters:
    #	item - Item to find
    #
    # Results:
    #	Returns a list of the partition's members
    #
    # Notes:
    #	This operation takes time proportional to the total number of elements
    #	in the disjoint-sets structure. If a simple name of the partition
    #	is all that is required, use "find-exemplar" instead, which runs
    #	in amortized time proportional to the inverse Ackermann function of
    #	the size of the partition.

    method find {item} {
	set result {}
	# No error on a nonexistent item
	if {![dict exists $elements $item]} {
	    return {}
	}
	set pnum [my FindNum $item]
	set n -1
	foreach row $tree {
	    if {[my FindByNum [incr n]] eq $pnum} {
		lappend result [lindex $row 0]
	    }
	}
	return $result
    }

    # find-exemplar --
    #
    #	Find a representative element of the partition that contains a given
    #	element.
    #
    # parameters:
    #	item - Item to examine
    #
    # Results:
    #	Returns the exemplar
    #
    # Notes:
    #	Takes O(alpha(|P|)) amortized time, where |P| is the size of the
    #	partition, and alpha is the inverse Ackermann function

    method find-exemplar {item} {
	return [lindex $tree [my FindNum $item] 0]
    }
    
    # merge --
    #
    #	Merges the partitions that two elements are in.
    #
    # Results:
    #	None.

    method merge {a b} {
	my MergeByNum [my FindNum $a] [my FindNum $b]
    }

    # num-partitions --
    #
    #	Counts the partitions of a disjoint-sets data structure
    #
    # Results:
    #	Returns the partition count.

    method num-partitions {} {
	return $nParts
    }
    
    # partitions --
    #
    #	Enumerates the partitions of a disjoint-sets data structure
    #
    # Results:
    #	Returns a list of lists. Each list is one of the partitions
    #	in the disjoint set, and each member of the sublist is one
    #	of the elements added to the structure.

    method partitions {} {

	# Find the partition number for each element, and accumulate a
	# list per partition
	set parts {}
	dict for {element eltNo} $elements {
	    set partNo [my FindByNum $eltNo]
	    dict lappend parts $partNo $element
	}
	return [dict values $parts]
    }

    # FindNum --
    #
    #	Finds the partition number for an element.
    #
    # Parameters:
    #	item - Item to look up
    #
    # Results:
    #	Returns the partition number

    method FindNum {item} {
	if {![dict exists $elements $item]} {
	    return -code error \
		-errorcode [list STRUCT DISJOINTSET NOTFOUND $item [self]] \
		"The element \"$item\" is not known to the disjoint\
                 set [self]"	  
	}
	return [my FindByNum [dict get $elements $item]]
    }

    # FindByNum --
    #
    #	Finds the partition number for an element, given the element's
    #	index
    #
    # Parameters:
    #	idx - Index of the item to look up
    #
    # Results:
    #	Returns the partition number
    #
    # Side effects:
    #	Performs path splitting

    method FindByNum {idx} {
	while {1} {
	    set parent [lindex $tree $idx 1]
	    if {$parent == $idx} {
		return $idx
	    }
	    set prev $idx
	    set idx $parent
	    lset tree $prev 1 [lindex $tree $idx 1]
	}
    }

    # MergeByNum --
    #
    #	Merges two partitions in a disjoint-sets data structure
    #
    # Parameters:
    #	x - Index of an element in the first partition
    #	y - Index of an element in the second partition
    #
    # Results:
    #	None
    #
    # Side effects:
    #	Merges the partition of the lower rank into the one of the
    #	higher rank.

    method MergeByNum {x y} {
	set xroot [my FindByNum $x]
	set yroot [my FindByNum $y]

	if {$xroot == $yroot} {
	    # The elements are already in the same partition
	    return
	}

	incr nParts -1

	# Make xroot the taller tree
	if {[lindex $tree $xroot 2] < [lindex $tree $yroot 2]} {
	    set t $xroot; set xroot $yroot; set yroot $t
	}

	# Merge yroot into xroot
	set xrank [lindex $tree $xroot 2]
	set yrank [lindex $tree $yroot 2]
	lset tree $yroot 1 $xroot
	if {$xrank == $yrank} {
	    lset tree $xroot 2 [expr {$xrank + 1}]
	}
    }
}

# ::struct::disjointset::disjointset --
#
#	Create a new disjoint set with a given name; if no name is
#	given, use disjointsetX, where X is a number.
#
# Arguments:
#	name	Optional name of the disjoint set; if not specified, generate one.
#
# Results:
#	name	Name of the disjoint set created

proc ::struct::disjointset::disjointset {args} {

















































































    switch -exact -- [llength $args] {

	0 {





	    return [_disjointset new]

	}
	1 {
	    # Name supplied by user
	    return [uplevel 1 [list [namespace which _disjointset] \

				   create [lindex $args 0]]]














	}



	default {



	    # Too many args
	    return -code error \



		-errorcode {TCL WRONGARGS} \




		"wrong # args: should be \"[lindex [info level 0] 0] ?name?\""


























	}



    }
}















































































































































namespace eval ::struct {
    namespace import disjointset::disjointset
    namespace export disjointset
}

package provide struct::disjointset 1.1
return

# -*- tcl -*-
# Test procedures for the disjoint set structure implementation
# Author: Alejandro Eduardo Cruz Paz
# 5 August 2008
# Copyright (c) 2018 by Kevin B. Kenny - reworked to a proper disjoint-sets
# data structure, added 'add-element', 'exemplars' and 'find-exemplar'.

package require tcltest
source [file join \
	[file dirname [file dirname [file join [pwd] [info script]]]] \
	devtools testutilities.tcl]

testsNeedTcl     8.6
testsNeedTcltest 1.0

support {


}
testing {
    useLocal disjointset.tcl struct::disjointset
}

############################################################
# Helper functions

    return [lsort -dict $res]
}

proc djstate {ds} {
    list [canonset [$ds partitions]] [$ds num-partitions]
}






























































source [localPath disjointset.testsuite]





testsuiteCleanup

# -*- tcl -*-
# Tests for the 'disjointset' module in the 'struct' library. -*- tcl -*-
#
# This file contains a collection of tests for one or more of the Tcllib
# procedures.  Sourcing this file into Tcl runs the tests and
# generates output for errors.  No output means no errors were found.
#
# Copyright (c) 2008 by Alejandro Eduardo Cruz Paz
# Copyright (c) 2008 by Andreas Kupries (extended for API changes and
# error conditions)
# Copyright (c) 2018 by Kevin B. Kenny - reworked to a proper disjoint-sets
# data structure, added 'add-element', 'exemplars' and 'find-exemplar'.
#
# RCS: @(#) $Id: disjointset.testsuite,v 1.1 2008/09/10 16:23:14 andreas_kupries Exp $

#----------------------------------------------------------------------

test disjointset-1.0 {disjointset creation} {
    ::struct::disjointset DS
    set result [djstate DS]
    DS destroy
    set result
} {{} 0}

test disjointset-1.1 {disjointset creation error} {
    catch {::struct::disjointset DS other} msg
    set result $msg
} {wrong # args: should be "::struct::disjointset ?name?"}

#----------------------------------------------------------------------

test disjointset-2.0 {disjointset add-partition error, wrong#args, missing} {
    ::struct::disjointset DS
    catch {DS add-partition} msg
    DS destroy
    set msg
} [tcltest::wrongNumArgs "DS add-partition" {items} 1]

test disjointset-2.1 {disjointset add-partition error, wrong#args, too many} {
    ::struct::disjointset DS
    catch {DS add-partition x y} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS add-partition" {items}]

test disjointset-2.2 {disjointset add-partition error, elements already known} {
    testset
    catch {DS add-partition {1}} msg
    DS destroy
    set msg
} {The element "1" is already known to the disjoint set ::DS}

test disjointset-2.3 {disjointset add-partition, ok} {
    testset
    set result [list [DS add-partition {11 14}] [djstate DS]]
    DS destroy
    set result
} {{} {{0 {1 2 3 4} {5 6} {7 10} {8 9} {11 14}} 6}}

#----------------------------------------------------------------------

test disjointset-3.0 {disjointset partitions error, wrong#args, too many} {
    ::struct::disjointset DS
    catch {DS partitions x} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS partitions" {}]

test disjointset-3.1 {disjointset partitions, ok} {
    testset
    set result [djstate DS]
    DS destroy
    set result
} {{0 {1 2 3 4} {5 6} {7 10} {8 9}} 5}

test disjointset-3.2 {disjointset partitions, empty} {
    ::struct::disjointset DS
    set result [DS partitions]
    DS destroy
    set result
} {}

#----------------------------------------------------------------------

test disjointset-4.0 {disjointset equal error, wrong#args, missing} {
    ::struct::disjointset DS
    catch {DS equal} msg
    DS destroy
    set msg
} [tcltest::wrongNumArgs "DS equal" {a b} 1]

test disjointset-4.1 {disjointset equal error, wrong#args, missing} {
    ::struct::disjointset DS
    catch {DS equal x} msg
    DS destroy
    set msg
} [tcltest::wrongNumArgs "DS equal" {a b} 2]

test disjointset-4.2 {disjointset equal error, wrong#args, too many} {
    ::struct::disjointset DS
    catch {DS equal x y z} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS equal" {a b}]

test disjointset-4.3 {disjointset equal error, unknown elements} {
    testset
    catch {DS equal x 1} msg
    DS destroy
    set msg
} {The element "x" is not known to the disjoint set ::DS}

test disjointset-4.4 {disjointset equal error, unknown elements} {
    testset
    catch {DS equal 1 x} msg
    DS destroy
    set msg
} {The element "x" is not known to the disjoint set ::DS}

test disjointset-4.5 {disjointset equal ok, unequal elements} {
    testset
    set res [DS equal 1 5]
    DS destroy
    set res
} 0

test disjointset-4.6 {disjointset equal ok, equal elements} {
    testset
    set res [DS equal 4 1]
    DS destroy
    set res
} 1

#----------------------------------------------------------------------

test disjointset-5.0 {disjointset merge error, wrong#args, missing} {
    ::struct::disjointset DS
    catch {DS merge} msg
    DS destroy
    set msg
} [tcltest::wrongNumArgs "DS merge" {a b} 1]

test disjointset-5.1 {disjointset merge error, wrong#args, missing} {
    ::struct::disjointset DS
    catch {DS merge x} msg
    DS destroy
    set msg
} [tcltest::wrongNumArgs "DS merge" {a b} 2]

test disjointset-5.2 {disjointset merge error, wrong#args, too many} {
    ::struct::disjointset DS
    catch {DS merge x y z} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS merge" {a b}]

test disjointset-5.3 {disjointset merge error, unknown elements} {
    testset
    catch {DS merge x 1} msg
    DS destroy
    set msg
} {The element "x" is not known to the disjoint set ::DS}

test disjointset-5.4 {disjointset merge error, unknown elements} {
    testset
    catch {DS merge 1 x} msg
    DS destroy
    set msg
} {The element "x" is not known to the disjoint set ::DS}

test disjointset-5.5 {disjointset merge ok, different partitions} {
    testset
    DS merge 1 5
    set result [djstate DS]
    DS destroy
    set result
} {{0 {1 2 3 4 5 6} {7 10} {8 9}} 4}

test disjointset-5.6 {disjointset merge ok, same partition, no change} {
    testset
    DS merge 4 3
    set result [djstate DS]
    DS destroy
    set result
} {{0 {1 2 3 4} {5 6} {7 10} {8 9}} 5}

#----------------------------------------------------------------------

test disjointset-6.0 {disjointset find error, wrong#args, missing} {
    ::struct::disjointset DS
    catch {DS find} msg
    DS destroy
    set msg
} [tcltest::wrongNumArgs "DS find" {item} 1]

test disjointset-6.1 {disjointset find error, wrong#args, too many} {
    ::struct::disjointset DS
    catch {DS find x y} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS find" {item}]

test disjointset-6.2 {disjointset find, unknown element} {
    testset
    set result [DS find 11]
    DS destroy
    set result
} {}

test disjointset-6.3 {disjointset find, known element} {
    testset
    set result [lsort -dict [DS find 3]]
    DS destroy
    set result
} {1 2 3 4}

#----------------------------------------------------------------------

test disjointset-7.0 {disjointset num-partitions error, wrong#args, too many} {
    ::struct::disjointset DS
    catch {DS num-partitions x} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS num-partitions" {}]

test disjointset-7.1 {disjointset num-partitions, ok} {
    testset
    set result [DS num-partitions]
    DS destroy
    set result
} 5

#----------------------------------------------------------------------

test disjointset-8.0 {disjointset add-element error, wrongArgs, none} {
    ::struct::disjointset DS
    catch {DS add-element} msg
    DS destroy
    set msg
} [tcltest::wrongNumArgs "DS add-element" {item} 1]

test disjointset-8.1 {disjointset add-element error, wrongArgs, too many} {
    ::struct::disjointset DS
    catch {DS add-element p q} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS add-element" {item}]

test disjointset-8.2 {disjointset add-element error, duplicate element} {
    testset
    catch {DS add-element 0} message
    DS destroy
    set message
} {The element "0" is already known to the disjoint set ::DS}

test disjointset-8.3 {disjointset add-element ok} {
    testset
    DS add-element 11
    set result [djstate DS]
    DS destroy
    set result
} {{0 {1 2 3 4} {5 6} {7 10} {8 9} 11} 6}

#----------------------------------------------------------------------

test disjointset-9.0 {disjointset find-exemplar error, wrongArgs, none} {
    ::struct::disjointset DS
    catch {DS find-exemplar} msg
    DS destroy
    set msg
} [tcltest::wrongNumArgs "DS find-exemplar" {item} 1]

test disjointset-9.1 {disjointset find-exemplar error, wrongArgs, too many} {
    ::struct::disjointset DS
    catch {DS find-exemplar p q} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS find-exemplar" {item}]

test disjointset-9.2 {disjointset find-exemplar error, not found} {
    testset
    catch {DS find-exemplar x} message
    DS destroy
    set message
} {The element "x" is not known to the disjoint set ::DS}    

test disjointset-9.3 {disjointset find-exemplar ok} {
    testset
    set result [DS find-exemplar 3]
    DS destroy
    expr {$result in {1 2 3 4}}
} {1}

#----------------------------------------------------------------------

test disjointset-10.0 {disjointset exemplars error, wrong#args, too many} {
    ::struct::disjointset DS
    catch {DS exemplars x} msg
    DS destroy
    set msg
} [tcltest::tooManyArgs "DS exemplars" {}]

test disjointset-10.1 {disjointset exemplars, ok} {
    ::struct::disjointset DS
    DS add-element 0
    set result [DS exemplars]
    DS destroy
    set result
} 0

test disjointset-10.2 {disjointset exemplars, empty} {
    ::struct::disjointset DS
    set result [DS exemplars]
    DS destroy
    set result
} {}

#----------------------------------------------------------------------

test disjointset-11.0 {disjointset merge - larger randomized set of merges} {
    struct::disjointset DS
    foreach item {a b c d e f g h i j k l m n o p q r s t u v w x y z} {
	DS add-partition [list $item]
    }
    DS merge g a
    DS merge o n
    DS merge v o
    DS merge c w
    DS merge r h
    DS merge s y
    DS merge g i
    DS merge d f
    DS merge m q
    DS merge a z
    DS merge k e
    DS merge x k
    DS merge r s
    DS merge h m
    DS merge d l
    DS merge e a
    DS merge o t
    DS merge q p
    DS merge u c
    DS merge o a
    DS merge p j
    DS merge b l
    DS merge p c
    DS merge f e
    set result [lsort [lmap x [DS partitions] {lsort $x}]]
    DS destroy
    set result
} {{a b d e f g i k l n o t v x z} {c h j m p q r s u w y}}

test disjointset-11.1 {disjointset merge - larger randomized set of merges} {
    struct::disjointset DS
    foreach item {a b c d e f g h i j k l m n o p q r s t u v w x y z} {
	DS add-partition [list $item]
    }
    DS merge g a
    DS merge o n
    DS merge v o
    DS merge c w
    DS merge r h
    DS merge s y
    DS merge g i
    DS merge d f
    DS merge m q
    DS merge a z
    DS merge k e
    DS merge x k
    DS merge r s
    DS merge h m
    DS merge d l
    DS merge e a
    DS merge o t
    DS merge q p
    DS merge u c
    DS merge o a
    DS merge p j
    DS merge b l
    DS merge p c
    DS merge f e
    set result [DS exemplars]
    DS destroy
    set trouble {}
    if {[llength $result] ne 2} {
	append trouble "\nShould be two exemplars, found $result"
    }
    lassign $result e1 e2
    set l1 {a b d e f g i k l n o t v x z}
    set l2 {c h j m p q r s u w y}
    if {!(($e1 in $l1) ^ ($e2 in $l1))} {
	append trouble "\nExactly one of $e1 and $e2\
                          should be in the first set"
    }
    if {!(($e1 in $l2) ^ ($e2 in $l2))} {
	append trouble "\nExactly one of $e1 and $e2\
                          should be in the second set"
    }
    set trouble
} {}

[comment {-*- tcl -*-}]
[vset VERSION 0.11.3]
[manpage_begin struct::graph::op n [vset VERSION]]
[keywords {adjacency list}]
[keywords {adjacency matrix}]
[keywords adjacent]
[keywords {approximation algorithm}]
[keywords arc]
[keywords {articulation point}]
[keywords {augmenting network}]

[keywords {vertex cover}]
[copyright {2008 Alejandro Paz <[email protected]>}]
[copyright {2008 (docs) Andreas Kupries <[email protected]>}]
[copyright {2009 Michal Antoniewski <[email protected]>}]
[moddesc   {Tcl Data Structures}]
[titledesc {Operation for (un)directed graph objects}]
[category  {Data structures}]
[require Tcl 8.6]
[require struct::graph::op [opt [vset VERSION]]]
[comment {[require struct::graph [opt 2.3]]   }]
[comment {[require struct::list  [opt 1.5]]   }]
[comment {[require struct::set   [opt 2.2.3]] }]
[description]
[para]

The package described by this document, [package struct::graph::op],

# of this file, and for a DISCLAIMER OF ALL WARRANTIES.
#
# RCS: @(#) $Id: graphops.tcl,v 1.19 2009/09/24 19:30:10 andreas_kupries Exp $

# ### ### ### ######### ######### #########
## Requisites

package require Tcl 8.6

package require struct::disjointset ; # Used by kruskal -- 8.6 required
package require struct::prioqueue   ; # Used by kruskal, prim
package require struct::queue       ; # Used by isBipartite?, connectedComponent(Of)
package require struct::stack       ; # Used by tarjan
package require struct::graph       ; # isBridge, isCutVertex
package require struct::tree        ; # Used by BFS

# ### ### ### ######### ######### #########

# -------------------------------------------------------------------------

source [file join \
	[file dirname [file dirname [file join [pwd] [info script]]]] \
	devtools testutilities.tcl]

testsNeedTcl     8.6
testsNeedTcltest 2.0

support {
    useLocal list.tcl struct::list

    useAccel [useTcllibC] struct/tree.tcl  struct::tree
    TestAccelInit                          struct::tree

if {![package vsatisfies [package provide Tcl] 8.2]} {return}
package ifneeded struct            2.1   [list source [file join $dir struct.tcl]]
package ifneeded struct            1.4   [list source [file join $dir struct1.tcl]]

package ifneeded struct::queue     1.4.5 [list source [file join $dir queue.tcl]]
package ifneeded struct::stack     1.5.3 [list source [file join $dir stack.tcl]]
package ifneeded struct::tree      2.1.2 [list source [file join $dir tree.tcl]]
package ifneeded struct::matrix    2.0.3 [list source [file join $dir matrix.tcl]]
package ifneeded struct::pool      1.2.3 [list source [file join $dir pool.tcl]]
package ifneeded struct::record    1.2.1 [list source [file join $dir record.tcl]]
package ifneeded struct::set       2.2.3 [list source [file join $dir sets.tcl]]

package ifneeded struct::prioqueue 1.4   [list source [file join $dir prioqueue.tcl]]
package ifneeded struct::skiplist  1.3   [list source [file join $dir skiplist.tcl]]

package ifneeded struct::graph     1.2.1 [list source [file join $dir graph1.tcl]]
package ifneeded struct::tree      1.2.2 [list source [file join $dir tree1.tcl]]
package ifneeded struct::matrix    1.2.1 [list source [file join $dir matrix1.tcl]]

if {![package vsatisfies [package provide Tcl] 8.4]} {return}
package ifneeded struct::list      1.8.3  [list source [file join $dir list.tcl]]
package ifneeded struct::graph     2.4.1  [list source [file join $dir graph.tcl]]

if {![package vsatisfies [package provide Tcl] 8.5]} {return}

if {![package vsatisfies [package provide Tcl] 8.6]} {return}
package ifneeded struct::disjointset 1.1 [list source [file join $dir disjointset.tcl]]
package ifneeded struct::graph::op 0.11.3 [list source [file join $dir graphops.tcl]]