# Codes of Partitioning Algorithms

in gunzipped tarred format. This code
was obtained from Professor
Shantanu Dutt and
Wenyong Deng at the
University of Minnesota Electrical
Engineering Department; we have slightly modified it to handle
circuits in the hypergraph format below.
The code is very efficient and utilizes a
LIFO (last-in-first-out) bucket structure which both Deng and Dutt
and Lars Hagen
Jen-Hsin Huang , and
Andrew B. Kahng discovered is significantly more effective
than either FIFO (first-in-first-out) or random bucket structures.
This FM code provides an effective benchmark against which other
partitioning codes can be measured in terms of runtimes and solution
quality.

This package contains algorithms for partitioning sets of points
in multi-dimensional space. Some algorithms included are

Complete-linkage algorithm
Single-linkage algorithm
Divisive min-diameter
Divisive sum-of-diameters
Agglomerative sum-of-diameters
K-Center algorithm

These algorithms are described in the paper "
Geometric Embeddings for Faster (and Better) Multi-Way
Partitioning".
Data sets can be generated via uniformly random or Gaussian
distributions, or they can be read from a file.
In addition code for the DP-RP algorithm as described in
"
Multi-Way Partitioning Via Spacefilling Curves and Dynamic
Programming" is included to address the min-diameter
objective. Finally, since DP-RP can split any ordering or tour into a
partitioning, we include various TSP algorithms:

2Opt
3Opt
Lin-Kernighan
Spacefilling Curves
3Opt-L

These heuristics are described in ""
Splitting Orderings into
Multi-Way Partitionings to Minimize the Maximum Diameter".
The code for these heuristics (except 3Opt-L) was originally provided
by Ken Boese (boese@cs.ucla.edu).

This package contains algorithms for partitioning
vertex orderings of circuit hypergraphs. It reads in
circuits in the
netlist hypergraph format. Included are the following
vertex ordering constructions as described in
"A General Framework for Vertex
Orderings, With Applications to Clustering":

Breadth-first Search
Depth-first Search
Max-adjacency
Cuthill-McKee
Reverse Cuthill-McKee
WINDOW

The WINDOW algorithm is a general graph traversal framework
which encompasses many well-known traversals and can be
tuned to specific clustering objectives. These orderings
can all be split by the DP-RP algorithm for either the
Scaled Cost or Absorption objective.

The code depends on the LEDA C++ data structure library. This library is an
excellent collection of routines for linked lists, sets, dictionaries,
graphs, etc.

For questions or comments, contact Charles Alpert at * cheese@cs.ucla.edu *