Codes of Partitioning Algorithms

Fiduccia-Mattheyses Code

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.

Algorithms for Partitioning Multi-dimensional Data Sets

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).

Algorithms for Ordering and Partitioning Hypergraphs

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

Charles Alpert's Home Page