\documentstyle[fullpage,12pt]{article}


\begin{document}


% insert name of program as subsection title
\subsection{COMBINATORIAL ALGORITHMS} 


\subsubsection{Who?}

%Who is creator of this software?
%Who is maintaining it, if anyone? (give name and email address -- confirm
%	they are still there)
The subroutines are offered by Albert Nijenhuis and Herbert S. Wilf in their
book: {\em Combinatorial Algorithms}, published in 1978 by Academic Press, Inc.


\subsubsection{Where?}

%Where (what university or institution) was the software created?
%Where can you ftp the software from (machine address, IP number, and directory)
The authors were teaching in Department of Mathematics at University of Pennsylvania
when writing the book.


\subsubsection{When?}

%When was the program first created?
%When was the last evidence it is being maintained (last date of modification)
%Which version number do you have, and when was it released?
Since the book I got is the second edition, the subroutines must be created
some time before 1975 when the first edition was issued.


\subsubsection{Why?}

%Why does the software exist -- ie. what types of problems and applications
%what it designed for?  Why would someone want to run it?

%Is it a library of subroutines designed to be incorporated into other programs?
%Is it an educational tool, designed to animate for teaching algorithms?
%Is it an isolated, efficient implementation of a particular algorithm,
%		developed for experimental purposes?
In this directory is a collection of subroutines, in FORTRAN 77, for the solution
of combinatorial problems. It could be used as not only a very helpful tool to teach the
algorithms of combinatorics but also a beginning set of building blocks for users
to incorporate into their programs to meet their own needs. Therefore, all the
subroutines are not just a collection of pretty airfacts to be looked at but basic
elements of the growing and working equipment of scientific investigation and 
learning.



\subsubsection{What?}

%What features does this software have -- describe them?
%(ie. which problems does it include algorithms for?)
The subroutines contained in this directory are:
\begin{description}
\item[backtr.f] Supervise the backtrace search. 
\item[chromp.f] Calculate the chromatic polynomial of a connected graph.
\item[colvrt.f] Find possible colors of vertex K.
\item[cycles.f] Count cycles, find sign of a permutation, tag and/or invert.
\item[eulcrc.f] Find candidates for Kth edge of Euler circuit.
\item[exheap.f] Sort a list of any items into linear order.
\item[hamcrc.f] Find candidates for Kth vertex in a Hamilton circuit.
\item[hpsort.f] Sort a linear array into nondecreasing order.
\item[invert.f] Invert upper triangular matrix.
\item[lbltre.f] Produce the edge list of a tree from its Priifer codeword.
\item[lexsub.f] Generate subsets of \{1, 2, ..., N\} which succeed input set, in lexicographical order, with optional jumps over supersets.
\item[minspt.f] Find spanning tree of minimal length.
\item[mobius.f] Find Mobius matrix from covering relation.
\item[netflo.f] Find maximum flow in a network.
\item[nexcom.f] Next composition of n into k parts.
\item[nexequ.f] Generate next equivalence relation on \{1, 2, .., n\}.
\item[nexksb.f] Next k-subset of a n-set, in lexicographic order.
\item[nexpar.f] Find next partition of n.
\item[nexper.f] Generate next permutation of 1, 2, ..., n.
\item[nexsub.f] Generate subsets of \{1, 2, ..., N\}, in an order specified by the Gray code.
\item[nexytb.f] Supplies the sequence of Young tableaux of given shape.
\item[nxksrd.f] List k-subsets of an n-set, in RD order.
\item[perman.f] Calculate permanent of square matrix.
\item[poly.f] Operations on polynomials in power and factorial form.
\item[powser.f] Compose power series.
\item[rancom.f] Random composition of n into k parts.
\item[ranequ.f] Generate random equivalence relation on \{1, 2, ..., n\}.
\item[ranksb.f] Choose a random k-subset of \{1, 2, ..., n\}.
\item[ranpar.f] Generate a random partition of n.
\item[ranper.f] Generate random permutation of n letters.
\item[ranrut.f] Generate random unlabeled rooted tree.
\item[ransub.f] Generate random subset of an n-set.
\item[ranytb.f] Selects, u.a.r., a Young tableau of given shape.
\item[renumb.f] Renumber rows and coloumns of a matrix.
\item[select.f] Implement the algorithms for performing any of the four 
	tasks (sequencing, ranking, unranking, and random selection) on
	any of the following families:
\end{description}

\begin{enumerate}
\item K-subsets of an N-set
\item partitions of N objects into K classes
\item permutations of N objects with K cycles
\item vector subspaces of dimension K of N-dimensional space
	over GF(Q)\footnote{Q is set to 2 by a DATA statement in the
	FUNCTION PH1 subprogram. It can easily be changed by user, if
	desired. Please refer to the source code for more detail.}
\item permutations of N letters with K runs
\item partitions of N whose largest part is K
\item compositions of N into K parts
\end{enumerate}

\begin{description}
\item[spanfo.f] Determine connectivity of a graph; find spanning forest.
\item[spntre.f] Find candidates for Kth edge of spanning tree.
\item[triangle.f] Discover consistent labeling of elements of partially ordered set.
\end{description}

%How comprehensive is it (ie. does it solve all related problems or particular
%type of problem)?

% THE TYPES OF PROBLEMS COULD BE REFLECTED BY THE ABOVE LIST, COULDN'T
% IT?
%What (if anything) does it do particularly well or is interesting or unusual?


\subsubsection{How?}

%Which algorithms does it use for the problems -- give the name if possible.
%Does it provide guaranteed optimal answers or use heuristics and give
%good but necessarily not-optimal answers?
In last section, a list of combinatorial objects have been shown. Two 
kinds of usages, the exhaustive search and the random sampling, are dealt
with. The two categories of use acall for different kinds of algorithms 
for different problems. Users could check Nijenhuis and Wilf's book to
get more information on the mathematical basis of the problems and the
algorithms, and even flow charts. The specifications of subroutines are 
also available.\\

We haven't tested all the subroutines by writing drivers for them. Users 
may have to write their own main programs to try them.\\

The subroutines that have drivers already are hpsort.f, nexytb.f, nexper.f, nexpar.f, and invert.f.


\subsubsection{Programming Language?}

%What programming language is it written in?
%Is there source code available for it?
%Does it seem like to might be reasonable to interface to it with programs
%	written in other languages, and if so which ones?
The source code was written in FORTRAN 77.\\

We use Fortran 77 compiler to make it.

%Which version of which compiler did you use to make it?


\subsubsection{Operating Environment?}

%What operating systems, machine architectures, and windowing environments
%is the software capable of running in?
The operating system we use is sparc-sun-sunos4.1.3.

\subsubsection{Efficiency?}

%Does the software appear to be fast or slow?
%Do you have any benchmark examples: give size of example and time and machine.
%	as evidence (use the UNIX 'time' command on the shell level, or
%	a wristwatch for embedded commands)

%What is the largest input you would consider using the software for (ie.
% 	what is the largest size that takes a few minutes to run)
So far with the subroutines for which we have made drivers, the efficiency is pretty satisfactory. The reason might be that all the calculation
needed is not very time consuming.


\subsubsection{Portability?}

%What experiences did you have trying to make things run?
To make the software run, users have to write main program in which 
the subroutines are called, and may also need to create some other
routines to interact with them. For example, in backtr.f, another
routine CANDTE might be needed to find the list of candidates and place 
them at the end of a STACK which is a parameter of backtr().\\

After the driver is set, just compile it with fortran 77 compiler and
offer some test data to run it.

%How portable is the software likely to be to different operating environments?


\subsubsection{Availability?}

%How did you get your hands on this software (ftp, WWW, email, purchase, etc?)

%Is the software free, shareware, or commercial?

%What are the license terms under which it is offered (look through the
%	header comments in the code, the README file, the documentation.
%	is it copyrighted (if so, by whom)?  Is it under the GNU general
%	license (copyleft).  Are there any restrictions of what you can
%	do with it (non-commercial use or educational use only, etc.) )
Since all the subroutines are extracted from Nijenhuis and Wilf's book,
there is no mention about the license issue in the software. Neither it
 could found in the book.


\subsubsection{Documentation?}

%What documentation is available for the software, either printed and on-line?
%	(is their a manual, README, inline comments, etc?)
%	Are there relevant newsgroups or mailing lists to monitor?
No document is available for the library of the subroutines. Nijenhuis
and Wilf's book is the best reference to understand and use the software.

%How good is the documentation?  Is it helpful for (1) someone who wants
%	to use it and/or (2) someone who wants to extent modify it?

 
\subsubsection{Robustness?}

%Does the software give the correct answer on reasonable inputs? (How did you
%	test it?)

%Does it to crash when given unreasonable inputs? (eg: empty graphs, 0 and
%	other boundary conditions)?

%Is it particularly designed to data for certain classes of applications, 
%	or can it handle arbitrary structures?
We just tested a small part of the subroutines and did not find problem 
with them except that there is a type error which might happen when
someone was entering the subroutine. And the Fortran 77 compiler seems
to be powerful to avoid any run time crash. 


\subsubsection{Data Formats?}

%What format does the program expect the data in?  (is it ascii or bitmapped,
%	and if ascii can you understand the format easily without the
%	documentation?  If you had the documentation, would it be easy to
%	create data in this format?   Could you easily write shell-perl-awk-C
%	programs to convert other data to this format?

%Is there a set of test data or examples for experimental purposes, and if so
%	how large/interesting a data set is it?

%If you create any examples or test data or scripts, mention these and
%	where the can be found.
The data formats are different depending on the problems and algorithms. The details are in Nijenhuis and Wilf's book. 


\subsubsection{Output and Visualization?}

%Does the program present its output?  (Are the answers printed on the screen
%	or sent to a file?   Is the output in such a format that the answers
%	could be easily exacted by a shell-perl-awk-C program and fed to
%	another application?   If one wanted to modify the program to change
%	the output format -- does this seem easy or hard

%Does the software provide a graphic or visual representation of the data or
%	results -- if so describe what it can do.   How are the graphics
%	presented -- ascii, windowing system, postscript, or other?
The software doesn't offer any output format. Users could define it in
their driver programs. Besides, in Nijenhuis and Wilf's book, there are
some hints on which data could be output and input, which is input only
or output only. Anyway, users still have flexibility to decide themselves.


\subsubsection{Ease of Interface} 

%How easy it is to use the software?  Is it flexible and powerful?
%Can one incorporate parts of the software easily into application
%programs, and if so how should one do it?
It is not difficult at all to use the software in case you know how
to write some pieces in Fortran 77. All the subroutines are created
in order to be incorporated into other applications, therefore they
have good interface -- explicit declaration of parameters.



\subsubsection{Usefulness?}

%Ultimately, how useful is this software?
%If it is useful, for what and why?

%Give a numerical rathing of the usefulness of the program 1 to 10
%	(1 -- not useful at all, 5 -- useful to some people,
%	10 -- fantastically useful)
9 -- very comprehensive and useful to learn combinatorial algorithms.



\end{document}