Quasi-Convex Matching Software
S. R. Buss, and K. G. Kanzelberger, and D. R. Robinson, and P. N. Yianilos
This software implements the near linear time algorithms of
Buss and Yianilos for solving a special class of bipartite
weighted matching problems (assignment). Their paper "Linear
and O(n log n) Time Minimum-Cost Matching Algorithms for
Quasi-convex Tours" appeared in SODA94, and will appear in
Siam J. Computing.
The software was first described in UCSD Technical Report
CS94-370 entitled "Solving the Minimum-Cost Matching Problem
for Quasi-Convex Tours: An Efficient ANSI C Implementation",
by the four authors above.
Description of Files:
Makefile
If you have gcc installed, you should be able to simply
type make. Otherwise you will need to edit this file.
qcmatch.c
This is the main matching routine. It operates on
pointers to graph vertices of unspecified type. The
appropriate cost function, and Omega function (see the
papers) are provided in seperate source files
described below, and are linked with this module to
form a complete system. It also includes an O(log n)
time "generic" Omega implementation which may be used
in cases where no constant time routine is available.
The overall matching problem is then solved in O(n log
n) time.
qcmatch.h
Defines the interface to qcmatch.c.
qcarc.c qcsqrtarc.c qcsqrtline.c
These files define three different settings. The
first corresponds to graphs on a circle, with costs
given by chord length, and might have been better
named "qcchord.c". The second modifes this cost by
taking its square root. The third corresponds to
graphs on a line, with costs given by the sqrt of
simple distance. The first and third include constant
time Omega implementations so that the overall
matching problem is solved in linear time.
qctest.c
This is the test driver program. It can generate
random test problems of various types, and generate
Postcript visualizations of their solutions. See
runtests.csh below. It includes a dynamic programming
(DP) algorithm (O(n^3) complexity) which is used to
check the solutions generated by qcmatch.c.
qcgrapharc.c qcgraphline.c
These modules generate Postscript visualizations of the solutions
to circular or linear matching problems respectively. They are
linked with qctest.c.
runtests.csh
Run this after you've made the software. It starts by
generating file "sample.ps" which depicts the solution
to a random circular matching problem. Many instances
of various problem types are then solved, and compared
with the solution from a brute-force dynamic
programming (DP) algorithm . You
should examine the output to be sure that no failures
are reported. Note however that the problems
generated do not always have a unique solution. For
this reason a success is defined as a matching which
has the same cost as that found by the DP, even though
the matching itself may differ. This is a rare event,
but does occur, and the number of cases is reported by
the script. Again, non zero counts do *not* indicate
an error.
qcarc.journal.c
This is an alternative implementation of qcarc.c which corresponds
more closely with the original Buss-Yianilos paper. It is included
for purely didactic reasons and is not used.
Changes since the UCSD Technical Report was issued:
Makefile - "ranlib" line neutralized
qctest.c - cpu_interval() timer function replaced with a more
modern version (necessary to compile under Solaris) A bug was
found in the released version of the qcmatch.c implementation,
and fixed as follows:
359,362c359,362 NEW
< M.d = (MNODE *) qc_match_malloc(3*(Max_node+1) * sizeof(MNODE));
< L = (LDEQUE *) qc_match_malloc(3 * sizeof(LDEQUE));
< L[0].d = (MNODE **) qc_match_malloc(3*(Max_node+1) * sizeof(MNODE *));
< L[2].d = (MNODE **) qc_match_malloc(3*(Max_node+1) * sizeof(MNODE *));
--- OLD
> M.d = (MNODE *) qc_match_malloc(3 * Max_node * sizeof(MNODE));
> L = (LDEQUE *) qc_match_malloc(3 * sizeof(LDEQUE));
> L[0].d = (MNODE **) qc_match_malloc(3 * Max_node * sizeof(MNODE *));
> L[2].d = (MNODE **) qc_match_malloc(3 * Max_node * sizeof(MNODE *));
The allocation of all three deques requires one extra element, corresponding
to the "imaginary" node used to fill out unbalanced subtours. Deques were
overflowing for small Max_node and small unbalanced tours.